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 <redacted>

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
    text    data     bss     dec     hex filename
   13714       4      64   13782    35d6 net/ipv4/fib_trie.o.before
   13279       4      64   13347    3423 net/ipv4/fib_trie.o

Signed-off-by: Eric Dumazet <redacted>

From: Eric Dumazet <redacted>
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.

On Sat, 12 Jan 2008 12:16:13 +0100
Eric Dumazet [off-list ref] wrote:

Stephen Hemminger a écrit :

quoted

Make FIB TRIE go through sparse checker without warnings.

Signed-off-by: Stephen Hemminger <redacted>

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 [off-list ref]

On Sat, 12 Jan 2008 12:16:13 +0100
Eric Dumazet [off-list ref] wrote:

Stephen Hemminger a écrit :

quoted

Make FIB TRIE go through sparse checker without warnings.

Signed-off-by: Stephen Hemminger <redacted>

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
    text    data     bss     dec     hex filename
   13714       4      64   13782    35d6 net/ipv4/fib_trie.o.before
   13279       4      64   13347    3423 net/ipv4/fib_trie.o

Signed-off-by: Eric Dumazet <redacted>

I agree they should not have been bitfields in the first place.

-- 
Stephen Hemminger [off-list ref]

From: Stephen Hemminger <redacted>
Date: Sat, 12 Jan 2008 13:09:46 -0800

On Sat, 12 Jan 2008 12:16:13 +0100
Eric Dumazet [off-list ref] wrote:

quoted

[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
    text    data     bss     dec     hex filename
   13714       4      64   13782    35d6 net/ipv4/fib_trie.o.before
   13279       4      64   13347    3423 net/ipv4/fib_trie.o

Signed-off-by: Eric Dumazet <redacted>

I agree they should not have been bitfields in the first place.

Applied.

Eric Dumazet a écrit :

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.

Hi David

In my testings, I found that once a tnode is built with 2^16 slots (or more), 
it cannot be freed.

Extract of /proc/net/fib_triestat

Main:
  Aver depth:     1.50
  Max depth:      2
  Leaves:         2
  Internal nodes: 3
    1: 1  2: 1  17: 1
  Pointers: 131078
Null ptrs: 131074
Total size: 513  kB
# ip route
192.168.11.0/24 dev eth0  proto kernel  scope link  src 192.168.11.129
default via 192.168.11.2 dev eth0

Two fixes are possible : Enlarge full_children & empty_children to 32bits, or 
force a limit in code to never exceed 2^15 children in a tnode. I chose the 
first solution since it can be done with 0 memory cost on 64bit arches.

Thank you

[FIB]: full_children & empty_children should be uint, not ushort

If declared as unsigned short, these fields can overflow, and whole trie logic
is broken. I could not make the machine crash, but some tnode can never
be freed.

Note for 64 bit arches : By reordering t_key and parent in [node, leaf, tnode] 
structures, we can use 32 bits hole after t_key so that sizeof(struct tnode) 
doesnt change after this patch.

Signed-off-by: Eric Dumazet <redacted>

Eric Dumazet writes:
 > Eric Dumazet a écrit :
 > > 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.

 > Two fixes are possible : Enlarge full_children & empty_children to 32bits, or 
 > force a limit in code to never exceed 2^15 children in a tnode. I chose the 
 > first solution since it can be done with 0 memory cost on 64bit arches.

 Hello,

 Thanks for spotting this. No we don't want put limits on the (root) node size.
 You see the comment in code is correct so unsigned short are some leftover from 
 old testing which could have hit us hard as the routing table slowly grows.

 Cheers
						--ro


Signed-off-by: Robert Olsson <redacted>
 

 > [FIB]: full_children & empty_children should be uint, not ushort
 > 
 > If declared as unsigned short, these fields can overflow, and whole trie logic
 > is broken. I could not make the machine crash, but some tnode can never
 > be freed.
 > 
 > Note for 64 bit arches : By reordering t_key and parent in [node, leaf, tnode] 
 > structures, we can use 32 bits hole after t_key so that sizeof(struct tnode) 
 > doesnt change after this patch.
 > 
 > Signed-off-by: Eric Dumazet [off-list ref]
 > 
 > diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
 > index f26ba31..9696722 100644
 > --- a/net/ipv4/fib_trie.c
 > +++ b/net/ipv4/fib_trie.c
 > @@ -97,13 +97,13 @@ typedef unsigned int t_key;
 >  #define IS_LEAF(n) (n->parent & T_LEAF)
 >  
 >  struct node {
 > -	t_key key;
 >  	unsigned long parent;
 > +	t_key key;
 >  };
 >  
 >  struct leaf {
 > -	t_key key;
 >  	unsigned long parent;
 > +	t_key key;
 >  	struct hlist_head list;
 >  	struct rcu_head rcu;
 >  };
 > @@ -116,12 +116,12 @@ struct leaf_info {
 >  };
 >  
 >  struct tnode {
 > -	t_key key;
 >  	unsigned long parent;
 > +	t_key key;
 >  	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 */
 > +	unsigned int full_children;	/* KEYLENGTH bits needed */
 > +	unsigned int empty_children;	/* KEYLENGTH bits needed */
 >  	struct rcu_head rcu;
 >  	struct node *child[0];
 >  };
 > @@ -329,12 +329,12 @@ static inline void free_leaf_info(struct leaf_info *leaf)
 >  	call_rcu(&leaf->rcu, __leaf_info_free_rcu);
 >  }
 >  
 > -static struct tnode *tnode_alloc(unsigned int size)
 > +static struct tnode *tnode_alloc(size_t size)
 >  {
 >  	struct page *pages;
 >  
 >  	if (size <= PAGE_SIZE)
 > -		return kcalloc(size, 1, GFP_KERNEL);
 > +		return kzalloc(size, GFP_KERNEL);
 >  
 >  	pages = alloc_pages(GFP_KERNEL|__GFP_ZERO, get_order(size));
 >  	if (!pages)
 > @@ -346,8 +346,8 @@ static struct tnode *tnode_alloc(unsigned int size)
 >  static void __tnode_free_rcu(struct rcu_head *head)
 >  {
 >  	struct tnode *tn = container_of(head, struct tnode, rcu);
 > -	unsigned int size = sizeof(struct tnode) +
 > -		(1 << tn->bits) * sizeof(struct node *);
 > +	size_t size = sizeof(struct tnode) +
 > +		      (sizeof(struct node *) << tn->bits);
 >  
 >  	if (size <= PAGE_SIZE)
 >  		kfree(tn);
 > @@ -386,8 +386,7 @@ static struct leaf_info *leaf_info_new(int plen)
 >  
 >  static struct tnode* tnode_new(t_key key, int pos, int bits)
 >  {
 > -	int nchildren = 1<<bits;
 > -	int sz = sizeof(struct tnode) + nchildren * sizeof(struct node *);
 > +	size_t sz = sizeof(struct tnode) + (sizeof(struct node *) << bits);
 >  	struct tnode *tn = tnode_alloc(sz);
 >  
 >  	if (tn) {
 > @@ -399,8 +398,8 @@ static struct tnode* tnode_new(t_key key, int pos, int bits)
 >  		tn->empty_children = 1<<bits;
 >  	}
 >  
 > -	pr_debug("AT %p s=%u %u\n", tn, (unsigned int) sizeof(struct tnode),
 > -		 (unsigned int) (sizeof(struct node) * 1<<bits));
 > +	pr_debug("AT %p s=%u %lu\n", tn, (unsigned int) sizeof(struct tnode),
 > +		 (unsigned long) (sizeof(struct node) << bits));
 >  	return tn;
 >  }
 >  

From: Robert Olsson <redacted>
Date: Sun, 13 Jan 2008 23:02:11 +0100

Eric Dumazet writes:
 > Eric Dumazet a écrit :
 > > 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.

 > Two fixes are possible : Enlarge full_children & empty_children to 32bits, or 
 > force a limit in code to never exceed 2^15 children in a tnode. I chose the 
 > first solution since it can be done with 0 memory cost on 64bit arches.

 ...

 Thanks for spotting this. No we don't want put limits on the (root) node size.
 You see the comment in code is correct so unsigned short are some leftover from 
 old testing which could have hit us hard as the routing table slowly grows.

 ...

Signed-off-by: Robert Olsson <redacted>

Applied, thanks everyone.

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 -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

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

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 ?

fib_trie_seq_show() uses two helper functions, rtn_scope() and 
rtn_type() that can
write to static storage without locking.

Just pass to them a temporary buffer to avoid potential  corruption
(probably not triggerable but still...)

Signed-off-by: Eric Dumazet <redacted>

From: Eric Dumazet <redacted>
Date: Mon, 14 Jan 2008 20:27:11 +0100

fib_trie_seq_show() uses two helper functions, rtn_scope() and 
rtn_type() that can
write to static storage without locking.

Just pass to them a temporary buffer to avoid potential  corruption
(probably not triggerable but still...)

Signed-off-by: Eric Dumazet <redacted>

Applied to net-2.6.25, but I had to tweak it to apply
cleanly since the %d in rtn_type() is now a %u