Re: [RFC] fib_trie: memory waste solutions

[Eric Dumazet <dada1@cosmosbay.com>]

Stephen Hemminger a écrit :
> Eric wisely pointed out that for larger sizes of nodes, the
> current allocation in fib_trie wastes lots of memory.  For a sample
> of routes extracted from the bugzilla bug the largest node grows
> to 2M bytes on 64 bit system. This leads to 2044K of wasted memory.
>
> There are two possible solutions (see attached). One uses vmalloc()
> rather than alloc_pages, but has to add complexity on freeing.
> The other adds a layer of indirection to the tnode lookup.
>
> Both have been tested on net-2.6.26 with the huge route table.
> I slightly prefer the vmalloc version, but both work fine.
>
>   
> ------------------------------------------------------------------------
>
> IPV4: fib_trie use vmalloc for large tnodes
>
> Use vmalloc rather than alloc_pages to avoid wasting memory.
> The problem is that tnode structure has a power of 2 sized array,
> plus a header. So the current code wastes almost half the memory
> allocated because it always needs the next bigger size to hold
> that small header.
>
> This is similar to an earlier patch by Eric, but instead of a list
> and lock, I used a workqueue to handle the fact that vfree can't
> be done in interrupt context.
>
> Signed-off-by: Stephen Hemminger <shemminger@vyatta.com>
>
> ---
>  net/ipv4/fib_trie.c |   25 +++++++++++++++----------
>  1 file changed, 15 insertions(+), 10 deletions(-)
>
> --- a/net/ipv4/fib_trie.c	2008-04-04 08:57:01.000000000 -0700
> +++ b/net/ipv4/fib_trie.c	2008-04-04 08:57:03.000000000 -0700
> @@ -122,7 +122,10 @@ struct tnode {
>  	unsigned char bits;		/* 2log(KEYLENGTH) bits needed */
>  	unsigned int full_children;	/* KEYLENGTH bits needed */
>  	unsigned int empty_children;	/* KEYLENGTH bits needed */
> -	struct rcu_head rcu;
> +	union {
> +		struct rcu_head rcu;
> +		struct work_struct work;
> +	};
>  	struct node *child[0];
>   
Hum...

I prefer my patch Stephen, as your version enlarges every tnode with an 
embedded "struct work_struct" which can be larger than a "struct rcu_head"

And as your 2nd patch doesnt use vmalloc() at all, we only can gain one 
order for the max bits in root node (19 instead of 18) :
We will hit the 'bug' again in a couple of months, or if router memory 
is somehow fragmented.