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 for Android: free password hash cracker in your pocket

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

Message-ID: <20080407154800.6912ad1d@speedy>
Date:	Mon, 7 Apr 2008 15:48:00 -0700
From:	Stephen Hemminger <stephen.hemminger@...tta.com>
To:	Eric Dumazet <dada1@...mosbay.com>
Cc:	Stephen Hemminger <shemminger@...tta.com>,
	David Miller <davem@...emloft.net>,
	Robert Olsson <Robert.Olsson@...a.slu.se>,
	netdev@...r.kernel.org
Subject: Re: [RFC] fib_trie: memory waste solutions

On Mon, 07 Apr 2008 18:46:29 +0200
Eric Dumazet <dada1@...mosbay.com> wrote:

> 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"

The number of tnode's is small and the size growth of 2*(unsigned long) is not
worth worrying about. Also theoretically, my version could have multiple
work elements processed at once.

--
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