xfs: fix a couple sparse chunk alloc problems
cover xfs: fix a couple sparse chunk alloc problems
Hi all,
This series is a couple small sparse chunk alloc related fixes. Patch 1 is LLM detected and generated (I rewrote the commit log) during the process of investigating the problem fixed by the second. Patch 2 fixes the problem reported by Matt here [1].
Note that patch 2 is semi-RFC. Personally I'm Ok with using this as the fix, but I don't love it and recognize that it's more of a band-aid. The fundamental problem seems more that the space availability requirements change within a transaction that targets a single AG, but I haven't yet thought of an elegant enough way to fix that for something that is kind of a corner case.
The LLM came up with a fix that basically bumps up minleft within the allocator path by the extra space that would be required by the inobt allocation, but I didn't really like that at all and tossed it in favor of this.
I had a couple other things I thought about as potential alternatives. One is to perhaps use or repurpose something like the XFS_ALLOC_FLAG_FREEING flag for this pattern where we have a minleft gated allocation followed by a targeted alloc to the same AG. This would presumably allow the allocation to succeed.
Another is to perhaps enhance the xfs_alloc_min_freelist() logic to just start to use the allocbt maxlevels value for requirements calculation as an AG starts to approach -ENOSPC. That is more of a heuristic and similar sort of workaround for the problem, but more directly encodes that reliability is priority over squeezing every last block from an AG. I also think it's a little risky as it may involve a new mode of allocation across the board (not just sparse chunk allocs).
I also suspect this wouldn't be a problem if the inobt were covered as perag metadata res the way the finobt is, but I haven't thought that through fully.
So all in all I'm curious what folks think about any of this or have any other potential ideas. My main concern is that I don't want to introduce something too complex for the single uncommon use case of sparse inodes. I.e., this problem seems a lot like a corner case of a corner case to me. Thoughts?
Brian
[1] https://lore.kernel.org/linux-xfs/[email protected]/
Brian Foster (2):
xfs: set minleft correctly for sparse chunk errortag allocation
xfs: consistent low ag space behavior for sparse inode chunk allocs
fs/xfs/libxfs/xfs_ialloc.c | 18 ++++++++++++------ 1 file changed, 12 insertions(+), 6 deletions(-)
Signature · 1 line
2.55.0
PATCH 1/2 xfs: set minleft correctly for sparse chunk errortag allocation
The errortag instrumentation for forced sparse chunk allocation jumps straight to the allocation path without setting args.minleft. minleft is unconditionally set to ->inobt_maxlevels for the normal allocation path. Lift the assignment to the initial args setup so it covers all possible paths.
--- fs/xfs/libxfs/xfs_ialloc.c | 10 ++++------ 1 file changed, 4 insertions(+), 6 deletions(-)
fs/xfs/libxfs/xfs_ialloc.c +4 -6
@@ -733,6 +733,10 @@ xfs_ialloc_ag_alloc( igeo->maxicount)return -ENOSPC ; args.minlen = args.maxlen = igeo->ialloc_blks; + +/* Allow space for the inode btree to split. */ + args.minleft = igeo->inobt_maxlevels; +/* * First try to allocate inodes contiguous with the last-allocated * chunk of inodes. If the filesystem is striped, this will fill
@@ -764,8 +768,6 @@ xfs_ialloc_ag_alloc( args.alignment =1 ; args.minalignslop = igeo->cluster_align -1 ; -/* Allow space for the inode btree to split. */ - args.minleft = igeo->inobt_maxlevels; error =xfs_alloc_vextent_exact_bno (&args,xfs_agbno_to_fsb (pag, args.agbno));if (error)
@@ -804,10 +806,6 @@ xfs_ialloc_ag_alloc(* Allocate a fixed-size extent of inodes. */ args.prod =1 ; -/* -* Allow space for the inode btree to split. -*/ - args.minleft = igeo->inobt_maxlevels; error =xfs_alloc_vextent_near_bno (&args,xfs_agbno_to_fsb (pag,be32_to_cpu (agi->agi_root)));
Signature · 1 line
2.55.0
Re: [External] : [PATCH 1/2] xfs: set minleft correctly for sparse chunk errortag allocation
Quoted 38 lines · Brian Foster
The errortag instrumentation for forced sparse chunk allocation jumps straight to the allocation path without setting args.minleft. minleft is unconditionally set to ->inobt_maxlevels for the normal allocation path. Lift the assignment to the initial args setup so it covers all possible paths.
Assisted-by LLMFixes 1cdadee11f8d ("xfs: randomly do sparse inode allocations in DEBUG mode")Signed-off-by Brian Foster <[email protected]>--- fs/xfs/libxfs/xfs_ialloc.c | 10 ++++------ 1 file changed, 4 insertions(+), 6 deletions(-)fs/xfs/libxfs/xfs_ialloc.c +4
-2@@ -733,6 +733,10 @@ xfs_ialloc_ag_alloc( igeo->maxicount)return -ENOSPC ; args.minlen = args.maxlen = igeo->ialloc_blks; + +/* Allow space for the inode btree to split. */ + args.minleft = igeo->inobt_maxlevels; +/* * First try to allocate inodes contiguous with the last-allocated * chunk of inodes. If the filesystem is striped, this will fill @@ -764,8 +768,6 @@ xfs_ialloc_ag_alloc( args.alignment =1 ; args.minalignslop = igeo->cluster_align -1 ; -/* Allow space for the inode btree to split. */ - args.minleft = igeo->inobt_maxlevels; error =xfs_alloc_vextent_exact_bno (&args,xfs_agbno_to_fsb (pag, args.agbno));if (error)
fs/xfs/libxfs/xfs_ialloc.c xfs_ialloc_ag_alloc( · line 811
Quoted 10 lines
fs/xfs/libxfs/xfs_ialloc.c +0
-4@@ -804,10 +806,6 @@ xfs_ialloc_ag_alloc(* Allocate a fixed-size extent of inodes. */ args.prod =1 ; -/* -* Allow space for the inode btree to split. -*/ - args.minleft = igeo->inobt_maxlevels; error =xfs_alloc_vextent_near_bno (&args,xfs_agbno_to_fsb (pag,be32_to_cpu (agi->agi_root)));
I got the patches backwards...I agree we need to increase the minleft in the other patch by 4 blocks (2 btrees * 2 for the level increase) but I wonder why can't a full size inode chunk also split the by-count and by-block btrees and the inode btree allocation also be short when fixing AGFL?
Re: [External] : [PATCH 1/2] xfs: set minleft correctly for sparse chunk errortag allocation
Quoted 43 lines · Mark Tinguely
Quoted 42 lines · Brian Foster
The errortag instrumentation for forced sparse chunk allocation jumps straight to the allocation path without setting args.minleft. minleft is unconditionally set to ->inobt_maxlevels for the normal allocation path. Lift the assignment to the initial args setup so it covers all possible paths.
Assisted-by LLMFixes 1cdadee11f8d ("xfs: randomly do sparse inode allocations in DEBUG mode")Signed-off-by Brian Foster <[email protected]>--- fs/xfs/libxfs/xfs_ialloc.c | 10 ++++------ 1 file changed, 4 insertions(+), 6 deletions(-)fs/xfs/libxfs/xfs_ialloc.c +4
-4@@ -733,6 +733,10 @@ xfs_ialloc_ag_alloc( igeo->maxicount)return -ENOSPC ; args.minlen = args.maxlen = igeo->ialloc_blks; + +/* Allow space for the inode btree to split. */ + args.minleft = igeo->inobt_maxlevels; +/* * First try to allocate inodes contiguous with the last-allocated * chunk of inodes. If the filesystem is striped, this will fill @@ -764,8 +768,6 @@ xfs_ialloc_ag_alloc( args.alignment =1 ; args.minalignslop = igeo->cluster_align -1 ; -/* Allow space for the inode btree to split. */ - args.minleft = igeo->inobt_maxlevels; error =xfs_alloc_vextent_exact_bno (&args,xfs_agbno_to_fsb (pag, args.agbno));if (error)@@ -804,10 +806,6 @@ xfs_ialloc_ag_alloc(* Allocate a fixed-size extent of inodes. */ args.prod =1 ; -/* -* Allow space for the inode btree to split.
Quoted 9 lines
fs/xfs/libxfs/xfs_ialloc.c xfs_ialloc_ag_alloc( · line 811
Quoted 5 lines
fs/xfs/libxfs/xfs_ialloc.c +0
-2-*/ - args.minleft = igeo->inobt_maxlevels; error =xfs_alloc_vextent_near_bno (&args,xfs_agbno_to_fsb (pag,be32_to_cpu (agi->agi_root)));Reviewed-by Mark Tinguely <[email protected]>
Thanks..
Quoted 5 lines
I got the patches backwards...I agree we need to increase the minleft in the other patch by 4 blocks (2 btrees * 2 for the level increase) but I wonder why can't a full size inode chunk also split the by-count and by-block btrees and the inode btree allocation also be short when fixing AGFL?
Yeah, I had the same general question in the original report. I'm not sure it can't happen for full size chunks. I was kind of taking it for granted that sparse inodes seem required to reproduce this just by virtue of smaller allocations and the allocator maybe having enough slop in the various calculations to gate it otherwise, but I'm not confident in that having now looked more through this code.
Perhaps Matt can comment on if or how hard we tried to reproduce this with full inode chunks..? I'm curious.. was the creation of the reproducer based on a detected flaw in the code (LLM scan or something?), or a low space stress test or something were this problem just happened to fall out..?
If we could reproduce or manufacture this with normal inode chunks, then I suppose that would lend more credence to a more generic solution within the allocator.
Brian
PATCH 2/2 xfs: consistent low ag space behavior for sparse inode chunk allocs
In reply to Brian FosterMatt Fleming reports a filesystem shutdown due to inobt block allocation failure during sparse chunk allocation. Inode creation can involve multiple allocations in a transaction via the initial chunk allocation and inode btree growth via the subsequent inobt record insertion. Technically this should be safe as the chunk allocation sets the allocation minleft parameter to the max depth of the inode btree, which means the allocation selects an AG only if there is enough free space for record insertion after the allocation. The record insertion naturally occurs in the same AG as the allocation and the associated AGF is locked and held by the current transaction.
The situation that reproduces this failure is a bit of a corner case. The allocation and inode btrees are all completely full and require a split on the next insertion. The AG has just enough available space to satisfy inode creation through sparse allocation (i.e. 7 blocks in this example). The block allocation occurs within an existing free space record, splitting the free space record into two and triggering the aforementioned allocbt splits.
The sparse chunk allocation consumes 4 blocks for the chunk, and 4 blocks from the AGFL for the two allocbt splits. This leaves the AGFL with 4 remaining blocks and 3 available blocks in the AG. The record insertion attempts block allocation for the inobt split, but even though space is available, the geometry change has changed the minimum allocation requirements enforced by xfs_alloc_fix_freelist(). The min freelist value jumps from 8 to 12 due to the alloc btree level increases, so the available space calculation goes from something like this before the allocation:
free + agfl - res - minfree - minleft = avail 2514 + 8 - 2505 - 8 - 2 = 7
... to this after it:
2510 + 4 - 2505 - 12 - 0 = -3
Essentially the minleft value of 2 for the chunk alloc is not sufficient to overcome the additional requirements imposed on the subsequent inobt alloc due to the allocbt geometry changes caused by the first.
Technically this shouldn't be a concern because a full split of any of the allocation btrees in one transaction means that we're not going to see another full split in the lifetime of that transaction, but the allocation path does not behave that way.
Absent of a clear way to lock in the agfl state for the particular case of multiple allocations into a single AG, this patch works around the problem by increasing the minleft requirement for sparse chunk allocations. Specifically, we increase minleft by the number of blocks that the alloc length was reduced by. The reasoning behind this is to generally preserve the AG level no space behavior between full and sparse inode chunk allocations.
The purpose of sparse inode chunks is to facilitate allocation in AGs under severe free space fragmentation and thus prevent premature -ENOSPC conditions across the broader fs, not necessarily squeeze every last block out of any single AG. Therefore, this helps ensure the low AG space boundary conditions for sparse inode chunks are relatively well tested compared to full inode chunks.
--- fs/xfs/libxfs/xfs_ialloc.c | 8 ++++++++ 1 file changed, 8 insertions(+)
fs/xfs/libxfs/xfs_ialloc.c +8 -0
@@ -840,6 +840,14 @@ xfs_ialloc_ag_alloc( args.minlen = igeo->ialloc_min_blks; args.maxlen = args.minlen; +/* +* Bump minleft by the alloc size delta to maintain consistent +* out of space behavior with normal sized chunks. This isn't a +* requirement, but helps avoid sparse chunk and inobt block +* allocation quirks at or close to AG depletion. +*/ + args.minleft += igeo->ialloc_blks - igeo->ialloc_min_blks; +/* * The inode record will be aligned to full chunk size. We must * prevent sparse allocation from AG boundaries that result in
Signature · 1 line
2.55.0
Re: [External] : [PATCH 2/2] xfs: consistent low ag space behavior for sparse inode chunk allocs
Quoted 78 lines · Brian Foster
Matt Fleming reports a filesystem shutdown due to inobt block allocation failure during sparse chunk allocation. Inode creation can involve multiple allocations in a transaction via the initial chunk allocation and inode btree growth via the subsequent inobt record insertion. Technically this should be safe as the chunk allocation sets the allocation minleft parameter to the max depth of the inode btree, which means the allocation selects an AG only if there is enough free space for record insertion after the allocation. The record insertion naturally occurs in the same AG as the allocation and the associated AGF is locked and held by the current transaction.
The situation that reproduces this failure is a bit of a corner case. The allocation and inode btrees are all completely full and require a split on the next insertion. The AG has just enough available space to satisfy inode creation through sparse allocation (i.e. 7 blocks in this example). The block allocation occurs within an existing free space record, splitting the free space record into two and triggering the aforementioned allocbt splits.
The sparse chunk allocation consumes 4 blocks for the chunk, and 4 blocks from the AGFL for the two allocbt splits. This leaves the AGFL with 4 remaining blocks and 3 available blocks in the AG. The record insertion attempts block allocation for the inobt split, but even though space is available, the geometry change has changed the minimum allocation requirements enforced by
xfs_alloc_fix_freelist(). The min freelist value jumps from 8 to 12 due to the alloc btree level increases, so the available space calculation goes from something like this before the allocation:free + agfl - res - minfree - minleft = avail 2514 + 8 - 2505 - 8 - 2 = 7... to this after it:
2510 + 4 - 2505 - 12 - 0 = -3Essentially the minleft value of 2 for the chunk alloc is not sufficient to overcome the additional requirements imposed on the subsequent inobt alloc due to the allocbt geometry changes caused by the first.
Technically this shouldn't be a concern because a full split of any of the allocation btrees in one transaction means that we're not going to see another full split in the lifetime of that transaction, but the allocation path does not behave that way.
Absent of a clear way to lock in the agfl state for the particular case of multiple allocations into a single AG, this patch works around the problem by increasing the minleft requirement for sparse chunk allocations. Specifically, we increase minleft by the number of blocks that the alloc length was reduced by. The reasoning behind this is to generally preserve the AG level no space behavior between full and sparse inode chunk allocations.
The purpose of sparse inode chunks is to facilitate allocation in AGs under severe free space fragmentation and thus prevent premature
-ENOSPCconditions across the broader fs, not necessarily squeeze every last block out of any single AG. Therefore, this helps ensure the low AG space boundary conditions for sparse inode chunks are relatively well tested compared to full inode chunks.Fixes 56d1115c9bc7 ("xfs: allocate sparse inode chunks on full chunk allocation failure")Reported-by Matt Fleming <[email protected]>Signed-off-by Brian Foster <[email protected]>--- fs/xfs/libxfs/xfs_ialloc.c | 8 ++++++++ 1 file changed, 8 insertions(+)fs/xfs/libxfs/xfs_ialloc.c +1
-0@@ -840,6 +840,14 @@ xfs_ialloc_ag_alloc( args.minlen = igeo->ialloc_min_blks; args.maxlen = args.minlen; +/*
fs/xfs/libxfs/xfs_ialloc.c xfs_ialloc_ag_alloc( · line 853
Quoted 10 lines
fs/xfs/libxfs/xfs_ialloc.c +7
-0+* Bump minleft by the alloc size delta to maintain consistent +* out of space behavior with normal sized chunks. This isn't a +* requirement, but helps avoid sparse chunk and inobt block +* allocation quirks at or close to AG depletion. +*/ + args.minleft += igeo->ialloc_blks - igeo->ialloc_min_blks; +/* * The inode record will be aligned to full chunk size. We must * prevent sparse allocation from AG boundaries that result in
Good catch.
Re: [PATCH 2/2] xfs: consistent low ag space behavior for sparse inode chunk allocs
In reply to Brian FosterHi Brian,
Quoted 20 lines · Brian Foster
Matt Fleming reports a filesystem shutdown due to inobt block allocation failure during sparse chunk allocation. Inode creation can involve multiple allocations in a transaction via the initial chunk allocation and inode btree growth via the subsequent inobt record insertion. Technically this should be safe as the chunk allocation sets the allocation minleft parameter to the max depth of the inode btree, which means the allocation selects an AG only if there is enough free space for record insertion after the allocation. The record insertion naturally occurs in the same AG as the allocation and the associated AGF is locked and held by the current transaction.
The situation that reproduces this failure is a bit of a corner case. The allocation and inode btrees are all completely full and require a split on the next insertion. The AG has just enough available space to satisfy inode creation through sparse allocation (i.e. 7 blocks in this example). The block allocation occurs within an existing free space record, splitting the free space record into two and triggering the aforementioned allocbt splits.
Quoted 9 lines
The sparse chunk allocation consumes 4 blocks for the chunk, and 4 blocks from the AGFL for the two allocbt splits. This leaves the AGFL with 4 remaining blocks and 3 available blocks in the AG. The record insertion attempts block allocation for the inobt split, but even though space is available, the geometry change has changed the minimum allocation requirements enforced by
xfs_alloc_fix_freelist(). The min freelist value jumps from 8 to 12 due to the alloc btree level increases, so the available space calculation goes from something like this before the allocation:
Ok, in my own words, the problem is that the minleft takes into account the space needed by the inobt/finobt allocations, but the allocator doesn't take into account that the AGFL requirement may increase for the second allocation in the transaction because the first allocation split the free space trees?
Is that an accurate summary of the issue?
If that is the case, then I think the root cause of the issue is that amount we are reserving for the AGFL on the first transaction is insufficient. ENOSPC needs to be detected before we modify anything, so it has to be done at the first allocation. However, it appears to be based on the current level of the bno/cnt btrees, not the potential for the level to increase and the AGFL require a larger block reservation than we've accounted for with minleft.
Therefore, we need to account for the AGFL demand increase in the first reservation that might occur for the second (and subsequent allocations.
i.e. if minleft != 0, then the agfl btree block reservations need to be done for (current level + 1) to take into account space for the trees to split during the dependent allocation chain that minleft != 0 implies is about to occur.
This isn't an issue just for inobt/finobt blocks on inode chunk alloc, it's also an issue for anything that sets minleft for a dependent, multi-allocation operation (e.g. data extent allocation + BMBT block allocation).
So from this perspective, I think the fix needs to be made to the calculation in xfs_alloc_min_freelist() to take into account minleft needing a larger AGFL reservation if any of the allocations in the chain splits.
Hmmmm. I'm not sure the calculation in xfs_alloc_min_freelist() is correct, either:
/*
* For a btree shorter than the maximum height, the worst case is that
* every level gets split and a new level is added, then while inserting
* another entry to refill the AGFL, every level under the old root gets
* split again. This is:
*
* (full height split reservation) + (AGFL refill split height)
* = (current height + 1) + (current height - 1)
* = (new height) + (new height - 2)
* = 2 * new height - 2
i.e. I think the AGFL refill split height is wrong.
Look at it this way: we do the AGFL refill -first-, so if that splits, we consume (current height + 1) blocks, and then new_height = (current height + 1). Then if the actual data allocation does a full split again (i.e. all except for the root block), that needs (new_height -1) blocks. So that becomes:
new_height = current height + 1; blocks = new_height + (new_height - 1) = 2 * new_height - 1.
IOWs, I think there's an existing off-by one in the AGFL btree block reservation calculation that contributes to this problem as well.
Put these two things together:
/*
* if minleft is set, we are going to do multiple * allocations in this
* transaction (e.g. inode chunk followed by inobt). Hence
* we need to make sure we have enough space for fixing up
* the freelists after the split as the btree level
* increases the AGFL reservation size mid-transaction. If
* we are close to ENOSPC, this AGFL reservation increase may
* trigger ENOSPC from the subsequent allocation attempt,
* and then we shutdown the filesystem. Hence if minleft is
* set, reserve enough AGFL space for a potential split
* during the allocation chain in this transaction up front.
*/
split_space = 1;
if (minleft)
split_space = 2;
/* space needed by-bno freespace btree */
min_free = min(bno_level + split_space, mp->m_alloc_maxlevels) * 2 - 1;
/* space needed by-size freespace btree */
min_free += min(cnt_level + split_space, mp->m_alloc_maxlevels) * 2 - 1;
/* space needed reverse mapping used space btree */
if (xfs_has_rmapbt(mp))
min_free += min(rmap_level + split_space, mp->m_rmap_maxlevels) * 2 - 1;
return min_free;This is all off the top of my head, I haven't verified it so it'll need checking. However, I think handling this situation generically in the allocator is a better solution than trying to work around it with caller-based minleft heuristics.
Cheers,
Dave.
Signature · 2 lines
Dave Chinner [email protected]
Re: [PATCH 2/2] xfs: consistent low ag space behavior for sparse inode chunk allocs
Quoted 33 lines · Dave Chinner
Hi Brian,
Quoted 20 lines · Brian Foster
Matt Fleming reports a filesystem shutdown due to inobt block allocation failure during sparse chunk allocation. Inode creation can involve multiple allocations in a transaction via the initial chunk allocation and inode btree growth via the subsequent inobt record insertion. Technically this should be safe as the chunk allocation sets the allocation minleft parameter to the max depth of the inode btree, which means the allocation selects an AG only if there is enough free space for record insertion after the allocation. The record insertion naturally occurs in the same AG as the allocation and the associated AGF is locked and held by the current transaction.
The situation that reproduces this failure is a bit of a corner case. The allocation and inode btrees are all completely full and require a split on the next insertion. The AG has just enough available space to satisfy inode creation through sparse allocation (i.e. 7 blocks in this example). The block allocation occurs within an existing free space record, splitting the free space record into two and triggering the aforementioned allocbt splits.
Quoted 9 lines
The sparse chunk allocation consumes 4 blocks for the chunk, and 4 blocks from the AGFL for the two allocbt splits. This leaves the AGFL with 4 remaining blocks and 3 available blocks in the AG. The record insertion attempts block allocation for the inobt split, but even though space is available, the geometry change has changed the minimum allocation requirements enforced by
xfs_alloc_fix_freelist(). The min freelist value jumps from 8 to 12 due to the alloc btree level increases, so the available space calculation goes from something like this before the allocation:
Quoted 8 lines
Ok, in my own words, the problem is that the minleft takes into account the space needed by the inobt/finobt allocations, but the allocator doesn't take into account that the AGFL requirement may increase for the second allocation in the transaction because the first allocation split the free space trees?
Is that an accurate summary of the issue?
Yup.
Quoted 8 lines
If that is the case, then I think the root cause of the issue is that amount we are reserving for the AGFL on the first transaction is insufficient. ENOSPC needs to be detected before we modify anything, so it has to be done at the first allocation. However, it appears to be based on the current level of the bno/cnt btrees, not the potential for the level to increase and the AGFL require a larger block reservation than we've accounted for with minleft.
Quoted 9 lines
Therefore, we need to account for the AGFL demand increase in the first reservation that might occur for the second (and subsequent allocations.
i.e. if minleft != 0, then the agfl btree block reservations need to be done for (current level + 1) to take into account space for the trees to split during the dependent allocation chain that minleft != 0 implies is about to occur.
Ok, this more aligns with what the LLM had suggested, at least in terms of fixing the problem at the first AGFL check via the minfree calculation. IIRC it wanted to bump minleft internally and that came out rather uglier than bumping min_free (as below).
Quoted 5 lines
This isn't an issue just for inobt/finobt blocks on inode chunk alloc, it's also an issue for anything that sets minleft for a dependent, multi-allocation operation (e.g. data extent allocation + BMBT block allocation).
Yeah, I noticed we had a handful of other cases that use minleft like this. I wonder if the main reason we don't hit this from the bmapi path is that it's usually open to multiple AGs for bmbt allocs and not fixed to a single AG like inode chunk and corresponding inobt block allocs obviously are.
Quoted 27 lines
So from this perspective, I think the fix needs to be made to the calculation in
xfs_alloc_min_freelist()to take into account minleft needing a larger AGFL reservation if any of the allocations in the chain splits.Hmmmm. I'm not sure the calculation in
xfs_alloc_min_freelist()is correct, either:/*
* For a btree shorter than the maximum height, the worst case is that
* every level gets split and a new level is added, then while inserting
* another entry to refill the AGFL, every level under the old root gets
* split again. This is:
*
* (full height split reservation) + (AGFL refill split height)
* = (current height + 1) + (current height - 1)
* = (new height) + (new height - 2)
* = 2 * new height - 2i.e. I think the AGFL refill split height is wrong.
Look at it this way: we do the AGFL refill -first-, so if that splits, we consume (current height + 1) blocks, and then
new_height= (current height + 1). Then if the actual data allocation does a full split again (i.e. all except for the root block), that needs (new_height-1) blocks. So that becomes:
Quoted 7 lines
new_height = current height + 1; blocks = new_height + (new_height - 1) = 2 * new_height - 1.IOWs, I think there's an existing off-by one in the AGFL btree block reservation calculation that contributes to this problem as well.
Hmm.. I need to stare at this a little more, but I think that makes sense.
Quoted 27 lines
Put these two things together:
/* * if minleft is set, we are going to do multiple * allocations in this * transaction (e.g. inode chunk followed by inobt). Hence * we need to make sure we have enough space for fixing up * the freelists after the split as the btree level * increases the AGFL reservation size mid-transaction. If * we are close to ENOSPC, this AGFL reservation increase may * trigger ENOSPC from the subsequent allocation attempt, * and then we shutdown the filesystem. Hence if minleft is * set, reserve enough AGFL space for a potential split * during the allocation chain in this transaction up front. */ split_space = 1; if (minleft) split_space = 2; /* space needed by-bno freespace btree */ min_free = min(bno_level + split_space, mp->m_alloc_maxlevels) * 2 - 1; /* space needed by-size freespace btree */ min_free += min(cnt_level + split_space, mp->m_alloc_maxlevels) * 2 - 1; /* space needed reverse mapping used space btree */ if (xfs_has_rmapbt(mp)) min_free += min(rmap_level + split_space, mp->m_rmap_maxlevels) * 2 - 1; return min_free;
Quoted 5 lines
This is all off the top of my head, I haven't verified it so it'll need checking. However, I think handling this situation generically in the allocator is a better solution than trying to work around it with caller-based minleft heuristics.
I think this is reasonable. The thing that stands out a little bit is that technically we're reserving for the worst case min_free allocation requirement of the second alloc, not necessarily the actual number of blocks needed, right? That seems fine if so. I just want to make sure we're clear and we document the updated calculation appropriately (i.e. noting how minleft > 0 is a somewhat special case).
The off-by-one thing aside, IIUC the current min_free calculation correctly accounts the actual number of blocks we'd consume in the worst case for both allocations, it just doesn't account for how the min_free requirements change upon reentry into the allocator after a minleft > 0 allocation.
I'll throw some testing at this. Thanks for the feedback.
Brian
Quoted 8 lines
Cheers,
Dave.
Signature · 2 lines
Dave Chinner [email protected]
Re: [PATCH 2/2] xfs: consistent low ag space behavior for sparse inode chunk allocs
Quoted 13 lines · Brian Foster
Quoted 12 lines · Dave Chinner
Quoted 11 lines · Brian Foster
Matt Fleming reports a filesystem shutdown due to inobt block allocation failure during sparse chunk allocation. Inode creation can involve multiple allocations in a transaction via the initial chunk allocation and inode btree growth via the subsequent inobt record insertion. Technically this should be safe as the chunk allocation sets the allocation minleft parameter to the max depth of the inode btree, which means the allocation selects an AG only if there is enough free space for record insertion after the allocation. The record insertion naturally occurs in the same AG as the allocation and the associated AGF is locked and held by the current transaction.
[snip]
Quoted 10 lines
Quoted 5 lines
i.e. if minleft != 0, then the agfl btree block reservations need to be done for (current level + 1) to take into account space for the trees to split during the dependent allocation chain that minleft != 0 implies is about to occur.
Ok, this more aligns with what the LLM had suggested, at least in terms of fixing the problem at the first AGFL check via the minfree calculation. IIRC it wanted to bump minleft internally and that came out rather uglier than bumping
min_free(as below).
Yeah, sounds pretty normal LLM analysis -> fix progression to me.
IME, LLMs often get close to the right solution, but they lack the subject matter expertise and/or the deep abstract thinking needed to understand that the problem is in the underlying behavioural constraints rather than the context triggering the issue.
Hence they output hacks to address the symptom the problematic context displays rather than a proper fix for the underlying issue...
Quoted 11 lines
Quoted 5 lines
This isn't an issue just for inobt/finobt blocks on inode chunk alloc, it's also an issue for anything that sets minleft for a dependent, multi-allocation operation (e.g. data extent allocation + BMBT block allocation).
Yeah, I noticed we had a handful of other cases that use minleft like this. I wonder if the main reason we don't hit this from the bmapi path is that it's usually open to multiple AGs for bmbt allocs and not fixed to a single AG like inode chunk and corresponding inobt block allocs obviously are.
*nod* Seems likely to me.
Also, data extent allocations often have slop in them for alignment on top of the minleft value, so I suspect that AGFL reservation growth could be hidden by the alignment slop that was reserved but not used.
Quoted 31 lines
Quoted 31 lines
So from this perspective, I think the fix needs to be made to the calculation in
xfs_alloc_min_freelist()to take into account minleft needing a larger AGFL reservation if any of the allocations in the chain splits.Hmmmm. I'm not sure the calculation in
xfs_alloc_min_freelist()is correct, either:/*
* For a btree shorter than the maximum height, the worst case is that
* every level gets split and a new level is added, then while inserting
* another entry to refill the AGFL, every level under the old root gets
* split again. This is:
*
* (full height split reservation) + (AGFL refill split height)
* = (current height + 1) + (current height - 1)
* = (new height) + (new height - 2)
* = 2 * new height - 2i.e. I think the AGFL refill split height is wrong.
Look at it this way: we do the AGFL refill -first-, so if that splits, we consume (current height + 1) blocks, and then
new_height= (current height + 1). Then if the actual data allocation does a full split again (i.e. all except for the root block), that needs (new_height-1) blocks. So that becomes:new_height = current height + 1; blocks = new_height + (new_height - 1) = 2 * new_height - 1.
Quoted 6 lines
Quoted 3 lines
IOWs, I think there's an existing off-by one in the AGFL btree block reservation calculation that contributes to this problem as well.
Hmm.. I need to stare at this a little more, but I think that makes sense.
I've thought on it a bit more, too, and I now realise the original code is correct.
I failed to take into account that we can't split the two blocks the old root was split into again - they will be at 50% capacity after the first split, so a split up to one of their child nodes will only add one more ptr to them. They can't fill and split again in the current transaction chain.
Hence the second split can only occur up to (current height - 1), and so the existing calculation is correct.
[snip]
Quoted 7 lines
I think this is reasonable. The thing that stands out a little bit is that technically we're reserving for the worst case
min_freeallocation requirement of the second alloc, not necessarily the actual number of blocks needed, right? That seems fine if so. I just want to make sure we're clear and we document the updated calculation appropriately (i.e. noting how minleft > 0 is a somewhat special case).
Quoted 5 lines
The off-by-one thing aside, IIUC the current
min_freecalculation correctly accounts the actual number of blocks we'd consume in the worst case for both allocations, it just doesn't account for how themin_freerequirements change upon reentry into the allocator after a minleft > 0 allocation.
Right, that's my understanding of the issue - that min_free is an up front worst case reservation to prevent downstream ENOSPC within the AG during the transactional modification that is about to take place.
i.e. it's taken over 30 years for us to realise that the AGFL reservation could change in the middle of a multi-allocation transaction and that the minfree calc has never taken that into account. i.e. this is yet another zero-day bug in the AGFL fixup code...
Cheers,
Dave.
Signature · 2 lines
Dave Chinner [email protected]
Re: [PATCH 2/2] xfs: consistent low ag space behavior for sparse inode chunk allocs
Quoted 30 lines · Dave Chinner
Quoted 13 lines · Brian Foster
Quoted 12 lines · Dave Chinner
Quoted 11 lines · Brian Foster
Matt Fleming reports a filesystem shutdown due to inobt block allocation failure during sparse chunk allocation. Inode creation can involve multiple allocations in a transaction via the initial chunk allocation and inode btree growth via the subsequent inobt record insertion. Technically this should be safe as the chunk allocation sets the allocation minleft parameter to the max depth of the inode btree, which means the allocation selects an AG only if there is enough free space for record insertion after the allocation. The record insertion naturally occurs in the same AG as the allocation and the associated AGF is locked and held by the current transaction.
[snip]
Quoted 10 lines
Quoted 5 lines
i.e. if minleft != 0, then the agfl btree block reservations need to be done for (current level + 1) to take into account space for the trees to split during the dependent allocation chain that minleft != 0 implies is about to occur.
Ok, this more aligns with what the LLM had suggested, at least in terms of fixing the problem at the first AGFL check via the minfree calculation. IIRC it wanted to bump minleft internally and that came out rather uglier than bumping
min_free(as below).Yeah, sounds pretty normal LLM analysis -> fix progression to me.
Quoted 9 lines
IME, LLMs often get close to the right solution, but they lack the subject matter expertise and/or the deep abstract thinking needed to understand that the problem is in the underlying behavioural constraints rather than the context triggering the issue.
Hence they output hacks to address the symptom the problematic context displays rather than a proper fix for the underlying issue...
Heh, as it turns out I need to give it a little more credit even. I've run into a couple issues with just bumping min_free as such.
I started hitting xfs/076 failures with this change and observe that this seemed to pretty much defeat the purpose of sparse inodes in this test. I end up seeing -ENOSPC at like 60% usage or something rather than the expected 95%+. Without tracing exactly, I think the issue here is the more aggressive min_free filters down into xfs_alloc_longest_free_extent() and trips up the allocation there.
Before digging too deep into that, the second thing I realized when poking around is that this min_left bump for ->minfree != 0 creates a transient AGFL increase for the uncommon case of full allocbt splits. IOW, every inode chunk allocation would aggressively populate AGFL for the inode chunk alloc and then an inobt record insert alloc (or maybe more likely just the next alloc on the AG) would trim the AGFL back down based on the normal requirement. This may be immediately harmless (i.e. no test failures), but it doesn't feel quite right and wouldn't surprise me a ton if at some point down the road we hear about some obscure allocation regression or some such tied to this spurious behavior.
Anyways, this is all just to say that I think the general design/approach here still applies, but I've tweaked the implementation a bit to store the elevated AGFL requirement in ->minleft instead of minfree so that it only affects the AG selection in the first alloc and doesn't lead to real AGFL state changes unless really necessary in the followup alloc. So far this seems to prevent both the original shutdown problem and allows sparse inodes to remain working as intended..
Getting back to the LLM.. this is kind of what it wanted to do initially, but still with a worse (IMO) implementation. I don't know if that was luck or through real analysis, but that question is not all that unique to LLMs either. ;)
Brian
Quoted 102 lines
Quoted 11 lines
Quoted 5 lines
This isn't an issue just for inobt/finobt blocks on inode chunk alloc, it's also an issue for anything that sets minleft for a dependent, multi-allocation operation (e.g. data extent allocation + BMBT block allocation).
Yeah, I noticed we had a handful of other cases that use minleft like this. I wonder if the main reason we don't hit this from the bmapi path is that it's usually open to multiple AGs for bmbt allocs and not fixed to a single AG like inode chunk and corresponding inobt block allocs obviously are.
*nod* Seems likely to me.
Also, data extent allocations often have slop in them for alignment on top of the minleft value, so I suspect that AGFL reservation growth could be hidden by the alignment slop that was reserved but not used.
Quoted 31 lines
Quoted 31 lines
So from this perspective, I think the fix needs to be made to the calculation in
xfs_alloc_min_freelist()to take into account minleft needing a larger AGFL reservation if any of the allocations in the chain splits.Hmmmm. I'm not sure the calculation in
xfs_alloc_min_freelist()is correct, either:/*
* For a btree shorter than the maximum height, the worst case is that
* every level gets split and a new level is added, then while inserting
* another entry to refill the AGFL, every level under the old root gets
* split again. This is:
*
* (full height split reservation) + (AGFL refill split height)
* = (current height + 1) + (current height - 1)
* = (new height) + (new height - 2)
* = 2 * new height - 2i.e. I think the AGFL refill split height is wrong.
Look at it this way: we do the AGFL refill -first-, so if that splits, we consume (current height + 1) blocks, and then
new_height= (current height + 1). Then if the actual data allocation does a full split again (i.e. all except for the root block), that needs (new_height-1) blocks. So that becomes:new_height = current height + 1; blocks = new_height + (new_height - 1) = 2 * new_height - 1.Quoted 6 lines
Quoted 3 lines
IOWs, I think there's an existing off-by one in the AGFL btree block reservation calculation that contributes to this problem as well.
Hmm.. I need to stare at this a little more, but I think that makes sense.
I've thought on it a bit more, too, and I now realise the original code is correct.
I failed to take into account that we can't split the two blocks the old root was split into again - they will be at 50% capacity after the first split, so a split up to one of their child nodes will only add one more ptr to them. They can't fill and split again in the current transaction chain.
Hence the second split can only occur up to (current height - 1), and so the existing calculation is correct.
[snip]
Quoted 7 lines
I think this is reasonable. The thing that stands out a little bit is that technically we're reserving for the worst case
min_freeallocation requirement of the second alloc, not necessarily the actual number of blocks needed, right? That seems fine if so. I just want to make sure we're clear and we document the updated calculation appropriately (i.e. noting how minleft > 0 is a somewhat special case).Quoted 5 lines
The off-by-one thing aside, IIUC the current
min_freecalculation correctly accounts the actual number of blocks we'd consume in the worst case for both allocations, it just doesn't account for how themin_freerequirements change upon reentry into the allocator after a minleft > 0 allocation.Right, that's my understanding of the issue - that
min_freeis an up front worst case reservation to prevent downstream ENOSPC within the AG during the transactional modification that is about to take place.i.e. it's taken over 30 years for us to realise that the AGFL reservation could change in the middle of a multi-allocation transaction and that the minfree calc has never taken that into account. i.e. this is yet another zero-day bug in the AGFL fixup code...
Cheers,
Dave.
Signature · 2 lines
Dave Chinner [email protected]