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

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

[Eric Paris]

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.

Signed-off-by: Eric Paris <eparis@redhat.com>
---

 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(-)

diff --git a/fs/inode.c b/fs/inode.c
index 8646433..5d7ce1e 100644
--- a/fs/inode.c
+++ b/fs/inode.c
@@ -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
diff --git a/include/linux/fs.h b/include/linux/fs.h
index 5fb4dfd..3a402b3 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -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;
diff --git a/include/linux/ima.h b/include/linux/ima.h
index 975837e..1c4bdb9 100644
--- a/include/linux/ima.h
+++ b/include/linux/ima.h
@@ -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 */
diff --git a/security/integrity/ima/ima.h b/security/integrity/ima/ima.h
index 3fbcd1d..e500fe3 100644
--- a/security/integrity/ima/ima.h
+++ b/security/integrity/ima/ima.h
@@ -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;
 };
diff --git a/security/integrity/ima/ima_iint.c b/security/integrity/ima/ima_iint.c
index afba4ae..c584938 100644
--- a/security/integrity/ima/ima_iint.c
+++ b/security/integrity/ima/ima_iint.c
@@ -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);
 }
 
diff --git a/security/integrity/ima/ima_main.c b/security/integrity/ima/ima_main.c
index e662b89..a70700b 100644
--- a/security/integrity/ima/ima_main.c
+++ b/security/integrity/ima/ima_main.c
@@ -97,18 +97,19 @@ out:
  */
 enum iint_pcr_error { TOMTOU, OPEN_WRITERS };
 static void ima_read_write_check(enum iint_pcr_error error,
-				 struct ima_iint_cache *iint,
 				 struct inode *inode,
 				 const unsigned char *filename)
 {
+	BUG_ON(!mutex_is_locked(&inode->i_mutex));
+
 	switch (error) {
 	case TOMTOU:
-		if (iint->readcount > 0)
+		if (inode->i_readers > 0)
 			ima_add_violation(inode, filename, "invalid_pcr",
 					  "ToMToU");
 		break;
 	case OPEN_WRITERS:
-		if (iint->writecount > 0)
+		if (inode->i_writers > 0)
 			ima_add_violation(inode, filename, "invalid_pcr",
 					  "open_writers");
 		break;
@@ -118,15 +119,15 @@ static void ima_read_write_check(enum iint_pcr_error error,
 /*
  * Update the counts given an fmode_t
  */
-static void ima_inc_counts(struct ima_iint_cache *iint, fmode_t mode)
+static void ima_inc_counts(struct inode *inode, fmode_t mode)
 {
-	BUG_ON(!mutex_is_locked(&iint->mutex));
+	BUG_ON(!mutex_is_locked(&inode->i_mutex));
 
-	iint->opencount++;
+	inode->i_opencount++;
 	if ((mode & (FMODE_READ | FMODE_WRITE)) == FMODE_READ)
-		iint->readcount++;
+		inode->i_readers++;
 	if (mode & FMODE_WRITE)
-		iint->writecount++;
+		inode->i_writers++;
 }
 
 /*
@@ -154,6 +155,7 @@ void ima_counts_get(struct file *file)
 	if (!iint)
 		return;
 	mutex_lock(&iint->mutex);
+	mutex_lock(&inode->i_mutex);
 	if (!ima_initialized)
 		goto out;
 	rc = ima_must_measure(iint, inode, MAY_READ, FILE_CHECK);
@@ -161,12 +163,13 @@ void ima_counts_get(struct file *file)
 		goto out;
 
 	if (mode & FMODE_WRITE) {
-		ima_read_write_check(TOMTOU, iint, inode, dentry->d_name.name);
+		ima_read_write_check(TOMTOU, inode, dentry->d_name.name);
 		goto out;
 	}
-	ima_read_write_check(OPEN_WRITERS, iint, inode, dentry->d_name.name);
+	ima_read_write_check(OPEN_WRITERS, inode, dentry->d_name.name);
 out:
-	ima_inc_counts(iint, file->f_mode);
+	ima_inc_counts(inode, file->f_mode);
+	mutex_unlock(&inode->i_mutex);
 	mutex_unlock(&iint->mutex);
 
 	kref_put(&iint->refcount, iint_free);
@@ -180,25 +183,26 @@ static void ima_dec_counts(struct ima_iint_cache *iint, struct inode *inode,
 {
 	mode_t mode = file->f_mode;
 	BUG_ON(!mutex_is_locked(&iint->mutex));
+	BUG_ON(!mutex_is_locked(&inode->i_mutex));
 
-	iint->opencount--;
+	inode->i_opencount--;
 	if ((mode & (FMODE_READ | FMODE_WRITE)) == FMODE_READ)
-		iint->readcount--;
+		inode->i_readers--;
 	if (mode & FMODE_WRITE) {
-		iint->writecount--;
-		if (iint->writecount == 0) {
+		inode->i_writers--;
+		if (inode->i_writers == 0) {
 			if (iint->version != inode->i_version)
 				iint->flags &= ~IMA_MEASURED;
 		}
 	}
 
-	if (((iint->opencount < 0) ||
-	     (iint->readcount < 0) ||
-	     (iint->writecount < 0)) &&
+	if (((inode->i_opencount < 0) ||
+	     (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__, iint->readcount, iint->writecount,
-		       iint->opencount);
+		       __func__, inode->i_readers, inode->i_writers,
+		       inode->i_opencount);
 		dump_stack();
 	}
 }
@@ -208,7 +212,7 @@ static void ima_dec_counts(struct ima_iint_cache *iint, struct inode *inode,
  * @file: pointer to file structure being freed
  *
  * Flag files that changed, based on i_version;
- * and decrement the iint readcount/writecount.
+ * and decrement the i_readers/i_writers.
  */
 void ima_file_free(struct file *file)
 {
@@ -222,8 +226,10 @@ void ima_file_free(struct file *file)
 		return;
 
 	mutex_lock(&iint->mutex);
+	mutex_lock(&inode->i_mutex);
 	ima_dec_counts(iint, inode, file);
 	mutex_unlock(&iint->mutex);
+	mutex_unlock(&inode->i_mutex);
 	kref_put(&iint->refcount, iint_free);
 }
 

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

[Eric Paris]

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.

Signed-off-by: Eric Paris <eparis@redhat.com>
---

 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(-)

diff --git a/include/linux/fs.h b/include/linux/fs.h
index 3a402b3..593bb4d 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -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;
diff --git a/security/integrity/ima/ima_iint.c b/security/integrity/ima/ima_iint.c
index c584938..2dc32d6 100644
--- a/security/integrity/ima/ima_iint.c
+++ b/security/integrity/ima/ima_iint.c
@@ -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 */
diff --git a/security/integrity/ima/ima_main.c b/security/integrity/ima/ima_main.c
index a70700b..92235a0 100644
--- a/security/integrity/ima/ima_main.c
+++ b/security/integrity/ima/ima_main.c
@@ -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();
 	}
 }

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

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

Signed-off-by: Eric Paris <eparis@redhat.com>
---

 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(-)

diff --git a/include/linux/fs.h b/include/linux/fs.h
index 593bb4d..8f46e5b 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -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;
diff --git a/security/integrity/ima/ima_iint.c b/security/integrity/ima/ima_iint.c
index 2dc32d6..d327840 100644
--- a/security/integrity/ima/ima_iint.c
+++ b/security/integrity/ima/ima_iint.c
@@ -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;
diff --git a/security/integrity/ima/ima_main.c b/security/integrity/ima/ima_main.c
index 92235a0..68ecb43 100644
--- a/security/integrity/ima/ima_main.c
+++ b/security/integrity/ima/ima_main.c
@@ -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();
 	}

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

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

Signed-off-by: Eric Paris <eparis@redhat.com>
---

 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(-)

diff --git a/include/linux/ima.h b/include/linux/ima.h
index 1c4bdb9..72644a5 100644
--- a/include/linux/ima.h
+++ b/include/linux/ima.h
@@ -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;
diff --git a/security/integrity/ima/ima.h b/security/integrity/ima/ima.h
index e500fe3..0767717 100644
--- a/security/integrity/ima/ima.h
+++ b/security/integrity/ima/ima.h
@@ -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);
diff --git a/security/integrity/ima/ima_api.c b/security/integrity/ima/ima_api.c
index 52015d0..44f779f 100644
--- a/security/integrity/ima/ima_api.c
+++ b/security/integrity/ima/ima_api.c
@@ -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);
diff --git a/security/integrity/ima/ima_iint.c b/security/integrity/ima/ima_iint.c
index d327840..0bab052 100644
--- a/security/integrity/ima/ima_iint.c
+++ b/security/integrity/ima/ima_iint.c
@@ -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);
 }
diff --git a/security/integrity/ima/ima_main.c b/security/integrity/ima/ima_main.c
index 68ecb43..860e161 100644
--- a/security/integrity/ima/ima_main.c
+++ b/security/integrity/ima/ima_main.c
@@ -145,19 +145,17 @@ void ima_counts_get(struct file *file)
 	struct dentry *dentry = file->f_path.dentry;
 	struct inode *inode = dentry->d_inode;
 	fmode_t mode = file->f_mode;
-	struct ima_iint_cache *iint;
 	int rc;
 
 	if (!iint_initialized || !S_ISREG(inode->i_mode))
 		return;
-	iint = ima_iint_find_get(inode);
-	if (!iint)
-		return;
-	mutex_lock(&iint->mutex);
+
 	mutex_lock(&inode->i_mutex);
+
 	if (!ima_initialized)
 		goto out;
-	rc = ima_must_measure(iint, inode, MAY_READ, FILE_CHECK);
+
+	rc = ima_must_measure(NULL, inode, MAY_READ, FILE_CHECK);
 	if (rc < 0)
 		goto out;
 
@@ -169,21 +167,16 @@ void ima_counts_get(struct file *file)
 out:
 	ima_inc_counts(inode, file->f_mode);
 	mutex_unlock(&inode->i_mutex);
-	mutex_unlock(&iint->mutex);
-
-	kref_put(&iint->refcount, iint_free);
 }
 
 /*
  * Decrement ima counts
  */
-static void ima_dec_counts(struct ima_iint_cache *iint, struct inode *inode,
-			   struct file *file)
+static void ima_dec_counts(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) {
@@ -195,10 +188,6 @@ static void ima_dec_counts(struct ima_iint_cache *iint, struct inode *inode,
 		if (unlikely(inode->i_writers == 0))
 			dump = true;
 		inode->i_writers--;
-		if (inode->i_writers == 0) {
-			if (iint->version != inode->i_version)
-				iint->flags &= ~IMA_MEASURED;
-		}
 	}
 
 	if (dump && !ima_limit_imbalance(file)) {
@@ -208,6 +197,45 @@ static void ima_dec_counts(struct ima_iint_cache *iint, struct inode *inode,
 	}
 }
 
+static void ima_check_last_writer(struct ima_iint_cache *iint,
+				  struct inode *inode,
+				  struct file *file)
+{
+	mode_t mode = file->f_mode;
+
+	BUG_ON(!mutex_is_locked(&iint->mutex));
+	BUG_ON(!mutex_is_locked(&inode->i_mutex));
+
+	if (mode & FMODE_WRITE &&
+	    inode->i_writers == 0 &&
+	    iint->version != inode->i_version)
+		iint->flags &= ~IMA_MEASURED;
+}
+
+static void ima_file_free_iint(struct ima_iint_cache *iint, struct inode *inode,
+			       struct file *file)
+{
+	mutex_lock(&iint->mutex);
+	mutex_lock(&inode->i_mutex);
+
+	ima_dec_counts(inode, file);
+	ima_check_last_writer(iint, inode, file);
+
+	mutex_unlock(&inode->i_mutex);
+	mutex_unlock(&iint->mutex);
+
+	kref_put(&iint->refcount, iint_free);
+}
+
+static void ima_file_free_noiint(struct inode *inode, struct file *file)
+{
+	mutex_lock(&inode->i_mutex);
+
+	ima_dec_counts(inode, file);
+
+	mutex_unlock(&inode->i_mutex);
+}
+
 /**
  * ima_file_free - called on __fput()
  * @file: pointer to file structure being freed
@@ -223,15 +251,12 @@ void ima_file_free(struct file *file)
 	if (!iint_initialized || !S_ISREG(inode->i_mode))
 		return;
 	iint = ima_iint_find_get(inode);
-	if (!iint)
-		return;
 
-	mutex_lock(&iint->mutex);
-	mutex_lock(&inode->i_mutex);
-	ima_dec_counts(iint, inode, file);
-	mutex_unlock(&iint->mutex);
-	mutex_unlock(&inode->i_mutex);
-	kref_put(&iint->refcount, iint_free);
+	if (iint)
+		ima_file_free_iint(iint, inode, file);
+	else
+		ima_file_free_noiint(inode, file);
+
 }
 
 static int process_measurement(struct file *file, const unsigned char *filename,
@@ -243,11 +268,21 @@ static int process_measurement(struct file *file, const unsigned char *filename,
 
 	if (!ima_initialized || !S_ISREG(inode->i_mode))
 		return 0;
+
+	rc = ima_must_measure(NULL, inode, mask, function);
+	if (rc != 0)
+		return rc;
+retry:
 	iint = ima_iint_find_get(inode);
-	if (!iint)
-		return -ENOMEM;
+	if (!iint) {
+		rc = ima_inode_alloc(inode);
+		if (!rc || rc == -EEXIST)
+			goto retry;
+		return rc;
+	}
 
 	mutex_lock(&iint->mutex);
+
 	rc = ima_must_measure(iint, inode, mask, function);
 	if (rc != 0)
 		goto out;
diff --git a/security/security.c b/security/security.c
index ad5ca29..04c098d 100644
--- a/security/security.c
+++ b/security/security.c
@@ -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;
 }
 

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

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

Reported-by: Dave Chinner <david@fromorbit.com>
Signed-off-by: Eric Paris <eparis@redhat.com>
---

 security/integrity/ima/ima.h      |    4 +-
 security/integrity/ima/ima_iint.c |   85 ++++++++++++++++++++++++++++---------
 2 files changed, 67 insertions(+), 22 deletions(-)

diff --git a/security/integrity/ima/ima.h b/security/integrity/ima/ima.h
index 0767717..386026a 100644
--- a/security/integrity/ima/ima.h
+++ b/security/integrity/ima/ima.h
@@ -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);
diff --git a/security/integrity/ima/ima_iint.c b/security/integrity/ima/ima_iint.c
index 0bab052..bef6e8f 100644
--- a/security/integrity/ima/ima_iint.c
+++ b/security/integrity/ima/ima_iint.c
@@ -12,21 +12,48 @@
  * File: ima_iint.c
  * 	- implements the IMA hooks: ima_inode_alloc, ima_inode_free
  *	- cache integrity information associated with an inode
- *	  using a radix tree.
+ *	  using a rbtree tree.
  */
 #include <linux/slab.h>
 #include <linux/module.h>
 #include <linux/spinlock.h>
-#include <linux/radix-tree.h>
+#include <linux/rbtree.h>
 #include "ima.h"
 
-RADIX_TREE(ima_iint_store, GFP_ATOMIC);
+static struct rb_root ima_iint_tree = RB_ROOT;
 DEFINE_SPINLOCK(ima_iint_lock);
 static struct kmem_cache *iint_cache __read_mostly;
 
 int iint_initialized = 0;
 
-/* ima_iint_find_get - return the iint associated with an inode
+/*
+ * __ima_iint_find - return the iint associated with an inode
+ *
+ * The caller must hold either the rcu_read_lock or the ima_iint_lock
+ */
+static struct ima_iint_cache *__ima_iint_find(struct inode *inode)
+{
+	struct ima_iint_cache *iint;
+	struct rb_node *n = ima_iint_tree.rb_node;
+
+	while (n) {
+		iint = rb_entry(n, struct ima_iint_cache, rb_node);
+
+		if (inode < iint->inode)
+			n = n->rb_left;
+		else if (inode > iint->inode)
+			n = n->rb_right;
+		else
+			break;
+	}
+	if (!n)
+		return NULL;
+
+	return iint;
+}
+
+/*
+ * ima_iint_find_get - return the iint associated with an inode
  *
  * ima_iint_find_get gets a reference to the iint. Caller must
  * remember to put the iint reference.
@@ -36,12 +63,11 @@ struct ima_iint_cache *ima_iint_find_get(struct inode *inode)
 	struct ima_iint_cache *iint;
 
 	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();
+
 	return iint;
 }
 
@@ -51,24 +77,39 @@ out:
  */
 int ima_inode_alloc(struct inode *inode)
 {
-	struct ima_iint_cache *iint = NULL;
+	struct rb_node **p;
+	struct rb_node *new_node, *parent = NULL;
+	struct ima_iint_cache *new_iint, *test_iint;
 	int rc = 0;
 
-	iint = kmem_cache_alloc(iint_cache, GFP_NOFS);
-	if (!iint)
+	new_iint = kmem_cache_alloc(iint_cache, GFP_NOFS);
+	if (!new_iint)
 		return -ENOMEM;
 
-	rc = radix_tree_preload(GFP_NOFS);
-	if (rc < 0)
-		goto out;
+	new_iint->inode = inode;
+	new_node = &new_iint->rb_node;
 
 	spin_lock(&ima_iint_lock);
-	rc = radix_tree_insert(&ima_iint_store, (unsigned long)inode, iint);
-	spin_unlock(&ima_iint_lock);
-	radix_tree_preload_end();
+
+	p = &ima_iint_tree.rb_node;
+	while (*p) {
+		parent = *p;
+		test_iint = rb_entry(parent, struct ima_iint_cache, rb_node);
+
+		if (inode < test_iint->inode)
+			p = &(*p)->rb_left;
+		else if (inode > test_iint->inode)
+			p = &(*p)->rb_right;
+		else {
+			rc = -EEXIST;
+			goto out;
+		}
+	}
+
+	rb_link_node(new_node, parent, p);
+	rb_insert_color(new_node, &ima_iint_tree);
 out:
-	if (rc < 0)
-		kmem_cache_free(iint_cache, iint);
+	spin_unlock(&ima_iint_lock);
 
 	return rc;
 }
@@ -113,7 +154,9 @@ void ima_inode_free(struct inode *inode)
 	struct ima_iint_cache *iint;
 
 	spin_lock(&ima_iint_lock);
-	iint = radix_tree_delete(&ima_iint_store, (unsigned long)inode);
+	iint = __ima_iint_find(inode);
+	if (iint)
+		rb_erase(&iint->rb_node, &ima_iint_tree);
 	spin_unlock(&ima_iint_lock);
 	if (iint)
 		call_rcu(&iint->rcu, iint_rcu_free);

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

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

Signed-off-by: Eric Paris <eparis@redhat.com>
---

 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(-)

diff --git a/include/linux/fs.h b/include/linux/fs.h
index 8f46e5b..5dbbf6b 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -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;
diff --git a/security/integrity/ima/ima_iint.c b/security/integrity/ima/ima_iint.c
index bef6e8f..6e82324 100644
--- a/security/integrity/ima/ima_iint.c
+++ b/security/integrity/ima/ima_iint.c
@@ -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 */
diff --git a/security/integrity/ima/ima_main.c b/security/integrity/ima/ima_main.c
index 860e161..668ea93 100644
--- a/security/integrity/ima/ima_main.c
+++ b/security/integrity/ima/ima_main.c
@@ -85,48 +85,15 @@ out:
 	return found;
 }
 
-/* ima_read_write_check - reflect possible reading/writing errors in the PCR.
- *
- * When opening a file for read, if the file is already open for write,
- * the file could change, resulting in a file measurement error.
- *
- * Opening a file for write, if the file is already open for read, results
- * in a time of measure, time of use (ToMToU) error.
- *
- * In either case invalidate the PCR.
- */
-enum iint_pcr_error { TOMTOU, OPEN_WRITERS };
-static void ima_read_write_check(enum iint_pcr_error error,
-				 struct inode *inode,
-				 const unsigned char *filename)
-{
-	BUG_ON(!mutex_is_locked(&inode->i_mutex));
-
-	switch (error) {
-	case TOMTOU:
-		if (inode->i_readers > 0)
-			ima_add_violation(inode, filename, "invalid_pcr",
-					  "ToMToU");
-		break;
-	case OPEN_WRITERS:
-		if (inode->i_writers > 0)
-			ima_add_violation(inode, filename, "invalid_pcr",
-					  "open_writers");
-		break;
-	}
-}
-
 /*
  * Update the counts given an fmode_t
  */
 static void ima_inc_counts(struct inode *inode, fmode_t mode)
 {
-	BUG_ON(!mutex_is_locked(&inode->i_mutex));
+	assert_spin_locked(&inode->i_lock);
 
 	if ((mode & (FMODE_READ | FMODE_WRITE)) == FMODE_READ)
 		inode->i_readers++;
-	if (mode & FMODE_WRITE)
-		inode->i_writers++;
 }
 
 /*
@@ -146,11 +113,12 @@ void ima_counts_get(struct file *file)
 	struct inode *inode = dentry->d_inode;
 	fmode_t mode = file->f_mode;
 	int rc;
+	bool send_tomtou = false, send_writers = false;
 
-	if (!iint_initialized || !S_ISREG(inode->i_mode))
+	if (!S_ISREG(inode->i_mode))
 		return;
 
-	mutex_lock(&inode->i_mutex);
+	spin_lock(&inode->i_lock);
 
 	if (!ima_initialized)
 		goto out;
@@ -160,13 +128,23 @@ void ima_counts_get(struct file *file)
 		goto out;
 
 	if (mode & FMODE_WRITE) {
-		ima_read_write_check(TOMTOU, inode, dentry->d_name.name);
+		if (inode->i_readers)
+			send_tomtou = true;
 		goto out;
 	}
-	ima_read_write_check(OPEN_WRITERS, inode, dentry->d_name.name);
+
+	if (atomic_read(&inode->i_writecount) > 0)
+		send_writers = true;
 out:
 	ima_inc_counts(inode, file->f_mode);
-	mutex_unlock(&inode->i_mutex);
+	spin_unlock(&inode->i_lock);
+
+	if (send_tomtou)
+		ima_add_violation(inode, dentry->d_name.name, "invalid_pcr",
+				  "ToMToU");
+	if (send_writers)
+		ima_add_violation(inode, dentry->d_name.name, "invalid_pcr",
+				  "open_writers");
 }
 
 /*
@@ -175,25 +153,18 @@ out:
 static void ima_dec_counts(struct inode *inode, struct file *file)
 {
 	mode_t mode = file->f_mode;
-	bool dump = false;
 
-	BUG_ON(!mutex_is_locked(&inode->i_mutex));
+	assert_spin_locked(&inode->i_lock);
 
 	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 (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();
+		if (unlikely(inode->i_readers == 0) &&
+		    !ima_limit_imbalance(file)) {
+			printk(KERN_INFO "%s: open/free imbalance (r:%u)\n",
+			       __func__, inode->i_readers);
+			dump_stack();
+		} else {
+			inode->i_readers--;
+		}
 	}
 }
 
@@ -204,10 +175,10 @@ static void ima_check_last_writer(struct ima_iint_cache *iint,
 	mode_t mode = file->f_mode;
 
 	BUG_ON(!mutex_is_locked(&iint->mutex));
-	BUG_ON(!mutex_is_locked(&inode->i_mutex));
+	assert_spin_locked(&inode->i_lock);
 
 	if (mode & FMODE_WRITE &&
-	    inode->i_writers == 0 &&
+	    atomic_read(&inode->i_writecount) <= 0 &&
 	    iint->version != inode->i_version)
 		iint->flags &= ~IMA_MEASURED;
 }
@@ -216,12 +187,12 @@ static void ima_file_free_iint(struct ima_iint_cache *iint, struct inode *inode,
 			       struct file *file)
 {
 	mutex_lock(&iint->mutex);
-	mutex_lock(&inode->i_mutex);
+	spin_lock(&inode->i_lock);
 
 	ima_dec_counts(inode, file);
 	ima_check_last_writer(iint, inode, file);
 
-	mutex_unlock(&inode->i_mutex);
+	spin_unlock(&inode->i_lock);
 	mutex_unlock(&iint->mutex);
 
 	kref_put(&iint->refcount, iint_free);
@@ -229,11 +200,11 @@ static void ima_file_free_iint(struct ima_iint_cache *iint, struct inode *inode,
 
 static void ima_file_free_noiint(struct inode *inode, struct file *file)
 {
-	mutex_lock(&inode->i_mutex);
+	spin_lock(&inode->i_lock);
 
 	ima_dec_counts(inode, file);
 
-	mutex_unlock(&inode->i_mutex);
+	spin_unlock(&inode->i_lock);
 }
 
 /**
@@ -241,7 +212,7 @@ static void ima_file_free_noiint(struct inode *inode, struct file *file)
  * @file: pointer to file structure being freed
  *
  * Flag files that changed, based on i_version;
- * and decrement the i_readers/i_writers.
+ * and decrement the i_readers.
  */
 void ima_file_free(struct file *file)
 {

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

[Dave Chinner]

On Tue, Oct 19, 2010 at 06:58:39PM -0400, Eric Paris wrote:
> @@ -36,12 +63,11 @@ struct ima_iint_cache *ima_iint_find_get(struct inode *inode)
>  	struct ima_iint_cache *iint;
>  
>  	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.

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com

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

[Linus Torvalds]

On Tue, Oct 19, 2010 at 3:58 PM, Eric Paris <eparis@redhat.com> wrote:
>
> 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

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

[Al Viro]

On Tue, Oct 19, 2010 at 06:58:33PM -0400, Eric Paris wrote:
> 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...

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

[Peter Zijlstra]

On Wed, 2010-10-20 at 10:17 +1100, Dave Chinner wrote:
> On Tue, Oct 19, 2010 at 06:58:39PM -0400, Eric Paris wrote:
> > @@ -36,12 +63,11 @@ struct ima_iint_cache *ima_iint_find_get(struct inode *inode)
> >  	struct ima_iint_cache *iint;
> >  
> >  	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;
  

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

[Dave Chinner]

On Wed, Oct 20, 2010 at 01:31:09PM +0200, Peter Zijlstra wrote:
> On Wed, 2010-10-20 at 10:17 +1100, Dave Chinner wrote:
> > On Tue, Oct 19, 2010 at 06:58:39PM -0400, Eric Paris wrote:
> > > @@ -36,12 +63,11 @@ struct ima_iint_cache *ima_iint_find_get(struct inode *inode)
> > >  	struct ima_iint_cache *iint;
> > >  
> > >  	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;

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.
-- 
Dave Chinner
david@fromorbit.com

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

[Linus Torvalds]

On Wed, Oct 20, 2010 at 3:05 PM, Dave Chinner <david@fromorbit.com> wrote:
>
> /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

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

[Trond Myklebust]

On Wed, 2010-10-20 at 15:22 -0700, Linus Torvalds wrote:
> On Wed, Oct 20, 2010 at 3:05 PM, Dave Chinner <david@fromorbit.com> wrote:
> >
> > /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

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

Cheers
   Trond

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

[Linus Torvalds]

On Wed, Oct 20, 2010 at 3:47 PM, Trond Myklebust
<Trond.Myklebust@netapp.com> wrote:
>
> 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

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

[Dave Chinner]

On Wed, Oct 20, 2010 at 05:58:19PM -0700, Linus Torvalds wrote:
> On Wed, Oct 20, 2010 at 3:47 PM, Trond Myklebust
> <Trond.Myklebust@netapp.com> wrote:
> >
> > 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.

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.
-- 
Dave Chinner
david@fromorbit.com

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

[Eric Paris]

On Tue, 2010-10-19 at 17:25 -0700, Linus Torvalds wrote:
> On Tue, Oct 19, 2010 at 3:58 PM, Eric Paris <eparis@redhat.com> wrote:
> >
> > 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.

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

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

[Mimi Zohar]

On Fri, 2010-10-22 at 23:01 -0400, Eric Paris wrote:
> On Tue, 2010-10-19 at 17:25 -0700, Linus Torvalds wrote:
> > On Tue, Oct 19, 2010 at 3:58 PM, Eric Paris <eparis@redhat.com> wrote:
> > >
> > > 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.
> 
> 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

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!

Signed-off-by: Mimi Zohar <zohar@us.ibm.com>

thanks,

Mimi