ima: use of radix tree cache indexing == massive waste of memory?

[Linus Torvalds]

On Mon, Oct 18, 2010 at 9:48 AM, Eric Paris <eparis at redhat.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