[lkml]   [2010]   [Oct]   [18]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: ima: use of radix tree cache indexing == massive waste of memory?

* H. Peter Anvin <> 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

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



 \ /
  Last update: 2010-10-18 20:15    [from the cache]
©2003-2014 Jasper Spaans. hosted at Digital Ocean