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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20101018181136.GA12372@elte.hu>
Date:	Mon, 18 Oct 2010 20:11:36 +0200
From:	Ingo Molnar <mingo@...e.hu>
To:	"H. Peter Anvin" <hpa@...or.com>
Cc:	Eric Paris <eparis@...hat.com>, Kyle McMartin <kyle@...artin.ca>,
	James Morris <jmorris@...ei.org>,
	Christoph Hellwig <hch@...radead.org>,
	kernel@...ts.fedoraproject.org, Mimi Zohar <zohar@...ibm.com>,
	warthog9@...nel.org, Dave Chinner <david@...morbit.com>,
	linux-kernel@...r.kernel.org, Serge Hallyn <serue@...ibm.com>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Andrew Morton <akpm@...ux-foundation.org>
Subject: Re: ima: use of radix tree cache indexing == massive waste of memory?


* H. Peter Anvin <hpa@...or.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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/