ext3 [linux-2.6.2.]: accessing already freed inodes when under memory pressure

Hi all,

recently we ran into a problem found during our 2.6. test activities on s390 architecture. The problem occured running a glibc build on Linux 2.6.2. running in a z/VM virtual machine with 6 processors on a z990 Server (6Processor SMP, 64-bit, big endian).
We were able to identify ext3 as the cause of the problem with the following debugging patch:
diff -ruN linux-2.6.2/fs/ext3/super.c linux-2.6.2+bug_statement/fs/ext3/super.c
--- linux-2.6.2/fs/ext3/super.c 2004-02-19 12:52:01.000000000 +0100 +++ linux-2.6.2+bug_statement/fs/ext3/super.c   2004-02-19 12:51:35.000000000 +0100
@@ -449,6 +449,7 @@

 static void ext3_destroy_inode(struct inode *inode)
 {
+       BUG_ON (!list_empty(&EXT3_I(inode)->i_orphan)); kmem_cache_free(ext3_inode_cachep, EXT3_I(inode));
 }

The output of the BUG_ON statement shows, that prune_icache [fs/inode.c] picks an inode with i_count == 0 and calls (via dispose_list) clear_inode() and destroy_inode(). Because the inode is still in use by ext3 internally, ext3 later on reads from or writes to freed memory causing random behavior of the system. I think, this BUG_ON should go into the vanilla kernel to prevent data corruption.

Above was so far only reproducable in rare conditions when the system was under heavy memory pressure. Therefore I continued to debug this further:
The problem seemed to be related to reference counting of inodes. Therefore I added a debugging patch to iput_final() [fs/inode.c], that checks if an inode that is being dropped is still in the ext3 orphan list. This situation is quite easy to reproduce, and has shown one example path were this happens:
A user process calls sys_unlink() [fs/namei.c], which increments i_count, calls vfs_unlink [fs/namei.c] and afterwards calls iput(). vfs_unlink [fs/namei.c] works with the dentry, calls i_op->unlink() (in this case ext3_unlink) and returns.
ext3_unlink [FILE] decrements i_nlink and adds the inode to the s_orphan list before returning.
After sys_unlink() has completed, the inode is still referenced by ext3 while i_count has the same value like before, which triggers the problem in case prune_icache would now choose this inode to be freed.

Possible ways to fix above problem is change reference counting for inodes or make the prune_icache function aware of the internal reference to the inode (preferably without knowing about the internal data structures of the filesystem which would be a layering violation). The patch below does take the 2nd approach:
- adds additional super_operation s_op->inode_busy() allowing VFS to query if an inode is still internally referenced by the fs.
- adds ext3_inode_busy() to ext3 that checks if he inode is still internally referenced
- changes prune_icache to query inode_busy() in case this s_op is implemented by the individual fs

Patch fixing the problem:

diff -ruN linux-2.6.2/fs/ext3/super.c linux-2.6.2+ext3fix/fs/ext3/super.c
@@ -453,6 +453,14 @@

        kmem_cache_free(ext3_inode_cachep, EXT3_I(inode));
 }

+static int ext3_inode_busy(struct inode *inode)
+{
+       if (!list_empty(&EXT3_I(inode)->i_orphan))
+               return 1;
+       else
+               return 0;
+}
+
 static void init_once(void * foo, kmem_cache_t * cachep, unsigned long flags) {
        struct ext3_inode_info *ei = (struct ext3_inode_info *) foo; @@ -510,6 +518,7 @@
 static struct super_operations ext3_sops = {
        .alloc_inode    = ext3_alloc_inode,
        .destroy_inode  = ext3_destroy_inode,
+       .inode_busy     = ext3_inode_busy,
        .read_inode     = ext3_read_inode,
        .write_inode    = ext3_write_inode,
        .dirty_inode    = ext3_dirty_inode,

diff -ruN linux-2.6.2/fs/inode.c linux-2.6.2+ext3fix/fs/inode.c
@@ -391,6 +391,9 @@

                return 0;
        if (inode->i_data.nrpages)
                return 0;
+       if (inode->i_sb->s_op->inode_busy
+           && inode->i_sb->s_op->inode_busy(inode))
+               return 0;
        return 1;
 }

@@ -424,7 +427,9 @@

                inode = list_entry(inode_unused.prev, struct inode, i_list);

-               if (inode->i_state || atomic_read(&inode->i_count)) {
+               if (inode->i_state || atomic_read(&inode->i_count)

+                   || (inode->i_sb->s_op->inode_busy
+                        && (inode->i_sb->s_op->inode_busy(inode)))) { list_move(&inode->i_list, &inode_unused); continue;
                }
diff -ruN linux-2.6.2/include/linux/fs.h linux-2.6.2+ext3fix/include/linux/fs.h
--- linux-2.6.2/include/linux/fs.h      2004-02-19 12:46:35.000000000 +0100 +++ linux-2.6.2+ext3fix/include/linux/fs.h      2004-02-18 18:45:15.000000000 +0100
@@ -866,6 +866,7 @@
 struct super_operations {
        struct inode *(*alloc_inode)(struct super_block *sb); void (*destroy_inode)(struct inode *);
+       int  (*inode_busy)(struct inode *);

        void (*read_inode) (struct inode *);

-
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

Thanks Carsten,

Ouch. ext3 should definitely keep the inode count elevated while it is on the s_orphan list, and do the final iput() on it when removing it from the orphan list.

I really think this is wrong. The bug is clearly in ext3 reference count handling, and I'd much rather just have ext3 fix its reference count than add a totally new interface for ext3 breakage.

Andrew, Stephen? Comments?

Linus

Hi,

An orphan is either a file being truncated (if the truncate spans multiple transactions), or a file that's deleted but still open.

In the latter case, we need to preserve the inode on the on-disk orphan list until the final user closes it. The final remove-from-orphan-list really has to happen in ext3_inode_delete, which happens after the last iput(); so if we held an extra refcount ourselves, the inode would never get deleted at all.

At the end of ext3_truncate(), we do:

	if (inode->i_nlink)
		ext3_orphan_del(handle, inode);

so the only time we'll be left with the inode on the orphan list after the truncate is on a true final-unlink, not on a [f]truncate(). If it's unlink, we rely on the delete_inode() processing to call us and remove the orphan reference before the inode is destroyed.

I can't immediately see why this should be wrong --- delete_inode() is supposed to give us this chance to cleanup before the struct inode actually gets nuked. The orphan list entry should persist only as long as inode->i_count is raised, and if it's raised, there should be no risk of the struct getting reused.

I may be missing some background from previous emails --- is this just a hypothetical race, or have we actually seen this mechanism breaking down in practice?

Cheers,
Stephen

Am Donnerstag 19 Februar 2004 19:49 schrieb Andrew Morton:

So far not, all I know is the symptom and a probable cause may be the sys_unlink path. I will try to dig that direction with another debugging patch tomorrow.

We hold ->i_sem *on* *the* *inode*. And yes, unlink does grab it both on parent and child.

Am Donnerstag 19 Februar 2004 21:26 schrieb
[email protected]:

True. The problem is, that both are released before the inode is been removed from the s_orphan list.

I tried the following *dirty* debugging patch that triggers in iput_final() exactly when i_count is lowered to zero while the orphan list entry does still persist.
I have not been able to startup my system, panic output shows the sys_unlink() path -like fully described in the initial mail starting this thread- causes running into the panic()

diff -ruN linux-2.6.3/fs/inode.c linux-2.6.3+debug/fs/inode.c
@@ -1058,6 +1058,96 @@
 		generic_forget_inode(inode);
 }
 
+struct ext3_inode_info {
+        __u32   i_data[15];
+        __u32   i_flags;
+#ifdef EXT3_FRAGMENTS
+        __u32   i_faddr;
+        __u8    i_frag_no;
+        __u8    i_frag_size;
+#endif
+        __u32   i_file_acl;
+        __u32   i_dir_acl;
+        __u32   i_dtime;
+
+        /*
+         * i_block_group is the number of the block group which contains
+         * this file's inode.  Constant across the lifetime of the inode,
+         * it is ued for making block allocation decisions - we try to
+         * place a file's data blocks near its inode block, and new inodes
+         * near to their parent directory's inode.
+         */
+        __u32   i_block_group;
+        __u32   i_state;                /* Dynamic state flags for ext3 */
+
+        /*
+         * i_next_alloc_block is the logical (file-relative) number of the
+         * most-recently-allocated block in this file.  Yes, it is misnamed.
+         * We use this for detecting linearly ascending allocation requests.
+         */
+        __u32   i_next_alloc_block;
+
+        /*
+         * i_next_alloc_goal is the *physical* companion to 

i_next_alloc_block.
+ * it the the physical block number of the block which was
most-recently
+ * allocated to this file. This give us the goal (target) for the
next
+ * allocation when we detect linearly ascending requests.
+ */
+ __u32 i_next_alloc_goal;
+#ifdef EXT3_PREALLOCATE

+        __u32   i_prealloc_block;
+        __u32   i_prealloc_count;

+#endif
+ __u32 i_dir_start_lookup;
+#ifdef CONFIG_EXT3_FS_XATTR
+ /*

+         * Extended attributes can be read independently of the main file
+         * data. Taking i_sem even when reading would cause contention
+         * between readers of EAs and writers of regular file data, so
+         * instead we synchronize on xattr_sem when reading or changing
+         * EAs.
+         */
+        struct rw_semaphore xattr_sem;
+#endif
+#ifdef CONFIG_EXT3_FS_POSIX_ACL
+        struct posix_acl        *i_acl;
+        struct posix_acl        *i_default_acl;

+#endif
+
+ struct list_head i_orphan; /* unlinked but open inodes */
+
+ /*

+         * i_disksize keeps track of what the inode size is ON DISK, not
+         * in memory.  During truncate, i_size is set to the new size by
+         * the VFS prior to calling ext3_truncate(), but the filesystem won't
+         * set i_disksize to 0 until the truncate is actually under way.
+         *
+         * The intent is that i_disksize always represents the blocks which
+         * are used by this file.  This allows recovery to restart truncate
+         * on orphans if we crash during truncate.  We actually write 
i_disksize
+         * into the on-disk inode when writing inodes out, instead of i_size.
+         *
+         * The only time when i_disksize and i_size may be different is when
+         * a truncate is in progress.  The only things which change 

i_disksize
+ * are ext3_get_block (growth) and ext3_truncate (shrinkth).
+ */
+ loff_t i_disksize;
+
+ /*

+         * truncate_sem is for serialising ext3_truncate() against
+         * ext3_getblock().  In the 2.4 ext2 design, great chunks of inode's
+         * data tree are chopped off during truncate. We can't do that in
+         * ext3 because whenever we perform intermediate commits during
+         * truncate, the inode and all the metadata blocks *must* be in a
+         * consistent state which allows truncation of the orphans to restart
+         * during recovery.  Hence we must fix the get_block-vs-truncate race
+         * by other means, so we have truncate_sem.
+         */

+ struct semaphore truncate_sem;
+ struct inode vfs_inode;
+};
+
+
/*
* Called when we're dropping the last reference
* to an inode.
@@ -1073,6 +1163,15 @@
{
struct super_operations *op = inode->i_sb->s_op; void (*drop)(struct inode *) = generic_drop_inode;
+ struct ext3_inode_info* ext3_i;
+
+ if (!strcmp (inode->i_sb->s_type->name, "ext3")) {
+ // this is an ext3 inode. check if it is still orphan
+ ext3_i = container_of (inode, struct ext3_inode_info, vfs_inode);
+ if (!list_empty (&ext3_i->i_orphan)) {
+ panic ("iput_final: found inode in ext3's orphan list, am asked to drop it
\n");
+ }
+ }

if (op && op->drop_inode)
drop = op->drop_inode;

That patch isn't right. Note how we go on to generic_delete_inode() which then does the orphan_del().

The below patch should detect us adding orphan inodes to inode_unused.
Could you see if this triggers? It doesn't for me, of course :(

Also, I have gone through and verified that all modifications of inode->i_nlink are happening under inode->i_sem, so scrub that theory.

I'm a bit suspicious of the code in __sync_single_inode(), where it decides to dump the inode on inode_unused. Maybe it's not checking all the right things. Still, that doesn't explain why the inode gets through the prune_icache checks as well.

Both patches are here:

diff -puN fs/inode.c~ext3-dirty-debug-patch fs/inode.c
@@ -20,6 +20,7 @@
 #include <linux/security.h>
 #include <linux/pagemap.h>
 #include <linux/cdev.h>
+#include <linux/ext3_fs_i.h>
 
 /*
  * This is needed for the following functions:

@@ -1019,6 +1020,14 @@ static void generic_forget_inode(struct 
 
 	if (!hlist_unhashed(&inode->i_hash)) {
 		if (!(inode->i_state & (I_DIRTY|I_LOCK))) {
+			if (!strcmp(inode->i_sb->s_type->name, "ext3")) {
+				struct ext3_inode_info *ext3_i;
+				ext3_i = container_of(inode,
+						struct ext3_inode_info,
+						vfs_inode);
+				if (!list_empty(&ext3_i->i_orphan))
+					WARN_ON(1);
+			}
 			list_del(&inode->i_list);
 			list_add(&inode->i_list, &inode_unused);
 		}

@@ -1066,7 +1075,7 @@ static void generic_drop_inode(struct in
  * held, and the drop function is supposed to release
  * the lock!
  */
-static inline void iput_final(struct inode *inode)
+static void iput_final(struct inode *inode)
 {
 	struct super_operations *op = inode->i_sb->s_op;
 	void (*drop)(struct inode *) = generic_drop_inode;

diff -puN fs/fs-writeback.c~ext3-dirty-debug-patch fs/fs-writeback.c
@@ -22,6 +22,7 @@
 #include <linux/blkdev.h>
 #include <linux/backing-dev.h>
 #include <linux/buffer_head.h>
+#include <linux/ext3_fs_i.h>
 
 extern struct super_block *blockdev_superblock;
 

@@ -187,6 +188,14 @@ __sync_single_inode(struct inode *inode,
 			list_move(&inode->i_list, &inode_in_use);
 		} else {
 			mapping->dirtied_when = 0;
+			if (!strcmp(inode->i_sb->s_type->name, "ext3")) {
+				struct ext3_inode_info *ext3_i;
+				ext3_i = container_of(inode,
+						struct ext3_inode_info,
+						vfs_inode);
+				if (!list_empty(&ext3_i->i_orphan))
+					WARN_ON(1);
+			}
 			list_move(&inode->i_list, &inode_unused);
 		}
 	}

_

 fs/ext3/ialloc.c |    0 
 fs/ext3/inode.c  |    0 
 fs/ext3/namei.c  |   49 +++++++++++++++++++++++++++++++++++++++++++++++--
 fs/ext3/super.c  |    0 
 4 files changed, 47 insertions(+), 2 deletions(-)

diff -puN fs/ext3/ialloc.c~ext3-i_nlink-check fs/ext3/ialloc.c diff -puN fs/ext3/inode.c~ext3-i_nlink-check fs/ext3/inode.c

diff -puN fs/ext3/super.c~ext3-i_nlink-check fs/ext3/super.c

_

Am Donnerstag 19 Februar 2004 17:53 schrieb Linus Torvalds:

I do agree that the final patch fixing the problem should not add a new interface. This one clearly should not go into vanilla, but consider adding the BUG_ON statement at least for the time being until there is a real fix. diff -ruN linux-2.6.2/fs/ext3/super.c linux-2.6.2+bug_statement/fs/ext3/super.c
--- linux-2.6.2/fs/ext3/super.c 2004-02-19 12:52:01.000000000 +0100
+++ linux-2.6.2+bug_statement/fs/ext3/super.c 2004-02-19 12:51:35.000000000
+0100
@@ -449,6 +449,7 @@

static void ext3_destroy_inode(struct inode *inode) {

+       BUG_ON (!list_empty(&EXT3_I(inode)->i_orphan));
        kmem_cache_free(ext3_inode_cachep, EXT3_I(inode));

}

atomic_dec_and_lock() decrements i_count, so this warning will be triggered by people calling iput() with an orphan inode which has a refcount of 2,
not of 1. Please change the

	if (atomic_read(&inode->i_count) == 1)

to

	if (atomic_read(&inode->i_count) == 0)

Thanks.