Re: [RFC] fib_trie: flush improvement

[Stephen Hemminger <shemminger@vyatta.com>]

On Wed, 02 Apr 2008 16:35:04 +0200
Eric Dumazet <dada1@cosmosbay.com> wrote:

> Eric Dumazet a écrit :
> > Stephen Hemminger a écrit :
> >> This is an attempt to fix the problem described in:
> >>      http://bugzilla.kernel.org/show_bug.cgi?id=6648
> >> I can reproduce this by loading lots and lots of routes and the taking
> >> the interface down. This causes all entries in trie to be flushed, but
> >> each leaf removal causes a rebalance of the trie. And since the removal
> >> is depth first, it creates lots of needless work.
> >>
> >> Instead on flush, just walk the trie and prune as we go.
> >> The implementation is for description only, it probably doesn't work 
> >> yet.
> >>
> >>   
> >
> > I dont get it, since the bug reporter mentions with recent kernels :
> >
> > Fix inflate_threshold_root. Now=15 size=11 bits
> >
> > Is it what you get with your tests ?
> >
> > Pawel reports :
> >
> > cat /proc/net/fib_triestat
> > Main: Aver depth: 2.26 Max depth: 6 Leaves: 235924
> > Internal nodes: 57854 1: 31632 2: 11422 3: 8475 4: 3755 5: 1676 6: 893 
> > 18: 1
> >
> > Pointers: 609760 Null ptrs: 315983 Total size: 16240 kB
> >
> > warning messages comes from rootnode that cannot be expanded, since it 
> > hits MAX_ORDER (on a 32bit x86)
> >
> >
> >
> > (sizeof(struct tnode) + (sizeof(struct node *) << bits);) is rounded 
> > to 4 << (bit + 1), ie 2 << 20
> >
> > For larger allocations Pawel has two choices :
> >
> > change MAX_ORDER from 11 to 13 or 14
> > If this machine is a pure router, this change wont have performance 
> > impact.
> >
> > Or (more difficult, but more appropriate for mainline) change 
> > fib_trie.c to use vmalloc() for very big allocaions (for the root 
> > only), and vfree()
> >
> > Since vfree() cannot be called from rcu callback, one has to setup a 
> > struct work_struct helper.
> >
> Here is a patch (untested unfortunatly) to implement this.
> 
> [IPV4] fib_trie: root_tnode can benefit of vmalloc()
> 
> FIB_TRIE root node can be very large and currently hits MAX_ORDER limit.
> It also wastes about 50% of allocated size, because of power of two 
> rounding of tnode.
> 
> A switch to vmalloc() can improve FIB_TRIE performance by allowing root 
> node to grow
> past the alloc_pages() limit, while preserving memory.
> 
> Special care must be taken to free such zone, as rcu handler is not 
> allowed to call vfree(),
> we use a worker instead.
> 
> Signed-off-by: Eric Dumazet <dada1@cosmosbay.com>
> 
> 

Rather than switching between three allocation strategies, I would rather
just have kmalloc and vmalloc.