Skip to contentSkip to conversation

xfs: prevent bmap btree from using alloc btree reserved blocks

RFC PATCH Lachlan McIlroy 1 participant 1 message Sep 24, 2010 1 message not in the archive

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): 419117193.267231285302375889.JavaMail.root@zmail05.collab.prod.int.phx2.redhat.com

#1 lore raw
Quoted 60 lines · ----- "Dave Chinner
Quoted 8 lines · Lachlan McIlroy

Looks good, some questions inline.

Quoted 6 lines · ----- "Dave Chinner
Quoted 3 lines · Dave Chinner

From: Dave Chinner <[email protected]>

Recently we've had WANT_CORRUPTED_GOTO filesystem shutdowns

reported

Quoted 1 line

on filesystems with large numbers of small AGs. RedHat QA found

a

Quoted 11 lines
Quoted 11 lines
Quoted 11 lines

simple test case at:

https://bugzilla.redhat.com/show_bug.cgi?id=626244

Which was further refined to:

# mkfs.xfs -f -d agsize=16m,size=50g <dev>
# mount <dev> /mnt
# xfs_io -f -c 'resvsp 0 40G' /mnt/foo

The initial analysis is in the above bug. The fundamental

problem

Quoted 2 lines
Quoted 2 lines

is

Quoted 1 line

that the data extent allocation is using all the free blocks in

the

Quoted 4 lines
Quoted 4 lines
Quoted 4 lines

allocation group, and then the bmap btree block allocation is dipping into the reserved block pool that each AG holds for freespace btree manipulations. This results in failures when multiple bmap btree blocks are needed for a multilevel split of

the

Quoted 4 lines
Quoted 4 lines
Quoted 4 lines

bmap btree.

The reason this is occurring is that when we do a btree block allocation after a data extent allocation we run down the path

that

Quoted 1 line
Quoted 1 line
Quoted 1 line

does not set up the minleft allocation parameter. That is, we

allow

Quoted 1 line
Quoted 1 line
Quoted 1 line

the btree block allocation to use up all the blocks in the

current

Quoted 1 line
Quoted 1 line
Quoted 1 line

AG if that is what will make the current allocation succeed.

This

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

what we are supposed to only allow the low space allocation algorithm to do, not a normal allocation. The result is that we

can

Quoted 1 line
Quoted 1 line
Quoted 1 line

allocate the first block from the AG freelist, and then the

second

Quoted 1 line
Quoted 1 line
Quoted 1 line

block allocation in the split will fail in the same AG because

we

Quoted 2 lines
Quoted 2 lines

do

Quoted 1 line

not have a minleft parameter set and hence will not pass the

checks

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

in xfs_alloc_fix_freelist() and hence the allocation will fail. Further, because no minleft parameter is set, the btree block allocation will not retry the allocation with different

parameters

Quoted 5 lines
Quoted 1 line
Quoted 1 line

and (potentially) enable the low space algorithm.

I think the assumption here is that if the first btree block (with minleft set) succeeds then all the required free blocks for further btree allocations will be available if needed and allocations

Quoted 7 lines

shouldn't

Quoted 1 line

fail.

Right, but I think that the blocks reserved for different trees are getting confused. That is, I think minleft is reserving space for bmap btree blocks, while XFS_MIN_FREELIST_PAG() is reserving the minimum necessary space for the freespace btree operations.

Yes that's my understanding too - minleft is for the bmap btree and XFS_MIN_FREELIST_PAG() is for the freelist tree. I can't see how they are getting mixed up though.

Quoted 5 lines
Quoted 2 lines

But this clearly isn't holding true.

Right - I think that the bmap btree blocks are being taken from the freespace tree reserve because minleft is set to zero.

Okay, that shouldn't happen. My understanding of minleft is that the allocation is conditional on there being at least minleft blocks left after the allocation (after taking into account the freelist tree blocks) otherwise the allocation will not proceed. Using a minleft of 0 means we can allocate the last available block in an AG while still leaving XFS_MIN_FREELIST_PAG() blocks.

We have this condition in xfs_alloc_fix_freelist():

		need = XFS_MIN_FREELIST_PAG(pag, mp);
...
		    ((int)(pag->pagf_freeblks + pag->pagf_flcount -
			   need - args->total) < (int)args->minleft)) {

But I cannot see where args->total gets set. I see it is initialised to zero but shouldn't it be set to 1 for the block we need to allocate? If this remains as zero then we could steal a block from the freespace reserve by allowing an allocation to proceed when it shouldn't. I think this may be the source of the problem.

Quoted 4 lines
Quoted 3 lines

Do we have multiple threads
allocating from the same AG stealing each other's minleft blocks?

Quoted 8 lines

No. The issue, I think, is that for this filesystem both XFS_MIN_FREELIST_PAG() and the bmap btree max split are equal at 4 blocks. Hence I think the first allocation is succeeding because minleft modifies the check that xfs_alloc_fix_freelist() does - it appears to allow dipping into XFS_MIN_FREELIST_PAG() when minleft == XFS_MIN_FREELIST_PAG(). For the second block, minleft was zero, which means it couldn't dip into the reserve and hence failed without a fallback or checking another AG.

I don't see how it's dipping into the freelist reserve. From what I can see it sums up all the free blocks, subtracts the reserved space that can't be used, subtracts the space for the current allocation and if that leaves less than minleft left then fail.

So I think the logic should be - if minleft is > 0 and it fails then try another AG. If all AGs fail then restart with minleft == 0 and if that fails try another AG again. Well that's the case with XFS_ALLOCTYPE_START_BNO. With XFS_ALLOCTYPE_NEAR_BNO it wont try other AGs and fails prematurely (but your fix prevents that).

I think that having minleft set for every allocation isn't that important (well, it may improve the chances of getting most bmap btree blocks in one AG if we can't find an AG to fit all of them in) but what is important is retrying the allocation to give it a chance to succeed in another AG.

So I think a one-liner to change XFS_ALLOCTYPE_NEAR_BNO to XFS_ALLOCTYPE_START_BNO is all that's needed. The condition '(args.fsbno == NULLFSBLOCK && args.minleft)' still works because minleft > 0 implies b.firstblock == NULLFSBLOCK and we can try the allocation again from AG 0. If minleft == 0 we've already locked an AG and cannot restart from AG 0.

Quoted 6 lines

I think the way minleft affects xfs_alloc_fix_freelist() behaviour might be part of the problem - it seems wrong to me to let bmap btree blocks (which can be located in any AG) use blocks reserved for the freelists themselves. Could you have a look at this and let me know what you think?

Yeah it definitely seems wrong for the bmap btree to use freelist blocks and it shouldn't happen. If there's anyway we can catch/assert that we should - just not sure how to.

Quoted 104 lines
Quoted 7 lines
Quoted 7 lines
Quoted 4 lines
---
 fs/xfs/xfs_bmap_btree.c |   51

++++++++++++++++++++++++++++++++++++++--------

Quoted 2 lines
 1 files changed, 42 insertions(+), 9 deletions(-)
Quoted 10 lines
Quoted 8 lines

fs/xfs/xfs_bmap_btree.c xfs_bmbt_alloc_block( · line 540

Quoted 8 lines
fs/xfs/xfs_bmap_btree.c +0 -0
index 87d3c10..d5ef4e3 100644
@@ -538,6 +538,25 @@ xfs_bmbt_alloc_block(
 		args.type = XFS_ALLOCTYPE_START_BNO;
 	} else {
 		args.type = XFS_ALLOCTYPE_NEAR_BNO;

Could we use XFS_ALLOCTYPE_START_BNO here so that it automatically

tries other

Quoted 1 line

AGs instead of doing it manually (like you've done below)? It

should even

Quoted 5 lines

restart from AG 0 if no other allocations have been done.

Quoted 3 lines

fs/xfs/xfs_bmap_btree.c xfs_bmbt_alloc_block( · line 543

Quoted 3 lines
fs/xfs/xfs_bmap_btree.c +3 -0
+
+		/*
+		 * we've come in here because this is the second or

subsequent

Quoted 4 lines
Quoted 4 lines

fs/xfs/xfs_bmap_btree.c xfs_bmbt_alloc_block( · line 547

Quoted 4 lines
fs/xfs/xfs_bmap_btree.c +4 -0
+		 * btree block we need to allocate for the bmap btree
+		 * modification. If we've just emptied the AG and there are
+		 * only free list blocks left, we need to make sure that we
+		 * take into account the minleft value that was reserved on

the

Quoted 2 lines
Quoted 2 lines

fs/xfs/xfs_bmap_btree.c xfs_bmbt_alloc_block( · line 549

Quoted 2 lines
fs/xfs/xfs_bmap_btree.c +2 -0
+		 * first allocation through here (the NULLFSBLOCK branch
+		 * above). In that case, minleft will already take into

account

Quoted 1 line
Quoted 1 line

fs/xfs/xfs_bmap_btree.c xfs_bmbt_alloc_block( · line 550

Quoted 1 line
fs/xfs/xfs_bmap_btree.c +1 -0
+		 * the maximum number of blocks needed for a btree split,

and

Quoted 2 lines
Quoted 2 lines

fs/xfs/xfs_bmap_btree.c xfs_bmbt_alloc_block( · line 552

Quoted 2 lines
fs/xfs/xfs_bmap_btree.c +2 -0
+		 * the number of blocks already allocated is recorded in the
+		 * cursor. From that, we can work out exactly how much

smaller

Quoted 2 lines
Quoted 2 lines

fs/xfs/xfs_bmap_btree.c xfs_bmbt_alloc_block( · line 554

Quoted 2 lines
fs/xfs/xfs_bmap_btree.c +2 -0
+		 * the minleft should be so that we don't select an AG that
+		 * does not have enough blocks available to continue the

entire

Quoted 12 lines
Quoted 12 lines
Quoted 12 lines
fs/xfs/xfs_bmap_btree.c +5 -0
+		 * btree split.
+		 */
+		args.minleft = XFS_BM_MAXLEVELS(args.mp,
+					(int)cur->bc_private.b.whichfork) - 1 -
+				cur->bc_private.b.allocated;
 	}
 
 	args.minlen = args.maxlen = args.prod = 1;
@@ -550,15 +569,29 @@ xfs_bmbt_alloc_block(
 	if (error)
 		goto error0;
 
Quoted 13 lines
Quoted 11 lines

fs/xfs/xfs_bmap_btree.c xfs_bmbt_alloc_block( · line 573

Quoted 11 lines
fs/xfs/xfs_bmap_btree.c +2 -9
-	if (args.fsbno == NULLFSBLOCK && args.minleft) {
-		/*
-		 * Could not find an AG with 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;
+	while (args.fsbno == NULLFSBLOCK && args.minleft) {
+		if (cur->bc_private.b.firstblock == NULLFSBLOCK) {

Makes sense, need to check b_firstblock since minleft is always set

now.

Quoted 1 line

Do we still need the check for minleft here? The only case I can

see that

Quoted 1 line

minleft would be 0 now is for the low space algorithm and there may

be some

Quoted 1 line

benefit it letting it try again.

Yes, I think that makes sense.

Quoted 12 lines
Quoted 10 lines

fs/xfs/xfs_bmap_btree.c xfs_bmbt_alloc_block( · line 582

Quoted 10 lines
fs/xfs/xfs_bmap_btree.c +9 -0
+			/*
+			 * Could not find an AG with enough free space to satisfy
+			 * a full btree split.  Try again without minleft and if
+			 * successful activate the lowspace algorithm.
+			 */
+			args.type = XFS_ALLOCTYPE_FIRST_AG;
+			args.fsbno = 0;
+			args.minleft = 0;
+		} else {

Nice one, allow the allocator to hunt for btree blocks in later

AGs.

Quoted 14 lines
Quoted 11 lines

fs/xfs/xfs_bmap_btree.c xfs_bmbt_alloc_block( · line 592

Quoted 11 lines
fs/xfs/xfs_bmap_btree.c +10 -0
+			/*
+			 * Failed to find enough space for a btree block after
+			 * a extent allocation has already occurred. Continue
+			 * searching other AGs that can hold the remaining
+			 * blocks. If we fail with minleft set, then clear it
+			 * and try again.
+			 */
+			args.type = XFS_ALLOCTYPE_START_AG;
+			args.fsbno = cur->bc_private.b.firstblock;
+			if (cur->bc_private.b.flist->xbf_low)

I don't think xbf_low can be set here - if it was set then minleft would be 0 and we wouldn't have reached here.

Quoted 15 lines

True. I need to redo the loop termination if I'm going to let the minleft = 0 case retry allocation, in which case we could get here with xbf_low set...

Cheers,

Dave.

Signature · 7 lines
Dave Chinner
[email protected]

_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs

_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs