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

[Ingo Molnar]

* H. Peter Anvin <hpa at zytor.com> wrote:

> On 10/18/2010 09:48 AM, Eric Paris 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.
> 
> Radix trees can efficiently store data associated with sparse keys *as long as the 
> keys are clustered*.  For random key distributions, they perform horribly.

For random key distributions hash and rbtree data structures are pretty good 
choices.

But the (much) more fundamental question is to turn the non-trivial allocation 
overhead of this opt-in feature into truly opt-in overhead.

Thanks,

	Ingo