[PATCH v4] xfs: Fix agi&agf ABBA deadlock when performing rename with RENAME_WHITEOUT flag

[PATCH v4] xfs: Fix agi&agf ABBA deadlock when performing rename with RENAME_WHITEOUT flag

[kaixuxia]

When performing rename operation with RENAME_WHITEOUT flag, we will
hold AGF lock to allocate or free extents in manipulating the dirents
firstly, and then doing the xfs_iunlink_remove() call last to hold
AGI lock to modify the tmpfile info, so we the lock order AGI->AGF.

The big problem here is that we have an ordering constraint on AGF
and AGI locking - inode allocation locks the AGI, then can allocate
a new extent for new inodes, locking the AGF after the AGI. Hence
the ordering that is imposed by other parts of the code is AGI before
AGF. So we get the ABBA agi&agf deadlock here.

Process A:
Call trace:
 ? __schedule+0x2bd/0x620
 schedule+0x33/0x90
 schedule_timeout+0x17d/0x290
 __down_common+0xef/0x125
 ? xfs_buf_find+0x215/0x6c0 [xfs]
 down+0x3b/0x50
 xfs_buf_lock+0x34/0xf0 [xfs]
 xfs_buf_find+0x215/0x6c0 [xfs]
 xfs_buf_get_map+0x37/0x230 [xfs]
 xfs_buf_read_map+0x29/0x190 [xfs]
 xfs_trans_read_buf_map+0x13d/0x520 [xfs]
 xfs_read_agf+0xa6/0x180 [xfs]
 ? schedule_timeout+0x17d/0x290
 xfs_alloc_read_agf+0x52/0x1f0 [xfs]
 xfs_alloc_fix_freelist+0x432/0x590 [xfs]
 ? down+0x3b/0x50
 ? xfs_buf_lock+0x34/0xf0 [xfs]
 ? xfs_buf_find+0x215/0x6c0 [xfs]
 xfs_alloc_vextent+0x301/0x6c0 [xfs]
 xfs_ialloc_ag_alloc+0x182/0x700 [xfs]
 ? _xfs_trans_bjoin+0x72/0xf0 [xfs]
 xfs_dialloc+0x116/0x290 [xfs]
 xfs_ialloc+0x6d/0x5e0 [xfs]
 ? xfs_log_reserve+0x165/0x280 [xfs]
 xfs_dir_ialloc+0x8c/0x240 [xfs]
 xfs_create+0x35a/0x610 [xfs]
 xfs_generic_create+0x1f1/0x2f0 [xfs]
 ...

Process B:
Call trace:
 ? __schedule+0x2bd/0x620
 ? xfs_bmapi_allocate+0x245/0x380 [xfs]
 schedule+0x33/0x90
 schedule_timeout+0x17d/0x290
 ? xfs_buf_find+0x1fd/0x6c0 [xfs]
 __down_common+0xef/0x125
 ? xfs_buf_get_map+0x37/0x230 [xfs]
 ? xfs_buf_find+0x215/0x6c0 [xfs]
 down+0x3b/0x50
 xfs_buf_lock+0x34/0xf0 [xfs]
 xfs_buf_find+0x215/0x6c0 [xfs]
 xfs_buf_get_map+0x37/0x230 [xfs]
 xfs_buf_read_map+0x29/0x190 [xfs]
 xfs_trans_read_buf_map+0x13d/0x520 [xfs]
 xfs_read_agi+0xa8/0x160 [xfs]
 xfs_iunlink_remove+0x6f/0x2a0 [xfs]
 ? current_time+0x46/0x80
 ? xfs_trans_ichgtime+0x39/0xb0 [xfs]
 xfs_rename+0x57a/0xae0 [xfs]
 xfs_vn_rename+0xe4/0x150 [xfs]
 ...

In this patch we move the xfs_iunlink_remove() call to
before acquiring the AGF lock to preserve correct AGI/AGF locking
order.

Signed-off-by: kaixuxia <kaixuxia@tencent.com>
---
 fs/xfs/xfs_inode.c | 76 ++++++++++++++++++++++++++++--------------------------
 1 file changed, 39 insertions(+), 37 deletions(-)

diff --git a/fs/xfs/xfs_inode.c b/fs/xfs/xfs_inode.c
index 6467d5e..fd0f5ec 100644
--- a/fs/xfs/xfs_inode.c
+++ b/fs/xfs/xfs_inode.c
@@ -3282,18 +3282,46 @@ struct xfs_iunlink {
 					spaceres);
 
 	/*
-	 * Set up the target.
+	 * Check for expected errors before we dirty the transaction
+	 * so we can return an error without a transaction abort.
 	 */
-	if (target_ip == NULL) {
+	if (!target_ip && !spaceres) {
 		/*
 		 * If there's no space reservation, check the entry will
 		 * fit before actually inserting it.
 		 */
-		if (!spaceres) {
-			error = xfs_dir_canenter(tp, target_dp, target_name);
-			if (error)
-				goto out_trans_cancel;
-		}
+		error = xfs_dir_canenter(tp, target_dp, target_name);
+		if (error)
+			goto out_trans_cancel;
+	} else if (target_ip && S_ISDIR(VFS_I(target_ip)->i_mode) &&
+		  (!(xfs_dir_isempty(target_ip)) ||
+		  (VFS_I(target_ip)->i_nlink > 2))) {
+		/*
+		 * If target exists and it's a directory, check that whether
+		 * it can be destroyed.
+		 */
+		error = -EEXIST;
+		goto out_trans_cancel;
+	}
+
+	/*
+	 * Directory entry creation below may acquire the AGF. Remove
+	 * the whiteout from the unlinked list first to preserve correct
+	 * AGI/AGF locking order. This dirties the transaction so failures
+	 * after this point will abort and log recovery will clean up the
+	 * mess.
+	 */
+	if (wip) {
+		ASSERT(VFS_I(wip)->i_nlink == 0);
+		error = xfs_iunlink_remove(tp, wip);
+		if (error)
+			goto out_trans_cancel;
+	}
+
+	/*
+	 * Set up the target.
+	 */
+	if (target_ip == NULL) {
 		/*
 		 * If target does not exist and the rename crosses
 		 * directories, adjust the target directory link count
@@ -3312,22 +3340,6 @@ struct xfs_iunlink {
 		}
 	} else { /* target_ip != NULL */
 		/*
-		 * If target exists and it's a directory, check that both
-		 * target and source are directories and that target can be
-		 * destroyed, or that neither is a directory.
-		 */
-		if (S_ISDIR(VFS_I(target_ip)->i_mode)) {
-			/*
-			 * Make sure target dir is empty.
-			 */
-			if (!(xfs_dir_isempty(target_ip)) ||
-			    (VFS_I(target_ip)->i_nlink > 2)) {
-				error = -EEXIST;
-				goto out_trans_cancel;
-			}
-		}
-
-		/*
 		 * Link the source inode under the target name.
 		 * If the source inode is a directory and we are moving
 		 * it across directories, its ".." entry will be
@@ -3419,25 +3431,15 @@ struct xfs_iunlink {
 
 	/*
 	 * For whiteouts, we need to bump the link count on the whiteout inode.
-	 * This means that failures all the way up to this point leave the inode
-	 * on the unlinked list and so cleanup is a simple matter of dropping
-	 * the remaining reference to it. If we fail here after bumping the link
-	 * count, we're shutting down the filesystem so we'll never see the
-	 * intermediate state on disk.
+	 * The whiteout inode has been removed from the unlinked list and log
+	 * recovery will clean up the mess for the failures up to this point.
+	 * After this point we have a real link, clear the tmpfile state flag
+	 * from the inode so it doesn't accidentally get misused in future.
 	 */
 	if (wip) {
 		ASSERT(VFS_I(wip)->i_nlink == 0);
 		xfs_bumplink(tp, wip);
-		error = xfs_iunlink_remove(tp, wip);
-		if (error)
-			goto out_trans_cancel;
 		xfs_trans_log_inode(tp, wip, XFS_ILOG_CORE);
-
-		/*
-		 * Now we have a real link, clear the "I'm a tmpfile" state
-		 * flag from the inode so it doesn't accidentally get misused in
-		 * future.
-		 */
 		VFS_I(wip)->i_state &= ~I_LINKABLE;
 	}
 
-- 
1.8.3.1

-- 
kaixuxia

Re: [PATCH v4] xfs: Fix agi&agf ABBA deadlock when performing rename with RENAME_WHITEOUT flag

[Dave Chinner]

On Thu, Aug 22, 2019 at 12:33:23PM +0800, kaixuxia wrote:
> When performing rename operation with RENAME_WHITEOUT flag, we will
> hold AGF lock to allocate or free extents in manipulating the dirents
> firstly, and then doing the xfs_iunlink_remove() call last to hold
> AGI lock to modify the tmpfile info, so we the lock order AGI->AGF.
> 
> The big problem here is that we have an ordering constraint on AGF
> and AGI locking - inode allocation locks the AGI, then can allocate
> a new extent for new inodes, locking the AGF after the AGI. Hence
> the ordering that is imposed by other parts of the code is AGI before
> AGF. So we get the ABBA agi&agf deadlock here.

'So we get an ABBA deadlock between the AGI and AGF here."

Can you also change the subject line to "AGI and AGF" instead of
"agi&agf" which isn't easily searchable? e.g. "xfs: fix ABBA
deadlock between AGI and AGF in rename()".

>  	/*
> -	 * Set up the target.
> +	 * Check for expected errors before we dirty the transaction
> +	 * so we can return an error without a transaction abort.
>  	 */
> -	if (target_ip == NULL) {
> +	if (!target_ip && !spaceres) {
>  		/*
>  		 * If there's no space reservation, check the entry will
>  		 * fit before actually inserting it.
>  		 */
> -		if (!spaceres) {
> -			error = xfs_dir_canenter(tp, target_dp, target_name);
> -			if (error)
> -				goto out_trans_cancel;
> -		}
> +		error = xfs_dir_canenter(tp, target_dp, target_name);
> +		if (error)
> +			goto out_trans_cancel;
> +	} else if (target_ip && S_ISDIR(VFS_I(target_ip)->i_mode) &&
> +		  (!(xfs_dir_isempty(target_ip)) ||
> +		  (VFS_I(target_ip)->i_nlink > 2))) {
> +		/*
> +		 * If target exists and it's a directory, check that whether
> +		 * it can be destroyed.
> +		 */
> +		error = -EEXIST;
> +		goto out_trans_cancel;
> +	}

I do think this would be better left separate if statements like
this:

	if (!target_ip) {
		/*
		 * If there's no space reservation, check the entry will
		 * fit before actually inserting it.
		 */
		if (!spaceres) {
			error = xfs_dir_canenter(tp, target_dp, target_name);
			if (error)
				goto out_trans_cancel;
		}
	} else {
		/*
		 * If target exists and it's a directory, check that whether
		 * it can be destroyed.
		 */
		if (S_ISDIR(VFS_I(target_ip)->i_mode) &&
		    (!(xfs_dir_isempty(target_ip)) ||
		    (VFS_I(target_ip)->i_nlink > 2))) {
			error = -EEXIST;
			goto out_trans_cancel;
		}
	}

I find this much easier to read and follow the logic, and we don't
really care if it takes a couple more lines of code to make the
comments and code flow more logically.

> @@ -3419,25 +3431,15 @@ struct xfs_iunlink {
>  
>  	/*
>  	 * For whiteouts, we need to bump the link count on the whiteout inode.

Shouldn't this line be removed as well?

> -	 * This means that failures all the way up to this point leave the inode
> -	 * on the unlinked list and so cleanup is a simple matter of dropping
> -	 * the remaining reference to it. If we fail here after bumping the link
> -	 * count, we're shutting down the filesystem so we'll never see the
> -	 * intermediate state on disk.
> +	 * The whiteout inode has been removed from the unlinked list and log
> +	 * recovery will clean up the mess for the failures up to this point.
> +	 * After this point we have a real link, clear the tmpfile state flag
> +	 * from the inode so it doesn't accidentally get misused in future.
>  	 */
>  	if (wip) {
>  		ASSERT(VFS_I(wip)->i_nlink == 0);
>  		xfs_bumplink(tp, wip);
> -		error = xfs_iunlink_remove(tp, wip);
> -		if (error)
> -			goto out_trans_cancel;
>  		xfs_trans_log_inode(tp, wip, XFS_ILOG_CORE);
> -
> -		/*
> -		 * Now we have a real link, clear the "I'm a tmpfile" state
> -		 * flag from the inode so it doesn't accidentally get misused in
> -		 * future.
> -		 */
>  		VFS_I(wip)->i_state &= ~I_LINKABLE;
>  	}

Why not move all this up into the same branch that removes the
whiteout from the unlinked list? Why separate this logic as none of
what is left here could cause a failure even if it is run earlier?

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com

Re: [PATCH v4] xfs: Fix agi&agf ABBA deadlock when performing rename with RENAME_WHITEOUT flag

[kaixuxia]

On 2019/8/22 13:01, Dave Chinner wrote:
> On Thu, Aug 22, 2019 at 12:33:23PM +0800, kaixuxia wrote:
>> When performing rename operation with RENAME_WHITEOUT flag, we will
>> hold AGF lock to allocate or free extents in manipulating the dirents
>> firstly, and then doing the xfs_iunlink_remove() call last to hold
>> AGI lock to modify the tmpfile info, so we the lock order AGI->AGF.
>>
>> The big problem here is that we have an ordering constraint on AGF
>> and AGI locking - inode allocation locks the AGI, then can allocate
>> a new extent for new inodes, locking the AGF after the AGI. Hence
>> the ordering that is imposed by other parts of the code is AGI before
>> AGF. So we get the ABBA agi&agf deadlock here.
> 
> 'So we get an ABBA deadlock between the AGI and AGF here."
> 
> Can you also change the subject line to "AGI and AGF" instead of
> "agi&agf" which isn't easily searchable? e.g. "xfs: fix ABBA
> deadlock between AGI and AGF in rename()".

OK , will follow it.
> 
>>  	/*
>> -	 * Set up the target.
>> +	 * Check for expected errors before we dirty the transaction
>> +	 * so we can return an error without a transaction abort.
>>  	 */
>> -	if (target_ip == NULL) {
>> +	if (!target_ip && !spaceres) {
>>  		/*
>>  		 * If there's no space reservation, check the entry will
>>  		 * fit before actually inserting it.
>>  		 */
>> -		if (!spaceres) {
>> -			error = xfs_dir_canenter(tp, target_dp, target_name);
>> -			if (error)
>> -				goto out_trans_cancel;
>> -		}
>> +		error = xfs_dir_canenter(tp, target_dp, target_name);
>> +		if (error)
>> +			goto out_trans_cancel;
>> +	} else if (target_ip && S_ISDIR(VFS_I(target_ip)->i_mode) &&
>> +		  (!(xfs_dir_isempty(target_ip)) ||
>> +		  (VFS_I(target_ip)->i_nlink > 2))) {
>> +		/*
>> +		 * If target exists and it's a directory, check that whether
>> +		 * it can be destroyed.
>> +		 */
>> +		error = -EEXIST;
>> +		goto out_trans_cancel;
>> +	}
> 
> I do think this would be better left separate if statements like
> this:
> 
> 	if (!target_ip) {
> 		/*
> 		 * If there's no space reservation, check the entry will
> 		 * fit before actually inserting it.
> 		 */
> 		if (!spaceres) {
> 			error = xfs_dir_canenter(tp, target_dp, target_name);
> 			if (error)
> 				goto out_trans_cancel;
> 		}
> 	} else {
> 		/*
> 		 * If target exists and it's a directory, check that whether
> 		 * it can be destroyed.
> 		 */
> 		if (S_ISDIR(VFS_I(target_ip)->i_mode) &&
> 		    (!(xfs_dir_isempty(target_ip)) ||
> 		    (VFS_I(target_ip)->i_nlink > 2))) {
> 			error = -EEXIST;
> 			goto out_trans_cancel;
> 		}
> 	}
> 
> I find this much easier to read and follow the logic, and we don't
> really care if it takes a couple more lines of code to make the
> comments and code flow more logically.

Right, it is much easier to read and understand the logical.
> 
>> @@ -3419,25 +3431,15 @@ struct xfs_iunlink {
>>  
>>  	/*
>>  	 * For whiteouts, we need to bump the link count on the whiteout inode.
> 
> Shouldn't this line be removed as well?

Because the xfs_bumplink() call below will do this.
> 
>> -	 * This means that failures all the way up to this point leave the inode
>> -	 * on the unlinked list and so cleanup is a simple matter of dropping
>> -	 * the remaining reference to it. If we fail here after bumping the link
>> -	 * count, we're shutting down the filesystem so we'll never see the
>> -	 * intermediate state on disk.
>> +	 * The whiteout inode has been removed from the unlinked list and log
>> +	 * recovery will clean up the mess for the failures up to this point.
>> +	 * After this point we have a real link, clear the tmpfile state flag
>> +	 * from the inode so it doesn't accidentally get misused in future.
>>  	 */
>>  	if (wip) {
>>  		ASSERT(VFS_I(wip)->i_nlink == 0);
>>  		xfs_bumplink(tp, wip);
>> -		error = xfs_iunlink_remove(tp, wip);
>> -		if (error)
>> -			goto out_trans_cancel;
>>  		xfs_trans_log_inode(tp, wip, XFS_ILOG_CORE);
>> -
>> -		/*
>> -		 * Now we have a real link, clear the "I'm a tmpfile" state
>> -		 * flag from the inode so it doesn't accidentally get misused in
>> -		 * future.
>> -		 */
>>  		VFS_I(wip)->i_state &= ~I_LINKABLE;
>>  	}
> 
> Why not move all this up into the same branch that removes the
> whiteout from the unlinked list? Why separate this logic as none of
> what is left here could cause a failure even if it is run earlier?

Yep, it could not cause a failure if we move all this into the same
branch that xfs_iunlink_remove() call. We move the xfs_iunlink_remove()
first to preserve correct AGI/AGF locking order, and maybe it is better
we bump the link count after using the whiteout inode really, such as
xfs_dir_replace(...,wip,...) ...
> 
> Cheers,
> 
> Dave.
> 

-- 
kaixuxia

Re: [PATCH v4] xfs: Fix agi&agf ABBA deadlock when performing rename with RENAME_WHITEOUT flag

[Dave Chinner]

On Thu, Aug 22, 2019 at 01:45:48PM +0800, kaixuxia wrote:
> On 2019/8/22 13:01, Dave Chinner wrote:
> > On Thu, Aug 22, 2019 at 12:33:23PM +0800, kaixuxia wrote:
> > 
> >> @@ -3419,25 +3431,15 @@ struct xfs_iunlink {
> >>  
> >>  	/*
> >>  	 * For whiteouts, we need to bump the link count on the whiteout inode.
> > 
> > Shouldn't this line be removed as well?
> 
> Because the xfs_bumplink() call below will do this.

Oh, yeah, I just assumed that from the "we have a real link" part of
the new comment :P

> >> -	 * This means that failures all the way up to this point leave the inode
> >> -	 * on the unlinked list and so cleanup is a simple matter of dropping
> >> -	 * the remaining reference to it. If we fail here after bumping the link
> >> -	 * count, we're shutting down the filesystem so we'll never see the
> >> -	 * intermediate state on disk.
> >> +	 * The whiteout inode has been removed from the unlinked list and log
> >> +	 * recovery will clean up the mess for the failures up to this point.
> >> +	 * After this point we have a real link, clear the tmpfile state flag
> >> +	 * from the inode so it doesn't accidentally get misused in future.
> >>  	 */
> >>  	if (wip) {
> >>  		ASSERT(VFS_I(wip)->i_nlink == 0);
> >>  		xfs_bumplink(tp, wip);
> >> -		error = xfs_iunlink_remove(tp, wip);
> >> -		if (error)
> >> -			goto out_trans_cancel;
> >>  		xfs_trans_log_inode(tp, wip, XFS_ILOG_CORE);
> >> -
> >> -		/*
> >> -		 * Now we have a real link, clear the "I'm a tmpfile" state
> >> -		 * flag from the inode so it doesn't accidentally get misused in
> >> -		 * future.
> >> -		 */
> >>  		VFS_I(wip)->i_state &= ~I_LINKABLE;
> >>  	}
> > 
> > Why not move all this up into the same branch that removes the
> > whiteout from the unlinked list? Why separate this logic as none of
> > what is left here could cause a failure even if it is run earlier?
> 
> Yep, it could not cause a failure if we move all this into the same
> branch that xfs_iunlink_remove() call. We move the xfs_iunlink_remove()
> first to preserve correct AGI/AGF locking order, and maybe it is better
> we bump the link count after using the whiteout inode really, such as
> xfs_dir_replace(...,wip,...) ...

It makes no difference where we bump the link count as long as we do
it after the xfs_iunlink_remove() call. At that point, any failure
will result in a shutdown and so it doesn't matter that we've
already bumped the link count because the shutdown with prevent
it from reaching the disk...

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com

Re: [PATCH v4] xfs: Fix agi&agf ABBA deadlock when performing rename with RENAME_WHITEOUT flag

[kaixuxia]

On 2019/8/22 14:06, Dave Chinner wrote:
> On Thu, Aug 22, 2019 at 01:45:48PM +0800, kaixuxia wrote:
>> On 2019/8/22 13:01, Dave Chinner wrote:
>>> On Thu, Aug 22, 2019 at 12:33:23PM +0800, kaixuxia wrote:
>>>
>>>> @@ -3419,25 +3431,15 @@ struct xfs_iunlink {
>>>>  
>>>>  	/*
>>>>  	 * For whiteouts, we need to bump the link count on the whiteout inode.
>>>
>>> Shouldn't this line be removed as well?
>>
>> Because the xfs_bumplink() call below will do this.
> 
> Oh, yeah, I just assumed that from the "we have a real link" part of
> the new comment :P
> 
>>>> -	 * This means that failures all the way up to this point leave the inode
>>>> -	 * on the unlinked list and so cleanup is a simple matter of dropping
>>>> -	 * the remaining reference to it. If we fail here after bumping the link
>>>> -	 * count, we're shutting down the filesystem so we'll never see the
>>>> -	 * intermediate state on disk.
>>>> +	 * The whiteout inode has been removed from the unlinked list and log
>>>> +	 * recovery will clean up the mess for the failures up to this point.
>>>> +	 * After this point we have a real link, clear the tmpfile state flag
>>>> +	 * from the inode so it doesn't accidentally get misused in future.
>>>>  	 */
>>>>  	if (wip) {
>>>>  		ASSERT(VFS_I(wip)->i_nlink == 0);
>>>>  		xfs_bumplink(tp, wip);
>>>> -		error = xfs_iunlink_remove(tp, wip);
>>>> -		if (error)
>>>> -			goto out_trans_cancel;
>>>>  		xfs_trans_log_inode(tp, wip, XFS_ILOG_CORE);
>>>> -
>>>> -		/*
>>>> -		 * Now we have a real link, clear the "I'm a tmpfile" state
>>>> -		 * flag from the inode so it doesn't accidentally get misused in
>>>> -		 * future.
>>>> -		 */
>>>>  		VFS_I(wip)->i_state &= ~I_LINKABLE;
>>>>  	}
>>>
>>> Why not move all this up into the same branch that removes the
>>> whiteout from the unlinked list? Why separate this logic as none of
>>> what is left here could cause a failure even if it is run earlier?
>>
>> Yep, it could not cause a failure if we move all this into the same
>> branch that xfs_iunlink_remove() call. We move the xfs_iunlink_remove()
>> first to preserve correct AGI/AGF locking order, and maybe it is better
>> we bump the link count after using the whiteout inode really, such as
>> xfs_dir_replace(...,wip,...) ...
> 
> It makes no difference where we bump the link count as long as we do
> it after the xfs_iunlink_remove() call. At that point, any failure
> will result in a shutdown and so it doesn't matter that we've
> already bumped the link count because the shutdown with prevent
> it from reaching the disk...

Yeah, so it can be like this:

	/*
	 * For whiteouts, we need to bump the link count on the whiteout inode.
	 * The whiteout inode is removed from the unlinked list and log recovery
	 * will clean up the mess for the failures after this point. After this
 	 * point we have a real link, clear the tmpfile state flag from the inode
	 * so it doesn't accidentally get misused in future.
	 */
	if (wip) {
		ASSERT(VFS_I(wip)->i_nlink == 0);
		error = xfs_iunlink_remove(tp, wip);
		if (error)
			...
		xfs_bumplink(tp, wip);
		xfs_trans_log_inode(tp, wip, XFS_ILOG_CORE);
		VFS_I(wip)->i_state &= ~I_LINKABLE;
	}

Right?

> 
> Cheers,
> 
> Dave.
> 

-- 
kaixuxia