[PATCH 0/4] ext[34]: Fix deadlock between truncate and get_block()

[PATCH 0/4] ext[34]: Fix deadlock between truncate and get_block()

[Jan Kara]

  Hello,

  below come patches that fix lockdep annotations in JBD / JBD2 so that we are
properly warned about possibly deadlocks caused by a transaction being
restarted. Further follow patches that fix a possible deadlock between truncate
and get_blocks() in ext3/ext4 which Ted spotted. I'm quite confident in the ext3
fix but the ext4 fix definitely needs a serious review because there are
cosiderably more places working with the extent tree. I *think* ext4 patch is
fine as I argue in the changelog and I went through all places acquiring
i_data_sem but I might have missed some interaction / callsite...

									Honza

[PATCH 1/4] jbd: Annotate transaction start also for journal_restart()

[Jan Kara]

lockdep annotation for a transaction start has been at the end of
journal_start(). But a transaction is also started from journal_restart(). Move
the lockdep annotation to start_this_handle() which covers both cases.

Signed-off-by: Jan Kara <jack@suse.cz>
---
 fs/jbd/transaction.c |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/fs/jbd/transaction.c b/fs/jbd/transaction.c
index 833c167..006f9ad 100644
--- a/fs/jbd/transaction.c
+++ b/fs/jbd/transaction.c
@@ -229,6 +229,8 @@ repeat_locked:
 		  __log_space_left(journal));
 	spin_unlock(&transaction->t_handle_lock);
 	spin_unlock(&journal->j_state_lock);
+
+	lock_map_acquire(&handle->h_lockdep_map);
 out:
 	if (unlikely(new_transaction))		/* It's usually NULL */
 		kfree(new_transaction);
@@ -293,9 +295,6 @@ handle_t *journal_start(journal_t *journal, int nblocks)
 		handle = ERR_PTR(err);
 		goto out;
 	}
-
-	lock_map_acquire(&handle->h_lockdep_map);

[PATCH 2/4] ext3: Fix possible deadlock between ext3_truncate() and ext3_get_blocks()

[Jan Kara]

During truncate we are sometimes forced to start a new transaction as the
amount of blocks to be journaled is both quite large and hard to predict. So
far we restarted a transaction while holding truncate_mutex and that violates
lock ordering because truncate_mutex ranks below transaction start (and it
can lead to a real deadlock with ext3_get_blocks() allocating new blocks
from ext3_writepage()).

Luckily, the problem is easy to fix: We just drop the truncate_mutex before
restarting the transaction and acquire it afterwards. We are safe to do this as
by the time ext3_truncate() is called, all the page cache for the truncated
part of the file is dropped and so writepage() cannot come and allocate new
blocks in the part of the file we are truncating. The rest of writers is
stopped by us holding i_mutex.

Signed-off-by: Jan Kara <jack@suse.cz>
---
 fs/ext3/inode.c |   19 +++++++++++++++----
 1 files changed, 15 insertions(+), 4 deletions(-)

diff --git a/fs/ext3/inode.c b/fs/ext3/inode.c
index b49908a..eb0b4e0 100644
--- a/fs/ext3/inode.c
+++ b/fs/ext3/inode.c
@@ -172,10 +172,21 @@ static int try_to_extend_transaction(handle_t *handle, struct inode *inode)
  * so before we call here everything must be consistently dirtied against
  * this transaction.
  */
-static int ext3_journal_test_restart(handle_t *handle, struct inode *inode)
+static int truncate_restart_transaction(handle_t *handle, struct inode *inode)
 {
+	int ret;
+
 	jbd_debug(2, "restarting handle %p\n", handle);
-	return ext3_journal_restart(handle, blocks_for_truncate(inode));
+	/*
+	 * Drop truncate_mutex to avoid deadlock with ext3_get_blocks_handle
+	 * At this moment, get_block can be called only for blocks inside
+	 * i_size since page cache has been already dropped and writes are
+	 * blocked by i_mutex. So we can safely drop the truncate_mutex.
+	 */
+	mutex_unlock(&EXT3_I(inode)->truncate_mutex);
+	ret = ext3_journal_restart(handle, blocks_for_truncate(inode));
+	mutex_lock(&EXT3_I(inode)->truncate_mutex);
+	return ret;
 }
 
 /*
@@ -2072,7 +2083,7 @@ static void ext3_clear_blocks(handle_t *handle, struct inode *inode,
 			ext3_journal_dirty_metadata(handle, bh);
 		}
 		ext3_mark_inode_dirty(handle, inode);
-		ext3_journal_test_restart(handle, inode);
+		truncate_restart_transaction(handle, inode);
 		if (bh) {
 			BUFFER_TRACE(bh, "retaking write access");
 			ext3_journal_get_write_access(handle, bh);
@@ -2282,7 +2293,7 @@ static void ext3_free_branches(handle_t *handle, struct inode *inode,
 				return;
 			if (try_to_extend_transaction(handle, inode)) {
 				ext3_mark_inode_dirty(handle, inode);
-				ext3_journal_test_restart(handle, inode);
+				truncate_restart_transaction(handle, inode);
 			}
 
 			ext3_free_blocks(handle, inode, nr, 1);
-- 
1.6.0.2

Re: [PATCH 2/4] ext3: Fix possible deadlock between ext3_truncate() and ext3_get_blocks()

[Andrew Morton]

On Fri, 14 Aug 2009 14:26:10 +0200
Jan Kara <jack@suse.cz> wrote:

> During truncate we are sometimes forced to start a new transaction as the
> amount of blocks to be journaled is both quite large and hard to predict. So
> far we restarted a transaction while holding truncate_mutex and that violates
> lock ordering because truncate_mutex ranks below transaction start (and it
> can lead to a real deadlock with ext3_get_blocks() allocating new blocks
> from ext3_writepage()).
> 
> Luckily, the problem is easy to fix: We just drop the truncate_mutex before
> restarting the transaction and acquire it afterwards. We are safe to do this as
> by the time ext3_truncate() is called, all the page cache for the truncated
> part of the file is dropped and so writepage() cannot come and allocate new
> blocks in the part of the file we are truncating. The rest of writers is
> stopped by us holding i_mutex.

For ext2 we have the comment:

	/*
	 * truncate_mutex is for serialising ext2_truncate() against
	 * ext2_getblock().  It also protects the internals of the inode's
	 * reservation data structures: ext2_reserve_window and
	 * ext2_reserve_window_node.
	 */

does truncate_mutex also protect ext3's reservation data?  If so, is
that impacted by this patch?

Re: [PATCH 2/4] ext3: Fix possible deadlock between ext3_truncate() and ext3_get_blocks()

[Jan Kara]

[-- Attachment #1: Type: text/plain, Size: 2118 bytes --]

On Fri 14-08-09 16:41:05, Andrew Morton wrote:
> On Fri, 14 Aug 2009 14:26:10 +0200
> Jan Kara <jack@suse.cz> wrote:
> 
> > During truncate we are sometimes forced to start a new transaction as the
> > amount of blocks to be journaled is both quite large and hard to predict. So
> > far we restarted a transaction while holding truncate_mutex and that violates
> > lock ordering because truncate_mutex ranks below transaction start (and it
> > can lead to a real deadlock with ext3_get_blocks() allocating new blocks
> > from ext3_writepage()).
> > 
> > Luckily, the problem is easy to fix: We just drop the truncate_mutex before
> > restarting the transaction and acquire it afterwards. We are safe to do this as
> > by the time ext3_truncate() is called, all the page cache for the truncated
> > part of the file is dropped and so writepage() cannot come and allocate new
> > blocks in the part of the file we are truncating. The rest of writers is
> > stopped by us holding i_mutex.
> 
> For ext2 we have the comment:
> 
> 	/*
> 	 * truncate_mutex is for serialising ext2_truncate() against
> 	 * ext2_getblock().  It also protects the internals of the inode's
> 	 * reservation data structures: ext2_reserve_window and
> 	 * ext2_reserve_window_node.
> 	 */
> 
> does truncate_mutex also protect ext3's reservation data?  If so, is
> that impacted by this patch?
  That's a good question: ext3 seems to use truncate_mutex to guard
reservation internals as well. Currently, truncate calls
ext3_discard_reservation() in the end of truncate. That is slightly
suboptimal when we can drop truncate_mutex during truncate as that can lead
to allocation from reservation window which is not well placed wrt the new
file end. Otherwise I don't think there's any issue since reservation is
just an interval of blocks we'd like to allocate from so it's not bound to
blocks allocated to the inode in any way.
  I'll move ext3_discard_reservation() to the beginning of the truncate
to fix the above issue. Thanks for the comment. Attached is a new version
of the patch.

								Honza
-- 
Jan Kara <jack@suse.cz>
SUSE Labs, CR

[-- Attachment #2: 0001-ext3-Fix-possible-deadlock-between-ext3_truncate.patch --]
[-- Type: text/x-patch, Size: 3544 bytes --]

>From fad69f21486f4b2d78444acc321803bdb571e9d7 Mon Sep 17 00:00:00 2001
From: Jan Kara <jack@suse.cz>
Date: Tue, 11 Aug 2009 19:06:10 +0200
Subject: [PATCH] ext3: Fix possible deadlock between ext3_truncate() and ext3_get_blocks()

During truncate we are sometimes forced to start a new transaction as the
amount of blocks to be journaled is both quite large and hard to predict. So
far we restarted a transaction while holding truncate_mutex and that violates
lock ordering because truncate_mutex ranks below transaction start (and it
can lead to a real deadlock with ext3_get_blocks() allocating new blocks
from ext3_writepage()).

Luckily, the problem is easy to fix: We just drop the truncate_mutex before
restarting the transaction and acquire it afterwards. We are safe to do this as
by the time ext3_truncate() is called, all the page cache for the truncated
part of the file is dropped and so writepage() cannot come and allocate new
blocks in the part of the file we are truncating. The rest of writers is
stopped by us holding i_mutex. We also move discarding of a reservation window
to the beginning of truncate so that we don't use it when an allocation happens
while we have dropped truncate_mutex during the truncate.

Signed-off-by: Jan Kara <jack@suse.cz>
---
 fs/ext3/inode.c |   23 +++++++++++++++++------
 1 files changed, 17 insertions(+), 6 deletions(-)

diff --git a/fs/ext3/inode.c b/fs/ext3/inode.c
index b49908a..f591e58 100644
--- a/fs/ext3/inode.c
+++ b/fs/ext3/inode.c
@@ -172,10 +172,21 @@ static int try_to_extend_transaction(handle_t *handle, struct inode *inode)
  * so before we call here everything must be consistently dirtied against
  * this transaction.
  */
-static int ext3_journal_test_restart(handle_t *handle, struct inode *inode)
+static int truncate_restart_transaction(handle_t *handle, struct inode *inode)
 {
+	int ret;
+
 	jbd_debug(2, "restarting handle %p\n", handle);
-	return ext3_journal_restart(handle, blocks_for_truncate(inode));
+	/*
+	 * Drop truncate_mutex to avoid deadlock with ext3_get_blocks_handle
+	 * At this moment, get_block can be called only for blocks inside
+	 * i_size since page cache has been already dropped and writes are
+	 * blocked by i_mutex. So we can safely drop the truncate_mutex.
+	 */
+	mutex_unlock(&EXT3_I(inode)->truncate_mutex);
+	ret = ext3_journal_restart(handle, blocks_for_truncate(inode));
+	mutex_lock(&EXT3_I(inode)->truncate_mutex);
+	return ret;
 }
 
 /*
@@ -2072,7 +2083,7 @@ static void ext3_clear_blocks(handle_t *handle, struct inode *inode,
 			ext3_journal_dirty_metadata(handle, bh);
 		}
 		ext3_mark_inode_dirty(handle, inode);
-		ext3_journal_test_restart(handle, inode);
+		truncate_restart_transaction(handle, inode);
 		if (bh) {
 			BUFFER_TRACE(bh, "retaking write access");
 			ext3_journal_get_write_access(handle, bh);
@@ -2282,7 +2293,7 @@ static void ext3_free_branches(handle_t *handle, struct inode *inode,
 				return;
 			if (try_to_extend_transaction(handle, inode)) {
 				ext3_mark_inode_dirty(handle, inode);
-				ext3_journal_test_restart(handle, inode);
+				truncate_restart_transaction(handle, inode);
 			}
 
 			ext3_free_blocks(handle, inode, nr, 1);
@@ -2435,6 +2446,8 @@ void ext3_truncate(struct inode *inode)
 	 */
 	mutex_lock(&ei->truncate_mutex);
 
+	ext3_discard_reservation(inode);
+
 	if (n == 1) {		/* direct blocks */
 		ext3_free_data(handle, inode, NULL, i_data+offsets[0],
 			       i_data + EXT3_NDIR_BLOCKS);
@@ -2495,8 +2508,6 @@ do_indirects:
 		;
 	}
 
-	ext3_discard_reservation(inode);

[PATCH 3/4] jbd2: Annotate transaction start also for jbd2_journal_restart()

[Jan Kara]

lockdep annotation for a transaction start has been at the end of
jbd2_journal_start(). But a transaction is also started from
jbd2_journal_restart(). Move the lockdep annotation to start_this_handle()
which covers both cases.

Signed-off-by: Jan Kara <jack@suse.cz>
---
 fs/jbd2/transaction.c |    5 +++--
 1 files changed, 3 insertions(+), 2 deletions(-)

diff --git a/fs/jbd2/transaction.c b/fs/jbd2/transaction.c
index 6213ac7..8b6a692 100644
--- a/fs/jbd2/transaction.c
+++ b/fs/jbd2/transaction.c
@@ -238,6 +238,8 @@ repeat_locked:
 		  __jbd2_log_space_left(journal));
 	spin_unlock(&transaction->t_handle_lock);
 	spin_unlock(&journal->j_state_lock);
+
+	lock_map_acquire(&handle->h_lockdep_map);
 out:
 	if (unlikely(new_transaction))		/* It's usually NULL */
 		kfree(new_transaction);
@@ -303,8 +305,6 @@ handle_t *jbd2_journal_start(journal_t *journal, int nblocks)
 		handle = ERR_PTR(err);
 		goto out;
 	}

Re: [PATCH 3/4] jbd2: Annotate transaction start also for jbd2_journal_restart()

[Theodore Tso]

On Fri, Aug 14, 2009 at 02:26:11PM +0200, Jan Kara wrote:
> lockdep annotation for a transaction start has been at the end of
> jbd2_journal_start(). But a transaction is also started from
> jbd2_journal_restart(). Move the lockdep annotation to start_this_handle()
> which covers both cases.
> 
> Signed-off-by: Jan Kara <jack@suse.cz>

Added to the ext4 patch queue, thanks!!!

				- Ted

[PATCH 4/4] ext4: Fix possible deadlock between ext4_truncate() and ext4_get_blocks()

[Jan Kara]

During truncate we are sometimes forced to start a new transaction as the
amount of blocks to be journaled is both quite large and hard to predict. So
far we restarted a transaction while holding i_data_sem and that violates lock
ordering because i_data_sem ranks below a transaction start (and it can lead to
a real deadlock with ext4_get_blocks() mapping blocks in some page while having
a transaction open).

We fix the problem by dropping the i_data_sem before restarting the transaction
and acquire it afterwards. It's slightly subtle that this works:
1) by the time ext4_truncate() is called, all the page cache for the truncated part
of the file is dropped so get_block() should not be called on it (we only have to
invalidate extent cache after we reacquire i_data_sem because some extent from
not-truncated part could extend also into the part we are going to truncate).
2) writes, migrate or defrag hold i_mutex so they are stopped for all the time
of the truncate.

Thig bug has been found and analyzed by Ted Tytso <tytso@mit.edu>.

Signed-off-by: Jan Kara <jack@suse.cz>
---
 fs/ext4/ext4.h    |    1 +
 fs/ext4/extents.c |   15 ++++++++++++---
 fs/ext4/inode.c   |   23 +++++++++++++++++++----
 3 files changed, 32 insertions(+), 7 deletions(-)

diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
index 9714db3..f7b2ed7 100644
--- a/fs/ext4/ext4.h
+++ b/fs/ext4/ext4.h
@@ -1367,6 +1367,7 @@ extern int ext4_change_inode_journal_flag(struct inode *, int);
 extern int ext4_get_inode_loc(struct inode *, struct ext4_iloc *);
 extern int ext4_can_truncate(struct inode *inode);
 extern void ext4_truncate(struct inode *);
+extern int ext4_truncate_restart_trans(handle_t *, struct inode *, int nblocks);
 extern void ext4_set_inode_flags(struct inode *);
 extern void ext4_get_inode_flags(struct ext4_inode_info *);
 extern int ext4_alloc_da_blocks(struct inode *inode);
diff --git a/fs/ext4/extents.c b/fs/ext4/extents.c
index 73ebfb4..9b48314 100644
--- a/fs/ext4/extents.c
+++ b/fs/ext4/extents.c
@@ -93,7 +93,9 @@ static void ext4_idx_store_pblock(struct ext4_extent_idx *ix, ext4_fsblk_t pb)
 	ix->ei_leaf_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) & 0xffff);
 }
 
-static int ext4_ext_journal_restart(handle_t *handle, int needed)
+static int ext4_ext_truncate_extend_restart(handle_t *handle,
+					    struct inode *inode,
+					    int needed)
 {
 	int err;
 
@@ -104,7 +106,14 @@ static int ext4_ext_journal_restart(handle_t *handle, int needed)
 	err = ext4_journal_extend(handle, needed);
 	if (err <= 0)
 		return err;
-	return ext4_journal_restart(handle, needed);
+	err = ext4_truncate_restart_trans(handle, inode, needed);
+	/*
+	 * We have dropped i_data_sem so someone might have cached again
+	 * an extent we are going to truncate.
+	 */
+	ext4_ext_invalidate_cache(inode);
+
+	return err;
 }
 
 /*
@@ -2138,7 +2147,7 @@ ext4_ext_rm_leaf(handle_t *handle, struct inode *inode,
 		}
 		credits += 2 * EXT4_QUOTA_TRANS_BLOCKS(inode->i_sb);
 
-		err = ext4_ext_journal_restart(handle, credits);
+		err = ext4_ext_truncate_extend_restart(handle, inode, credits);
 		if (err)
 			goto out;
 
diff --git a/fs/ext4/inode.c b/fs/ext4/inode.c
index f9c642b..04c5a35 100644
--- a/fs/ext4/inode.c
+++ b/fs/ext4/inode.c
@@ -192,11 +192,24 @@ static int try_to_extend_transaction(handle_t *handle, struct inode *inode)
  * so before we call here everything must be consistently dirtied against
  * this transaction.
  */
-static int ext4_journal_test_restart(handle_t *handle, struct inode *inode)
+ int ext4_truncate_restart_trans(handle_t *handle, struct inode *inode,
+				 int nblocks)
 {
+	int ret;
+
+	/*
+	 * Drop i_data_sem to avoid deadlock with ext4_get_blocks At this
+	 * moment, get_block can be called only for blocks inside i_size since
+	 * page cache has been already dropped and writes are blocked by
+	 * i_mutex. So we can safely drop the i_data_sem here.
+	 */
 	BUG_ON(EXT4_JOURNAL(inode) == NULL);
 	jbd_debug(2, "restarting handle %p\n", handle);
-	return ext4_journal_restart(handle, blocks_for_truncate(inode));
+	up_write(&EXT4_I(inode)->i_data_sem);
+	ret = ext4_journal_restart(handle, blocks_for_truncate(inode));
+	down_write(&EXT4_I(inode)->i_data_sem);
+
+	return ret;
 }
 
 /*
@@ -3659,7 +3672,8 @@ static void ext4_clear_blocks(handle_t *handle, struct inode *inode,
 			ext4_handle_dirty_metadata(handle, inode, bh);
 		}
 		ext4_mark_inode_dirty(handle, inode);
-		ext4_journal_test_restart(handle, inode);
+		ext4_truncate_restart_trans(handle, inode,
+					    blocks_for_truncate(inode));
 		if (bh) {
 			BUFFER_TRACE(bh, "retaking write access");
 			ext4_journal_get_write_access(handle, bh);
@@ -3870,7 +3884,8 @@ static void ext4_free_branches(handle_t *handle, struct inode *inode,
 				return;
 			if (try_to_extend_transaction(handle, inode)) {
 				ext4_mark_inode_dirty(handle, inode);
-				ext4_journal_test_restart(handle, inode);
+				ext4_truncate_restart_trans(handle, inode,
+					    blocks_for_truncate(inode));
 			}
 
 			ext4_free_blocks(handle, inode, nr, 1, 1);
-- 
1.6.0.2

Re: [PATCH 4/4] ext4: Fix possible deadlock between ext4_truncate() and ext4_get_blocks()

[Theodore Tso]

Added to the ext4 patch queue, thanks!!

I did fix the comments a little:

> Thig bug has been found and analyzed by Ted Tytso <tytso@mit.edu>.

The last name is "Ts'o".  :-)

					- Ted