Subject: Re: [RFC] fib_trie: flush improvement

From: Eric Dumazet <[email-masked]>
Date: Wed, 02 Apr 2008 10:01:06 +0200

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.