Subject: Re: [PATCH 9/9] fix sparse warnings

From: Stephen Hemminger <[email-masked]>
Date: Sat, 12 Jan 2008 13:08:24 -0800

On Sat, 12 Jan 2008 12:16:13 +0100
Eric Dumazet <[email-masked]> wrote:

> Stephen Hemminger a écrit :
> > Make FIB TRIE go through sparse checker without warnings.
> > 
> > Signed-off-by: Stephen Hemminger <[email-masked]>
> 
> 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-masked]>