Skip to contentSkip to conversation

IMA: move read/write counters into struct inode

PATCH In review Eric Paris 7 participants 17 messages Oct 19, 2010 – Oct 24, 2010

Subsystems (4)
lore
Share & tools
lore

Eric Paris

author
#0 lore raw

PATCH 1/6 IMA: move read/write counters into struct inode

IMA currently alocated an inode integrity structure for every inode in core. This stucture is about 120 bytes long. Most files however (especially on a system which doesn't make use of IMA) will never need any of this space. The problem is that if IMA is enabled we need to know information about the number of readers and the number of writers for every inode on the box. At the moment we collect that information in the per inode iint structure and waste the rest of the space. This patch moves those counters into the struct inode so we can eventually stop allocating an IMA integrity structure except when absolutely needed.

This patch does the minimum needed to move the location of the data. Further cleanups, especially the location of counter updates, may still be possible.

---

 fs/inode.c                        |    2 ++
 include/linux/fs.h                |    6 +++++
 include/linux/ima.h               |    5 ++++
 security/integrity/ima/ima.h      |    3 --
 security/integrity/ima/ima_iint.c |   32 +++++++++++--------------
 security/integrity/ima/ima_main.c |   48 +++++++++++++++++++++----------------
 6 files changed, 54 insertions(+), 42 deletions(-)
fs/inode.c +2 -0
index 8646433..5d7ce1e 100644
@@ -24,6 +24,7 @@
 #include <linux/mount.h>
 #include <linux/async.h>
 #include <linux/posix_acl.h>
+#include <linux/ima.h>
 
 /*
  * This is needed for the following functions:
@@ -224,6 +225,7 @@ static struct inode *alloc_inode(struct super_block *sb)
 void __destroy_inode(struct inode *inode)
 {
 	BUG_ON(inode_has_buffers(inode));
+	ima_check_counters(inode);
 	security_inode_free(inode);
 	fsnotify_inode_delete(inode);
 #ifdef CONFIG_FS_POSIX_ACL
include/linux/fs.h +6 -0
index 5fb4dfd..3a402b3 100644
@@ -776,6 +776,12 @@ struct inode {
 #ifdef CONFIG_SECURITY
 	void			*i_security;
 #endif
+#ifdef CONFIG_IMA
+	/* all protected by i_mutex */
+	long			i_readers; /* struct files open RO */
+	long			i_writers; /* struct files open WR */
+	long			i_opencount; /* total open files (readers + writers) */
+#endif
 #ifdef CONFIG_FS_POSIX_ACL
 	struct posix_acl	*i_acl;
 	struct posix_acl	*i_default_acl;
include/linux/ima.h +5 -0
index 975837e..1c4bdb9 100644
@@ -21,6 +21,7 @@ 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 void ima_check_counters(struct inode *inode);
 
 #else
 static inline int ima_bprm_check(struct linux_binprm *bprm)
@@ -58,5 +59,9 @@ static inline void ima_counts_get(struct file *file)
 	return;
 }
 
+static inline void ima_check_counters(struct inode *inode)
+{
+	return;
+}
 #endif /* CONFIG_IMA_H */
 #endif /* _LINUX_IMA_H */
security/integrity/ima/ima.h +0 -3
index 3fbcd1d..e500fe3 100644
@@ -104,9 +104,6 @@ struct ima_iint_cache {
 	unsigned long flags;
 	u8 digest[IMA_DIGEST_SIZE];
 	struct mutex mutex;	/* protects: version, flags, digest */
-	long readcount;		/* measured files readcount */
-	long writecount;	/* measured files writecount */
-	long opencount;		/* opens reference count */
 	struct kref refcount;	/* ima_iint_cache reference count */
 	struct rcu_head rcu;
 };
security/integrity/ima/ima_iint.c +14 -18
index afba4ae..c584938 100644
@@ -73,6 +73,20 @@ out:
 	return rc;
 }
 
+void ima_check_counters(struct inode *inode)
+{
+	if (inode->i_readers)
+		printk(KERN_INFO "%s: readcount: %ld\n", __func__, inode->i_readers);
+	if (inode->i_writers)
+		printk(KERN_INFO "%s: writers: %ld\n", __func__, inode->i_writers);
+	if (inode->i_opencount)
+		printk(KERN_INFO "%s: opencount: %ld\n", __func__, inode->i_opencount);
+
+	inode->i_readers = 0;
+	inode->i_writers = 0;
+	inode->i_opencount = 0;
+}
+
 /* iint_free - called when the iint refcount goes to zero */
 void iint_free(struct kref *kref)
 {
@@ -80,21 +94,6 @@ void iint_free(struct kref *kref)
 						   refcount);
 	iint->version = 0;
 	iint->flags = 0UL;
-	if (iint->readcount != 0) {
-		printk(KERN_INFO "%s: readcount: %ld\n", __func__,
-		       iint->readcount);
-		iint->readcount = 0;
-	}
-	if (iint->writecount != 0) {
-		printk(KERN_INFO "%s: writecount: %ld\n", __func__,
-		       iint->writecount);
-		iint->writecount = 0;
-	}
-	if (iint->opencount != 0) {
-		printk(KERN_INFO "%s: opencount: %ld\n", __func__,
-		       iint->opencount);
-		iint->opencount = 0;
-	}
 	kref_init(&iint->refcount);
 	kmem_cache_free(iint_cache, iint);
 }
@@ -131,9 +130,6 @@ static void init_once(void *foo)
 	iint->version = 0;
 	iint->flags = 0UL;
 	mutex_init(&iint->mutex);
-	iint->readcount = 0;
-	iint->writecount = 0;
-	iint->opencount = 0;
 	kref_init(&iint->refcount);
 }
 
security/integrity/ima/ima_main.c +27 -21

118 lines not on this page · raw message

author
#1 lore raw

PATCH 2/6 IMA: drop the inode opencount since it isn't needed for operation

The opencount was used to help depugging to make sure that everything which created a struct file also correctly made the IMA calls. Since we moved all of that into the VFS this isn't as necessary. We should be able to get the same amount of debugging out of just the reader and write count.

---

 include/linux/fs.h                |    1 -
 security/integrity/ima/ima_iint.c |    3 ---
 security/integrity/ima/ima_main.c |   10 +++-------
 3 files changed, 3 insertions(+), 11 deletions(-)
include/linux/fs.h +0 -1
index 3a402b3..593bb4d 100644
@@ -780,7 +780,6 @@ struct inode {
 	/* all protected by i_mutex */
 	long			i_readers; /* struct files open RO */
 	long			i_writers; /* struct files open WR */
-	long			i_opencount; /* total open files (readers + writers) */
 #endif
 #ifdef CONFIG_FS_POSIX_ACL
 	struct posix_acl	*i_acl;
security/integrity/ima/ima_iint.c +0 -3
index c584938..2dc32d6 100644
@@ -79,12 +79,9 @@ void ima_check_counters(struct inode *inode)
 		printk(KERN_INFO "%s: readcount: %ld\n", __func__, inode->i_readers);
 	if (inode->i_writers)
 		printk(KERN_INFO "%s: writers: %ld\n", __func__, inode->i_writers);
-	if (inode->i_opencount)
-		printk(KERN_INFO "%s: opencount: %ld\n", __func__, inode->i_opencount);
 
 	inode->i_readers = 0;
 	inode->i_writers = 0;
-	inode->i_opencount = 0;
 }
 
 /* iint_free - called when the iint refcount goes to zero */
security/integrity/ima/ima_main.c +3 -7
index a70700b..92235a0 100644
@@ -123,7 +123,6 @@ static void ima_inc_counts(struct inode *inode, fmode_t mode)
 {
 	BUG_ON(!mutex_is_locked(&inode->i_mutex));
 
-	inode->i_opencount++;
 	if ((mode & (FMODE_READ | FMODE_WRITE)) == FMODE_READ)
 		inode->i_readers++;
 	if (mode & FMODE_WRITE)
@@ -185,7 +184,6 @@ static void ima_dec_counts(struct ima_iint_cache *iint, struct inode *inode,
 	BUG_ON(!mutex_is_locked(&iint->mutex));
 	BUG_ON(!mutex_is_locked(&inode->i_mutex));
 
-	inode->i_opencount--;
 	if ((mode & (FMODE_READ | FMODE_WRITE)) == FMODE_READ)
 		inode->i_readers--;
 	if (mode & FMODE_WRITE) {
@@ -196,13 +194,11 @@ static void ima_dec_counts(struct ima_iint_cache *iint, struct inode *inode,
 		}
 	}
 
-	if (((inode->i_opencount < 0) ||
-	     (inode->i_readers < 0) ||
+	if (((inode->i_readers < 0) ||
 	     (inode->i_writers < 0)) &&
 	    !ima_limit_imbalance(file)) {
-		printk(KERN_INFO "%s: open/free imbalance (r:%ld w:%ld o:%ld)\n",
-		       __func__, inode->i_readers, inode->i_writers,
-		       inode->i_opencount);
+		printk(KERN_INFO "%s: open/free imbalance (r:%ld w:%ld)\n",
+		       __func__, inode->i_readers, inode->i_writers);
 		dump_stack();
 	}
 }
author
#2 lore raw

PATCH 3/6 IMA: use unsigned int instead of long for counters

In reply to Eric Paris

Currently IMA uses 2 longs in struct inode. To save space (and as it seems impossible to overflow 32 bits) we switch these to unsigned int. The switch to unsigned does require slightly different checks for underflow, but it isn't complex.

---

 include/linux/fs.h                |    4 ++--
 security/integrity/ima/ima_iint.c |    4 ++--
 security/integrity/ima/ima_main.c |   15 ++++++++++-----
 3 files changed, 14 insertions(+), 9 deletions(-)
include/linux/fs.h +2 -2
index 593bb4d..8f46e5b 100644
@@ -778,8 +778,8 @@ struct inode {
 #endif
 #ifdef CONFIG_IMA
 	/* all protected by i_mutex */
-	long			i_readers; /* struct files open RO */
-	long			i_writers; /* struct files open WR */
+	unsigned int		i_readers; /* struct files open RO */
+	unsigned int		i_writers; /* struct files open WR */
 #endif
 #ifdef CONFIG_FS_POSIX_ACL
 	struct posix_acl	*i_acl;
security/integrity/ima/ima_iint.c +2 -2
index 2dc32d6..d327840 100644
@@ -76,9 +76,9 @@ out:
 void ima_check_counters(struct inode *inode)
 {
 	if (inode->i_readers)
-		printk(KERN_INFO "%s: readcount: %ld\n", __func__, inode->i_readers);
+		printk(KERN_INFO "%s: readcount: %u\n", __func__, inode->i_readers);
 	if (inode->i_writers)
-		printk(KERN_INFO "%s: writers: %ld\n", __func__, inode->i_writers);
+		printk(KERN_INFO "%s: writers: %u\n", __func__, inode->i_writers);
 
 	inode->i_readers = 0;
 	inode->i_writers = 0;
security/integrity/ima/ima_main.c +10 -5
index 92235a0..68ecb43 100644
@@ -181,12 +181,19 @@ static void ima_dec_counts(struct ima_iint_cache *iint, struct inode *inode,
 			   struct file *file)
 {
 	mode_t mode = file->f_mode;
+	bool dump = false;
+
 	BUG_ON(!mutex_is_locked(&iint->mutex));
 	BUG_ON(!mutex_is_locked(&inode->i_mutex));
 
-	if ((mode & (FMODE_READ | FMODE_WRITE)) == FMODE_READ)
+	if ((mode & (FMODE_READ | FMODE_WRITE)) == FMODE_READ) {
+		if (unlikely(inode->i_readers == 0))
+			dump = true;
 		inode->i_readers--;
+	}
 	if (mode & FMODE_WRITE) {
+		if (unlikely(inode->i_writers == 0))
+			dump = true;
 		inode->i_writers--;
 		if (inode->i_writers == 0) {
 			if (iint->version != inode->i_version)
@@ -194,10 +201,8 @@ static void ima_dec_counts(struct ima_iint_cache *iint, struct inode *inode,
 		}
 	}
 
-	if (((inode->i_readers < 0) ||
-	     (inode->i_writers < 0)) &&
-	    !ima_limit_imbalance(file)) {
-		printk(KERN_INFO "%s: open/free imbalance (r:%ld w:%ld)\n",
+	if (dump && !ima_limit_imbalance(file)) {
+		printk(KERN_INFO "%s: open/free imbalance (r:%u w:%u)\n",
 		       __func__, inode->i_readers, inode->i_writers);
 		dump_stack();
 	}
author
#3 lore raw

PATCH 4/6 IMA: only allocate iint when needed

In reply to Eric Paris

IMA always allocates an integrity structure to hold information about every inode, but only needed this structure to tract the number of readers and writers currently accessing a given inode. Since that information was moved into struct inode instead of the integrity struct this patch stops allocating the integrity stucture until it is needed. Thurs greatly reducing memory usage.

---

 include/linux/ima.h               |    6 ---
 security/integrity/ima/ima.h      |    1 
 security/integrity/ima/ima_api.c  |    2 -
 security/integrity/ima/ima_iint.c |    4 --
 security/integrity/ima/ima_main.c |   87 ++++++++++++++++++++++++++-----------
 security/security.c               |    4 --
 6 files changed, 65 insertions(+), 39 deletions(-)
include/linux/ima.h +0 -6
index 1c4bdb9..72644a5 100644
@@ -15,7 +15,6 @@ 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);
@@ -29,11 +28,6 @@ static inline int ima_bprm_check(struct linux_binprm *bprm)
 	return 0;
 }
 
-static inline int ima_inode_alloc(struct inode *inode)
-{
-	return 0;
-}
-
 static inline void ima_inode_free(struct inode *inode)
 {
 	return;
security/integrity/ima/ima.h +1 -0
index e500fe3..0767717 100644
@@ -70,6 +70,7 @@ int ima_init(void);
 void ima_cleanup(void);
 int ima_fs_init(void);
 void ima_fs_cleanup(void);
+int ima_inode_alloc(struct inode *inode);
 int ima_add_template_entry(struct ima_template_entry *entry, int violation,
 			   const char *op, struct inode *inode);
 int ima_calc_hash(struct file *file, char *digest);
security/integrity/ima/ima_api.c +1 -1
index 52015d0..44f779f 100644
@@ -116,7 +116,7 @@ int ima_must_measure(struct ima_iint_cache *iint, struct inode *inode,
 {
 	int must_measure;
 
-	if (iint->flags & IMA_MEASURED)
+	if (iint && (iint->flags & IMA_MEASURED))
 		return 1;
 
 	must_measure = ima_match_policy(inode, function, mask);
security/integrity/ima/ima_iint.c +1 -3
index d327840..0bab052 100644
@@ -123,9 +123,7 @@ static void init_once(void *foo)
 {
 	struct ima_iint_cache *iint = foo;
 
-	memset(iint, 0, sizeof *iint);
-	iint->version = 0;
-	iint->flags = 0UL;
+	memset(iint, 0, sizeof(*iint));
 	mutex_init(&iint->mutex);
 	kref_init(&iint->refcount);
 }
security/integrity/ima/ima_main.c +61 -26

143 lines not on this page · raw message

security/security.c +1 -3
index ad5ca29..04c098d 100644
@@ -331,9 +331,7 @@ int security_inode_alloc(struct inode *inode)
 	ret =  security_ops->inode_alloc_security(inode);
 	if (ret)
 		return ret;
-	ret = ima_inode_alloc(inode);
-	if (ret)
-		security_inode_free(inode);
+
 	return ret;
 }
 
maintainer
#4 lore raw

Re: [PATCH 4/6] IMA: only allocate iint when needed

Quoted 6 lines · Eric Paris

IMA always allocates an integrity structure to hold information about every inode, but only needed this structure to tract the number of readers and writers currently accessing a given inode. Since that information was moved into struct inode instead of the integrity struct this patch stops allocating the integrity stucture until it is needed. Thurs greatly reducing memory usage.

OK, I'm really confused. Could you explain what's going on with refcounts now? AFAICS, you allocate them in process_measurement() now and they live until the inode is torn down. Fine by me. However
* why bother with bumping refcount in ima_file_free()? It's not going
to die until we free the inode, for fsck sake...
* i_mutex is a damn strange choice for protecting your write counter
* for that matter, why bother with refcount at all? What could
hold a reference to that sucker without holding a reference to struct inode? I don't see anything of that sort, other that delayed freeing that'll hold the only remaining pointer to iint until the callback where it'll promptly drop it.

And while we are at it, you are forcing a hash lookup on _every_ _damn_ close(2) of a regular file. How about marking the inode as ima-infested so that it wouldn't bother? For that matter, this "final writer" logics needs explanation as well...

author
#5 lore raw

PATCH 5/6 IMA: use rbtree instead of radix tree for inode information cache

In reply to Eric Paris

The IMA code needs to store the number of tasks which have an open fd granting permission to write a file even when IMA is not in use. It needs this information in order to be enabled at a later point in time without losing it's integrity garantees. At the moment that means we store a little bit of data about every inode in a cache. We use a radix tree key'd on the inode's memory address. Dave Chinner pointed out that a radix tree is a terrible data structure for such a sparse key space. This patch switches to using an rbtree which should be more efficient.

Bug report from Dave:

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.

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

---

 security/integrity/ima/ima.h      |    4 +-
 security/integrity/ima/ima_iint.c |   85 ++++++++++++++++++++++++++++---------
 2 files changed, 67 insertions(+), 22 deletions(-)
security/integrity/ima/ima.h +3 -1
index 0767717..386026a 100644
@@ -101,6 +101,8 @@ static inline unsigned long ima_hash_key(u8 *digest)
 
 /* integrity data associated with an inode */
 struct ima_iint_cache {
+	struct rb_node rb_node; /* rooted in ima_iint_tree */
+	struct inode *inode;	/* back pointer to inode in question */
 	u64 version;		/* track inode changes */
 	unsigned long flags;
 	u8 digest[IMA_DIGEST_SIZE];
@@ -120,7 +122,7 @@ int ima_store_template(struct ima_template_entry *entry, int violation,
 void ima_template_show(struct seq_file *m, void *e,
 		       enum ima_show_type show);
 
-/* radix tree calls to lookup, insert, delete
+/* rbtree tree calls to lookup, insert, delete
  * integrity data associated with an inode.
  */
 struct ima_iint_cache *ima_iint_insert(struct inode *inode);
security/integrity/ima/ima_iint.c +64 -21

128 lines not on this page · raw message

#6 lore raw

Re: [PATCH 5/6] IMA: use rbtree instead of radix tree for inode information cache

Quoted 4 lines · Eric Paris
security/integrity/ima/ima_iint.c +0 -0
@@ -36,12 +63,11 @@ struct ima_iint_cache *ima_iint_find_get(struct inode *inode)
 	struct ima_iint_cache *iint;
 
 	rcu_read_lock();

security/integrity/ima/ima_iint.c struct ima_iint_cache *ima_iint_find_get(struct inode *inode) · line 70

Quoted 10 lines
security/integrity/ima/ima_iint.c +4 -5
-	iint = radix_tree_lookup(&ima_iint_store, (unsigned long)inode);
-	if (!iint)
-		goto out;
-	kref_get(&iint->refcount);
-out:
+	iint = __ima_iint_find(inode);
+	if (iint)
+		kref_get(&iint->refcount);
 	rcu_read_unlock();
+

This is wrong - the rbtree is protected only by the ima_iint_lock(), not RCU. Hence you can't do lockless lookups on an rbtree in this manner as they will race with inserts and deletes.

Cheers,

Dave.

Signature · 2 lines
Dave Chinner
[email protected]
#7 lore raw

Re: [PATCH 5/6] IMA: use rbtree instead of radix tree for inode information cache

Quoted 4 lines · Dave Chinner
Quoted 3 lines · Eric Paris
(quoted diff) +0 -0
@@ -36,12 +63,11 @@ struct ima_iint_cache *ima_iint_find_get(struct inode *inode)
 	struct ima_iint_cache *iint;
 
Quoted 15 lines

security/integrity/ima/ima_iint.c struct ima_iint_cache *ima_iint_find_get(struct inode *inode) · line 70

Quoted 11 lines
security/integrity/ima/ima_iint.c +4 -5
 	rcu_read_lock();
-	iint = radix_tree_lookup(&ima_iint_store, (unsigned long)inode);
-	if (!iint)
-		goto out;
-	kref_get(&iint->refcount);
-out:
+	iint = __ima_iint_find(inode);
+	if (iint)
+		kref_get(&iint->refcount);
 	rcu_read_unlock();
+

This is wrong - the rbtree is protected only by the ima_iint_lock(), not RCU. Hence you can't do lockless lookups on an rbtree in this manner as they will race with inserts and deletes.

Correct, what can be made to work is combine RCU with a seqlock. Retry the lookup using read_seqretry(), RCU here helps to ensure you're not stepping on already freed memory.

So, tree modification does:

  write_seqlock();
  /* frob RB-tree, using call_rcu() for frees where needed */
  write_sequnlock();

Lookup does:

unsigned seq;

rcu_read_lock()
again;
seq = read_seqbegin();

/* RB-tree lookup */

if (read_seqretry(seq))

    goto again;
  rcu_read_unlock();

return obj;

#8 lore raw

Re: [PATCH 5/6] IMA: use rbtree instead of radix tree for inode information cache

Quoted 40 lines · Peter Zijlstra
Quoted 4 lines · Dave Chinner
Quoted 3 lines · Eric Paris
(quoted diff) +0 -0
@@ -36,12 +63,11 @@ struct ima_iint_cache *ima_iint_find_get(struct inode *inode)
 	struct ima_iint_cache *iint;
 
Quoted 15 lines

security/integrity/ima/ima_iint.c struct ima_iint_cache *ima_iint_find_get(struct inode *inode) · line 70

Quoted 11 lines
security/integrity/ima/ima_iint.c +4 -5
 	rcu_read_lock();
-	iint = radix_tree_lookup(&ima_iint_store, (unsigned long)inode);
-	if (!iint)
-		goto out;
-	kref_get(&iint->refcount);
-out:
+	iint = __ima_iint_find(inode);
+	if (iint)
+		kref_get(&iint->refcount);
 	rcu_read_unlock();
+

This is wrong - the rbtree is protected only by the ima_iint_lock(), not RCU. Hence you can't do lockless lookups on an rbtree in this manner as they will race with inserts and deletes.

Correct, what can be made to work is combine RCU with a seqlock. Retry the lookup using read_seqretry(), RCU here helps to ensure you're not stepping on already freed memory.

So, tree modification does:

  write_seqlock();
  /* frob RB-tree, using call_rcu() for frees where needed */
  write_sequnlock();

Lookup does:

unsigned seq;

rcu_read_lock()
again;
seq = read_seqbegin();

Quoted 8 lines

/* RB-tree lookup */

if (read_seqretry(seq))

    goto again;
  rcu_read_unlock();

return obj;

Nice trick, Peter. Thanks for sharing that - I'll definitely find that useful. :)

/me wanders off to look at converting the xfs buffer cache rbtrees to RCU....

Cheers,

Dave.

Signature · 2 lines
Dave Chinner
[email protected]
#9 lore raw

Re: [PATCH 5/6] IMA: use rbtree instead of radix tree for inode information cache

Quoted 3 lines · Dave Chinner

/me wanders off to look at converting the xfs buffer cache rbtrees to RCU....

Look out for livelocks, though. And yes, they can happen.

So rather than a loop, one option is to do basically

  rcu_read_lock();
  seq = read_seqbegin();

.. do lookup ..

  need_lock = read_seqretry(seq);
  rcu_read_unlock();

  if (need_lock) {
    get_real_lock();
    .. do lookup ..

    drop_real_lock();

}

which just falls back to a locked access if the rcu model doesn't work.

Linus

#10 lore raw

Re: [PATCH 5/6] IMA: use rbtree instead of radix tree for inode information cache

Quoted 20 lines · Linus Torvalds
Quoted 3 lines · Dave Chinner

/me wanders off to look at converting the xfs buffer cache rbtrees to RCU....

Look out for livelocks, though. And yes, they can happen.

So rather than a loop, one option is to do basically

  rcu_read_lock();
  seq = read_seqbegin();

.. do lookup ..

  need_lock = read_seqretry(seq);
  rcu_read_unlock();

  if (need_lock) {
    get_real_lock();
Quoted 8 lines
    .. do lookup ..

    drop_real_lock();

}

which just falls back to a locked access if the rcu model doesn't work.

Linus

That is a really interesting alternative to traditional locking. Could we perhaps document it in Documentation/rbtree.txt?

Cheers
Trond

#11 lore raw

Re: [PATCH 5/6] IMA: use rbtree instead of radix tree for inode information cache

Quoted 3 lines · Trond Myklebust

That is a really interesting alternative to traditional locking. Could we perhaps document it in Documentation/rbtree.txt?

Well, I'd actually suggest avoiding it unless you feel that you _really_ need it. So I wouldn't want to really suggest it as a generic locking model - you had better have looked at pretty much all other alternatives first. And if that seqlock starts failing a lot under load, it ends up being _more_ expensive than just taking the lock in the first place.

Linus

#12 lore raw

Re: [PATCH 5/6] IMA: use rbtree instead of radix tree for inode information cache

Quoted 6 lines · Linus Torvalds
Quoted 3 lines · Trond Myklebust

That is a really interesting alternative to traditional locking. Could we perhaps document it in Documentation/rbtree.txt?

Quoted 6 lines

Well, I'd actually suggest avoiding it unless you feel that you _really_ need it. So I wouldn't want to really suggest it as a generic locking model - you had better have looked at pretty much all other alternatives first. And if that seqlock starts failing a lot under load, it ends up being _more_ expensive than just taking the lock in the first place.

Thanks for pointing out that caveat. I think that the XFS buffer cache case won't have that problem - I'm seeing better than a 100:1 tree lookup (>1M/s) to modification rate (<10k inserts/s) under workloads that are stressing the cache on an 8-way VM...

Still, as the only method I've heard of that allows RCU lookup on rbtrees, perhaps it is still worth documenting along with all the caveats of when not to use this.

Cheers,

Dave.

Signature · 2 lines
Dave Chinner
[email protected]
author
#13 lore raw

PATCH 6/6 IMA: use i_writecount rather than a private counter

In reply to Eric Paris

IMA tracks the number of struct files which are holding a given inode readonly and the number white are holding the inode write or r/w. It needs this information so when a new reader or writer comes in it can tell if this new file will be able to invalidate results it already made about existing files.

aka if a task is holding a struct file open RO, IMA measured the file and recorded those measurements and then a task opens the file RW IMA needs to note in the logs that the old measurement may not be correct. It's called a "Time of Measure Time of Use" (ToMToU) issue. The same is true is a RO file is opened to an inode which has an open writer. We cannot, with any validity, measure the file in question since it could be changing.

This patch attempts to use the i_writecount field to track writers. The i_writecount field actually embeds more information in it's value that IMA needs but it should work for our purposes and allow us to shrink the struct inode even more.

---

 include/linux/fs.h                |    3 -
 security/integrity/ima/ima_iint.c |    3 -
 security/integrity/ima/ima_main.c |   95 +++++++++++++------------------------
 3 files changed, 34 insertions(+), 67 deletions(-)
include/linux/fs.h +1 -2
index 8f46e5b..5dbbf6b 100644
@@ -777,9 +777,8 @@ struct inode {
 	void			*i_security;
 #endif
 #ifdef CONFIG_IMA
-	/* all protected by i_mutex */
+	/* all protected by i_lock */
 	unsigned int		i_readers; /* struct files open RO */
-	unsigned int		i_writers; /* struct files open WR */
 #endif
 #ifdef CONFIG_FS_POSIX_ACL
 	struct posix_acl	*i_acl;
security/integrity/ima/ima_iint.c +0 -3
index bef6e8f..6e82324 100644
@@ -118,11 +118,8 @@ void ima_check_counters(struct inode *inode)
 {
 	if (inode->i_readers)
 		printk(KERN_INFO "%s: readcount: %u\n", __func__, inode->i_readers);
-	if (inode->i_writers)
-		printk(KERN_INFO "%s: writers: %u\n", __func__, inode->i_writers);
 
 	inode->i_readers = 0;
-	inode->i_writers = 0;
 }
 
 /* iint_free - called when the iint refcount goes to zero */
security/integrity/ima/ima_main.c +33 -62

170 lines not on this page · raw message

#14 lore raw
In reply to Eric Paris
Quoted 3 lines · Eric Paris

This patch does the minimum needed to move the location of the data.  Further cleanups, especially the location of counter updates, may still be possible.

Hmm. The end result looks fine (adding four bytes to struct inode in order to avoid all the complexity seems reasonable), but I do get the feeling that this should likely be the last in the series, so that the VFS level files would get minimal changes. IOW, do the cleanups inside the IMA code first, and then do the switch-over to using counters in the inode last.

Well, not last, since I think you need to do this before you can do the "only allocate iint when needed" only after you've moved the counters. But I think the logical order would be
- switch to rbtree
- drop opencount
- switch counts to 'unsigned int'
- drop iint->writecount and use i_writecount instead
- move the remaining readcount to i_readcount
- only allocate iint when necessary

That way you'd only have _one_ patch that touches <linux/fs.h>, rather than four, and the remaining patches would all be to security/ima.

But maybe I missed some reason for this particular ordering.

Oh, and btw, due to alignment reasons it looks like the 4-byte i_readcount would take 8 bytes due to bad structure packing. I don't know if that is avoidable, but I do think it would make more sense to put it next to i_writecount instead of in between two pointers. That still doesn't help (we've got 3 32-bit values next to each other), but it's at least -closer- to working out.

Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

author
#15 lore raw
Quoted 25 lines · Linus Torvalds
Quoted 3 lines · Eric Paris

This patch does the minimum needed to move the location of the data. Further cleanups, especially the location of counter updates, may still be possible.

Hmm. The end result looks fine (adding four bytes to struct inode in order to avoid all the complexity seems reasonable), but I do get the feeling that this should likely be the last in the series, so that the VFS level files would get minimal changes. IOW, do the cleanups inside the IMA code first, and then do the switch-over to using counters in the inode last.

Well, not last, since I think you need to do this before you can do the "only allocate iint when needed" only after you've moved the counters. But I think the logical order would be
- switch to rbtree
- drop opencount
- switch counts to 'unsigned int'
- drop iint->writecount and use i_writecount instead
- move the remaining readcount to i_readcount
- only allocate iint when necessary

That way you'd only have _one_ patch that touches <linux/fs.h>, rather than four, and the remaining patches would all be to security/ima.

Quoted 8 lines

But maybe I missed some reason for this particular ordering.

Oh, and btw, due to alignment reasons it looks like the 4-byte i_readcount would take 8 bytes due to bad structure packing. I don't know if that is avoidable, but I do think it would make more sense to put it next to i_writecount instead of in between two pointers. That still doesn't help (we've got 3 32-bit values next to each other), but it's at least -closer- to working out.

Believe me, this series has not been forgotten over the week. I know that IBM research tested my series from yesterday and found that it didn't break any of their test suite but they haven't reviewed them well enough to give an ACK.

I probably should spend another couple of hours myself looking over my series before I ask for a pull from anyone but I'm willing to show my latest work.

http://git.infradead.org/users/eparis/ima.git
(these patches are still being changed so don't trust this tree)

Main changes from last series:
1) did away with rcu altogether
2) added a new inode->i_flags, S_IMA which gets set when an ima integrity structure is allocated so common case on inode free is lockless.
3) shrunk the integrity structure more. Now even with all of lock debugging turned on it's 232 bytes (most of that is a struct mutex i'm going to look at doing away with down the line)

-Eric

#16 lore raw
Quoted 56 lines · Eric Paris
Quoted 25 lines · Linus Torvalds
Quoted 3 lines · Eric Paris

This patch does the minimum needed to move the location of the data. Further cleanups, especially the location of counter updates, may still be possible.

Hmm. The end result looks fine (adding four bytes to struct inode in order to avoid all the complexity seems reasonable), but I do get the feeling that this should likely be the last in the series, so that the VFS level files would get minimal changes. IOW, do the cleanups inside the IMA code first, and then do the switch-over to using counters in the inode last.

Well, not last, since I think you need to do this before you can do the "only allocate iint when needed" only after you've moved the counters. But I think the logical order would be
- switch to rbtree
- drop opencount
- switch counts to 'unsigned int'
- drop iint->writecount and use i_writecount instead
- move the remaining readcount to i_readcount
- only allocate iint when necessary

That way you'd only have _one_ patch that touches <linux/fs.h>, rather than four, and the remaining patches would all be to security/ima.

Quoted 8 lines

But maybe I missed some reason for this particular ordering.

Oh, and btw, due to alignment reasons it looks like the 4-byte i_readcount would take 8 bytes due to bad structure packing. I don't know if that is avoidable, but I do think it would make more sense to put it next to i_writecount instead of in between two pointers. That still doesn't help (we've got 3 32-bit values next to each other), but it's at least -closer- to working out.

Believe me, this series has not been forgotten over the week. I know that IBM research tested my series from yesterday and found that it didn't break any of their test suite but they haven't reviewed them well enough to give an ACK.

I probably should spend another couple of hours myself looking over my series before I ask for a pull from anyone but I'm willing to show my latest work.

http://git.infradead.org/users/eparis/ima.git
(these patches are still being changed so don't trust this tree)

Main changes from last series:
1) did away with rcu altogether
2) added a new inode->i_flags, S_IMA which gets set when an ima integrity structure is allocated so common case on inode free is lockless.
3) shrunk the integrity structure more. Now even with all of lock debugging turned on it's 232 bytes (most of that is a struct mutex i'm going to look at doing away with down the line)

Quoted 1 line

-Eric

In [PATCH 08/11] IMA: only allocate iint when needed

+ if (unlikely(inode->i_readcount == 0) &&
+ !ima_limit_imbalance(file)) {
+ printk(KERN_INFO "%s: open/free imbalance (r:%
u)\n",
+ __func__, inode->i_readcount);
+ dump_stack();
+ } else {
+ inode->i_readcount--;
+ }

Please separate the i_readcount test from the !ima_limit_imbalance() test.

Other than this, and a couple of typos in the patch descriptions, the patches look really nice!

thanks,

Mimi