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: <1287449890.2530.97.camel@localhost.localdomain>
Date:	Mon, 18 Oct 2010 20:58:10 -0400
From:	Eric Paris <eparis@...hat.com>
To:	Ingo Molnar <mingo@...e.hu>
Cc:	Linus Torvalds <torvalds@...ux-foundation.org>,
	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, "H. Peter Anvin" <hpa@...or.com>,
	Serge Hallyn <serue@...ibm.com>,
	Andrew Morton <akpm@...ux-foundation.org>
Subject: Re: ima: use of radix tree cache indexing == massive waste of
 memory?

On Mon, 2010-10-18 at 20:19 +0200, Ingo Molnar wrote:

> I think it would be fair to argue that #2 is the thing that should be fixed first 
> and foremost - before touching any data structure details.
> 
> Because if you fix #2 then all the other items will become no-op to 99.9% of the 
> people who are affected by this bug today.

Where I stand at the end of the day:

Executive summary for the TLDNR crowd:  Before upcoming patch series IMA
wasted 4,720k of memory on my test box when not configured to do
anything.  After patches IMA wastes 120k when not configured to do
anything.

------------------------

I'm considering a system with 5000 inodes in core and 1500 inodes which
IMA thinks should be measured (if it's on).  (which just so happens to
be close to the system I've been testing on shortly after reboot)

I'm going to consider 6 cases of memory usage and will post the patches
shortly after this mail.  My cases are going to be:

Linus - IMA Enabled
Linus - IMA Disabled
Allocate iint only when needed - IMA Enabled
Allocate iint only when needed - IMA Disabled
Allocate iint + RBTREE - IMA Enabled
allocate iint + RBTREE - IMA Disabled

In each case I consider 'disabled' to be 'compiled in but you didn't
tell it to do anything.'

So for Linus:
sizeof(iint) = 312
sizeof(radix) = 632
sizeof(inode delta) = 0  (how much I grew struct inode)

Given my scenario of a stock F14ish machine where 5000 inodes in core
and 1500 are IMA relevant when enabled we end up with:

Linus - Enabled			Linus - Disabled
------------------		----------------
iint_cache = 1,560k		iint_cache = 1,560k
radix = 3,160k			radix = 3,160k
inode d = 0			inode d = 0

total = 4,720k			total = 4,720k

For Allocate iint only when needed:
sizeof(iint) = 288
sizeof(radix) = 632
sizeof(inode delta) = 24 (24 bytes from iint move to struct inode)

Allocate iint - Enabled		Alloce iint - Disabled
-----------------------		----------------------
iint_cache = 342k		iint_cache = 0
radix = 948k			radix = 0
inode d = 120k			inode d  = 120k

total = 1,410k			total = 120k

For allocate iint only when needed and use rbtrees:
sizeof(iint) = 320
sizeof(radix) = 632 (but irrelevant)
sizeof(inode delta) = 24

Allocate + RBTREE - Enabled	Allocate iint + RBTREE - Disabled
---------------------------	---------------------------------
iint_cache = 480k		iint_cache = 0
radix = 0			radix = 0
inode d = 120k			inode d = 120k

total = 600k			total = 120k

Seems like about the best we can do.  This patch series attempts to
addresses all 3 of the problems I believe we identified (we still
serialize IMA relevant inodes but not the majority of them and none when
IMA is not enabled)

IMA will continue to waste 24 bytes per inode in core even when it isn't
doing anything useful just by compiling it in.  Future work to use a
freezer could get rid of this if the complexity is worth the tradeoff.
But I don't think it's worth it tonight.

-Eric

--
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/