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

[Dave Chinner <david@fromorbit.com>]

On Sun, Oct 17, 2010 at 09:12:47AM -0400, Eric Paris wrote:
> We could split this into 2 structures, thus greatly shrinking the size
> of the structure needed for the default/disabled case, but it doesn't

I don't think the 128 byte structure is a big problem. If this is
too much overhead, then add a boot parameter to enable storage of
IMA information that defaults to disabled. That way it can be
compiled in with no runtime overhead at all and only those that want
to use can turn it on.

> help the fact that the suggested structure for storage (the radix
> tree) is apparently quite inefficient.  I'd love to hear other
> suggestions for a better structure....

You've just answered the question I asked in my bug posting.  Use an
rbtree or btree instead if you want to use the address of the struct
inode as the lookup key.  If you want to use a denser key such as
inode->i_ino, you're going to need to handle duplicates which means
you still can't use a radix tree.

Hence I think a btree or rbtree is your simplest solution as there
are library functions for implementing them.

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com