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

[Eric Paris <eparis@redhat.com>]

On Sun, 2010-10-17 at 15:59 +0200, Peter Zijlstra wrote:
> On Sun, 2010-10-17 at 09:12 -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,
> 
> Well, it does suck it needs to bloat data and code when its effectively
> disabled. Isn't there a way to gather this data before we enable it, eg.
> scan the files list on enable or somesuch?

I'll think about it, but I think (without having looked) that it's
hard/impossible given an inode to backtrack to all of the files which
have it open.

If instead you attack the problem from the other side and start with all
of the files we'd need some kind of freezer to so we could get the
atomicity required.  We'd have to review every single file on the system
before we could be certain that the inode was correct.  Maybe I'm wrong
and someone else can help me see how to solve it this way....

> I mean, if you mandate an external storage you might as well extend
> struct inode, that's cheaper in each respect.

I personally think the cheapest would be to move the counters into the
inode and leave the rest of it, which would only ever exist for measured
inodes, in external storage.  On a 'CONFIG=Y but disabled by non-use'
your impact would be sruct inode grows by a long and when opening and
closing a struct file write perms a counter would be inc/dec....

> Me, I'm henceforth making sure to have CONFIG_IMA disabled...
> 
> >  but it doesn't
> > 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.... 
> 
> radix tree is efficient for dense sets, not sparse sets.

I didn't mean to imply that I thought radix trees were inefficient in an
of themselves and hope it didn't come across that way, I recognize that
IMA is apparently using the wrong data structure for the job.  Any
suggestions other than hand rolling a hashtable?  I know that SELinux
has some pretty generic hashtable code, maybe I should move it into
lib/ ?  Do any other subsystems have generic hashtable code?  Maybe this
is a time I'm forced to do some consolidation...

-Eric