[PATCH 1/2] set minleft in xfs_bmbt_split()

[PATCH 1/2] set minleft in xfs_bmbt_split()

[Lachlan McIlroy]

The bmap btree split code relies on a previous data extent allocation
(from xfs_bmap_btalloc()) to find an AG that has sufficient space
to perform a full btree split, when inserting the extent.  When
converting unwritten extents we don't allocate a data extent so a
btree split will be the first allocation.  In this case we need to
set minleft so the allocator will pick an AG that has space to
complete the split(s).

Lachlan

--- 2.6.x-agno2.orig/fs/xfs/xfs_bmap_btree.c
+++ 2.6.x-agno2/fs/xfs/xfs_bmap_btree.c
@@ -1493,12 +1493,20 @@ xfs_bmbt_split(
 	left = XFS_BUF_TO_BMBT_BLOCK(lbp);
 	args.fsbno = cur->bc_private.b.firstblock;
 	args.firstblock = args.fsbno;
+	args.minleft = 0;
 	if (args.fsbno == NULLFSBLOCK) {
 		args.fsbno = lbno;
 		args.type = XFS_ALLOCTYPE_START_BNO;
+		/*
+		 * Make sure there is sufficient room left in the AG to
+		 * complete a full tree split for an extent insert.  If
+		 * we are converting the middle part of an extent then
+		 * we may need space for two tree splits.
+		 */
+		args.minleft = xfs_trans_get_block_res(args.tp);
 	} else
 		args.type = XFS_ALLOCTYPE_NEAR_BNO;
-	args.mod = args.minleft = args.alignment = args.total = args.isfl =
+	args.mod = args.alignment = args.total = args.isfl =
 		args.userdata = args.minalignslop = 0;
 	args.minlen = args.maxlen = args.prod = 1;
 	args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL;

Re: [PATCH 1/2] set minleft in xfs_bmbt_split()

[Dave Chinner]

On Tue, Jun 24, 2008 at 12:09:08PM +1000, Lachlan McIlroy wrote:
> The bmap btree split code relies on a previous data extent allocation
> (from xfs_bmap_btalloc()) to find an AG that has sufficient space
> to perform a full btree split, when inserting the extent.  When
> converting unwritten extents we don't allocate a data extent so a
> btree split will be the first allocation.  In this case we need to
> set minleft so the allocator will pick an AG that has space to
> complete the split(s).

looks good, execpt...

> 
> Lachlan
> 
> --- 2.6.x-agno2.orig/fs/xfs/xfs_bmap_btree.c
> +++ 2.6.x-agno2/fs/xfs/xfs_bmap_btree.c
> @@ -1493,12 +1493,20 @@ xfs_bmbt_split(
> 	left = XFS_BUF_TO_BMBT_BLOCK(lbp);
> 	args.fsbno = cur->bc_private.b.firstblock;
> 	args.firstblock = args.fsbno;
> +	args.minleft = 0;
> 	if (args.fsbno == NULLFSBLOCK) {
> 		args.fsbno = lbno;
> 		args.type = XFS_ALLOCTYPE_START_BNO;
> +		/*
> +		 * Make sure there is sufficient room left in the AG to
> +		 * complete a full tree split for an extent insert.  If
> +		 * we are converting the middle part of an extent then
> +		 * we may need space for two tree splits.
> +		 */
> +		args.minleft = xfs_trans_get_block_res(args.tp);

I'd mention in this comment that transaction reservation needs to
take this specifically into account. It is probably also worth
adding a matching comment to xfs_iomap_write_unwritten() where
the double reservation is done (i.e. explain the magic "<< 1").

Cheers,

Dave.
-- 
Dave Chinner
dchinner@agami.com

Re: [PATCH 1/2] set minleft in xfs_bmbt_split()

[Lachlan McIlroy]

Dave Chinner wrote:
> On Tue, Jun 24, 2008 at 12:09:08PM +1000, Lachlan McIlroy wrote:
>> The bmap btree split code relies on a previous data extent allocation
>> (from xfs_bmap_btalloc()) to find an AG that has sufficient space
>> to perform a full btree split, when inserting the extent.  When
>> converting unwritten extents we don't allocate a data extent so a
>> btree split will be the first allocation.  In this case we need to
>> set minleft so the allocator will pick an AG that has space to
>> complete the split(s).
> 
> looks good, execpt...
> 
>> Lachlan
>>
>> --- 2.6.x-agno2.orig/fs/xfs/xfs_bmap_btree.c
>> +++ 2.6.x-agno2/fs/xfs/xfs_bmap_btree.c
>> @@ -1493,12 +1493,20 @@ xfs_bmbt_split(
>> 	left = XFS_BUF_TO_BMBT_BLOCK(lbp);
>> 	args.fsbno = cur->bc_private.b.firstblock;
>> 	args.firstblock = args.fsbno;
>> +	args.minleft = 0;
>> 	if (args.fsbno == NULLFSBLOCK) {
>> 		args.fsbno = lbno;
>> 		args.type = XFS_ALLOCTYPE_START_BNO;
>> +		/*
>> +		 * Make sure there is sufficient room left in the AG to
>> +		 * complete a full tree split for an extent insert.  If
>> +		 * we are converting the middle part of an extent then
>> +		 * we may need space for two tree splits.
>> +		 */
>> +		args.minleft = xfs_trans_get_block_res(args.tp);
> 
> I'd mention in this comment that transaction reservation needs to
> take this specifically into account.
How would transaction reservation take this into account?  Are you
implying they could do something different if they knew about this
fix?

> It is probably also worth
> adding a matching comment to xfs_iomap_write_unwritten() where
> the double reservation is done (i.e. explain the magic "<< 1").
> 
Will do.

Re: [PATCH 1/2] set minleft in xfs_bmbt_split()

[Dave Chinner]

On Tue, Jun 24, 2008 at 03:22:03PM +1000, Lachlan McIlroy wrote:
> Dave Chinner wrote:
> >On Tue, Jun 24, 2008 at 12:09:08PM +1000, Lachlan McIlroy wrote:
> >>The bmap btree split code relies on a previous data extent allocation
> >>(from xfs_bmap_btalloc()) to find an AG that has sufficient space
> >>to perform a full btree split, when inserting the extent.  When
> >>converting unwritten extents we don't allocate a data extent so a
> >>btree split will be the first allocation.  In this case we need to
> >>set minleft so the allocator will pick an AG that has space to
> >>complete the split(s).
> >
> >looks good, execpt...
> >
> >>Lachlan
> >>
> >>--- 2.6.x-agno2.orig/fs/xfs/xfs_bmap_btree.c
> >>+++ 2.6.x-agno2/fs/xfs/xfs_bmap_btree.c
> >>@@ -1493,12 +1493,20 @@ xfs_bmbt_split(
> >>	left = XFS_BUF_TO_BMBT_BLOCK(lbp);
> >>	args.fsbno = cur->bc_private.b.firstblock;
> >>	args.firstblock = args.fsbno;
> >>+	args.minleft = 0;
> >>	if (args.fsbno == NULLFSBLOCK) {
> >>		args.fsbno = lbno;
> >>		args.type = XFS_ALLOCTYPE_START_BNO;
> >>+		/*
> >>+		 * Make sure there is sufficient room left in the AG to
> >>+		 * complete a full tree split for an extent insert.  If
> >>+		 * we are converting the middle part of an extent then
> >>+		 * we may need space for two tree splits.
> >>+		 */
> >>+		args.minleft = xfs_trans_get_block_res(args.tp);
> >
> >I'd mention in this comment that transaction reservation needs to
> >take this specifically into account.
> How would transaction reservation take this into account?  Are you
> implying they could do something different if they knew about this
> fix?

No, I'm implying that the transaction reservation better be correct.
i.e. anywhere that unwritten extent conversion can take place needs
to supply a reservation of enough blocks to allow a double split to
occur.  i.e. we are relying on the caller to get this right, so we
need to ensure that a comment explaining the potential landmine is
present....

Cheers,

Dave.
-- 
Dave Chinner
dchinner@agami.com

Re: [PATCH 1/2] set minleft in xfs_bmbt_split()

[Lachlan McIlroy]

Dave Chinner wrote:
> On Tue, Jun 24, 2008 at 03:22:03PM +1000, Lachlan McIlroy wrote:
>> Dave Chinner wrote:
>>> On Tue, Jun 24, 2008 at 12:09:08PM +1000, Lachlan McIlroy wrote:
>>>> The bmap btree split code relies on a previous data extent allocation
>>>> (from xfs_bmap_btalloc()) to find an AG that has sufficient space
>>>> to perform a full btree split, when inserting the extent.  When
>>>> converting unwritten extents we don't allocate a data extent so a
>>>> btree split will be the first allocation.  In this case we need to
>>>> set minleft so the allocator will pick an AG that has space to
>>>> complete the split(s).
>>> looks good, execpt...
>>>
>>>> Lachlan
>>>>
>>>> --- 2.6.x-agno2.orig/fs/xfs/xfs_bmap_btree.c
>>>> +++ 2.6.x-agno2/fs/xfs/xfs_bmap_btree.c
>>>> @@ -1493,12 +1493,20 @@ xfs_bmbt_split(
>>>> 	left = XFS_BUF_TO_BMBT_BLOCK(lbp);
>>>> 	args.fsbno = cur->bc_private.b.firstblock;
>>>> 	args.firstblock = args.fsbno;
>>>> +	args.minleft = 0;
>>>> 	if (args.fsbno == NULLFSBLOCK) {
>>>> 		args.fsbno = lbno;
>>>> 		args.type = XFS_ALLOCTYPE_START_BNO;
>>>> +		/*
>>>> +		 * Make sure there is sufficient room left in the AG to
>>>> +		 * complete a full tree split for an extent insert.  If
>>>> +		 * we are converting the middle part of an extent then
>>>> +		 * we may need space for two tree splits.
>>>> +		 */
>>>> +		args.minleft = xfs_trans_get_block_res(args.tp);
>>> I'd mention in this comment that transaction reservation needs to
>>> take this specifically into account.
>> How would transaction reservation take this into account?  Are you
>> implying they could do something different if they knew about this
>> fix?
> 
> No, I'm implying that the transaction reservation better be correct.
> i.e. anywhere that unwritten extent conversion can take place needs
> to supply a reservation of enough blocks to allow a double split to
> occur.  i.e. we are relying on the caller to get this right, so we
> need to ensure that a comment explaining the potential landmine is
> present....

Okay.  With the change above we can still have xfs_bmbt_split() fail
to allocate btree blocks if it cannot find a single AG with enough
free space.  Although in my testing I haven't seen it fail yet.

We really don't want to fail here because we have already partly
modified the extent btree (ie for the case where we convert the middle
part of an unwritten extent we do an xfs_bmbt_update before the insert)
and we dont undo the damage.  Also a failure to allocate in
xfs_bmbt_split() will be caught by the XFS_WANT_CORRUPTED_GOTO() in
xfs_bmbt_insert() and the error set to EFSCORRUPTED which is only going
to create confusion.  I have another patch that allows xfs_bmbt_split()
and xfs_bmbt_newroot() to fall back to the lowspace algorithm - I'm
just testing it now.

Re: [PATCH 1/2] set minleft in xfs_bmbt_split()

[Dave Chinner]

On Tue, Jun 24, 2008 at 04:16:50PM +1000, Lachlan McIlroy wrote:
> Dave Chinner wrote:
> >On Tue, Jun 24, 2008 at 03:22:03PM +1000, Lachlan McIlroy wrote:
> >>Dave Chinner wrote:
> >>>On Tue, Jun 24, 2008 at 12:09:08PM +1000, Lachlan McIlroy wrote:
> >>>>The bmap btree split code relies on a previous data extent allocation
> >>>>(from xfs_bmap_btalloc()) to find an AG that has sufficient space
> >>>>to perform a full btree split, when inserting the extent.  When
> >>>>converting unwritten extents we don't allocate a data extent so a
> >>>>btree split will be the first allocation.  In this case we need to
> >>>>set minleft so the allocator will pick an AG that has space to
> >>>>complete the split(s).
> >>>looks good, execpt...
> >>>
> >>>>Lachlan
> >>>>
> >>>>--- 2.6.x-agno2.orig/fs/xfs/xfs_bmap_btree.c
> >>>>+++ 2.6.x-agno2/fs/xfs/xfs_bmap_btree.c
> >>>>@@ -1493,12 +1493,20 @@ xfs_bmbt_split(
> >>>>	left = XFS_BUF_TO_BMBT_BLOCK(lbp);
> >>>>	args.fsbno = cur->bc_private.b.firstblock;
> >>>>	args.firstblock = args.fsbno;
> >>>>+	args.minleft = 0;
> >>>>	if (args.fsbno == NULLFSBLOCK) {
> >>>>		args.fsbno = lbno;
> >>>>		args.type = XFS_ALLOCTYPE_START_BNO;
> >>>>+		/*
> >>>>+		 * Make sure there is sufficient room left in the AG to
> >>>>+		 * complete a full tree split for an extent insert.  If
> >>>>+		 * we are converting the middle part of an extent then
> >>>>+		 * we may need space for two tree splits.
> >>>>+		 */
> >>>>+		args.minleft = xfs_trans_get_block_res(args.tp);
> >>>I'd mention in this comment that transaction reservation needs to
> >>>take this specifically into account.
> >>How would transaction reservation take this into account?  Are you
> >>implying they could do something different if they knew about this
> >>fix?
> >
> >No, I'm implying that the transaction reservation better be correct.
> >i.e. anywhere that unwritten extent conversion can take place needs
> >to supply a reservation of enough blocks to allow a double split to
> >occur.  i.e. we are relying on the caller to get this right, so we
> >need to ensure that a comment explaining the potential landmine is
> >present....
> 
> Okay.  With the change above we can still have xfs_bmbt_split() fail
> to allocate btree blocks if it cannot find a single AG with enough
> free space.  Although in my testing I haven't seen it fail yet.

Sure, but at that point you've most likely got a real ENOSPC condition.

> We really don't want to fail here because we have already partly
> modified the extent btree (ie for the case where we convert the middle
> part of an unwritten extent we do an xfs_bmbt_update before the insert)
> and we dont undo the damage. 

Yes, but lets deal with one problem at a time ;)

> Also a failure to allocate in
> xfs_bmbt_split() will be caught by the XFS_WANT_CORRUPTED_GOTO() in
> xfs_bmbt_insert() and the error set to EFSCORRUPTED which is only going
> to create confusion. 

For whom? Log an error message when allocation fails if you're
worried that we won't be able to determine what went wrong...

> I have another patch that allows xfs_bmbt_split()
> and xfs_bmbt_newroot() to fall back to the lowspace algorithm - I'm
> just testing it now.

Cool - that should solve the corner cases you mention above...

Cheers,

Dave.
-- 
Dave Chinner
dchinner@agami.com

Re: [PATCH 1/2] set minleft in xfs_bmbt_split()

[Lachlan McIlroy]

Dave Chinner wrote:
> On Tue, Jun 24, 2008 at 04:16:50PM +1000, Lachlan McIlroy wrote:
>> Dave Chinner wrote:
>>> On Tue, Jun 24, 2008 at 03:22:03PM +1000, Lachlan McIlroy wrote:
>>>> Dave Chinner wrote:
>>>>> On Tue, Jun 24, 2008 at 12:09:08PM +1000, Lachlan McIlroy wrote:
>>>>>> The bmap btree split code relies on a previous data extent allocation
>>>>>> (from xfs_bmap_btalloc()) to find an AG that has sufficient space
>>>>>> to perform a full btree split, when inserting the extent.  When
>>>>>> converting unwritten extents we don't allocate a data extent so a
>>>>>> btree split will be the first allocation.  In this case we need to
>>>>>> set minleft so the allocator will pick an AG that has space to
>>>>>> complete the split(s).
>>>>> looks good, execpt...
>>>>>
>>>>>> Lachlan
>>>>>>
>>>>>> --- 2.6.x-agno2.orig/fs/xfs/xfs_bmap_btree.c
>>>>>> +++ 2.6.x-agno2/fs/xfs/xfs_bmap_btree.c
>>>>>> @@ -1493,12 +1493,20 @@ xfs_bmbt_split(
>>>>>> 	left = XFS_BUF_TO_BMBT_BLOCK(lbp);
>>>>>> 	args.fsbno = cur->bc_private.b.firstblock;
>>>>>> 	args.firstblock = args.fsbno;
>>>>>> +	args.minleft = 0;
>>>>>> 	if (args.fsbno == NULLFSBLOCK) {
>>>>>> 		args.fsbno = lbno;
>>>>>> 		args.type = XFS_ALLOCTYPE_START_BNO;
>>>>>> +		/*
>>>>>> +		 * Make sure there is sufficient room left in the AG to
>>>>>> +		 * complete a full tree split for an extent insert.  If
>>>>>> +		 * we are converting the middle part of an extent then
>>>>>> +		 * we may need space for two tree splits.
>>>>>> +		 */
>>>>>> +		args.minleft = xfs_trans_get_block_res(args.tp);
>>>>> I'd mention in this comment that transaction reservation needs to
>>>>> take this specifically into account.
>>>> How would transaction reservation take this into account?  Are you
>>>> implying they could do something different if they knew about this
>>>> fix?
>>> No, I'm implying that the transaction reservation better be correct.
>>> i.e. anywhere that unwritten extent conversion can take place needs
>>> to supply a reservation of enough blocks to allow a double split to
>>> occur.  i.e. we are relying on the caller to get this right, so we
>>> need to ensure that a comment explaining the potential landmine is
>>> present....
>> Okay.  With the change above we can still have xfs_bmbt_split() fail
>> to allocate btree blocks if it cannot find a single AG with enough
>> free space.  Although in my testing I haven't seen it fail yet.
> 
> Sure, but at that point you've most likely got a real ENOSPC condition.
> 
>> We really don't want to fail here because we have already partly
>> modified the extent btree (ie for the case where we convert the middle
>> part of an unwritten extent we do an xfs_bmbt_update before the insert)
>> and we dont undo the damage. 
> 
> Yes, but lets deal with one problem at a time ;)
> 
>> Also a failure to allocate in
>> xfs_bmbt_split() will be caught by the XFS_WANT_CORRUPTED_GOTO() in
>> xfs_bmbt_insert() and the error set to EFSCORRUPTED which is only going
>> to create confusion. 
> 
> For whom? Log an error message when allocation fails if you're
> worried that we won't be able to determine what went wrong...
> 
>> I have another patch that allows xfs_bmbt_split()
>> and xfs_bmbt_newroot() to fall back to the lowspace algorithm - I'm
>> just testing it now.
> 
> Cool - that should solve the corner cases you mention above...

This is the fallback code.  Do you think I also need to make the same
minleft change above and this change below to xfs_bmbt_newroot()?

I'm inclined to change both xfs_bmbt_split() and xfs_bmbt_newroot()
and keep them as similar as possible.  For the newroot case we know we
only need one block and we know there will be no more allocations for
this insert so using 'minleft = xfs_trans_get_block_res()' is silly but
on the other hand we don't have any other way to detect the double
insert case.

--- 2.6.x-agno2.orig/fs/xfs/xfs_bmap_btree.c
+++ 2.6.x-agno2/fs/xfs/xfs_bmap_btree.c
@@ -1525,6 +1525,21 @@ xfs_bmbt_split(
 		XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 		return error;
 	}
+	if (args.fsbno == NULLFSBLOCK && args.minleft) {
+		/*
+		 * Could not find an AG will enough free space to satisfy
+		 * a full btree split.  Try again without minleft and if
+		 * successful activate the lowspace algorithm.
+		 */
+		args.fsbno = 0;
+		args.type = XFS_ALLOCTYPE_FIRST_AG;
+		args.minleft = 0;
+		if ((error = xfs_alloc_vextent(&args))) {
+			XFS_BMBT_TRACE_CURSOR(cur, ERROR);
+			return error;
+		}
+		cur->bc_private.b.flist->xbf_low = 1;
+	}
 	if (args.fsbno == NULLFSBLOCK) {
 		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 		*stat = 0;

Re: [PATCH 1/2] set minleft in xfs_bmbt_split()

[Dave Chinner]

On Tue, Jun 24, 2008 at 05:10:08PM +1000, Lachlan McIlroy wrote:

[....]

> This is the fallback code.  Do you think I also need to make the same
> minleft change above and this change below to xfs_bmbt_newroot()?
>
> I'm inclined to change both xfs_bmbt_split() and xfs_bmbt_newroot()
> and keep them as similar as possible.  For the newroot case we know we
> only need one block and we know there will be no more allocations for
> this insert so using 'minleft = xfs_trans_get_block_res()' is silly but
> on the other hand we don't have any other way to detect the double
> insert case.

OTOH, if we do a double insert, is it even possible for that to
trigger a full tree double split? i.e. after the first split that
allocates a new root, the new root will only be partially full, so
we should be able to insert there in all cases without a split on
the second insert. The case of a second split occurring is when the
second insert goes into a different leaf block to the first insert
and that needs splitting as well. If it's a completely different
path up to the root of the tree, then the place where they will join
is the old root block (remember that the new root block contains the
old contents of the inode fork - it's not really a split but a move
operation) and so a second newroot allocation will not be necessary.
Hence I think that the newroot allocation will never be triggered
twice in the unwritten extent double insert case.

*However*, if the newroot function is first allocation, it still may
need to take into account the second insert which may split a leaf
as well. I don't think this can happen - the only time we'll do a
newroot allocation without having first done an allocation in
xfs_bmbt_split() is when adding an attribute fork and we need to
push the data fork root out to make room for the attr fork.  In this
case, we don't have a split occurring at all and so we only need one
block for the new root.

Hence I don't think the newroot case needs to reserve space for
entire splits or multiple splits at all - if that is going to happen
it should already have been taken into account by earlier allocations...

> --- 2.6.x-agno2.orig/fs/xfs/xfs_bmap_btree.c
> +++ 2.6.x-agno2/fs/xfs/xfs_bmap_btree.c
> @@ -1525,6 +1525,21 @@ xfs_bmbt_split(
> 		XFS_BMBT_TRACE_CURSOR(cur, ERROR);
> 		return error;
> 	}
> +	if (args.fsbno == NULLFSBLOCK && args.minleft) {
> +		/*
> +		 * Could not find an AG will enough free space to satisfy
> +		 * a full btree split.  Try again without minleft and if
> +		 * successful activate the lowspace algorithm.
> +		 */
> +		args.fsbno = 0;
> +		args.type = XFS_ALLOCTYPE_FIRST_AG;
> +		args.minleft = 0;
> +		if ((error = xfs_alloc_vextent(&args))) {
> +			XFS_BMBT_TRACE_CURSOR(cur, ERROR);
> +			return error;
> +		}
> +		cur->bc_private.b.flist->xbf_low = 1;
> +	}

Yes, that change makes sense for the split case.

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com