linux-kernel - Re: ima: use of radix tree cache indexing == massive waste of memory?

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]

Date:	Mon, 18 Oct 2010 10:56:18 -0700
From:	Linus Torvalds <torvalds@...ux-foundation.org>
To:	Eric Paris <eparis@...hat.com>
Cc:	Kyle McMartin <kyle@...artin.ca>, James Morris <jmorris@...ei.org>,
	Christoph Hellwig <hch@...radead.org>,
	kernel@...ts.fedoraproject.org, Mimi Zohar <zohar@...ibm.com>,
	warthog9@...nel.org, Dave Chinner <david@...morbit.com>,
	linux-kernel@...r.kernel.org, "H. Peter Anvin" <hpa@...or.com>,
	Serge Hallyn <serue@...ibm.com>,
	Andrew Morton <akpm@...ux-foundation.org>, mingo@...e.hu
Subject: Re: ima: use of radix tree cache indexing == massive waste of memory?

On Mon, Oct 18, 2010 at 9:48 AM, Eric Paris <eparis@...hat.com> wrote:
>
> 1) IMA uses radix trees which end up wasting 500 bytes per inode because
> the key is too sparse.  I've got a patch which uses an rbtree instead
> I'm testing and will send along shortly.  I found it funny working on
> the patch to see that Documentation/rbtree.txt says "This differs from
> radix trees (which are used to efficiently store sparse arrays and thus
> use long integer indexes to insert/access/delete nodes)"  Which flys in
> the face of this report.

Please. Look at the report more carefully.

The radix tree memory use is disgusting. Yes. But it is absolutely NOT
sufficient to try to just fix that part. Go back, look at the original
report email, and this line in particular:

   2235648 2069791  92%    0.12K  69864       32    279456K iint_cache

There's 2.2 million iint_cache allocations too, each 128 bytes in
size. That's still a quarter _gigabyte_ of crap that adds zero value
at all.

Sure, memory is cheap, and this is on a machine with a lot of memory.
But it has lots of memory because it wants to cache a lot of files,
but because it wants to waste it on useless crap.

And yes, the radix tree usage is even worse, because radix trees are
useful for densely clustered indexing, not sparse ones. But even if
you were to get the indexing cost down to _zero_, it would still be
unacceptable to waste memory like this for absolutely ZERO GAIN.

The IMA code clearly needs fixing at a much more fundamental level
than just the indexing.

                                             Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/