netdev - Re: [RFC] fib_trie: memory waste solutions

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <47FA4FE5.5010500@cosmosbay.com>
Date:	Mon, 07 Apr 2008 18:46:29 +0200
From:	Eric Dumazet <dada1@...mosbay.com>
To:	Stephen Hemminger <shemminger@...tta.com>
Cc:	David Miller <davem@...emloft.net>,
	Robert Olsson <Robert.Olsson@...a.slu.se>,
	netdev@...r.kernel.org
Subject: Re: [RFC] fib_trie: memory waste solutions

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@...tta.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.





--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html