ima: use of radix tree cache indexing == massive waste of memory?
Dave Chinner
I was doing a quick check of kernel.org memory usage and behaviour
after the recent outage that occurred. I just noticed that slabtop
was reportingi an awfully high usage of radix tree nodes:
OBJS ACTIVE USE OBJ SIZE SLABS OBJ/SLAB CACHE SIZE NAME
4200331 2778082 66% 0.55K 144839 29 2317424K radix_tree_node
2321500 2060290 88% 1.00K 72581 32 2322592K xfs_inode
2235648 2069791 92% 0.12K 69864 32 279456K iint_cache
That is, 2.7M radix tree nodes are allocated, and the cache itself
is consuming 2.3GB of RAM. I know that the XFS inodei caches are
indexed by radix tree node, but for 2 million cached inodes that
would mean a density of 1 inode per radix tree node, which for a
system with 16M inodes in the filsystems is an impossibly low
density. The worst I've seen in a production system like kernel.org
is about 20-25% density, which would mean about 150−200k radix tree
nodes for that many inodes. So it's not the inode cache.
There's about 5GB of cached pages, so there's a few hundred thousand
nodes there, but even considering that there's still roughly 2
million nodes unaccounted for.
So I looked up what the iint_cache was. It appears to used for storing
per-inode IMA information, and uses a radix tree for indexing.
It uses the *address* of the struct inode as the indexing key. That
means the key space is extremely sparse - for XFS the struct inode
addresses are approximately 1000 bytes apart, which means the
closest the radix tree index keys get is ~1000. Which means
that there is a single entry per radix tree leaf node, so the radix
tree is using roughly 550 bytes for every 120byte structure being
cached. For the above example, it's probably wasting close to 1GB of
RAM....
IOWs, it looks to me like the choice a a radix tree for indexing the
IMA structures is probably the worst choice that could be made from
a memory usage point of view. Is there any specific reason this
cache uses radix trees, or can it be converted to use btrees or
rbtrees to stop it wasting so much memory?
Cheers,
Dave.
--
Dave Chinner
da...@fromorbit.com
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majo...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Christoph Hellwig
IMA to start with? Except for IBM looking for a reason to jusity why
TPM isn't a completely waster of ressources it's pointless. And it was
only merged under the premise that it would not affect innocent normal
users.
H. Peter Anvin
"Christoph Hellwig" <h...@infradead.org> wrote:
>Besides the algorithmic problems with ima, why is kernel.org using
>IMA to start with? Except for IBM looking for a reason to jusity why
>TPM isn't a completely waster of ressources it's pointless. And it was
>only merged under the premise that it would not affect innocent normal
>users.
>
--
Sent from my mobile phone. Please pardon any lack of formatting.
Dave Chinner
> "Christoph Hellwig" <h...@infradead.org> wrote:
> >Besides the algorithmic problems with ima, why is kernel.org using
> >IMA to start with? Except for IBM looking for a reason to jusity why
> >TPM isn't a completely waster of ressources it's pointless. And it was
> >only merged under the premise that it would not affect innocent normal
> >users.
>
> I'm confused ... what makes you think we are? This might have
> been an unintentional misconfiguration...
It's enabled in the kernel that is running:
$ grep CONFIG_IMA /boot/config-2.6.34.7-56.fc11.x86_64
CONFIG_IMA=y
CONFIG_IMA_MEASURE_PCR_IDX=10
CONFIG_IMA_AUDIT=y
CONFIG_IMA_LSM_RULES=y
$
and it's using lots of memory, so if you're not actually using it I
think it should be disabled.
If this is a stock fedora config, then they've got some work to
do....
Cheers,
Dave.
--
Dave Chinner
da...@fromorbit.com
J.H.
> On Sat, Oct 16, 2010 at 02:10:29PM -0700, H. Peter Anvin wrote:
>> "Christoph Hellwig" <h...@infradead.org> wrote:
>>> Besides the algorithmic problems with ima, why is kernel.org using
>>> IMA to start with? Except for IBM looking for a reason to jusity why
>>> TPM isn't a completely waster of ressources it's pointless. And it was
>>> only merged under the premise that it would not affect innocent normal
>>> users.
>>
>> I'm confused ... what makes you think we are? This might have
>> been an unintentional misconfiguration...
>
> It's enabled in the kernel that is running:
>
> $ grep CONFIG_IMA /boot/config-2.6.34.7-56.fc11.x86_64
> CONFIG_IMA=y
> CONFIG_IMA_MEASURE_PCR_IDX=10
> CONFIG_IMA_AUDIT=y
> CONFIG_IMA_LSM_RULES=y
> $
>
> and it's using lots of memory, so if you're not actually using it I
> think it should be disabled.
>
> If this is a stock fedora config, then they've got some work to
> do....
Considering the only change to the RPM I made for 2.6.34 (the kernel
currently running on master) was a one line change to get XFS to not
kill the box, it's standard.
Taking a quick glance at my laptop (F12) I'll note the following:
config-2.6.32.16-150.fc12.x86_64:CONFIG_IMA=y
config-2.6.32.16-150.fc12.x86_64:CONFIG_IMA_MEASURE_PCR_IDX=10
config-2.6.32.16-150.fc12.x86_64:CONFIG_IMA_AUDIT=y
config-2.6.32.16-150.fc12.x86_64:CONFIG_IMA_LSM_RULES=y
config-2.6.32.21-166.fc12.x86_64:CONFIG_IMA=y
config-2.6.32.21-166.fc12.x86_64:CONFIG_IMA_MEASURE_PCR_IDX=10
config-2.6.32.21-166.fc12.x86_64:CONFIG_IMA_AUDIT=y
config-2.6.32.21-166.fc12.x86_64:CONFIG_IMA_LSM_RULES=y
config-2.6.32.21-168.fc12.x86_64:CONFIG_IMA=y
config-2.6.32.21-168.fc12.x86_64:CONFIG_IMA_MEASURE_PCR_IDX=10
config-2.6.32.21-168.fc12.x86_64:CONFIG_IMA_AUDIT=y
config-2.6.32.21-168.fc12.x86_64:CONFIG_IMA_LSM_RULES=y
So I would happily punt this at Fedora as an issue upstream (Fedora) in
this case. This seems to be a boolean value inside the kernel, it's
either enabled, or it's not.
There does seem to be a boot option to disable it, but it seems to be on
by default if it's compiled in, and it's not like it's obvious that this
is there and chewing up resources, is there a way to find out how much
memory this is chewing up?
I can understand the distributions wanting to turn this on, there is
likely user requests to be able to use this. It's just annoying that
it's completely non-obvious that this change went in, it's on by default
and it's stealing memory, particularly when it's not being used for
anything.
Speaking to TPM, it's not quite an entire waste of resources - you can
use it as a random number generator source from hardware, so that's
useful - can't say much beyond that.
- John 'Warthog9' Hawley
Christoph Hellwig
I didn't mean to imply you enabled it intentionally. In fact it looks
like the inode tracking in IMA is always on once it's compiled in, which
totally defeats the purpose of doing it's on iternal inode tracking
instead of bloating the inode what they originally proposed. IMA really
needs a kernel parameter to only enabled this crap when people actually
use it.
And whoever turned it on in Fedora needs some serious wahcking.
Kyle McMartin
> On Sat, Oct 16, 2010 at 02:10:29PM -0700, H. Peter Anvin wrote:
> > I'm confused ... what makes you think we are? This might have been an unintentional misconfiguration...
>
> I didn't mean to imply you enabled it intentionally. In fact it looks
> like the inode tracking in IMA is always on once it's compiled in, which
> totally defeats the purpose of doing it's on iternal inode tracking
> instead of bloating the inode what they originally proposed. IMA really
> needs a kernel parameter to only enabled this crap when people actually
> use it.
>
> And whoever turned it on in Fedora needs some serious wahcking.
>
Hey Eric, sorry to throw you under the bus, but...
1.316 (eparis 11-Aug-09): CONFIG_IMA=y
Perhaps we should stop merging crap into the kernel if it's not supposed
to be enabled. (Granted, IMA is better than 99% of the random junk
merged in a release, it actually has somewhat useful Kconfig help text,
unlike the thousands of crap drivers that get merged which provide no
hint to what obscure medieval ARM board found only on three silicon
revisions two of which were never released they were for.)
The Kconfig description sounds generally useful to me. If it's bloated
crap, how did it get merged?
Sigh.
--Kyle
Christoph Hellwig
> The Kconfig description sounds generally useful to me. If it's bloated
> crap, how did it get merged?
Just like all the other crap. It's been made pretty clear that "no"
generally is not an answer for a merge request. Just bikeshedding over
whitespace or maintainer files entries for a couple month of delay is
fine.
Dave Chinner
> There does seem to be a boot option to disable it, but it seems to be on
> by default if it's compiled in, and it's not like it's obvious that this
> is there and chewing up resources, is there a way to find out how much
> memory this is chewing up?
$ grep iint_cache /proc/slabinfo | awk '// { print $2 * ($4 + 560) / 1048576 "MiB" }'
1164.91MiB
$
$ while [ 1 ]; do
> grep iint_cache /proc/slabinfo | awk '// { print $2 * ($4 + 560) / 1048576 "MiB" }'
> sleep 5
> done
955.706MiB
937.438MiB
928.851MiB
920.912MiB
919.067MiB
919.086MiB
919.111MiB
.....
This is only with about 1.2M inodes cached - yesterday I saw the
inode cache grow to 3.5M inodes during an rsync run....
Also, it's doing a good job of fragmenting the radix tree node cache
- it's currently at 50% population - 3.8M entries, 1.9M in use. i.e.
wasting another ~1GB of RAM itself right now....
Cheers,
Dave.
--
Dave Chinner
da...@fromorbit.com
Ingo Molnar
* Christoph Hellwig <h...@infradead.org> wrote:
> On Sat, Oct 16, 2010 at 02:10:29PM -0700, H. Peter Anvin wrote:
>
> > "Christoph Hellwig" <h...@infradead.org> wrote:
> >
> > > Besides the algorithmic problems with ima, why is kernel.org using
> > > IMA to start with? Except for IBM looking for a reason to jusity
> > > why TPM isn't a completely waster of ressources it's pointless.
> > > And it was only merged under the premise that it would not affect
> > > innocent normal users.
> >
> > I'm confused ... what makes you think we are? This might have been
> > an unintentional misconfiguration...
>
> I didn't mean to imply you enabled it intentionally. In fact it looks
> like the inode tracking in IMA is always on once it's compiled in,
> which totally defeats the purpose of doing it's on iternal inode
> tracking instead of bloating the inode what they originally proposed.
> IMA really needs a kernel parameter to only enabled this crap when
> people actually use it.
That is true.
> And whoever turned it on in Fedora needs some serious wahcking.
And that is false.
This security feature was merged upstream last year, it's not in
drivers/staging/ and the Kconfig help text does not contain any warning
that this is 'crap', so how were the Fedora people supposed to know?
If you are suggesting that distribution kernel maintainers should not
trust upstream kernel feature decisions and are expected to do a line by
line review of the ~40,000 commits that go upstream every year, to make
sure there's no hidden 'crap' in them (and failing that be labeled
incompetent idiots), then you are out of your mind.
It's just not possible to do that nor is it reasonable or efficient:
crap should be caught via hierarchical filtering: when the developer
posts the first patches to lkml, or when it merged into a maintainer
tree, or when it goes upstream or when it is upstream and then, as the
very last (and most expensive) line of defense, it will be caught when
it gets exposure in distributions. Which seems to be precisely what
happened here.
Fact is that Kyle did Linux a _favor_ by enabling the feature in Fedora,
as it allowed the bug/inefficiency/crap to be found by Dave. Linux got
richer as a result as we learned about a bug that affects many people.
Your gratuitous insults against him are highly misguided.
Thanks,
Ingo
Mimi Zohar
> Besides the algorithmic problems with ima, why is kernel.org using
> IMA to start with? Except for IBM looking for a reason to jusity why
> TPM isn't a completely waster of ressources it's pointless. And it was
> only merged under the premise that it would not affect innocent normal
> users.
>
Can we keep this at the design level please? When IMA is enabled, it
needs to store information on a per inode basis, yet has to wait to
late_initcall() for the TPM, at which point some inodes would have
already been created. For this reason, there is a two step
initialization process, one which allocates the iints at
security_initcall() and the other which enables IMA at late_initcall().
Instead of actually allocating the iints, between security_initcall()
and late_initcall(), the original design maintained a list of inodes and
only allocated the iints if/when IMA was enabled. This design was
rejected way back when.
As for using a radix tree, that was what you recommended.
Mimi
Ingo Molnar
* Christoph Hellwig <h...@infradead.org> wrote:
> On Sat, Oct 16, 2010 at 09:09:17PM -0400, Kyle McMartin wrote:
>
> > The Kconfig description sounds generally useful to me. If it's
> > bloated crap, how did it get merged?
>
> Just like all the other crap. It's been made pretty clear that "no"
> generally is not an answer for a merge request. Just bikeshedding
> over whitespace or maintainer files entries for a couple month of
> delay is fine.
IMO insensitive, tester alienating insults like the one you have just
launched against the wrong person are far more destructive to the
efficiency of the kernel quality process than the same-old influx of
crap.
You'd be right to flame the heck out of the lkml hardened person(s) who
allowed that crap, but not the person who was in the chain of testing
that helped us find it, for chrissakes!
We keep losing really good people due to social imbeciles like you.
Thanks,
Ingo
Peter Zijlstra
> On Sat, 2010-10-16 at 15:20 -0400, Christoph Hellwig wrote:
> > Besides the algorithmic problems with ima, why is kernel.org using
> > IMA to start with? Except for IBM looking for a reason to jusity why
> > TPM isn't a completely waster of ressources it's pointless. And it was
> > only merged under the premise that it would not affect innocent normal
> > users.
> >
>
> Can we keep this at the design level please? When IMA is enabled, it
> needs to store information on a per inode basis, yet has to wait to
> late_initcall() for the TPM, at which point some inodes would have
> already been created.
Being build (CONFIG_IMA=y) is not the same as default enabled. Is there
a way to build this stuff and not have it enabled?
Eric Paris
> On Sun, 2010-10-17 at 01:57 -0400, Mimi Zohar wrote:
>> On Sat, 2010-10-16 at 15:20 -0400, Christoph Hellwig wrote:
>> > Besides the algorithmic problems with ima, why is kernel.org using
>> > IMA to start with? �Except for IBM looking for a reason to jusity why
>> > TPM isn't a completely waster of ressources it's pointless. �And it was
>> > only merged under the premise that it would not affect innocent normal
>> > users.
>> >
>>
>> Can we keep this at the design level please? When IMA is enabled, it
>> needs to store information on a per inode basis, yet has to wait to
>> late_initcall() for the TPM, at which point some inodes would have
>> already been created.
>
> Being build (CONFIG_IMA=y) is not the same as default enabled. Is there
> a way to build this stuff and not have it enabled?
IMA isn't really 'enabled' by default (then again people might not
call it 'disabled' either). When 'enabled' IMA takes cryptographic
hashes of the contents of files, stores those in a list, and backs
that list storage with the TPM. If we expect IMA to ever transfer
from disabled to enabled we actually need a small amount of
information about inodes from the time it was disabled. We need to
know how many things have the given inode open for read and how many
for write. The reason it needs this information is that it needs to
be able to realize the the value of a cryptographic hash of the
contents of a file is useless if some other process is able to change
those contents immediately after the measurement. I haven't looked
closely, but we could probably get away with only knowing the number
of writers. Today, we collect readers, writers, and total number with
it open (should be equal to readers+writers) because that debugging
has found and fixed where a couple of filesystems are doing dumb
things. Maybe we could get rid of readers/total but then we have no
idea when 'some random fs' does something which makes the writers
count incorrect.
Today, by default, when 'not enabled' we create a full data structure
which includes the reader/writer count, space for cryptographic
information, and a couple of other little things and store them in a
radix tree just for the reader/writer count. I believe that if we
stored the writer count in the inode we could probably delay the
creation of the full structure until it was needed. But at the time
of merging/review putting anything in the inode was rejected and we
were told to use a radix tree.
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
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....
-Eric
Peter Zijlstra
> We could split this into 2 structures, thus greatly shrinking the size
> of the structure needed for the default/disabled case,
Well, it does suck it needs to bloat data and code when its effectively
disabled. Isn't there a way to gather this data before we enable it, eg.
scan the files list on enable or somesuch?
I mean, if you mandate an external storage you might as well extend
struct inode, that's cheaper in each respect.
Me, I'm henceforth making sure to have CONFIG_IMA disabled...
> but it doesn't
> 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....
radix tree is efficient for dense sets, not sparse sets.
Mimi Zohar
> On Sun, 2010-10-17 at 01:57 -0400, Mimi Zohar wrote:
> > On Sat, 2010-10-16 at 15:20 -0400, Christoph Hellwig wrote:
> > > Besides the algorithmic problems with ima, why is kernel.org using
> > > IMA to start with? Except for IBM looking for a reason to jusity why
> > > TPM isn't a completely waster of ressources it's pointless. And it was
> > > only merged under the premise that it would not affect innocent normal
> > > users.
> > >
> >
> > Can we keep this at the design level please? When IMA is enabled, it
> > needs to store information on a per inode basis, yet has to wait to
> > late_initcall() for the TPM, at which point some inodes would have
> > already been created.
>
> Being build (CONFIG_IMA=y) is not the same as default enabled. Is there
> a way to build this stuff and not have it enabled?
At one point there was a command line option, similar to
SECURITY_SELINUX_BOOTPARAM, to enable/disable IMA. Based on review
here, it was removed.
Mimi
Peter Zijlstra
> Me, I'm henceforth making sure to have CONFIG_IMA disabled...
Signed-off-by: Peter Zijlstra <a.p.zi...@chello.nl>
---
security/integrity/ima/Kconfig | 4 ++++
1 files changed, 4 insertions(+), 0 deletions(-)
diff --git a/security/integrity/ima/Kconfig b/security/integrity/ima/Kconfig
index b6ecfd4..278362c 100644
--- a/security/integrity/ima/Kconfig
+++ b/security/integrity/ima/Kconfig
@@ -24,6 +24,10 @@ config IMA
whether or not critical system files have been modified.
Read <http://www.usenix.org/events/sec04/tech/sailer.html>
to learn more about IMA.
+
+ When built-in (Y) this option will consume considerable
+ resources even when effectively disabled.
+
If unsure, say N.
config IMA_MEASURE_PCR_IDX
Eric Paris
> > We could split this into 2 structures, thus greatly shrinking the size
> > of the structure needed for the default/disabled case,
>
> Well, it does suck it needs to bloat data and code when its effectively
> disabled. Isn't there a way to gather this data before we enable it, eg.
> scan the files list on enable or somesuch?
I'll think about it, but I think (without having looked) that it's
hard/impossible given an inode to backtrack to all of the files which
have it open.
If instead you attack the problem from the other side and start with all
of the files we'd need some kind of freezer to so we could get the
atomicity required. We'd have to review every single file on the system
before we could be certain that the inode was correct. Maybe I'm wrong
and someone else can help me see how to solve it this way....
> I mean, if you mandate an external storage you might as well extend
> struct inode, that's cheaper in each respect.
I personally think the cheapest would be to move the counters into the
inode and leave the rest of it, which would only ever exist for measured
inodes, in external storage. On a 'CONFIG=Y but disabled by non-use'
your impact would be sruct inode grows by a long and when opening and
closing a struct file write perms a counter would be inc/dec....
> Me, I'm henceforth making sure to have CONFIG_IMA disabled...
>
> > but it doesn't
> > 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....
>
> radix tree is efficient for dense sets, not sparse sets.
I didn't mean to imply that I thought radix trees were inefficient in an
of themselves and hope it didn't come across that way, I recognize that
IMA is apparently using the wrong data structure for the job. Any
suggestions other than hand rolling a hashtable? I know that SELinux
has some pretty generic hashtable code, maybe I should move it into
lib/ ? Do any other subsystems have generic hashtable code? Maybe this
is a time I'm forced to do some consolidation...
-Eric
Christoph Hellwig
> As for using a radix tree, that was what you recommended.
I told you guys to use a separate tree exactly to avoid wasting
ressources if people don't use IMA. You guys back then promised
you would not ever turn it on in distros nad just use if for research.
Fact is you pressured distributions to turn it on now, and you fucked
up the requirement to not have any impact if enabled bu not used.
After fixing that mess it should be a lesson to not take more of this
crap that no one is going to use anywya.
Christoph Hellwig
> This security feature was merged upstream last year, it's not in
> drivers/staging/ and the Kconfig help text does not contain any warning
> that this is 'crap', so how were the Fedora people supposed to know?
By looking at what they turn on? What happened to the good old idea
of actually auditing what you turn on? It might be a bit too much
for every little driver, aven if that was helpful, but for security/
code with intricate hooks all over the kernel I think it is in order.
Especially as our merge requirements for security/ are a lot lower than
for the rest of the kernel given that James is very afraid of getting
whacked by Linux for not mering things.
> Fact is that Kyle did Linux a _favor_ by enabling the feature in Fedora,
> as it allowed the bug/inefficiency/crap to be found by Dave. Linux got
> richer as a result as we learned about a bug that affects many people.
> Your gratuitous insults against him are highly misguided.
I think you need to tune down your insult filter a bit :)
Christoph Hellwig
> Well, it does suck it needs to bloat data and code when its effectively
> disabled. Isn't there a way to gather this data before we enable it, eg.
> scan the files list on enable or somesuch?
>
> I mean, if you mandate an external storage you might as well extend
> struct inode, that's cheaper in each respect.
That's in fact what it did initially. While IBM claimed it would never
be enabled in distros and this would be fine I feared this would not be
true and told them to not make it have overhead if compiled in but not
used.
Turns out I wa right in my fear that IBM pressured distros to enable
it anyway. And turns out that I should have verified they didn't
actually mess it up instead of expecting people to get such trivial
things right.
> Me, I'm henceforth making sure to have CONFIG_IMA disabled...
Yeah.
> > but it doesn't
> > 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....
>
> radix tree is efficient for dense sets, not sparse sets.
Which actually works just fine for inodes on many filesystems if you
use the right key.
Pavel Machek
> On Sat, 2010-10-16 at 15:20 -0400, Christoph Hellwig wrote:
> > Besides the algorithmic problems with ima, why is kernel.org using
> > IMA to start with? Except for IBM looking for a reason to jusity why
> > TPM isn't a completely waster of ressources it's pointless. And it was
> > only merged under the premise that it would not affect innocent normal
> > users.
> >
>
> Can we keep this at the design level please? When IMA is enabled, it
> needs to store information on a per inode basis, yet has to wait to
> late_initcall() for the TPM, at which point some inodes would have
> already been created. For this reason, there is a two step
Move TPM earlier in the boot process...?
And... having huge structure for storing just number of writers (as
Eric explained) seems just wrong. Surely, you can do something like
lsof; which will be slow but only done when actually enabling IMA?
Pavel
--
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
Dave Chinner
> 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
da...@fromorbit.com
James Morris
> Especially as our merge requirements for security/ are a lot lower than
> for the rest of the kernel given that James is very afraid of getting
> whacked by Linux for not mering things.
I think historically you'll see that I'm not afraid of getting whacked by
Linus.
A procedure for merging security features has been adopted by consensus,
based on suggestions from Arjan, with the aim of preventing the literally
endless arguments which arise from security feature discussions. It's
sometimes referred to as the Arjan protocol, essentially:
If the feature correctly implements a well-defined security goal, meets
user needs without incurring unreasonable overheads, passes technical
review, and is supported by competent developers, then it is likely to
be merged.
If you disagree with a specific feature, you need to step up while it's
being reviewed and make a case against it according to the above criteria.
If you disagree with the protocol, then you need to come up with a better
one, and probably implement it yourself, to the satisfaction of all
parties.
- James
--
James Morris
<jmo...@namei.org>
Kyle McMartin
enabled, I'm going to apply the following patch to our kernel so that
IMA is globally an opt-in feature... Otherwise I'm inclined to just
disable it.
(But the more I look at this, the more it looks like a completely niche
option that has little use outside of three-letter agencies.)
I regret not looking at this more closely when it was enabled,
(although, in my defence, when the option first showed up, I left it
off...)
It's probably way more heavyweight than necessary, as I think in most
cases the iint_initalized test will cover the call into IMA. But better
safe than sorry or something and there's a bunch of other cases where
-ENOMEM will leak back up from failing kmem_cache_alloc, iirc.
regards, Kyle
---
From: Kyle McMartin <ky...@mcmartin.ca>
Date: Mon, 18 Oct 2010 02:08:35 -0400
Subject: [PATCH] ima: allow it to be completely disabled (and default to off)
Allow IMA to be entirely disabled, don't even bother calling into
the provided hooks, and avoid initializing caches.
(A lot of the hooks will test iint_initialized, and so this doubly
disables them, since the iint cache won't be enabled. But hey, we
avoid a pointless branch...)
Signed-off-by: Kyle McMartin <ky...@redhat.com>
---
include/linux/ima.h | 66 +++++++++++++++++++++++++++++++++----
security/integrity/ima/ima_iint.c | 13 +++++--
security/integrity/ima/ima_main.c | 34 +++++++++++++------
3 files changed, 91 insertions(+), 22 deletions(-)
diff --git a/include/linux/ima.h b/include/linux/ima.h
index 975837e..2fa456d 100644
--- a/include/linux/ima.h
+++ b/include/linux/ima.h
@@ -14,13 +14,65 @@
struct linux_binprm;
#ifdef CONFIG_IMA
-extern int ima_bprm_check(struct linux_binprm *bprm);
-extern int ima_inode_alloc(struct inode *inode);
-extern void ima_inode_free(struct inode *inode);
-extern int ima_file_check(struct file *file, int mask);
-extern void ima_file_free(struct file *file);
-extern int ima_file_mmap(struct file *file, unsigned long prot);
-extern void ima_counts_get(struct file *file);
+
+extern int ima_enabled;
+
+extern int __ima_bprm_check(struct linux_binprm *bprm);
+extern int __ima_inode_alloc(struct inode *inode);
+extern void __ima_inode_free(struct inode *inode);
+extern int __ima_file_check(struct file *file, int mask);
+extern void __ima_file_free(struct file *file);
+extern int __ima_file_mmap(struct file *file, unsigned long prot);
+extern void __ima_counts_get(struct file *file);
+
+static inline int ima_bprm_check(struct linux_binprm *bprm)
+{
+ if (ima_enabled)
+ return __ima_bprm_check(bprm);
+ return 0;
+}
+
+static inline int ima_inode_alloc(struct inode *inode)
+{
+ if (ima_enabled)
+ return __ima_inode_alloc(inode);
+ return 0;
+}
+
+static inline void ima_inode_free(struct inode *inode)
+{
+ if (ima_enabled)
+ __ima_inode_free(inode);
+ return;
+}
+
+static inline int ima_file_check(struct file *file, int mask)
+{
+ if (ima_enabled)
+ return __ima_file_check(file, mask);
+ return 0;
+}
+
+static inline void ima_file_free(struct file *file)
+{
+ if (ima_enabled)
+ __ima_file_free(file);
+ return;
+}
+
+static inline int ima_file_mmap(struct file *file, unsigned long prot)
+{
+ if (ima_enabled)
+ return __ima_file_mmap(file, prot);
+ return 0;
+}
+
+static inline void ima_counts_get(struct file *file)
+{
+ if (ima_enabled)
+ return __ima_counts_get(file);
+ return;
+}
#else
static inline int ima_bprm_check(struct linux_binprm *bprm)
diff --git a/security/integrity/ima/ima_iint.c b/security/integrity/ima/ima_iint.c
index afba4ae..767f026 100644
--- a/security/integrity/ima/ima_iint.c
+++ b/security/integrity/ima/ima_iint.c
@@ -46,10 +46,10 @@ out:
}
/**
- * ima_inode_alloc - allocate an iint associated with an inode
+ * __ima_inode_alloc - allocate an iint associated with an inode
* @inode: pointer to the inode
*/
-int ima_inode_alloc(struct inode *inode)
+int __ima_inode_alloc(struct inode *inode)
{
struct ima_iint_cache *iint = NULL;
int rc = 0;
@@ -107,12 +107,12 @@ void iint_rcu_free(struct rcu_head *rcu_head)
}
/**
- * ima_inode_free - called on security_inode_free
+ * __ima_inode_free - called on security_inode_free
* @inode: pointer to the inode
*
* Free the integrity information(iint) associated with an inode.
*/
-void ima_inode_free(struct inode *inode)
+void __ima_inode_free(struct inode *inode)
{
struct ima_iint_cache *iint;
@@ -139,6 +139,11 @@ static void init_once(void *foo)
static int __init ima_iintcache_init(void)
{
+ extern int ima_enabled;
+
+ if (!ima_enabled)
+ return 0;
+
iint_cache =
kmem_cache_create("iint_cache", sizeof(struct ima_iint_cache), 0,
SLAB_PANIC, init_once);
diff --git a/security/integrity/ima/ima_main.c b/security/integrity/ima/ima_main.c
index e662b89..92e084c 100644
--- a/security/integrity/ima/ima_main.c
+++ b/security/integrity/ima/ima_main.c
@@ -26,6 +26,7 @@
#include "ima.h"
int ima_initialized;
+int ima_enabled = 0;
char *ima_hash = "sha1";
static int __init hash_setup(char *str)
@@ -36,6 +37,14 @@ static int __init hash_setup(char *str)
}
__setup("ima_hash=", hash_setup);
+static int __init ima_enable(char *str)
+{
+ if (strncmp(str, "on", 2) == 0)
+ ima_enabled = 1;
+ return 1;
+}
+__setup("ima=", ima_enable);
+
struct ima_imbalance {
struct hlist_node node;
unsigned long fsmagic;
@@ -130,7 +139,7 @@ static void ima_inc_counts(struct ima_iint_cache *iint, fmode_t mode)
}
/*
- * ima_counts_get - increment file counts
+ * __ima_counts_get - increment file counts
*
* Maintain read/write counters for all files, but only
* invalidate the PCR for measured files:
@@ -140,7 +149,7 @@ static void ima_inc_counts(struct ima_iint_cache *iint, fmode_t mode)
* could result in a file measurement error.
*
*/
-void ima_counts_get(struct file *file)
+void __ima_counts_get(struct file *file)
{
struct dentry *dentry = file->f_path.dentry;
struct inode *inode = dentry->d_inode;
@@ -204,13 +213,13 @@ static void ima_dec_counts(struct ima_iint_cache *iint, struct inode *inode,
}
/**
- * ima_file_free - called on __fput()
+ * __ima_file_free - called on __fput()
* @file: pointer to file structure being freed
*
* Flag files that changed, based on i_version;
* and decrement the iint readcount/writecount.
*/
-void ima_file_free(struct file *file)
+void __ima_file_free(struct file *file)
{
struct inode *inode = file->f_dentry->d_inode;
struct ima_iint_cache *iint;
@@ -255,7 +264,7 @@ out:
}
/**
- * ima_file_mmap - based on policy, collect/store measurement.
+ * __ima_file_mmap - based on policy, collect/store measurement.
* @file: pointer to the file to be measured (May be NULL)
* @prot: contains the protection that will be applied by the kernel.
*
@@ -265,7 +274,7 @@ out:
* Return 0 on success, an error code on failure.
* (Based on the results of appraise_measurement().)
*/
-int ima_file_mmap(struct file *file, unsigned long prot)
+int __ima_file_mmap(struct file *file, unsigned long prot)
{
int rc;
@@ -278,7 +287,7 @@ int ima_file_mmap(struct file *file, unsigned long prot)
}
/**
- * ima_bprm_check - based on policy, collect/store measurement.
+ * __ima_bprm_check - based on policy, collect/store measurement.
* @bprm: contains the linux_binprm structure
*
* The OS protects against an executable file, already open for write,
@@ -290,7 +299,7 @@ int ima_file_mmap(struct file *file, unsigned long prot)
* Return 0 on success, an error code on failure.
* (Based on the results of appraise_measurement().)
*/
-int ima_bprm_check(struct linux_binprm *bprm)
+int __ima_bprm_check(struct linux_binprm *bprm)
{
int rc;
@@ -300,7 +309,7 @@ int ima_bprm_check(struct linux_binprm *bprm)
}
/**
- * ima_path_check - based on policy, collect/store measurement.
+ * __ima_path_check - based on policy, collect/store measurement.
* @file: pointer to the file to be measured
* @mask: contains MAY_READ, MAY_WRITE or MAY_EXECUTE
*
@@ -309,7 +318,7 @@ int ima_bprm_check(struct linux_binprm *bprm)
* Always return 0 and audit dentry_open failures.
* (Return code will be based upon measurement appraisal.)
*/
-int ima_file_check(struct file *file, int mask)
+int __ima_file_check(struct file *file, int mask)
{
int rc;
@@ -318,12 +327,15 @@ int ima_file_check(struct file *file, int mask)
FILE_CHECK);
return 0;
}
-EXPORT_SYMBOL_GPL(ima_file_check);
+EXPORT_SYMBOL_GPL(__ima_file_check);
static int __init init_ima(void)
{
int error;
+ if (!ima_enabled)
+ return 0;
+
error = ima_init();
ima_initialized = 1;
return error;
--
1.7.3.1
Andrew Morton
> Subject: [PATCH] ima: allow it to be completely disabled (and default to off)
Good enough as a short-term thing I guess.
But the memory consumption which David described is plain nuttiness and
needs to be fixed, presumably by using a more appropriate data structure
for lookups.
However unless I missed it, nobody has yet stated that they intend to
fix this?
Dave Chinner
> On Mon, 18 Oct 2010 02:25:30 -0400 Kyle McMartin <ky...@mcmartin.ca> wrote:
>
> > Subject: [PATCH] ima: allow it to be completely disabled (and default to off)
>
> Good enough as a short-term thing I guess.
>
> But the memory consumption which David described is plain nuttiness and
> needs to be fixed, presumably by using a more appropriate data structure
> for lookups.
>
> However unless I missed it, nobody has yet stated that they intend to
> fix this?
I think Eric said he is going to look at it.
Cheers,
Dave.
--
Dave Chinner
da...@fromorbit.com
Peter Zijlstra
> If instead you attack the problem from the other side and start with all
> of the files we'd need some kind of freezer to so we could get the
> atomicity required. We'd have to review every single file on the system
> before we could be certain that the inode was correct. Maybe I'm wrong
> and someone else can help me see how to solve it this way....
Well, you could use the actual freezer to freeze luserspace and then
simply iterate all open files, I mean, those few sods who actually want
this enabled can either pass a boot option to enable from boot or suffer
the overhead on enable, right?
Christoph Hellwig
> assuming the kernel and initrd were both measured and stored in a TPM
> PCR. I'm willing to agree that the usefulness might be limited, but it
> isn't non-existant. I'm going to make a note to look at other ways to
> cut down the memory usage.
It's not just memory overhead - it also adds another global reasource
and global lock for every inode allocation/freeing. That's okay if
people actually want to use IMA - but if you do it everywhere it's
a real PITA.
If there's seriously no way to fix it up to not cause harm by default
just extending the inode is the much better way to go. But given
that it's already in distros with a kABI I suspect some people will
be interested in fixing it for people instead of forcing this overhead
on their customers for years. We might want to just piggyback on that.
Eric Paris
> On Mon, Oct 18, 2010 at 01:57:28PM +0200, Peter Zijlstra wrote:
> > Well, you could use the actual freezer to freeze luserspace and then
> > simply iterate all open files, I mean, those few sods who actually want
> > this enabled can either pass a boot option to enable from boot or suffer
> > the overhead on enable, right?
>
> other than right away at boot? If you haven't been doing integrity
> management checking from the very beginning of the boot process, what
> does turning on IMA after the system has booted buy you in the way of
> security protections?
>
> In other words, turning on IMA via a boot option seems to be the only
> thing that makes any sense at all.
It can be turned on any time inside the initrd without loss of integrity
assuming the kernel and initrd were both measured and stored in a TPM
PCR. I'm willing to agree that the usefulness might be limited, but it
isn't non-existant. I'm going to make a note to look at other ways to
cut down the memory usage.
-Eric
Ted Ts'o
> simply iterate all open files, I mean, those few sods who actually want
> this enabled can either pass a boot option to enable from boot or suffer
> the overhead on enable, right?
I'm a little confused why anyone would want to turn on IMA at any time
other than right away at boot? If you haven't been doing integrity
management checking from the very beginning of the boot process, what
does turning on IMA after the system has booted buy you in the way of
security protections?
In other words, turning on IMA via a boot option seems to be the only
thing that makes any sense at all.
- Ted
Peter Zijlstra
> > Well, you could use the actual freezer to freeze luserspace and then
> > simply iterate all open files, I mean, those few sods who actually want
> > this enabled can either pass a boot option to enable from boot or suffer
> > the overhead on enable, right?
>
> I'm a little confused why anyone would want to turn on IMA at any time
> other than right away at boot? If you haven't been doing integrity
> management checking from the very beginning of the boot process, what
> does turning on IMA after the system has booted buy you in the way of
> security protections?
>
> In other words, turning on IMA via a boot option seems to be the only
> thing that makes any sense at all.
Fine with me.. I simply understood there was a requirement for post-boot
enablement and tried to come up with a solution for that.
Ryan Ware
> On Sun, Oct 17, 2010 at 03:59:20PM +0200, Peter Zijlstra wrote:
>> Well, it does suck it needs to bloat data and code when its effectively
>> disabled. Isn't there a way to gather this data before we enable it, eg.
>> scan the files list on enable or somesuch?
>>
>> I mean, if you mandate an external storage you might as well extend
>> struct inode, that's cheaper in each respect.
>
> That's in fact what it did initially. �While IBM claimed it would never
> be enabled in distros and this would be fine I feared this would not be
> true and told them to not make it have overhead if compiled in but not
> used.
Isn't it up to distros themselves to decide if this feature should be
enabled? I bring this up because we are intending to include this
turned on by default in the MeeGo kernel for the 1.2 release next
year.
I understand there are some technical concerns regarding performance.
We should figure out how to resolve those. That said, upstream is the
right place for this.
Ryan
Ryan Ware
> If someone gives me a good reason why Fedora actually needs this
> enabled, I'm going to apply the following patch to our kernel so that
> IMA is globally an opt-in feature... Otherwise I'm inclined to just
> disable it.
>
> (But the more I look at this, the more it looks like a completely niche
> �option that has little use outside of three-letter agencies.)
Not true. We'll be using it in MeeGo.
> I regret not looking at this more closely when it was enabled,
> (although, in my defence, when the option first showed up, I left it
> off...)
>
> It's probably way more heavyweight than necessary, as I think in most
> cases the iint_initalized test will cover the call into IMA. But better
> safe than sorry or something and there's a bunch of other cases where
> -ENOMEM will leak back up from failing kmem_cache_alloc, iirc.
Then let's bounce around ideas for making it more lightweight. I'd
love to hear suggestions.
Ryan
Eric Paris
> If someone gives me a good reason why Fedora actually needs this
> enabled, I'm going to apply the following patch to our kernel so that
> IMA is globally an opt-in feature... Otherwise I'm inclined to just
> disable it.
I'll can address this on the fedora list, but I think this is the wrong
approach. IMA is supposed to be of negligible impact when not 'enabled'
and I believe the right solution is to fix places where that isn't true.
At the moment 3 have been identified.
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.
2) IMA creates an entire integrity structure for every inode even when
most or all of this structure will not be needed.
3) IMA serializes bringing inodes into and out of core because it takes
a spinlock() when adding or removing the integrity structure to the
radix/rbtree.
I've got a patch for #1 and think 2 and 3 are relatively simple to fix
as well. Certainly #2 is, and I think that will lead to a solution to
#3.
> diff --git a/security/integrity/ima/ima_iint.c b/security/integrity/ima/ima_iint.c
> index afba4ae..767f026 100644
> --- a/security/integrity/ima/ima_iint.c
> +++ b/security/integrity/ima/ima_iint.c
> @@ -139,6 +139,11 @@ static void init_once(void *foo)
>
> static int __init ima_iintcache_init(void)
> {
> + extern int ima_enabled;
extern in a .c file? didn't you already expose this in the
appropriate .h file?
> +
> + if (!ima_enabled)
> + return 0;
> +
> iint_cache =
> kmem_cache_create("iint_cache", sizeof(struct ima_iint_cache), 0,
> SLAB_PANIC, init_once);
> diff --git a/security/integrity/ima/ima_main.c b/security/integrity/ima/ima_main.c
> index e662b89..92e084c 100644
> --- a/security/integrity/ima/ima_main.c
> +++ b/security/integrity/ima/ima_main.c
> @@ -26,6 +26,7 @@
> #include "ima.h"
>
> int ima_initialized;
> +int ima_enabled = 0;
initializing a global?
>
> char *ima_hash = "sha1";
> static int __init hash_setup(char *str)
Kyle McMartin
> I'll can address this on the fedora list, but I think this is the wrong
> approach. IMA is supposed to be of negligible impact when not 'enabled'
> and I believe the right solution is to fix places where that isn't true.
> At the moment 3 have been identified.
>
My beef is #2, which is what I want to see solved. If there's a million
people using Fedora, and 2 people use IMA, that's an awful lot of bytes
that could be otherwise used.
I think it should be entirely opt in, with a CONFIG_IMA_DEFAULT_ON or
something like we do for security hooks.
Anyway, If you can address #2, then I'm happy having it enabled. If it's
taken us this long to notice the impact, then it doesn't seem to be
all that large in the general case, and if it can be reduced, then that
should make everyone happy.
--Kyle
Kyle McMartin
>
A Red Hatter pointed out that ima_enabled needs to be exported for
modular users of IMA (like NFS...) and also Eric's points lead me to
think maybe just rolling them into the hooks might be a better solution
in the interim for Fedora 14, and we'll pull in the rbtree and other
fixes post-release and can talk about switching the toggle.
Thanks to you all for being so responsive about these issues.
regards, Kyle
---
security/integrity/ima/ima.h | 1 +
security/integrity/ima/ima_iint.c | 9 +++++++++
security/integrity/ima/ima_main.c | 24 +++++++++++++++++++++---
3 files changed, 31 insertions(+), 3 deletions(-)
diff --git a/security/integrity/ima/ima.h b/security/integrity/ima/ima.h
index 3fbcd1d..65c3977 100644
--- a/security/integrity/ima/ima.h
+++ b/security/integrity/ima/ima.h
@@ -37,6 +37,7 @@ enum tpm_pcrs { TPM_PCR0 = 0, TPM_PCR8 = 8 };
/* set during initialization */
extern int iint_initialized;
extern int ima_initialized;
+extern int ima_enabled;
extern int ima_used_chip;
extern char *ima_hash;
diff --git a/security/integrity/ima/ima_iint.c b/security/integrity/ima/ima_iint.c
index afba4ae..3d191ef 100644
--- a/security/integrity/ima/ima_iint.c
+++ b/security/integrity/ima/ima_iint.c
@@ -54,6 +54,9 @@ int ima_inode_alloc(struct inode *inode)
struct ima_iint_cache *iint = NULL;
int rc = 0;
+ if (!ima_enabled)
+ return 0;
+
iint = kmem_cache_alloc(iint_cache, GFP_NOFS);
if (!iint)
return -ENOMEM;
@@ -116,6 +119,9 @@ void ima_inode_free(struct inode *inode)
{
struct ima_iint_cache *iint;
+ if (!ima_enabled)
+ return;
+
spin_lock(&ima_iint_lock);
iint = radix_tree_delete(&ima_iint_store, (unsigned long)inode);
spin_unlock(&ima_iint_lock);
@@ -139,6 +145,9 @@ static void init_once(void *foo)
static int __init ima_iintcache_init(void)
{
+ if (!ima_enabled)
+ return 0;
+
iint_cache =
kmem_cache_create("iint_cache", sizeof(struct ima_iint_cache), 0,
SLAB_PANIC, init_once);
diff --git a/security/integrity/ima/ima_main.c b/security/integrity/ima/ima_main.c
index e662b89..6e91905 100644
--- a/security/integrity/ima/ima_main.c
+++ b/security/integrity/ima/ima_main.c
@@ -26,6 +26,7 @@
#include "ima.h"
int ima_initialized;
+int ima_enabled;
char *ima_hash = "sha1";
static int __init hash_setup(char *str)
@@ -36,6 +37,14 @@ static int __init hash_setup(char *str)
}
__setup("ima_hash=", hash_setup);
+static int __init ima_enable(char *str)
+{
+ if (strncmp(str, "on", 2) == 0)
+ ima_enabled = 1;
+ return 1;
+}
+__setup("ima=", ima_enable);
+
struct ima_imbalance {
struct hlist_node node;
unsigned long fsmagic;
@@ -148,7 +157,7 @@ void ima_counts_get(struct file *file)
struct ima_iint_cache *iint;
int rc;
- if (!iint_initialized || !S_ISREG(inode->i_mode))
+ if (!ima_enabled || !iint_initialized || !S_ISREG(inode->i_mode))
return;
iint = ima_iint_find_get(inode);
if (!iint)
@@ -215,7 +224,7 @@ void ima_file_free(struct file *file)
struct inode *inode = file->f_dentry->d_inode;
struct ima_iint_cache *iint;
- if (!iint_initialized || !S_ISREG(inode->i_mode))
+ if (!ima_enabled || !iint_initialized || !S_ISREG(inode->i_mode))
return;
iint = ima_iint_find_get(inode);
if (!iint)
@@ -269,7 +278,7 @@ int ima_file_mmap(struct file *file, unsigned long prot)
{
int rc;
- if (!file)
+ if (!ima_enabled || !file)
return 0;
if (prot & PROT_EXEC)
rc = process_measurement(file, file->f_dentry->d_name.name,
@@ -294,6 +303,9 @@ int ima_bprm_check(struct linux_binprm *bprm)
{
int rc;
+ if (!ima_enabled)
+ return 0;
+
rc = process_measurement(bprm->file, bprm->filename,
MAY_EXEC, BPRM_CHECK);
return 0;
@@ -313,6 +325,9 @@ int ima_file_check(struct file *file, int mask)
{
int rc;
+ if (!ima_enabled)
+ return 0;
+
rc = process_measurement(file, file->f_dentry->d_name.name,
mask & (MAY_READ | MAY_WRITE | MAY_EXEC),
FILE_CHECK);
@@ -324,6 +339,9 @@ static int __init init_ima(void)
{
int error;
+ if (!ima_enabled)
+ return 0;
+
error = ima_init();
ima_initialized = 1;
return error;
--
1.7.3.1
--
Linus Torvalds
>
> 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.
Please. Look at the report more carefully.
The radix tree memory use is disgusting. Yes. But it is absolutely NOT
sufficient to try to just fix that part. Go back, look at the original
report email, and this line in particular:
2235648 2069791 92% 0.12K 69864 32 279456K iint_cache
There's 2.2 million iint_cache allocations too, each 128 bytes in
size. That's still a quarter _gigabyte_ of crap that adds zero value
at all.
Sure, memory is cheap, and this is on a machine with a lot of memory.
But it has lots of memory because it wants to cache a lot of files,
but because it wants to waste it on useless crap.
And yes, the radix tree usage is even worse, because radix trees are
useful for densely clustered indexing, not sparse ones. But even if
you were to get the indexing cost down to _zero_, it would still be
unacceptable to waste memory like this for absolutely ZERO GAIN.
The IMA code clearly needs fixing at a much more fundamental level
than just the indexing.
Linus
H. Peter Anvin
>
> 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.
-hpa
Mimi Zohar
> enabled, I'm going to apply the following patch to our kernel so that
> IMA is globally an opt-in feature... Otherwise I'm inclined to just
> disable it.
Am hoping others will chime in.
> (But the more I look at this, the more it looks like a completely niche
> option that has little use outside of three-letter agencies.)
>
> I regret not looking at this more closely when it was enabled,
> (although, in my defence, when the option first showed up, I left it
> off...)
>
> It's probably way more heavyweight than necessary, as I think in most
> cases the iint_initalized test will cover the call into IMA. But better
> safe than sorry or something and there's a bunch of other cases where
> -ENOMEM will leak back up from failing kmem_cache_alloc, iirc.
>
> regards, Kyle
Thanks, will compile/test patch.
Mimi
--
Mimi Zohar
> On Sun, Oct 17, 2010 at 11:36:20PM -0700, Andrew Morton wrote:
> > On Mon, 18 Oct 2010 02:25:30 -0400 Kyle McMartin <ky...@mcmartin.ca> wrote:
> >
> > > Subject: [PATCH] ima: allow it to be completely disabled (and default to off)
> >
> > Good enough as a short-term thing I guess.
> >
> > But the memory consumption which David described is plain nuttiness and
> > needs to be fixed, presumably by using a more appropriate data structure
> > for lookups.
> >
> > However unless I missed it, nobody has yet stated that they intend to
> > fix this?
>
> I think Eric said he is going to look at it.
>
> Cheers,
>
> Dave.
Am looking at it as well.
Mimi
Ingo Molnar
* H. Peter Anvin <h...@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
H. Peter Anvin
>
> * H. Peter Anvin <h...@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.
>
Yes, and not just the allocation overhead, but apparently locking
overhead, too.
-hpa
J.H.
> On Sat, Oct 16, 2010 at 05:54:11PM -0700, J.H. wrote:
>> There does seem to be a boot option to disable it, but it seems to be on
>> by default if it's compiled in, and it's not like it's obvious that this
>> is there and chewing up resources, is there a way to find out how much
>> memory this is chewing up?
>
> $ grep iint_cache /proc/slabinfo | awk '// { print $2 * ($4 + 560) / 1048576 "MiB" }'
> 1164.91MiB
> $
Exciting, I saw that too. Not sure I'm going to get to do a reboot on
master before Kernel summit (and it's OS upgrade) but I'm re-compiling
the kernel with IMA disabled.
Master's live backup machine was chewing nearly 4G of memory, and
if/when I flip some of the big frontend machines over this is going to
be a completely unacceptable waste of memory.
For the record I'm really not happy or keen on having to maintain a
custom kernel just to get this disabled, but if it's going to save me 4G
on a single quiet machine I can only assumes it's going to save me
several 10s of gigs on some of the bigger machines.
> $ while [ 1 ]; do
>> grep iint_cache /proc/slabinfo | awk '// { print $2 * ($4 + 560) / 1048576 "MiB" }'
>> sleep 5
>> done
> 955.706MiB
> 937.438MiB
> 928.851MiB
> 920.912MiB
> 919.067MiB
> 919.086MiB
> 919.111MiB
> .....
>
> This is only with about 1.2M inodes cached - yesterday I saw the
> inode cache grow to 3.5M inodes during an rsync run....
>
> Also, it's doing a good job of fragmenting the radix tree node cache
> - it's currently at 50% population - 3.8M entries, 1.9M in use. i.e.
> wasting another ~1GB of RAM itself right now....
Ouch, thanks for giving us a heads up on it, definately not something I
expected to quietly creep in and bite me. I should have a solution, if
one I'm not happy with, in the short term. Hopefully Fedora/upstream
will have a better solution soon.
For the record I liked the explicit opt-in that was mentioned vs. and
automatic opt-in without disable we have now.
- John 'Warthog9' Hawley
Ingo Molnar
* Eric Paris <epa...@redhat.com> wrote:
> On Mon, 2010-10-18 at 10:56 -0700, Linus Torvalds wrote:
> > On Mon, Oct 18, 2010 at 9:48 AM, Eric Paris <epa...@redhat.com> 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.
> >
> > Please. Look at the report more carefully.
> >
> > The radix tree memory use is disgusting. Yes. But it is absolutely NOT
> > sufficient to try to just fix that part. Go back, look at the original
> > report email, and this line in particular:
> >
> > 2235648 2069791 92% 0.12K 69864 32 279456K iint_cache
> >
> > There's 2.2 million iint_cache allocations too, each 128 bytes in
> > size. That's still a quarter _gigabyte_ of crap that adds zero value
> > at all.
>
> That was #2 in my list of things to fix:
>
> 2) IMA creates an entire integrity structure for every inode even when most or all
> of this structure will not be needed.
>
> I'm stating with #1 since that was 2G of wasted space (thus far my switch to
> rbtree seems to be surviving an xfstest) so I expect to send the patch this
> afternoon. #2 should attack the size of the iint_cache entries. #3 should attack
> the scalability. I'm certainly hoping I didn't miss part of the report....
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.
It's also probably a much simpler fix for -stable, so should be done first, etc.
If you do the data structure changes first then #2 will likely not be backportable
standalone and #1 will be risky to backport - creating nasty dependencies.
Thanks,
Ingo
Eric Paris
Good point. I'll keep that in mind and possibly reorder.
-Eric
Ware, Ryan R
>On Mon, 2010-10-18 at 20:29 +1100, Dave Chinner wrote:
>> On Sun, Oct 17, 2010 at 11:36:20PM -0700, Andrew Morton wrote:
>> > On Mon, 18 Oct 2010 02:25:30 -0400 Kyle McMartin <ky...@mcmartin.ca>
>>wrote:
>> >
>> > > Subject: [PATCH] ima: allow it to be completely disabled (and
>>default to off)
>> >
>> > Good enough as a short-term thing I guess.
>> >
>> > But the memory consumption which David described is plain nuttiness
>>and
>> > needs to be fixed, presumably by using a more appropriate data
>>structure
>> > for lookups.
>> >
>> > However unless I missed it, nobody has yet stated that they intend to
>> > fix this?
>>
>> I think Eric said he is going to look at it.
>>
>> Cheers,
>>
>> Dave.
>
>Am looking at it as well.
>
>Mimi
I'll help look into this aspect too.
To be clear (since my first post seemed to go to the moderator), we will
be using this starting with MeeGo 1.2. Yes, this rather pigish memory
usage needs to be addressed. Let's focus on fixing that. I'd say there
are a number of options we can explore here to do that.
It's already upstream and in the appropriate place as far as I'm
concerned. Let's not chuck it out because on second blush there were
faults that no one expected.
Ryan
Eric Paris
> 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
Pavel Machek
> > Especially as our merge requirements for security/ are a lot lower than
> > for the rest of the kernel given that James is very afraid of getting
> > whacked by Linux for not mering things.
>
> I think historically you'll see that I'm not afraid of getting whacked by
> Linus.
>
> A procedure for merging security features has been adopted by consensus,
> based on suggestions from Arjan, with the aim of preventing the literally
> endless arguments which arise from security feature discussions. It's
> sometimes referred to as the Arjan protocol, essentially:
>
> If the feature correctly implements a well-defined security goal, meets
> user needs without incurring unreasonable overheads, passes technical
> review, and is supported by competent developers, then it is likely to
> be merged.
>
> If you disagree with a specific feature, you need to step up while it's
> being reviewed and make a case against it according to the above
> criteria.
Well, I'm arguing that the criteria are wrong. Duplicated crap is
creeping in (TOMOYO vs. AppArmor), and strange stuff that has no
legitimate use is in (IMA -- what is it good for? locking machines
down, iPhone style).
> If you disagree with the protocol, then you need to come up with a better
> one, and probably implement it yourself, to the satisfaction of all
> parties.
I do disagree, and I do not think 'satistfaction of all parties' is
reasonable goal. Rest of kernel has different rules, and IMO they are better.
--
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
Pavel Machek
> >> > Good enough as a short-term thing I guess.
> >> >
> >> > But the memory consumption which David described is plain nuttiness
> >>and
> >> > needs to be fixed, presumably by using a more appropriate data
> >>structure
> >> > for lookups.
> >> >
> >> > However unless I missed it, nobody has yet stated that they intend to
> >> > fix this?
> >>
> >> I think Eric said he is going to look at it.
> >>
> >> Cheers,
> >>
> >> Dave.
> >
> >Am looking at it as well.
> >
> >Mimi
>
> I'll help look into this aspect too.
>
> To be clear (since my first post seemed to go to the moderator), we will
> be using this starting with MeeGo 1.2. Yes, this rather pigish memory
> usage needs to be addressed. Let's focus on fixing that. I'd say there
> are a number of options we can explore here to do that.
Curious... I see how NSA might want to use it, but MeeGo?
Pavel
--
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html