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: <20101018000747.GH29677@dastard>
Date:	Mon, 18 Oct 2010 11:07:47 +1100
From:	Dave Chinner <david@...morbit.com>
To:	Eric Paris <eparis@...isplace.org>
Cc:	Peter Zijlstra <peterz@...radead.org>, eparis@...hat.com,
	Mimi Zohar <zohar@...ux.vnet.ibm.com>,
	Christoph Hellwig <hch@...radead.org>,
	linux-kernel@...r.kernel.org, Mimi Zohar <zohar@...ibm.com>,
	warthog9@...nel.org, hpa@...or.com, devel@...ts.fedoraprojet.org
Subject: Re: ima: use of radix tree cache indexing == massive waste of
 memory?

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@...morbit.com
--
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/