bringing back the AGFL reserve
RFC PATCH 3/4 xfs: let allocations tap the AGFL reserve
In reply to Krister JohansenIn the case where a transaction is making an allocation after its initial allocation, allow that transaction to tap the AGFL reserve. This is done in case a prior allocation depleted the freelists below their minimum fill and reserve space is needed to finish the transaction. This is predicated on the earlier phases of the allocation enforcing that the AGFL reserve has sufficient space for the transaction to refill the AGFL. That enforcement is in a separate commit.
--- fs/xfs/libxfs/xfs_alloc.c | 15 ++++++++++++++- 1 file changed, 14 insertions(+), 1 deletion(-)
fs/xfs/libxfs/xfs_alloc.c +14 -1
@@ -2389,6 +2389,7 @@ xfs_alloc_space_available( int flags) {struct xfs_perag *pag = args->pag; +enum xfs_ag_resv_type resv_type = args->resv;xfs_extlen_t alloc_len, longest;xfs_extlen_t reservation;/* blocks that are still reserved */ int available;
@@ -2397,7 +2398,19 @@ xfs_alloc_space_available(if (flags &XFS_ALLOC_FLAG_FREEING )return true; - reservation =xfs_ag_resv_needed (pag, args->resv); +/* +* If this allocation is a subsequent allocation in a transaction with +* multiple allocations, allow it to tap the AGFL reserve in order to +* ensure that it can refill its freelist if a prior transaction has +* depleted it. This is done to ensure that the available space checks +* below don't stop an allocation that's up against the reservation +* space limits when there is AGFL space still reserved and available. +*/ +if (args->tp->t_highest_agno !=NULLAGNUMBER && + args->resv ==XFS_AG_RESV_NONE ) { + resv_type =XFS_AG_RESV_AGFL ; + } + reservation =xfs_ag_resv_needed (pag, resv_type);/* do we have enough contiguous free space for the allocation? */ alloc_len = args->minlen + (args->alignment -1 ) + args->minalignslop;
Signature · 1 line
2.25.1
RFC PATCH 1/4 xfs: resurrect the AGFL reservation
In reply to Krister JohansenTransactions that perform multiple allocations may inadvertently run out of space after the first allocation selects an AG that appears to have enough available space. The problem occurs when the allocation in the transaction splits freespace b-trees but the second allocation does not have enough available space to refill the AGFL. This results in an aborted transaction and a filesystem shutdown. In this author's case, it's frequently encountered in the xfs_bmap_extents_to_btree path on a write to an AG that's almost reached its limits.
The AGFL reservation allows us to save some blocks to refill the AGFL to its minimum level in an Nth allocation, and to prevent allocations from proceeding when there's not enough reserved space to accommodate the refill.
This patch just brings back the reservation and does the plumbing. The policy decisions about which allocations to allow will be in a subsequent patch.
This implementation includes space for the bnobt and cnobt in the reserve. This was done largely because the AGFL reserve stubs appeared to already be doing it this way.
--- fs/xfs/libxfs/xfs_ag.h | 2 ++ fs/xfs/libxfs/xfs_ag_resv.c | 54 ++++++++++++++++++++++-------- fs/xfs/libxfs/xfs_ag_resv.h | 4 +++ fs/xfs/libxfs/xfs_alloc.c | 43 +++++++++++++++++++++++- fs/xfs/libxfs/xfs_alloc.h | 3 +- fs/xfs/libxfs/xfs_alloc_btree.c | 59 +++++++++++++++++++++++++++++++++ fs/xfs/libxfs/xfs_alloc_btree.h | 5 +++ fs/xfs/libxfs/xfs_rmap_btree.c | 5 +++ fs/xfs/scrub/fscounters.c | 1 + 9 files changed, 161 insertions(+), 15 deletions(-)
fs/xfs/libxfs/xfs_ag.h +2 -0
@@ -62,6 +62,8 @@ struct xfs_perag {struct xfs_ag_resv pag_meta_resv;/* Blocks reserved for the reverse mapping btree. */ struct xfs_ag_resv pag_rmapbt_resv; +/* Blocks reserved for the AGFL. */ +struct xfs_ag_resv pag_agfl_resv;/* for rcu-safe freeing */ struct rcu_head rcu_head;
fs/xfs/libxfs/xfs_ag_resv.c +41 -13
134 lines not on this page · raw message
fs/xfs/libxfs/xfs_ag_resv.h +4 -0
@@ -28,6 +28,8 @@ xfs_perag_resv(return &pag->pag_meta_resv;case XFS_AG_RESV_RMAPBT :return &pag->pag_rmapbt_resv; +case XFS_AG_RESV_AGFL : +return &pag->pag_agfl_resv;default :return NULL ; }
@@ -48,6 +50,8 @@ xfs_ag_resv_rmapbt_alloc( args.len =1 ; pag =xfs_perag_get (mp, agno); +/* Transfer this reservation from the AGFL to RMAPBT */ +xfs_ag_resv_free_extent (pag,XFS_AG_RESV_AGFL ,NULL ,1 );xfs_ag_resv_alloc_extent (pag,XFS_AG_RESV_RMAPBT , &args);xfs_perag_put (pag); }
fs/xfs/libxfs/xfs_alloc.c +42 -1
66 lines not on this page · raw message
fs/xfs/libxfs/xfs_alloc.h +2 -1
@@ -80,7 +80,8 @@ int xfs_alloc_get_freelist(struct xfs_perag *pag, struct xfs_trans *tp,int xfs_alloc_put_freelist (struct xfs_perag *pag,struct xfs_trans *tp,struct xfs_buf *agfbp,struct xfs_buf *agflbp,xfs_agblock_t bno,int btreeblk); - +int xfs_alloc_agfl_calc_reserves (struct xfs_mount *mp,struct xfs_trans *tp, +struct xfs_perag *pag,xfs_extlen_t *ask,xfs_extlen_t *used);/* * Compute and fill in value of m_alloc_maxlevels. */
fs/xfs/libxfs/xfs_alloc_btree.c +59 -0
65 lines not on this page · raw message
fs/xfs/libxfs/xfs_alloc_btree.h +5 -0
@@ -56,6 +56,11 @@ struct xfs_btree_cur *xfs_cntbt_init_cursor(struct xfs_mount *mp,extern int xfs_allocbt_maxrecs (struct xfs_mount *,int ,int );extern xfs_extlen_t xfs_allocbt_calc_size (struct xfs_mount *mp,unsigned long long len); +extern xfs_extlen_t xfs_allocbt_max_size (struct xfs_mount *mp, +xfs_agblock_t agblocks); + +extern int xfs_allocbt_calc_reserves (struct xfs_mount *mp,struct xfs_trans *tp, +struct xfs_perag *pag,xfs_extlen_t *ask,xfs_extlen_t *used);void xfs_allocbt_commit_staged_btree (struct xfs_btree_cur *cur,struct xfs_trans *tp,struct xfs_buf *agbp);
fs/xfs/libxfs/xfs_rmap_btree.c +5 -0
@@ -121,6 +121,7 @@ xfs_rmapbt_free_block(struct xfs_buf *agbp = cur->bc_ag.agbp;struct xfs_agf *agf = agbp->b_addr;struct xfs_perag *pag = cur->bc_ag.pag; +struct xfs_alloc_arg args = {NULL };xfs_agblock_t bno;int error;
@@ -135,6 +136,10 @@ xfs_rmapbt_free_block( XFS_EXTENT_BUSY_SKIP_DISCARD);xfs_ag_resv_free_extent (pag,XFS_AG_RESV_RMAPBT ,NULL ,1 ); + args.len =1 ; +/* Transfer this reservation back to the AGFL. */ +xfs_ag_resv_alloc_extent (pag,XFS_AG_RESV_AGFL , &args); +return 0 ; }
fs/xfs/scrub/fscounters.c +1 -0
@@ -338,6 +338,7 @@ xchk_fscount_aggregate_agcounts(*/ fsc->fdblocks -= pag->pag_meta_resv.ar_reserved; fsc->fdblocks -= pag->pag_rmapbt_resv.ar_orig_reserved; + fsc->fdblocks -= pag->pag_agfl_resv.ar_orig_reserved; }if (pag)
Signature · 1 line
2.25.1
RFC PATCH 4/4 xfs: refuse allocations without agfl refill space
In reply to Krister JohansenEnsure that an allocation that may be part of a multiple-allocation transaction has enough space in the AGFL reserve to refill the AGFL in a subsequent transaction. The AGFL reserve was established to make sure that there is enough space reserved for multiple allocation transactions to use this space to refill the AGFL close to ENOSPC.
Check an allocation against this reserve and refuse to let it proceed if the AGFL reserve cannot meet the needs of a subsequent allocation. Without this, the second transaction may ENOSPC if the first uses all of the AGFL blocks and the AG is close enough to the limits that it cannot refill.
--- fs/xfs/libxfs/xfs_alloc.c | 17 +++++++++++++++++ 1 file changed, 17 insertions(+)
fs/xfs/libxfs/xfs_alloc.c +17 -0
@@ -2389,11 +2389,13 @@ xfs_alloc_space_available( int flags) {struct xfs_perag *pag = args->pag; +struct xfs_ag_resv *resv;enum xfs_ag_resv_type resv_type = args->resv;xfs_extlen_t alloc_len, longest;xfs_extlen_t reservation;/* blocks that are still reserved */ int available;xfs_extlen_t agflcount; +unsigned int agfl_refill;if (flags &XFS_ALLOC_FLAG_FREEING )return true;
@@ -2429,6 +2431,21 @@ xfs_alloc_space_available(if (available < (int )max (args->total, alloc_len))return false; +/* +* If this is the first allocation in a transaction that may perform +* multiple allocations, check the AGFL reserve to see if it contains +* enough blocks to refill the AGFL if freespace b-trees split as part +* of the first allocation. This is done to ensure that subsequent +* allocations can utilize the reserve space instead of running out and +* triggering a shutdown. +*/ +if (args->tp->t_highest_agno ==NULLAGNUMBER && args->minleft >0 ) { + agfl_refill =xfs_alloc_min_freelist (args->mp, pag,1 ); + resv =xfs_perag_resv (pag,XFS_AG_RESV_AGFL ); +if (resv->ar_asked >0 && agfl_refill > resv->ar_reserved) +return false; + } +/* * Clamp maxlen to the amount of free space available for the actual * extent allocation.
Signature · 1 line
2.25.1
RFC PATCH 2/4 xfs: modify xfs_alloc_min_freelist to take an increment
In reply to Krister Johansenxfs_alloc_min_freelist is used to determine the minimum size for the AGFL based upon the current height of the bnobt, cnobt, and rmapbt.
In order to determine how much space needs to be in the AGFL reserve in order to permit a transacation that may perform multiple allocations, it is necessary to also know the minimum size of the AGFL after trees are split and the level has incremented.
Let xfs_alloc_min_freelist take an increment so that callers may request the minimum AGFL size based upon current + N.
This patch has no functional change. A subsequent patch will bring new users.
--- fs/xfs/libxfs/xfs_alloc.c | 21 +++++++++++++-------- fs/xfs/libxfs/xfs_alloc.h | 2 +- fs/xfs/libxfs/xfs_bmap.c | 2 +- fs/xfs/libxfs/xfs_ialloc.c | 2 +- 4 files changed, 16 insertions(+), 11 deletions(-)
fs/xfs/libxfs/xfs_alloc.c +13 -8
@@ -2325,17 +2325,22 @@ xfs_alloc_longest_free_extent(/* * Compute the minimum length of the AGFL in the given AG. If @pag is NULL, -* return the largest possible minimum length. +* return the largest possible minimum length. If @level_inc is greater than +* zero, increment the level being computed by cur + level_inc. */ unsigned int xfs_alloc_min_freelist (struct xfs_mount *mp, -struct xfs_perag *pag) +struct xfs_perag *pag, +unsigned int level_inc) {/* AG btrees have at least 1 level. */ -const unsigned int bno_level = pag ? pag->pagf_bno_level :1 ; -const unsigned int cnt_level = pag ? pag->pagf_cnt_level :1 ; -const unsigned int rmap_level = pag ? pag->pagf_rmap_level :1 ; +const unsigned int bno_level = + pag ? pag->pagf_bno_level + level_inc :1 ; +const unsigned int cnt_level = + pag ? pag->pagf_cnt_level + level_inc :1 ; +const unsigned int rmap_level = + pag ? pag->pagf_rmap_level + level_inc :1 ;unsigned int min_free;ASSERT (mp->m_alloc_maxlevels >0 );
@@ -2803,7 +2808,7 @@ xfs_alloc_agfl_calc_reserves(return error; agf = agbp->b_addr; - agfl_blocks =xfs_alloc_min_freelist (mp,NULL ); + agfl_blocks =xfs_alloc_min_freelist (mp,NULL ,0 ); list_len =be32_to_cpu (agf->agf_flcount);xfs_trans_brelse (tp, agbp);
@@ -2861,7 +2866,7 @@ xfs_alloc_fix_freelist( goto out_agbp_relse; } - need =xfs_alloc_min_freelist (mp, pag); + need =xfs_alloc_min_freelist (mp, pag,0 );if (!xfs_alloc_space_available (args, need, alloc_flags |XFS_ALLOC_FLAG_CHECK )) goto out_agbp_relse;
@@ -2885,7 +2890,7 @@ xfs_alloc_fix_freelist(xfs_agfl_reset (tp, agbp, pag);/* If there isn't enough total space or single-extent, reject it. */ - need =xfs_alloc_min_freelist (mp, pag); + need =xfs_alloc_min_freelist (mp, pag,0 );if (!xfs_alloc_space_available (args, need, alloc_flags)) goto out_agbp_relse;
fs/xfs/libxfs/xfs_alloc.h +1 -1
@@ -74,7 +74,7 @@ unsigned int xfs_alloc_ag_max_usable(struct xfs_mount *mp);xfs_extlen_t xfs_alloc_longest_free_extent (struct xfs_perag *pag,xfs_extlen_t need,xfs_extlen_t reserved);unsigned int xfs_alloc_min_freelist (struct xfs_mount *mp, -struct xfs_perag *pag); +struct xfs_perag *pag,unsigned int level_inc);int xfs_alloc_get_freelist (struct xfs_perag *pag,struct xfs_trans *tp,struct xfs_buf *agfbp,xfs_agblock_t *bnop,int btreeblk); int xfs_alloc_put_freelist(struct xfs_perag *pag, struct xfs_trans *tp,
fs/xfs/libxfs/xfs_bmap.c +1 -1
@@ -3270,7 +3270,7 @@ xfs_bmap_longest_free_extent( } longest =xfs_alloc_longest_free_extent (pag, -xfs_alloc_min_freelist (pag->pag_mount, pag), +xfs_alloc_min_freelist (pag->pag_mount, pag,0 ),xfs_ag_resv_needed (pag,XFS_AG_RESV_NONE ));if (*blen < longest) *blen = longest;
fs/xfs/libxfs/xfs_ialloc.c +1 -1
@@ -3047,7 +3047,7 @@ xfs_ialloc_calc_rootino( first_bno +=1 ;/* ...the initial AGFL... */ - first_bno +=xfs_alloc_min_freelist (mp,NULL ); + first_bno +=xfs_alloc_min_freelist (mp,NULL ,0 );/* ...the free inode btree root... */ if (xfs_has_finobt (mp))
Signature · 1 line
2.25.1
cover bringing back the AGFL reserve
Hi,
One of the teams that I work with hits WARNs in xfs_bmap_extents_to_btree() on a database workload of theirs. The last time the subject came up on linux-xfs, it was suggested[1] to try building an AG reserve pool for the AGFL.
I managed to work out a reproducer for the problem. Debugging that, the steps Gao outlined turned out to be essentially what was necessary to get the problem to happen repeatably.
1. Allocate almost all of the space in an AG
2. Free and reallocate that space to fragement it so the freespace b-trees are just about to split.
3. Allocate blocks in a file such that the next extent allocated for that file will cause its bmbt to get converted from an inline extent to a b-tree.
4. Free space such that the free-space btrees have a contiguous extent with a busy portion on either end
5. Allocate the portion in the middle, splitting the extent and triggering a b-tree split.
On older kernels this is all it takes. After the AG-aware allocator changes I also need to start the allocation in the highest numbered AG available while inducing lock contention in the lower numbered AGs.
In order to ensure that AGs have enough space to complete transactions with multiple allocations, I've taken a stab at implementing an AGFL reserve pool.
This patchset passes fstests without any regressions and also does not trigger the reproducers I wrote for the case above. I've also run those with tracing enabled to validate that it's got the accounting correct, is rejecting allocations when there's no space in the reserve, and is tapping the reserve when appropriate.
The first patch is the plumbing that re-establishes the reserve for the AGFL. I'm happy to break this into something smaller, if it's too large. The remaining patches add additional pieces needed to check how much space the AGFL might need on a refill, and then to actually use the reserve to permit or deny allocation requests, as the case may be.
I'm sending this as an RFC, since I still have a few outstanding questions and would appreciate feedback.
Some of those questions are:
Patch 1 includes all freespace that is not allocated to the rmapbt in its used / reserved accounting. It also borrows the heuristics from rmapbt in terms of picking the initial size of the reservation. The numbers I'm getting seem a bit large. Any suggestions about how to improve this further?
Patches 3 and 4 use the allocation args structure to attempt to decide whether an allocation is the first in a transaction, or if its a subsequent allocation. Are there any recommendations about a better way to do this?
Thanks,
-K
[1] https://lore.kernel.org/linux-xfs/[email protected]/
Krister Johansen (4):
xfs: resurrect the AGFL reservation
xfs: modify xfs_alloc_min_freelist to take an increment
xfs: let allocations tap the AGFL reserve
xfs: refuse allocations without agfl refill space
fs/xfs/libxfs/xfs_ag.h | 2 + fs/xfs/libxfs/xfs_ag_resv.c | 54 ++++++++++++++----- fs/xfs/libxfs/xfs_ag_resv.h | 4 ++ fs/xfs/libxfs/xfs_alloc.c | 94 +++++++++++++++++++++++++++++---- fs/xfs/libxfs/xfs_alloc.h | 5 +- fs/xfs/libxfs/xfs_alloc_btree.c | 59 +++++++++++++++++++++ fs/xfs/libxfs/xfs_alloc_btree.h | 5 ++ fs/xfs/libxfs/xfs_bmap.c | 2 +- fs/xfs/libxfs/xfs_ialloc.c | 2 +- fs/xfs/libxfs/xfs_rmap_btree.c | 5 ++ fs/xfs/scrub/fscounters.c | 1 + 11 files changed, 207 insertions(+), 26 deletions(-)
base-commit: 58f880711f2ba53fd5e959875aff5b3bf6d5c32e
Signature · 1 line
2.25.1
Quoted 10 lines · Krister Johansen
Hi,
One of the teams that I work with hits WARNs inxfs_bmap_extents_to_btree()on a database workload of theirs. The last time the subject came up on linux-xfs, it was suggested[1] to try building an AG reserve pool for the AGFL.I managed to work out a reproducer for the problem. Debugging that, the steps Gao outlined turned out to be essentially what was necessary to get the problem to happen repeatably.
Quoted 10 lines
1. Allocate almost all of the space in an AG
2. Free and reallocate that space to fragement it so the freespace b-trees are just about to split.
3. Allocate blocks in a file such that the next extent allocated for that file will cause its bmbt to get converted from an inline extent to a b-tree.
4. Free space such that the free-space btrees have a contiguous extent with a busy portion on either end
5. Allocate the portion in the middle, splitting the extent and triggering a b-tree split.
Do you have a script that sets up this precondition reliably? It sounds like it can be done from a known filesystem config. If you do have a script, can you share it? Or maybe even better, turn it into an fstest?
Quoted 3 lines
On older kernels this is all it takes. After the AG-aware allocator changes I also need to start the allocation in the highest numbered AG available while inducing lock contention in the lower numbered AGs.
Ah, so you have to perform a DOS on the lower AGFs so that the attempts made by the xfs_alloc_vextent_start_ag() to trylock the lower AGFs once it finds it cannot allocate in the highest AG anymore also fail.
That was one of the changes made in the perag aware allocator rework; it added full-range AG iteration when XFS_ALLOC_FLAG_TRYLOCK is set because we can't deadlock on reverse order AGF locking when using trylocks.
However, if the trylock iteration fails, it then sets the restart AG to the minimum AG be can wait for without deadlocking, removes the trylock and restarts the iteration. Hence you've had to create AGF lock contention to force the allocator back to being restricted by the AGF locking orders.
Is this new behaviour sufficient to mitigate the problem being seen with this database workload? Has it been tested with kernels that have those changes, and if so did it have any impact on the frequency of the issue occurring?
Quoted 3 lines
In order to ensure that AGs have enough space to complete transactions with multiple allocations, I've taken a stab at implementing an AGFL reserve pool.
OK. I'll comment directly on the code from here, hopefully I'll address your other questions in those comments.
-Dave.
Signature · 2 lines
Dave Chinner [email protected]
Re: [RFC PATCH 1/4] xfs: resurrect the AGFL reservation
In reply to Krister JohansenQuoted 39 lines · Krister Johansen
Transactions that perform multiple allocations may inadvertently run out of space after the first allocation selects an AG that appears to have enough available space. The problem occurs when the allocation in the transaction splits freespace b-trees but the second allocation does not have enough available space to refill the AGFL. This results in an aborted transaction and a filesystem shutdown. In this author's case, it's frequently encountered in the
xfs_bmap_extents_to_btreepath on a write to an AG that's almost reached its limits.The AGFL reservation allows us to save some blocks to refill the AGFL to its minimum level in an Nth allocation, and to prevent allocations from proceeding when there's not enough reserved space to accommodate the refill.
This patch just brings back the reservation and does the plumbing. The policy decisions about which allocations to allow will be in a subsequent patch.
This implementation includes space for the bnobt and cnobt in the reserve. This was done largely because the AGFL reserve stubs appeared to already be doing it this way.
Signed-off-by Krister Johansen <[email protected]>--- fs/xfs/libxfs/xfs_ag.h | 2 ++ fs/xfs/libxfs/xfs_ag_resv.c | 54 ++++++++++++++++++++++-------- fs/xfs/libxfs/xfs_ag_resv.h | 4 +++ fs/xfs/libxfs/xfs_alloc.c | 43 +++++++++++++++++++++++- fs/xfs/libxfs/xfs_alloc.h | 3 +- fs/xfs/libxfs/xfs_alloc_btree.c | 59 +++++++++++++++++++++++++++++++++ fs/xfs/libxfs/xfs_alloc_btree.h | 5 +++ fs/xfs/libxfs/xfs_rmap_btree.c | 5 +++ fs/xfs/scrub/fscounters.c | 1 + 9 files changed, 161 insertions(+), 15 deletions(-)fs/xfs/libxfs/xfs_ag.h +0
-0
fs/xfs/libxfs/xfs_ag.h struct xfs_perag { · line 66
Quoted 5 lines
fs/xfs/libxfs/xfs_ag.h +2
-0@@ -62,6 +62,8 @@ struct xfs_perag {struct xfs_ag_resv pag_meta_resv;/* Blocks reserved for the reverse mapping btree. */ struct xfs_ag_resv pag_rmapbt_resv; +/* Blocks reserved for the AGFL. */ +struct xfs_ag_resv pag_agfl_resv;
Ok, so you're creating a new pool for the AGFL refills.
....
Quoted 8 lines
fs/xfs/libxfs/xfs_ag.h +1
-2@@ -180,11 +188,13 @@ __xfs_ag_resv_init(switch (type) {case XFS_AG_RESV_RMAPBT : +case XFS_AG_RESV_AGFL :/* -* Space taken by the rmapbt is not subtracted from fdblocks -* because the rmapbt lives in the free space. Here we must
fs/xfs/libxfs/xfs_ag.h __xfs_ag_resv_init( · line 200
Quoted 10 lines
fs/xfs/libxfs/xfs_ag.h +5
-2-* subtract the entire reservation from fdblocks so that we -* always have blocks available for rmapbt expansion. +* Space taken by the rmapbt and agfl are not subtracted from +* fdblocks because they both live in the free space. Here we +* must subtract the entire reservation from fdblocks so that we +* always have blocks available for rmapbt expansion and agfl +* refilling. */ hidden_space = ask;break ;
And the AGFL and RMAPBT pools have largely the same behaviour.
fs/xfs/libxfs/xfs_ag.h xfs_ag_resv_init( · line 318
Quoted 11 lines
fs/xfs/libxfs/xfs_ag.h +7
-0@@ -299,6 +309,25 @@ xfs_ag_resv_init( has_resv = true; } +/* Create the AGFL reservation */ +if (pag->pag_agfl_resv.ar_asked ==0 ) { + ask = used =0 ; + + error =xfs_allocbt_calc_reserves (mp, tp, pag, &ask, &used); +if (error) + goto out;
I think this is wrong, more below.
Quoted 15 lines
fs/xfs/libxfs/xfs_ag.h +11
-0+ error =xfs_alloc_agfl_calc_reserves (mp, tp, pag, &ask, &used); +if (error) + goto out; + + error =__xfs_ag_resv_init (pag,XFS_AG_RESV_AGFL , ask, used); +if (error) + goto out; +if (ask) + has_resv = true; + } + out:/* * Initialize the pagf if we have at least one active reservation on the
fs/xfs/libxfs/xfs_ag.h xfs_ag_resv_init( · line 360
Quoted 9 lines
fs/xfs/libxfs/xfs_ag.h +2
-1@@ -324,7 +353,8 @@ xfs_ag_resv_init(*/ if (!error &&xfs_perag_resv (pag,XFS_AG_RESV_METADATA )->ar_reserved + -xfs_perag_resv (pag,XFS_AG_RESV_RMAPBT )->ar_reserved > +xfs_perag_resv (pag,XFS_AG_RESV_RMAPBT )->ar_reserved + +xfs_perag_resv (pag,XFS_AG_RESV_AGFL )->ar_reserved > pag->pagf_freeblks + pag->pagf_flcount) error = -ENOSPC ; }
This is now quite hard to read. Perhaps a helper:
xfs_ag_reserved_space(pag)
{
return pag->pag_meta_resv.ar_reserved +
pag->pag_rmapbt_resv.ar_reserved +
pag->pag_agfl_resv.ar_reserved;
}And that can also be used in xfs_ag_resv_needed()....
fs/xfs/libxfs/xfs_ag.h xfs_ag_resv_rmapbt_alloc( · line 57
Quoted 9 lines
fs/xfs/libxfs/xfs_ag.h +2
-0@@ -48,6 +50,8 @@ xfs_ag_resv_rmapbt_alloc( args.len =1 ; pag =xfs_perag_get (mp, agno); +/* Transfer this reservation from the AGFL to RMAPBT */ +xfs_ag_resv_free_extent (pag,XFS_AG_RESV_AGFL ,NULL ,1 );xfs_ag_resv_alloc_extent (pag,XFS_AG_RESV_RMAPBT , &args);xfs_perag_put (pag); }
I have no idea what this is accounting for or why it needs to be done. Comments need to explain why, not repeat what the code is doing.
Quoted 14 lines
fs/xfs/libxfs/xfs_ag.h +14
-0+/* +* Work out how many blocks to reserve for the AGFL as well as how many are in +* use currently. +*/ +int +xfs_alloc_agfl_calc_reserves ( +struct xfs_mount *mp, +struct xfs_trans *tp, +struct xfs_perag *pag, +xfs_extlen_t *ask, +xfs_extlen_t *used) +{ +struct xfs_buf *agbp; +struct xfs_agf *agf;
fs/xfs/libxfs/xfs_ag.h
Quoted 10 lines
fs/xfs/libxfs/xfs_ag.h +10
-0+xfs_extlen_t agfl_blocks; +xfs_extlen_t list_len; +int error; + + error =xfs_alloc_read_agf (pag, tp,0 , &agbp); +if (error) +return error; + + agf = agbp->b_addr; + agfl_blocks =xfs_alloc_min_freelist (mp,NULL );
Why are you passing a NULL for the perag in here? This minimum AGFL blocks we will reserve is for single level btrees.
When we are actually doing an allocation, this calculation returns a block count based on the current height of the btrees, and so the actual AGFL refill size is always going to be larger than the reserves calculated here.
fs/xfs/libxfs/xfs_ag.h
Quoted 1 line
fs/xfs/libxfs/xfs_ag.h +1
-0+ list_len =be32_to_cpu (agf->agf_flcount);
There is no relationship between the minimum AGFL block count and the current number of blocks on the AGFL. The number of blocks on the AGFL can be much larger than the minimum required to perform an allocation (e.g. we just did a series of merges that moved lots of blocks to the AGFL that was already at it's required size).
fs/xfs/libxfs/xfs_ag.h
Quoted 8 lines
fs/xfs/libxfs/xfs_ag.h +8
-0+xfs_trans_brelse (tp, agbp); + +/* +* Reserve enough space to refill AGFL to minimum fullness if btrees are +* at maximum height. +*/ + *ask += agfl_blocks; + *used += list_len;
Hence the above calculations can result in a situation where used > ask, and ask is not large enough for runtime AGFL reservations.
Quoted 15 lines
fs/xfs/libxfs/xfs_alloc_btree.c +7
-0@@ -671,6 +671,65 @@ xfs_allocbt_calc_size(return xfs_btree_calc_size (mp->m_alloc_mnr, len); } +/* +* Calculate the maximum alloc btree size. This is for a single allocbt. +* Callers wishing to compute both the size of the bnobt and cnobt must double +* this result. +*/ +xfs_extlen_t +xfs_allocbt_max_size(
fs/xfs/libxfs/xfs_alloc_btree.c xfs_allocbt_calc_size( · line 690
Quoted 10 lines
fs/xfs/libxfs/xfs_alloc_btree.c +10
-0+ struct xfs_mount *mp, + xfs_agblock_t agblocks) +{ + +/* Don't proceed if uninitialized. Can happen in mkfs. */ +if (mp->m_alloc_mxr[0 ] ==0 ) +return 0 ; + +return xfs_allocbt_calc_size (mp, agblocks); +}
So this is using a block count as the number of records in the btree? And it's returning the number of btree blocks that would be needed to index that number of records?
I'm not sure what you are attempting to calculate here, because...
Quoted 30 lines
fs/xfs/libxfs/xfs_alloc_btree.c +30
-0+/* +* Work out how many blocks to reserve for the bnobt and the cnobt as well as +* how many blocks are in use by these trees. +*/ +int +xfs_allocbt_calc_reserves ( +struct xfs_mount *mp, +struct xfs_trans *tp, +struct xfs_perag *pag, +xfs_extlen_t *ask, +xfs_extlen_t *used) +{ +struct xfs_buf *agbp; +struct xfs_agf *agf; +xfs_agblock_t agblocks; +xfs_extlen_t tree_len; +int error; + + error =xfs_alloc_read_agf (pag, tp,0 , &agbp); +if (error) +return error; + + agf = agbp->b_addr; + agblocks =be32_to_cpu (agf->agf_length); + tree_len =be32_to_cpu (agf->agf_btreeblks); +xfs_trans_brelse (tp, agbp); + +/* +* The log is permanently allocated. The space it occupies will never be +* available for btree expansion. Pretend the space is not there.
fs/xfs/libxfs/xfs_alloc_btree.c xfs_allocbt_calc_size( · line 731
Quoted 10 lines
fs/xfs/libxfs/xfs_alloc_btree.c +10
-0+*/ +if (xfs_ag_contains_log (mp, pag->pag_agno)) + agblocks -= mp->m_sb.sb_logblocks; + +/* Reserve 1% of the AG or enough for one block per record per tree. */ + *ask +=max (agblocks /100 ,2 *xfs_allocbt_max_size (mp, agblocks)); + *used += tree_len; + +return error; +}
... this is passing the AG size into xfs_allocbt_max_size(), but the free space btree cannot have that many records in it. If all the blocks are free, then there will be a single contiguous free space extent record spanning the entire space. That's definitely not what this is calculation results in. :)
I can see why you might be trying to calculate the max number of blocks in the btree - given worst case single block fragmentation, half the space in the AG can be indexed by the free space btree. That's a non-trivial number of records and a decent number of btree blocks to index them, but even then I don't think it's a relevant number to the AGFL reservation size.
The minimum AGFL size is tiny - it's just enough blocks to cover a full height split of each btree that sources blocks from the AGFL. If you point xfs_db at a filesystem and run the btheight command with the length of the AG as the record count, you'll get an idea of the worst case btree heights in the filesystem.
On the workstation I'm typing this one, /home is 1.8TB, has 32 AGs and has reflink and rmap enabled.
The worst case btree heights for both the bno and cnt btrees is 4 levels, and the rmapbt is 5 levels at worst. Hence for any given allocation the worst case AGFL length is going to be ~15 blocks.
Then we need to consider how many times we might have to refill the AGFL in a series of dependent allocations that might be forced into the same AG. i.e. the bmbt splitting during record insertion after a data extent allocation (which I think is the only case this matters)
The bmapbt for the above filesystem has a maximum height of 4 levels. Hence the worst case "data extent + bmbt split" allocation is going to require 1 + ((max bmbt level - 1) + 1) block allocations from the AG. i.e. (max bmbt level + 1) AGFL refills.
Hence to guarantee that we'd never run out of blocks on an allocation requiring worst case btree splits on all btrees on all allocations is ~75 blocks.
So I wouldn't expect the AGFL reserve pool to be any larger than a couple of hundred blocks in the worst case.
Which brings me to the next question: do we even need a reserve pool for this? We know when we are doing such a dependent allocation chain because args->minleft has to be set to ensure enough space is left after the first allocation to allow all the remaining allocations to succeed.
Perhaps we can to extend the minleft mechanism to indicate how many dependent allocations are in this chain (we know the bmbt height, too) and trigger the initial AGFL fill to handle multiple splits when the AG reservations cause the AG to be "empty" when there's actually still lots of free space in the AG?
Or maybe there's a simpler way? Just extend the RMAPBT reservation slightly and use it for AGFL blocks whenever that reservation is non-zero and causing ENOSPC for AGFL refills?
I'm not sure waht the best approach is here - even though I suggested making use of reserve pools some time ago, looking at the context and the maths again I'm not really sure that it is the only (or best) approach to solving the issue...
-Dave.
Signature · 2 lines
Dave Chinner [email protected]
Quoted 16 lines · Dave Chinner
Quoted 4 lines · Krister Johansen
I managed to work out a reproducer for the problem. Debugging that, the steps Gao outlined turned out to be essentially what was necessary to get the problem to happen repeatably.
Quoted 10 lines
1. Allocate almost all of the space in an AG
2. Free and reallocate that space to fragement it so the freespace b-trees are just about to split.
3. Allocate blocks in a file such that the next extent allocated for that file will cause its bmbt to get converted from an inline extent to a b-tree.
4. Free space such that the free-space btrees have a contiguous extent with a busy portion on either end
5. Allocate the portion in the middle, splitting the extent and triggering a b-tree split.
Quoted 4 lines
Do you have a script that sets up this precondition reliably? It sounds like it can be done from a known filesystem config. If you do have a script, can you share it? Or maybe even better, turn it into an fstest?
I do have a script that reproduces the problem. At the moment it is in a pretty embarrasing state. I'm happy to clean it up a bit and share it, or try to turn it into a fstest, or both. The script currently creates small loop devices to generate a filesystem layout that's a little easier to work with. Is it considered acceptable to have a fstest create a filesystem with a particular geometry? (And would you consider taking a patch to let mkfs.xfs --unsupported take both size and agsize arguments so the overall filesystem size and the per-ag size could be set by a test?)
Quoted 14 lines
Quoted 3 lines
On older kernels this is all it takes. After the AG-aware allocator changes I also need to start the allocation in the highest numbered AG available while inducing lock contention in the lower numbered AGs.
Ah, so you have to perform a DOS on the lower AGFs so that the attempts made by the
xfs_alloc_vextent_start_ag()to trylock the lower AGFs once it finds it cannot allocate in the highest AG anymore also fail.That was one of the changes made in the perag aware allocator rework; it added full-range AG iteration when
XFS_ALLOC_FLAG_TRYLOCKis set because we can't deadlock on reverse order AGF locking when using trylocks.
Quoted 5 lines
However, if the trylock iteration fails, it then sets the restart AG to the minimum AG be can wait for without deadlocking, removes the trylock and restarts the iteration. Hence you've had to create AGF lock contention to force the allocator back to being restricted by the AGF locking orders.
The other thing that I really appreciated here is that the patchset cleaned up a bunch of the different allocation functions and made everything easier to read and follow. Thanks for that as well.
Quoted 4 lines
Is this new behaviour sufficient to mitigate the problem being seen with this database workload? Has it been tested with kernels that have those changes, and if so did it have any impact on the frequency of the issue occurring?
I don't have a good answer for this yet. The team is planning to start migrating later in the year and this will probably run through to next year. I'll have that information eventually and will share it when I do, but don't know yet. Aside from the script, other synethtic load-tests have not been successful in reproducing the problemr. That may be the result of the databases that are spun up for load testing not having filesystems that as full and fragmented as the production ones.
Quoted 6 lines
Quoted 3 lines
In order to ensure that AGs have enough space to complete transactions with multiple allocations, I've taken a stab at implementing an AGFL reserve pool.
OK. I'll comment directly on the code from here, hopefully I'll address your other questions in those comments.
Thanks, Dave. I appreciate you spending the time to review and provide feedback.
-K
Quoted 22 lines · Krister Johansen
Quoted 16 lines · Dave Chinner
Quoted 4 lines · Krister Johansen
I managed to work out a reproducer for the problem. Debugging that, the steps Gao outlined turned out to be essentially what was necessary to get the problem to happen repeatably.
Quoted 10 lines
1. Allocate almost all of the space in an AG
2. Free and reallocate that space to fragement it so the freespace b-trees are just about to split.
3. Allocate blocks in a file such that the next extent allocated for that file will cause its bmbt to get converted from an inline extent to a b-tree.
4. Free space such that the free-space btrees have a contiguous extent with a busy portion on either end
5. Allocate the portion in the middle, splitting the extent and triggering a b-tree split.Quoted 4 lines
Do you have a script that sets up this precondition reliably? It sounds like it can be done from a known filesystem config. If you do have a script, can you share it? Or maybe even better, turn it into an fstest?
Quoted 6 lines
I do have a script that reproduces the problem. At the moment it is in a pretty embarrasing state. I'm happy to clean it up a bit and share it, or try to turn it into a fstest, or both. The script currently creates small loop devices to generate a filesystem layout that's a little easier to work with. Is it considered acceptable to have a fstest create a filesystem with a particular geometry?
Absolutely.
We do that quite a bit in fstests - if you just need one filesystem for this, then _scratch_mkfs_sized() can be used to make a filesystem of a specific size, or you can use _scratch_mkfs and pass the options you want directly to it. An example of this is xfs/227.
Otherwise you can create loop devices and use _mkfs_dev() to create the filesystems you need on them. An example of this is xfs/074.
Quoted 4 lines
(And would you
consider taking a patch to let mkfs.xfs --unsupported take both size and agsize arguments so the overall filesystem size and the per-ag size could be set by a test?)
We can already do that, but it's been placed behind a strong environmental guard to restrict such configurations to the fstests environment:
# TEST_DIR=foo TEST_DEV=foo QA_CHECK_FS=foo mkfs.xfs -dagcount=2,size=32m,file,name=foo
will bypass the "300MB minimum size" checks and allow you to make a filesystem image with 2x16MB AGs (i.e. a 32MB filesystem) ready to have a loop device created over it. If this is run inside a fstest, then you don't need the env variables because they are already set.
Quoted 29 lines
Quoted 14 lines
Quoted 3 lines
On older kernels this is all it takes. After the AG-aware allocator changes I also need to start the allocation in the highest numbered AG available while inducing lock contention in the lower numbered AGs.
Ah, so you have to perform a DOS on the lower AGFs so that the attempts made by the
xfs_alloc_vextent_start_ag()to trylock the lower AGFs once it finds it cannot allocate in the highest AG anymore also fail.That was one of the changes made in the perag aware allocator rework; it added full-range AG iteration when
XFS_ALLOC_FLAG_TRYLOCKis set because we can't deadlock on reverse order AGF locking when using trylocks.Quoted 5 lines
However, if the trylock iteration fails, it then sets the restart AG to the minimum AG be can wait for without deadlocking, removes the trylock and restarts the iteration. Hence you've had to create AGF lock contention to force the allocator back to being restricted by the AGF locking orders.
The other thing that I really appreciated here is that the patchset cleaned up a bunch of the different allocation functions and made everything easier to read and follow. Thanks for that as well.
Quoted 4 lines
Is this new behaviour sufficient to mitigate the problem being seen with this database workload? Has it been tested with kernels that have those changes, and if so did it have any impact on the frequency of the issue occurring?
Quoted 4 lines
I don't have a good answer for this yet. The team is planning to start migrating later in the year and this will probably run through to next year. I'll have that information eventually and will share it when I do, but don't know yet.
OK, that's fine. We still need to fix the issue, I just wanted to get an idea of the urgency of the situation.
Quoted 4 lines
Aside from the script, other synethtic
load-tests have not been successful in reproducing the problemr. That may be the result of the databases that are spun up for load testing not having filesystems that as full and fragmented as the production ones.
Yeah, that's typical when triaging these sorts of issues. We've had issues like this in the past with scyallaDB w.r.t. extent size hint based allocation occasionally failing at ~70% filesystem capacity. Situations like this require a very particular free space pattern to trigger, and it tends to be rare that they are hit in either test or production systems. Having a synthetic reproducer for such an issue is like finding gold. :)
-Dave.
Signature · 2 lines
Dave Chinner [email protected]
Re: [RFC PATCH 1/4] xfs: resurrect the AGFL reservation
In reply to Dave ChinnerQuoted 39 lines · Dave Chinner
Quoted 38 lines · Krister Johansen
Transactions that perform multiple allocations may inadvertently run out of space after the first allocation selects an AG that appears to have enough available space. The problem occurs when the allocation in the transaction splits freespace b-trees but the second allocation does not have enough available space to refill the AGFL. This results in an aborted transaction and a filesystem shutdown. In this author's case, it's frequently encountered in the
xfs_bmap_extents_to_btreepath on a write to an AG that's almost reached its limits.The AGFL reservation allows us to save some blocks to refill the AGFL to its minimum level in an Nth allocation, and to prevent allocations from proceeding when there's not enough reserved space to accommodate the refill.
This patch just brings back the reservation and does the plumbing. The policy decisions about which allocations to allow will be in a subsequent patch.
This implementation includes space for the bnobt and cnobt in the reserve. This was done largely because the AGFL reserve stubs appeared to already be doing it this way.
Signed-off-by Krister Johansen <[email protected]>--- fs/xfs/libxfs/xfs_ag.h | 2 ++ fs/xfs/libxfs/xfs_ag_resv.c | 54 ++++++++++++++++++++++-------- fs/xfs/libxfs/xfs_ag_resv.h | 4 +++ fs/xfs/libxfs/xfs_alloc.c | 43 +++++++++++++++++++++++- fs/xfs/libxfs/xfs_alloc.h | 3 +- fs/xfs/libxfs/xfs_alloc_btree.c | 59 +++++++++++++++++++++++++++++++++ fs/xfs/libxfs/xfs_alloc_btree.h | 5 +++ fs/xfs/libxfs/xfs_rmap_btree.c | 5 +++ fs/xfs/scrub/fscounters.c | 1 + 9 files changed, 161 insertions(+), 15 deletions(-)fs/xfs/libxfs/xfs_ag.h +0
-0
Quoted 8 lines
fs/xfs/libxfs/xfs_ag.h struct xfs_perag { · line 66
Quoted 6 lines
fs/xfs/libxfs/xfs_ag.h +2
-0@@ -62,6 +62,8 @@ struct xfs_perag {struct xfs_ag_resv pag_meta_resv;/* Blocks reserved for the reverse mapping btree. */ struct xfs_ag_resv pag_rmapbt_resv; +/* Blocks reserved for the AGFL. */ +struct xfs_ag_resv pag_agfl_resv;Ok, so you're creating a new pool for the AGFL refills.
Sorry, I should have been clearer about what I was trying to do. When I reviewed the patches[1] that created the rmapbt reservation, it looked like part of the justification for that work was that blocks from the agfl moving to other data structures, like the rmapbt, caused accounting inconsistencies. I worried that if I just accounted for the AGFL blocks without also trying to track the agfl blocks in use by the bnobt and the cnobt then I'd be re-creating a problem similar to what the previous patch had tried to fix.
After reading the rest of your comments, it sounds like I didn't get this right and we should probably discuss which approach is best to take.
Quoted 13 lines
fs/xfs/libxfs/xfs_ag.h xfs_ag_resv_rmapbt_alloc( · line 57
Quoted 9 lines
fs/xfs/libxfs/xfs_ag.h +2
-0@@ -48,6 +50,8 @@ xfs_ag_resv_rmapbt_alloc( args.len =1 ; pag =xfs_perag_get (mp, agno); +/* Transfer this reservation from the AGFL to RMAPBT */ +xfs_ag_resv_free_extent (pag,XFS_AG_RESV_AGFL ,NULL ,1 );xfs_ag_resv_alloc_extent (pag,XFS_AG_RESV_RMAPBT , &args);xfs_perag_put (pag); }I have no idea what this is accounting for or why it needs to be done. Comments need to explain why, not repeat what the code is doing.
Thanks, would something along the lines of the following been better?
/*
*
* The rmapbt has its own reservation separate from the AGFL. In cases
* where an agfl block is destined for use in the rmapbt, ensure that it
* is counted against the rmapbt reservation instead of the agfl's. */
Quoted 19 lines
Quoted 19 lines
fs/xfs/libxfs/xfs_ag.h +19
-0+/* +* Work out how many blocks to reserve for the AGFL as well as how many are in +* use currently. +*/ +int +xfs_alloc_agfl_calc_reserves ( +struct xfs_mount *mp, +struct xfs_trans *tp, +struct xfs_perag *pag, +xfs_extlen_t *ask, +xfs_extlen_t *used) +{ +struct xfs_buf *agbp; +struct xfs_agf *agf; +xfs_extlen_t agfl_blocks; +xfs_extlen_t list_len; +int error; + + error =xfs_alloc_read_agf (pag, tp,0 , &agbp);
Quoted 8 lines
fs/xfs/libxfs/xfs_ag.h
Quoted 5 lines
fs/xfs/libxfs/xfs_ag.h +5
-0+if (error) +return error; + + agf = agbp->b_addr; + agfl_blocks =xfs_alloc_min_freelist (mp,NULL );Why are you passing a NULL for the perag in here? This minimum AGFL blocks we will reserve is for single level btrees.
Thanks for catching this. I let myself get fooled by the comment at the top that said, "If @pag is NULL, return the largest possible minimum length" which was what I thought I wanted.
Quoted 14 lines
When we are actually doing an allocation, this calculation returns a block count based on the current height of the btrees, and so the actual AGFL refill size is always going to be larger than the reserves calculated here.
fs/xfs/libxfs/xfs_ag.h
Quoted 1 line
fs/xfs/libxfs/xfs_ag.h +1
-0+ list_len =be32_to_cpu (agf->agf_flcount);There is no relationship between the minimum AGFL block count and the current number of blocks on the AGFL. The number of blocks on the AGFL can be much larger than the minimum required to perform an allocation (e.g. we just did a series of merges that moved lots of blocks to the AGFL that was already at it's required size).
Quoted 11 lines
fs/xfs/libxfs/xfs_ag.h
Quoted 8 lines
fs/xfs/libxfs/xfs_ag.h +8
-0+xfs_trans_brelse (tp, agbp); + +/* +* Reserve enough space to refill AGFL to minimum fullness if btrees are +* at maximum height. +*/ + *ask += agfl_blocks; + *used += list_len;Hence the above calculations can result in a situation where used > ask, and ask is not large enough for runtime AGFL reservations.
It sounds like I need to work out some tests that involve generating a really full agfl and/or free-space trees without the change and then trying to use those with the change.
Quoted 104 lines
Quoted 15 lines
fs/xfs/libxfs/xfs_alloc_btree.c +7
-0@@ -671,6 +671,65 @@ xfs_allocbt_calc_size(return xfs_btree_calc_size (mp->m_alloc_mnr, len); } +/* +* Calculate the maximum alloc btree size. This is for a single allocbt. +* Callers wishing to compute both the size of the bnobt and cnobt must double +* this result. +*/ +xfs_extlen_t +xfs_allocbt_max_size(fs/xfs/libxfs/xfs_alloc_btree.c xfs_allocbt_calc_size( · line 690
Quoted 10 lines
fs/xfs/libxfs/xfs_alloc_btree.c +10
-0+ struct xfs_mount *mp, + xfs_agblock_t agblocks) +{ + +/* Don't proceed if uninitialized. Can happen in mkfs. */ +if (mp->m_alloc_mxr[0 ] ==0 ) +return 0 ; + +return xfs_allocbt_calc_size (mp, agblocks); +}So this is using a block count as the number of records in the btree? And it's returning the number of btree blocks that would be needed to index that number of records?
I'm not sure what you are attempting to calculate here, because...
Quoted 30 lines
fs/xfs/libxfs/xfs_alloc_btree.c +30
-0+/* +* Work out how many blocks to reserve for the bnobt and the cnobt as well as +* how many blocks are in use by these trees. +*/ +int +xfs_allocbt_calc_reserves ( +struct xfs_mount *mp, +struct xfs_trans *tp, +struct xfs_perag *pag, +xfs_extlen_t *ask, +xfs_extlen_t *used) +{ +struct xfs_buf *agbp; +struct xfs_agf *agf; +xfs_agblock_t agblocks; +xfs_extlen_t tree_len; +int error; + + error =xfs_alloc_read_agf (pag, tp,0 , &agbp); +if (error) +return error; + + agf = agbp->b_addr; + agblocks =be32_to_cpu (agf->agf_length); + tree_len =be32_to_cpu (agf->agf_btreeblks); +xfs_trans_brelse (tp, agbp); + +/* +* The log is permanently allocated. The space it occupies will never be +* available for btree expansion. Pretend the space is not there. fs/xfs/libxfs/xfs_alloc_btree.c xfs_allocbt_calc_size( · line 731
Quoted 10 lines
fs/xfs/libxfs/xfs_alloc_btree.c +10
-0+*/ +if (xfs_ag_contains_log (mp, pag->pag_agno)) + agblocks -= mp->m_sb.sb_logblocks; + +/* Reserve 1% of the AG or enough for one block per record per tree. */ + *ask +=max (agblocks /100 ,2 *xfs_allocbt_max_size (mp, agblocks)); + *used += tree_len; + +return error; +}... this is passing the AG size into
xfs_allocbt_max_size(), but the free space btree cannot have that many records in it. If all the blocks are free, then there will be a single contiguous free space extent record spanning the entire space. That's definitely not what this is calculation results in. :)I can see why you might be trying to calculate the max number of blocks in the btree - given worst case single block fragmentation, half the space in the AG can be indexed by the free space btree. That's a non-trivial number of records and a decent number of btree blocks to index them, but even then I don't think it's a relevant number to the AGFL reservation size.
The minimum AGFL size is tiny - it's just enough blocks to cover a full height split of each btree that sources blocks from the AGFL. If you point
xfs_dbat a filesystem and run the btheight command with the length of the AG as the record count, you'll get an idea of the worst case btree heights in the filesystem.On the workstation I'm typing this one, /home is 1.8TB, has 32 AGs and has reflink and rmap enabled.
The worst case btree heights for both the bno and cnt btrees is 4 levels, and the rmapbt is 5 levels at worst. Hence for any given allocation the worst case AGFL length is going to be ~15 blocks.
Then we need to consider how many times we might have to refill the AGFL in a series of dependent allocations that might be forced into the same AG. i.e. the bmbt splitting during record insertion after a data extent allocation (which I think is the only case this matters)
Quoted 8 lines
The bmapbt for the above filesystem has a maximum height of 4 levels. Hence the worst case "data extent + bmbt split" allocation is going to require 1 + ((max bmbt level - 1) + 1) block allocations from the AG. i.e. (max bmbt level + 1) AGFL refills.
Hence to guarantee that we'd never run out of blocks on an allocation requiring worst case btree splits on all btrees on all allocations is ~75 blocks.
Just to make certain I understand, for each allocation the correct way to calculate the AGFL refill size would be to use the formula in xfs_alloc_min_freelist(), and assume that in the worst-case the level increments each time?
Quoted 15 lines
So I wouldn't expect the AGFL reserve pool to be any larger than a couple of hundred blocks in the worst case.
Which brings me to the next question: do we even need a reserve pool for this? We know when we are doing such a dependent allocation chain because
args->minlefthas to be set to ensure enough space is left after the first allocation to allow all the remaining allocations to succeed.Perhaps we can to extend the minleft mechanism to indicate how many dependent allocations are in this chain (we know the bmbt height, too) and trigger the initial AGFL fill to handle multiple splits when the AG reservations cause the AG to be "empty" when there's actually still lots of free space in the AG?
Quoted 8 lines
Or maybe there's a simpler way? Just extend the RMAPBT reservation slightly and use it for AGFL blocks whenever that reservation is non-zero and causing ENOSPC for AGFL refills?
I'm not sure waht the best approach is here - even though I suggested making use of reserve pools some time ago, looking at the context and the maths again I'm not really sure that it is the only (or best) approach to solving the issue...
I'd be happy to explore some of these alternate approaches.
One approach that I tried before the agfl reserved pool was to work out how much space would be needed for the next agfl refill by allowing xfs_alloc_min_freelist to tell me the need at level n+1. From there, I required minleft > 0 allocations to have that additional space available. It seemed like it was working, but broke the stripe alignment tests in generic/336. The case where that test selects a really large extent size was failing because it was falling back to a minleft allocation and not getting proper stripe alignment.
This was because I was effectively reserving additional space, but not subtracting that space from m_ag_max_usable. The ag_resv code already does this, so I wondered if I might be acting like I was smarter than the experts and should try following the advice that was given.
Let me try to summarize and make a few of these proposals more concrete and then we can discuss the tradeoffs.
Based upon previous discussions, I was under the impression that a correct solution should maintain the following invariant:
xfs_alloc_fix_freelist() should not select an AG for which there is not enough space to satisfy all of the allocations in the transaction.
I had pedantically turned that into a pair of checks:
a. Validate that enough space exists to satisfy the transaction at the time the AG for the first allocation is selected.
b. Take additional steps in subsequent allocations in the same transaction to ensure available space could be used.
The absolutely _most_ simplistic approach I can think of is the following.
1. Allow AGFL refills to ignore the reservation if we're close to ENOSPC and are performing a subsequent allocation in a transaction.
I think you originally suggested this idea[2] in the previous discussion. It's a simplistic solution, and doesn't check ahead of time that enough blocks are available to meet the demand. However, in all of the cases where I've run into this problem, the filesystems that hit this case had substantially more than 75 blocks (approx 20x more) in the reserve, and were only doing a single bmbt, bnobt, and cnobt split. (Only short 8 blocks).
If the reserved block counter doesn't change as a result of the "borrowing" of these blocks, then subsequent allocation attempts will correctly get ENOSPC on that AG. Essentially, xfs_alloc_space_available might let one of these through, but it's unlikely to let any more through since the available count will now always be less than the reserved count after one of these borrow edge cases occurs.
2. Modify minleft to account for dependent allocations
Turn minleft into something like:
union xfs_minleft {
xfs_extlen_t blocksleft; unsigned int ndepallocs;
};
AFAICS, xfs_bmapi_minleft() handles this calculation for bmap allocations which just leaves the ialloc code using blocksleft as the original minfree. The code in xfs_alloc_space_available would need to know how to turn ndepallocs into a number of blocks, and then there's some tracepoint code to touch up.
The ialloc code sets owner info that we might be able to use later to determine whether to use blocksleft or ndepallocs, provided it's acceptable to rely on the field for that.
This is appealing because it would let the allocation path perform one allocation to fill the AGFL instead of multiple, and we'd know up front whether we could get all the space needed for the transaction or not.
The downside might be having to adjust the freelist length more frequently if we need to subsequently shrink it, or partially fill, hit an error, and then have to cleanup. The AGF modifications needed to be journaled so there might be additional overhead from that path.
3. Extend the RMAPBT reservation
Older filesystems don't default to having rmapbt enabled so they may not benefit from this adjustment. If we could extend both reservations that might be a compromise solution.
It seems like this solution would still want to look at the filesystem gemoetry and use that to make an estimate of how many additional blocks to reserve. That starts to look like the first step in creating a separate AGFL reservation which leaves...
4. Implement a less ambitious AGFL reserve
The draft in this thread tried to track all AGFL blocks from their allocation and continued to account for them during their lifetime in the bnobt and cnobt. Instead of trying to build a reserve for all free space management blocks that aren't rmapbt, reduce the scope of the AGFL reserve to be just the number of blocks needed to satsify a single transaction with multiple allocations that occurs close to an AG's ENOSPC.
Blocks would be subtracted from used on agfl block free, if used were non zero. Blocks would be added to used on agfl block allocation if a non-reserve alloction failed to obtain the requested number of blocks. The wanted size could be determined using the same calculation described
earlier: calculate the maximum number of bmbt splits in a transaction and add up the worst-case number of blocks for each split.
The one part I'm not quite sure how to work out is how to re-derive the amount of the AGFL reserve that's been taken and is currently in use on a subsequent mount of the filesystem. I think option #3 suffers from this problem as well. IOW, is there a sneaky way to re-compute this without having to add another field to the on-disk AGF?
Do any of these approaches stand out as clearly better (or worse) to you?
Thanks again for taking the time to read through these patches and provide feedback. I appreciate all the comments, ideas, and explanations.
-K
[1] https://lore.kernel.org/linux-xfs/[email protected]/
[2] https://lore.kernel.org/linux-xfs/[email protected]/
Re: [RFC PATCH 1/4] xfs: resurrect the AGFL reservation
[ Sorry for the long delay - PTO and then catchup time so I'm only just getting back to this now. This is long, and I disappeared down a rabbit hole in getting to the bottom of some of the code before I even read the summary you wrote. I think I came up with solution to your #4 proposal in the process... ]
Quoted 49 lines · Krister Johansen
Quoted 39 lines · Dave Chinner
Quoted 38 lines · Krister Johansen
Transactions that perform multiple allocations may inadvertently run out of space after the first allocation selects an AG that appears to have enough available space. The problem occurs when the allocation in the transaction splits freespace b-trees but the second allocation does not have enough available space to refill the AGFL. This results in an aborted transaction and a filesystem shutdown. In this author's case, it's frequently encountered in the
xfs_bmap_extents_to_btreepath on a write to an AG that's almost reached its limits.The AGFL reservation allows us to save some blocks to refill the AGFL to its minimum level in an Nth allocation, and to prevent allocations from proceeding when there's not enough reserved space to accommodate the refill.
This patch just brings back the reservation and does the plumbing. The policy decisions about which allocations to allow will be in a subsequent patch.
This implementation includes space for the bnobt and cnobt in the reserve. This was done largely because the AGFL reserve stubs appeared to already be doing it this way.
Signed-off-by Krister Johansen <[email protected]>--- fs/xfs/libxfs/xfs_ag.h | 2 ++ fs/xfs/libxfs/xfs_ag_resv.c | 54 ++++++++++++++++++++++-------- fs/xfs/libxfs/xfs_ag_resv.h | 4 +++ fs/xfs/libxfs/xfs_alloc.c | 43 +++++++++++++++++++++++- fs/xfs/libxfs/xfs_alloc.h | 3 +- fs/xfs/libxfs/xfs_alloc_btree.c | 59 +++++++++++++++++++++++++++++++++ fs/xfs/libxfs/xfs_alloc_btree.h | 5 +++ fs/xfs/libxfs/xfs_rmap_btree.c | 5 +++ fs/xfs/scrub/fscounters.c | 1 + 9 files changed, 161 insertions(+), 15 deletions(-)fs/xfs/libxfs/xfs_ag.h +0
-0Quoted 8 lines
fs/xfs/libxfs/xfs_ag.h struct xfs_perag { · line 66
Quoted 6 lines
fs/xfs/libxfs/xfs_ag.h +2
-0@@ -62,6 +62,8 @@ struct xfs_perag {struct xfs_ag_resv pag_meta_resv;/* Blocks reserved for the reverse mapping btree. */ struct xfs_ag_resv pag_rmapbt_resv; +/* Blocks reserved for the AGFL. */ +struct xfs_ag_resv pag_agfl_resv;Ok, so you're creating a new pool for the AGFL refills.
Quoted 8 lines
Sorry, I should have been clearer about what I was trying to do. When I reviewed the patches[1] that created the rmapbt reservation, it looked like part of the justification for that work was that blocks from the agfl moving to other data structures, like the rmapbt, caused accounting inconsistencies. I worried that if I just accounted for the AGFL blocks without also trying to track the agfl blocks in use by the bnobt and the cnobt then I'd be re-creating a problem similar to what the previous patch had tried to fix.
Ah. There's a key difference between bno/cnt btree blocks and rmapbt
blocks: bnobt/cntbt blocks are considered free space whilst rmapbt blocks are considered used space.
The reason for this is that the free space btrees have a special characteristic that only becomes obvious when someone points it out.
When the AG reaches a full state, there is no free space and the free space btrees are empty. Hence as we slowly consume space in the AG, the free space trees are shrinking and the record count decreases and the btree blocks indexing that free space get released as the index shrinks. Hence we don't have to account for those btree blocks as used space because they have always been released back to the free space btree by the time we get near ENOSPC. When we are near ENOSPC, the btree is reduced to a single root block that we never free. By the time we empty all the records in that root block, the only free space remaining in the AG is the blocks on the AGFL itself.
In comparison, the rmapbt does not shrink as the filesystem fills up; it continues to grow as we add more used space records. hence we have to account for the rmapbt records as used space, but to guarantee we can always allocate a new rmapbt record near ENOSPC, we have to guarantee that there are enough blocks to fill the AGFL for any given rampbt insertion. Hence we need a reserve pool of free space that ensures the free space btree can refill the AGFL blocks that the rmapbt can consume during growth near ENOSPC.
The fact that we don't account for bnobt/cntbt blocks as used space is also reflected in the behaviour of xfs_alloc_space_available() when we are freeing extents. It does:
if (flags & XFS_ALLOC_FLAG_FREEING) return true;
And so always allows extent freeing regardless of how little space is remaining the AG and AGFL.
The reason for this is that freeing space when the AGFL is empty will not require AGFL blocks to be consumed. The bnobt/cntbt root blocks are completely empty, and so freeing the extent will simply insert a new record into those blocks. No btree block allocation will be required. Any AGFL refill after this point will have some blocks that can be pulled from the free space btrees, hence the AGFL being undersized does not matter and hence we never return ENOSPC when freeing extents on a completely full AG.
The fundamental issue here is that the rmapbt and reflink reservations mean ENOSPC (AG full) is now occurring while there is still large amounts of space being free-but-reserved, and so the assumption that bno/cnt trees will never split on allocation nor grow when we free an extent when we are right at ENOSPC no longer holds true.
Hence the space we set aside for the AGFL for bno/cnt operation at ENOSPC is no longer sufficient.....
Quoted 18 lines
After reading the rest of your comments, it sounds like I didn't get this right and we should probably discuss which approach is best to take.
Quoted 13 lines
fs/xfs/libxfs/xfs_ag.h xfs_ag_resv_rmapbt_alloc( · line 57
Quoted 9 lines
fs/xfs/libxfs/xfs_ag.h +2
-0@@ -48,6 +50,8 @@ xfs_ag_resv_rmapbt_alloc( args.len =1 ; pag =xfs_perag_get (mp, agno); +/* Transfer this reservation from the AGFL to RMAPBT */ +xfs_ag_resv_free_extent (pag,XFS_AG_RESV_AGFL ,NULL ,1 );xfs_ag_resv_alloc_extent (pag,XFS_AG_RESV_RMAPBT , &args);xfs_perag_put (pag); }I have no idea what this is accounting for or why it needs to be done. Comments need to explain why, not repeat what the code is doing.
Quoted 8 lines
Thanks, would something along the lines of the following been better?
/*
*
* The rmapbt has its own reservation separate from the AGFL. In cases
* where an agfl block is destined for use in the rmapbt, ensure that it
* is counted against the rmapbt reservation instead of the agfl's. */
Ok, I understand what you are trying to do, but given the above I'm not sure this correct....
Quoted 30 lines
Quoted 30 lines
I can see why you might be trying to calculate the max number of blocks in the btree - given worst case single block fragmentation, half the space in the AG can be indexed by the free space btree. That's a non-trivial number of records and a decent number of btree blocks to index them, but even then I don't think it's a relevant number to the AGFL reservation size.
The minimum AGFL size is tiny - it's just enough blocks to cover a full height split of each btree that sources blocks from the AGFL. If you point
xfs_dbat a filesystem and run the btheight command with the length of the AG as the record count, you'll get an idea of the worst case btree heights in the filesystem.On the workstation I'm typing this one, /home is 1.8TB, has 32 AGs and has reflink and rmap enabled.
The worst case btree heights for both the bno and cnt btrees is 4 levels, and the rmapbt is 5 levels at worst. Hence for any given allocation the worst case AGFL length is going to be ~15 blocks.
Then we need to consider how many times we might have to refill the AGFL in a series of dependent allocations that might be forced into the same AG. i.e. the bmbt splitting during record insertion after a data extent allocation (which I think is the only case this matters)
The bmapbt for the above filesystem has a maximum height of 4 levels. Hence the worst case "data extent + bmbt split" allocation is going to require 1 + ((max bmbt level - 1) + 1) block allocations from the AG. i.e. (max bmbt level + 1) AGFL refills.
Quoted 8 lines
Quoted 3 lines
Hence to guarantee that we'd never run out of blocks on an allocation requiring worst case btree splits on all btrees on all allocations is ~75 blocks.
Just to make certain I understand, for each allocation the correct way to calculate the AGFL refill size would be to use the formula in
xfs_alloc_min_freelist(), and assume that in the worst-case the level increments each time?
Not quite. Btrees don't work that way - once you split the root block, it can't be split again until the root block fills. That means we have to split the level below the root block enough times to fill the root block. And that requires splitting the level below that enough times to fill and split the second level enough times to fill the root block. The number of inserts needed to split the root block increases exponentially with the height of the tree.
Hence if we've got a height of 2 and 10 records/ptrs per leaf/node, a full tree looks like this:
Level 1 0123456789
||.......|
/---------------/|.......\---------------\
| | |Level 0 0123456789 0123456789 ..... 0123456789
If we do an insert anywhere we'll get a full height split and a new root at level 2. Lets insert record A in the leaf at the left edge:
Level 2 01
||
/-------/\------\
| |
Level 1 0A1234 56789
|||... ....|
/-------/|\------\ ....\------------\
| | | |
Level 0 01234 A56789 0123456789 ..... 0123456789It should be obvious now that a followup insertion anywhere in the tree cannot split either the root node at level 2, nor the old root node that was split in two at level 1.
Yes, we can still split at level 0, but that will only result in nodes at level 1 getting updated, and only once they are full will they start splitting at level 1. And then level 2 (the root) won't split until level 1 has split enough to fill all the nodes in level 1.
What this means is that for any single insertion into a btree, the worst case demand for new blocks is "current height + 1". In the case of BMBT, INOBT and REFCOUNBT, we're typically only doing one or two adjacent record insertions in a given operation, so only one split will occur during the operation. The free space trees are different, however.
When the first allocation occurs, we split the tree as per above and that consumes (start height + 1) blocks from AGFL. We then get the next BMBT allocation request (because it's doing a multi-level split), and the best free space we find is, this time, in the leaf at the right side of the tree. Hence we split that block, but we don't need to split it's parent (level 1) block because it has free space in it. Hence the second allocation has a worst case block requirement of (start height - 1).
If we then do a third allocation (level 2 of the BMBT is splitting), and that lands in the middle of the tree, we split that block. That can be inserted into either of the level 1 blocks without causing a split there, either. Hence a worst case block requirement for that is also (start height - 1).
It's only once we've split enough blocks at (start height - 1) that to fill both blocks at start height that we'll get a larger split. We had ten blocks at level 0 to begin with, 11 after the first full hieght split, so we need, at minimum, another 9 splits at level 0 to fill level 1. This means we then have all the leaf blocks at either 5 or 6 records at the time the level 1 nodes fill. To then get another insert into level 1 to split that, we need to fill a minimum of -3 sibling- leaf blocks.
The reason we need to fill 3 leaf blocks and not 1 is that we shift records between left and right siblings instead of splitting. i.e. we steal space from a sibling in preference to splitting and inserting a new record into the parent. Hence we only insert into the parent when the insert node and both siblings are full completely full.
When we look at a typical AG btree on a v5 filesystem, we have at least 110 records/ptrs per block (1kB block size) so the minimum number of record inserts needed before we need to split a parent again after it was just split is at least 150 inserts.
Hence after a full height split, we are not going to split a node at the old root level again until at least 150 inserts (1kB block size) are done at the child level.
IOWs, we're never going to get two start height splits in a single allocation chain. At most we are going to get one start height split and then N (start height - 1) splits. That's the worst case AGFL we need to consider, but such a split chain would be so infintesimally probably that always reserving that amount of space in the AGFL is just a waste of space because it will never, ever be used.
So the worst case AGFL requirement for a data extent allocation or free will be:
1. data extent - full free space tree split * 2 + rmapbt
2. BMBT leaf split - (free space height - 2) * 2 + rmapbt
3. BMBT node split - (free space height - 2) * 2 + rmapbt
....
N. BMBT root split - (free space height - 2) * 2 + rmapbt
So the maximum number of chained allocations is likely going to be something like:
(max AGFL for one allocation) +
((max bmbt/refcountbt height) * (max agfl for dependent allocation))
Which is likely to be in the order of...
Quoted 2 lines
Quoted 2 lines
So I wouldn't expect the AGFL reserve pool to be any larger than a couple of hundred blocks in the worst case.
... this.
That's a lot of space (close on 1MB at 4kB block size) per AG to never be able to use for this exceedingly rare corner case situation. However, let's get the calculation right first and then see how it falls out in comparison to the amount of space we already reserve for rmapbt, refcountbt and finobt. It may just be noise...
Quoted 21 lines
Quoted 12 lines
Which brings me to the next question: do we even need a reserve pool for this? We know when we are doing such a dependent allocation chain because
args->minlefthas to be set to ensure enough space is left after the first allocation to allow all the remaining allocations to succeed.Perhaps we can to extend the minleft mechanism to indicate how many dependent allocations are in this chain (we know the bmbt height, too) and trigger the initial AGFL fill to handle multiple splits when the AG reservations cause the AG to be "empty" when there's actually still lots of free space in the AG?
Quoted 8 lines
Or maybe there's a simpler way? Just extend the RMAPBT reservation slightly and use it for AGFL blocks whenever that reservation is non-zero and causing ENOSPC for AGFL refills?
I'm not sure waht the best approach is here - even though I suggested making use of reserve pools some time ago, looking at the context and the maths again I'm not really sure that it is the only (or best) approach to solving the issue...
Quoted 7 lines
I'd be happy to explore some of these alternate approaches.
One approach that I tried before the agfl reserved pool was to work out how much space would be needed for the next agfl refill by allowing
xfs_alloc_min_freelistto tell me the need at level n+1. From there, I required minleft > 0 allocations to have that additional space available.
Yes, that would mostly work, but the issue is that every allocation that goes through xfs_bmapi_write() (essentially every data, directory and xattr block allocation) have minleft set. And it gets set on inode chunk allocation, too, because we need to have space for inobt/finobt record insertion...
Quoted 4 lines
It seemed like it was working, but broke the stripe alignment tests in generic/336. The case where that test selects a really large extent size was failing because it was falling back to a minleft allocation and not getting proper stripe alignment.
It would have been falling back to an *minlen* allocation, not a "minleft" allocation. Two very different things - minlen and maxlen define the allowable size of allocated extent, minleft defines how many blocks must remain free in the AG after the first allocation succeeds.
Quoted 4 lines
This was because I was effectively reserving additional space, but not subtracting that space from
m_ag_max_usable. Theag_resvcode already does this, so I wondered if I might be acting like I was smarter than the experts and should try following the advice that was given.
Hmmmm. Subtracting space from mp->m_ag_max_usable might be a viable option here - that's supposed to have an AGFL block reserve component in it already.
[ And now we disappear down the rabbit hole. ]
Take a look at xfs_alloc_ag_max_usable(), which is used to set mp->m_ag_max_usable:
blocks = XFS_BB_TO_FSB(mp, XFS_FSS_TO_BB(mp, 4)); /* ag headers */
blocks += XFS_ALLOCBT_AGFL_RESERVE;
blocks += 3; /* AGF, AGI btree root blocks */
....There's a number of blocks reserved for the AGFL that aren't usable already. What is that value for?
/*
* The number of blocks per AG that we withhold from xfs_dec_fdblocks to
* guarantee that we can refill the AGFL prior to allocating space in a nearly
* full AG. Although the space described by the free space btrees, the
* blocks used by the freesp btrees themselves, and the blocks owned by the
* AGFL are counted in the ondisk fdblocks, it's a mistake to let the ondisk
* free space in the AG drop so low that the free space btrees cannot refill an
* empty AGFL up to the minimum level. Rather than grind through empty AGs
* until the fs goes down, we subtract this many AG blocks from the incore
* fdblocks to ensure user allocation does not overcommit the space the
* filesystem needs for the AGFLs. The rmap btree uses a per-AG reservation to
* withhold space from xfs_dec_fdblocks, so we do not account for that here. */
#define XFS_ALLOCBT_AGFL_RESERVE 4
What is this magic number of 4, then?
Remember what I said above about the free space btree blocks being accounted as free space and that freeing extents are always allowed to go ahead, even when the AG is full?
This AGFL reserve is the minimum space needed for an extent free to successfully refill the AGFL at ENOSPC to allow the extent free to proceed. That is, both trees have a singel level, so a full height split of either tree will require 2 blocks to be allocated. 2 freespace trees per AG, two blocks per tree, and so we need 4 blocks per AG to ensure freeing extents at ENOSPC will always succeed.
This "magic 4" blocks isn't valid when we have rmapbt, recountbt, or finobt reservations in the AG anymore, because ENOSPC can occur when we still have multi-level bno/cnt btrees in the AG. That's the first thing we need to fix.
This AGFL set aside is taken out of the global free space pool via this function:
/*
* Compute the number of blocks that we set aside to guarantee the ability to
* refill the AGFL and handle a full bmap btree split.
*
* In order to avoid ENOSPC-related deadlock caused by out-of-order locking of
* AGF buffer (PV 947395), we place constraints on the relationship among
* actual allocations for data blocks, freelist blocks, and potential file data
* bmap btree blocks. However, these restrictions may result in no actual space
* allocated for a delayed extent, for example, a data block in a certain AG is
* allocated but there is no additional block for the additional bmap btree
* block due to a split of the bmap btree of the file. The result of this may
* lead to an infinite loop when the file gets flushed to disk and all delayed
* extents need to be actually allocated. To get around this, we explicitly set
* aside a few blocks which will not be reserved in delayed allocation. *
* For each AG, we need to reserve enough blocks to replenish a totally empty
* AGFL and 4 more to handle a potential split of the file's bmap btree. */
unsigned int
xfs_alloc_set_aside(
struct xfs_mount *mp)
{
return mp->m_sb.sb_agcount * (XFS_ALLOCBT_AGFL_RESERVE + 4);
}But where did that magic number of "4 more to handle a potential split of the file's bmap btree" come from?
Ah, a fix I made for a ENOSPC regression back in 2006:
+ * ..... Considering the minimum number of
+ * needed freelist blocks is 4 fsbs _per AG_, a potential split of file's bmap
+ * btree requires 1 fsb, so we set the number of set-aside blocks
+ * to 4 + 4*agcount.
+ */
+#define XFS_ALLOC_SET_ASIDE(mp) (4 + ((mp)->m_sb.sb_agcount * 4))
That was fixing a regression caused by an ENOSPC deadlock bug fix done for SGI PV 947395.
commit 96b336c71016a85cd193762199aa6f99f543b6fe
Author: Yingping Lu <[email protected]> Date: Tue May 23 19:28:08 2006 +0000
In actual allocation of file system blocks and freeing extents, the transaction within each such operation may involve multiple locking of AGF buffer. While the freeing extent function has sorted the extents based on AGF number before entering into transaction, however, when the file system space is very limited, the allocation of space would try every AGF to get space allocated, this could potentially cause out-of-order locking, thus deadlock could happen. This fix mitigates the scarce space for allocation by setting aside a few blocks without reservation, and avoid deadlock by maintaining ascending order of AGF locking.
Add a new flag XFS_ALLOC_FLAG_FREEING to indicate whether the caller is freeing or allocating. Add a field firstblock in structure xfs_alloc_arg to indicate whether this is the first allocation request.
Which included this:
+ * ...... Considering the minimum number of
+ * needed freelist blocks is 4 fsbs, a potential split of file's bmap
+ * btree requires 1 fsb, so we set the number of set-aside blocks to 8. +*/
+#define SET_ASIDE_BLOCKS 8
<ding!>
Ah, now I get it. It's only taken me 18 years to really understand how this value was originally derived and why it is wrong.
It assumed 4 blocks for the AGFL for the initial allocation to fill and empty AGFL, and then 4 more blocks for the AGFL to allow a refill for the subsequent BMBT block allocation to refill the AGFL. IOWs, it wasn't reserving blocks for the BMBT itself, it was reserving blocks for a second AGFL refill in the allocation chain....
Right, so I think what we need to change is XFS_ALLOCBT_AGFL_RESERVE and xfs_alloc_set_aside() to reflect the worst case size of the free space trees when we hit ENOSPC for user data, not a hard coded 4 + 4.
The worst case free space tree size is going to be single block free records when all the per-ag reservations are at their maximum values. So we need to calculate maximum reservation sizes for the AG, then calculate how many btree blocks that will require to index as single block free space extents, then calculate the hieght of the btrees needs to index that. That gives us out "free space tree height at ENOSPC", and then we can calculate how many AGFL blocks we need at ENOSPC to handle a split of both trees. That value replaces XFS_ALLOCBT_AGFL_RESERVE.
As for the BMBT split requiring more AGFL refills, we need to know what the maximum BMBT height the fs supports is (I think we already calculate that), and that then becomes the level we feed into the "how many AGFL blocks do we need in a full height BMBT split allocation chain. I did that math above, and that calculation should replace the "+ 4" in xfs_alloc_set_aside(). I think that ends up with the calculation being something like:
setaside = agcount * (number of dependent allocations *
AGFL blocks for refill at ENOSPC)
I think we also need to make mp->m_ag_max_usable also take into account the BMBT split related AGFL refills as xfs_alloc_set_aside() as it only considers XFS_ALLOCBT_AGFL_RESERVE right now. That will ensure we always have those blocks available for the AGFL.
Quoted 2 lines
Let me try to summarize and make a few of these proposals more concrete and then we can discuss the tradeoffs.
Fair summary. this is already long, and I think what I discovered above kinda comes under:
Quoted 1 line
4. Implement a less ambitious AGFL reserve
That's what we did back in 2006 - we just carved out the smallest amount of blocks we needed from the free space pool to ensure the failing case worked.
Quoted 7 lines
The draft in this thread tried to track all AGFL blocks from their allocation and continued to account for them during their lifetime in the bnobt and cnobt. Instead of trying to build a reserve for all free space management blocks that aren't rmapbt, reduce the scope of the AGFL reserve to be just the number of blocks needed to satsify a single transaction with multiple allocations that occurs close to an AG's ENOSPC.
Yes, and that's what I suggest we extend xfs_alloc_set_aside() and mp->m_ag_max_usable to encompass. That way we don't actually need to track anything, the AGs will always have that space available to use because mp->m_ag_max_usable prevents them from being used by anything else.
Quoted 2 lines
Do any of these approaches stand out as clearly better (or worse) to you?
I think I've convinced myself that we already use option 4 and the accounting just needs extending to reserve the correct amount of blocks...
Quoted 3 lines
Thanks again for taking the time to read through these patches and provide feedback. I appreciate all the comments, ideas, and explanations.
Don't thank me - I've got to thank you for taking the time and effort to understand this complex code well enough to ask exactly the right question. It's not often that answering a question on how to do something causes a whole bunch of not quite connected floating pieces in my head to suddenly fall and land in exactly the right places... :)
-Dave.
Signature · 2 lines
Dave Chinner [email protected]
Re: [RFC PATCH 1/4] xfs: resurrect the AGFL reservation
[ My turn to apologize. I had a couple of short weeks at the beginning of July, but have finally been able to get back to this. ]
Quoted 48 lines · Dave Chinner
Quoted 47 lines · Krister Johansen
Quoted 46 lines · Dave Chinner
Quoted 44 lines · Krister Johansen
Transactions that perform multiple allocations may inadvertently run out of space after the first allocation selects an AG that appears to have enough available space. The problem occurs when the allocation in the transaction splits freespace b-trees but the second allocation does not have enough available space to refill the AGFL. This results in an aborted transaction and a filesystem shutdown. In this author's case, it's frequently encountered in the
xfs_bmap_extents_to_btreepath on a write to an AG that's almost reached its limits.The AGFL reservation allows us to save some blocks to refill the AGFL to its minimum level in an Nth allocation, and to prevent allocations from proceeding when there's not enough reserved space to accommodate the refill.
This patch just brings back the reservation and does the plumbing. The policy decisions about which allocations to allow will be in a subsequent patch.
This implementation includes space for the bnobt and cnobt in the reserve. This was done largely because the AGFL reserve stubs appeared to already be doing it this way.
Signed-off-by Krister Johansen <[email protected]>--- fs/xfs/libxfs/xfs_ag.h | 2 ++ fs/xfs/libxfs/xfs_ag_resv.c | 54 ++++++++++++++++++++++-------- fs/xfs/libxfs/xfs_ag_resv.h | 4 +++ fs/xfs/libxfs/xfs_alloc.c | 43 +++++++++++++++++++++++- fs/xfs/libxfs/xfs_alloc.h | 3 +- fs/xfs/libxfs/xfs_alloc_btree.c | 59 +++++++++++++++++++++++++++++++++ fs/xfs/libxfs/xfs_alloc_btree.h | 5 +++ fs/xfs/libxfs/xfs_rmap_btree.c | 5 +++ fs/xfs/scrub/fscounters.c | 1 + 9 files changed, 161 insertions(+), 15 deletions(-)fs/xfs/libxfs/xfs_ag.h +2
-0@@ -62,6 +62,8 @@ struct xfs_perag {struct xfs_ag_resv pag_meta_resv;/* Blocks reserved for the reverse mapping btree. */ struct xfs_ag_resv pag_rmapbt_resv; +/* Blocks reserved for the AGFL. */ +struct xfs_ag_resv pag_agfl_resv;
<snip>
Quoted 109 lines
Not quite. Btrees don't work that way - once you split the root block, it can't be split again until the root block fills. That means we have to split the level below the root block enough times to fill the root block. And that requires splitting the level below that enough times to fill and split the second level enough times to fill the root block. The number of inserts needed to split the root block increases exponentially with the height of the tree.
Hence if we've got a height of 2 and 10 records/ptrs per leaf/node, a full tree looks like this:
Level 1 0123456789
||.......| /---------------/|.......\---------------\ | | |Level 0 0123456789 0123456789 ..... 0123456789
If we do an insert anywhere we'll get a full height split and a new root at level 2. Lets insert record A in the leaf at the left edge:
Level 2 01
|| /-------/\------\ | | Level 1 0A1234 56789 |||... ....| /-------/|\------\ ....\------------\ | | | | Level 0 01234 A56789 0123456789 ..... 0123456789It should be obvious now that a followup insertion anywhere in the tree cannot split either the root node at level 2, nor the old root node that was split in two at level 1.
Yes, we can still split at level 0, but that will only result in nodes at level 1 getting updated, and only once they are full will they start splitting at level 1. And then level 2 (the root) won't split until level 1 has split enough to fill all the nodes in level 1.
What this means is that for any single insertion into a btree, the worst case demand for new blocks is "current height + 1". In the case of BMBT, INOBT and REFCOUNBT, we're typically only doing one or two adjacent record insertions in a given operation, so only one split will occur during the operation. The free space trees are different, however.
When the first allocation occurs, we split the tree as per above and that consumes (start height + 1) blocks from AGFL. We then get the next BMBT allocation request (because it's doing a multi-level split), and the best free space we find is, this time, in the leaf at the right side of the tree. Hence we split that block, but we don't need to split it's parent (level 1) block because it has free space in it. Hence the second allocation has a worst case block requirement of (start height - 1).
If we then do a third allocation (level 2 of the BMBT is splitting), and that lands in the middle of the tree, we split that block. That can be inserted into either of the level 1 blocks without causing a split there, either. Hence a worst case block requirement for that is also (start height - 1).
It's only once we've split enough blocks at (start height - 1) that to fill both blocks at start height that we'll get a larger split. We had ten blocks at level 0 to begin with, 11 after the first full hieght split, so we need, at minimum, another 9 splits at level 0 to fill level 1. This means we then have all the leaf blocks at either 5 or 6 records at the time the level 1 nodes fill. To then get another insert into level 1 to split that, we need to fill a minimum of -3 sibling- leaf blocks.
The reason we need to fill 3 leaf blocks and not 1 is that we shift records between left and right siblings instead of splitting. i.e. we steal space from a sibling in preference to splitting and inserting a new record into the parent. Hence we only insert into the parent when the insert node and both siblings are full completely full.
When we look at a typical AG btree on a v5 filesystem, we have at least 110 records/ptrs per block (1kB block size) so the minimum number of record inserts needed before we need to split a parent again after it was just split is at least 150 inserts.
Hence after a full height split, we are not going to split a node at the old root level again until at least 150 inserts (1kB block size) are done at the child level.
IOWs, we're never going to get two start height splits in a single allocation chain. At most we are going to get one start height split and then N (start height - 1) splits. That's the worst case AGFL we need to consider, but such a split chain would be so infintesimally probably that always reserving that amount of space in the AGFL is just a waste of space because it will never, ever be used.
So the worst case AGFL requirement for a data extent allocation or free will be:
1. data extent - full free space tree split * 2 + rmapbt
2. BMBT leaf split - (free space height - 2) * 2 + rmapbt
3. BMBT node split - (free space height - 2) * 2 + rmapbt
....
N. BMBT root split - (free space height - 2) * 2 + rmapbtSo the maximum number of chained allocations is likely going to be something like:
(max AGFL for one allocation) +
((max bmbt/refcountbt height) * (max agfl for dependent allocation))
Quoted 6 lines
Which is likely to be in the order of...
Quoted 2 lines
Quoted 2 lines
So I wouldn't expect the AGFL reserve pool to be any larger than a couple of hundred blocks in the worst case.
... this.
Thanks for the detailed explanation. It helps.
I do have a few followup questions on this part.
What strategy would you recommend we use to calculate the 'rmapbt' portion of this equation? I've defaulted to the same strategy of a single full-space rmapbt tree split, plus N (height - 2) splits, but instead of using the free space height I used the maxlevel in m_rmap_maxlevels. Does that sound correct to you?
For trees that are short, like a free-space reservation with a max height of 2, this math actually yields a smaller number of blocks than the constants it might replace below. In the case of a b-tree with a max height of 2, do we assume then that we'd only need 2 blocks to handle the full split, and the remaining dependent allocations would not consume any more space as records are added to the tree? (It sounds like yes, but wanted to confirm)
Quoted 128 lines
[ And now we disappear down the rabbit hole. ]
Take a look at
xfs_alloc_ag_max_usable(), which is used to setmp->m_ag_max_usable:blocks = XFS_BB_TO_FSB(mp, XFS_FSS_TO_BB(mp, 4)); /* ag headers */ blocks += XFS_ALLOCBT_AGFL_RESERVE; blocks += 3; /* AGF, AGI btree root blocks */ ....There's a number of blocks reserved for the AGFL that aren't usable already. What is that value for?
/*
* The number of blocks per AG that we withhold fromxfs_dec_fdblocksto
* guarantee that we can refill the AGFL prior to allocating space in a nearly
* full AG. Although the space described by the free space btrees, the
* blocks used by the freesp btrees themselves, and the blocks owned by the
* AGFL are counted in the ondisk fdblocks, it's a mistake to let the ondisk
* free space in the AG drop so low that the free space btrees cannot refill an
* empty AGFL up to the minimum level. Rather than grind through empty AGs
* until the fs goes down, we subtract this many AG blocks from the incore
* fdblocks to ensure user allocation does not overcommit the space the
* filesystem needs for the AGFLs. The rmap btree uses a per-AG reservation to
* withhold space fromxfs_dec_fdblocks, so we do not account for that here. */
#defineXFS_ALLOCBT_AGFL_RESERVE4What is this magic number of 4, then?
Remember what I said above about the free space btree blocks being accounted as free space and that freeing extents are always allowed to go ahead, even when the AG is full?
This AGFL reserve is the minimum space needed for an extent free to successfully refill the AGFL at ENOSPC to allow the extent free to proceed. That is, both trees have a singel level, so a full height split of either tree will require 2 blocks to be allocated. 2 freespace trees per AG, two blocks per tree, and so we need 4 blocks per AG to ensure freeing extents at ENOSPC will always succeed.
This "magic 4" blocks isn't valid when we have rmapbt, recountbt, or finobt reservations in the AG anymore, because ENOSPC can occur when we still have multi-level bno/cnt btrees in the AG. That's the first thing we need to fix.
This AGFL set aside is taken out of the global free space pool via this function:
/*
* Compute the number of blocks that we set aside to guarantee the ability to
* refill the AGFL and handle a full bmap btree split.
*
* In order to avoid ENOSPC-related deadlock caused by out-of-order locking of
* AGF buffer (PV 947395), we place constraints on the relationship among
* actual allocations for data blocks, freelist blocks, and potential file data
* bmap btree blocks. However, these restrictions may result in no actual space
* allocated for a delayed extent, for example, a data block in a certain AG is
* allocated but there is no additional block for the additional bmap btree
* block due to a split of the bmap btree of the file. The result of this may
* lead to an infinite loop when the file gets flushed to disk and all delayed
* extents need to be actually allocated. To get around this, we explicitly set
* aside a few blocks which will not be reserved in delayed allocation. *
* For each AG, we need to reserve enough blocks to replenish a totally empty
* AGFL and 4 more to handle a potential split of the file's bmap btree. */
unsigned int
xfs_alloc_set_aside(
structxfs_mount*mp){ return mp->m_sb.sb_agcount * (XFS_ALLOCBT_AGFL_RESERVE + 4); }But where did that magic number of "4 more to handle a potential split of the file's bmap btree" come from?
Ah, a fix I made for a ENOSPC regression back in 2006:
+ * ..... Considering the minimum number of
+ * needed freelist blocks is 4 fsbs_perAG_, a potential split of file's bmap
+ * btree requires 1 fsb, so we set the number of set-aside blocks
+ * to 4 + 4*agcount.
+ */
+#defineXFS_ALLOC_SET_ASIDE(mp)(4 + ((mp)->m_sb.sb_agcount * 4))That was fixing a regression caused by an ENOSPC deadlock bug fix done for SGI PV 947395.
commit
96b336c71016a85cd193762199aa6f99f543b6feAuthor: Yingping Lu <[email protected]> Date: Tue May 23 19:28:08 2006 +0000In actual allocation of file system blocks and freeing extents, the transaction within each such operation may involve multiple locking of AGF buffer. While the freeing extent function has sorted the extents based on AGF number before entering into transaction, however, when the file system space is very limited, the allocation of space would try every AGF to get space allocated, this could potentially cause out-of-order locking, thus deadlock could happen. This fix mitigates the scarce space for allocation by setting aside a few blocks without reservation, and avoid deadlock by maintaining ascending order of AGF locking.
Add a new flagXFS_ALLOC_FLAG_FREEINGto indicate whether the caller is freeing or allocating. Add a field firstblock in structurexfs_alloc_argto indicate whether this is the first allocation request.Which included this:
+ * ...... Considering the minimum number of
+ * needed freelist blocks is 4 fsbs, a potential split of file's bmap
+ * btree requires 1 fsb, so we set the number of set-aside blocks to 8.(quoted diff) +2
-0+*/ +#define SET_ASIDE_BLOCKS 8<ding!>
Ah, now I get it. It's only taken me 18 years to really understand how this value was originally derived and why it is wrong.
It assumed 4 blocks for the AGFL for the initial allocation to fill and empty AGFL, and then 4 more blocks for the AGFL to allow a refill for the subsequent BMBT block allocation to refill the AGFL. IOWs, it wasn't reserving blocks for the BMBT itself, it was reserving blocks for a second AGFL refill in the allocation chain....
Right, so I think what we need to change is
XFS_ALLOCBT_AGFL_RESERVEandxfs_alloc_set_aside()to reflect the worst case size of the free space trees when we hit ENOSPC for user data, not a hard coded 4 + 4.
Quoted 9 lines
The worst case free space tree size is going to be single block free records when all the per-ag reservations are at their maximum values. So we need to calculate maximum reservation sizes for the AG, then calculate how many btree blocks that will require to index as single block free space extents, then calculate the hieght of the btrees needs to index that. That gives us out "free space tree height at ENOSPC", and then we can calculate how many AGFL blocks we need at ENOSPC to handle a split of both trees. That value replaces
XFS_ALLOCBT_AGFL_RESERVE.
Just to confirm, this would be xfs_btree_compute_maxlevels(mp->m_alloc_mnr, n_perag_resvd_blocks), correct?
Quoted 8 lines
As for the BMBT split requiring more AGFL refills, we need to know what the maximum BMBT height the fs supports is (I think we already calculate that), and that then becomes the level we feed into the "how many AGFL blocks do we need in a full height BMBT split allocation chain. I did that math above, and that calculation should replace the "+ 4" in
xfs_alloc_set_aside(). I think that ends up with the calculation being something like:
Quoted 7 lines
setaside = agcount * (number of dependent allocations *
AGFL blocks for refill at ENOSPC)I think we also need to make
mp->m_ag_max_usablealso take into account the BMBT split related AGFL refills asxfs_alloc_set_aside()as it only considersXFS_ALLOCBT_AGFL_RESERVEright now. That will ensure we always have those blocks available for the AGFL.
Thanks, this was convincing enough that I went off to prototype something that tried to faithfully follow your advice.
Quoted 23 lines
Fair summary. this is already long, and I think what I discovered above kinda comes under:
Quoted 1 line
4. Implement a less ambitious AGFL reserve
That's what we did back in 2006 - we just carved out the smallest amount of blocks we needed from the free space pool to ensure the failing case worked.
Quoted 7 lines
The draft in this thread tried to track all AGFL blocks from their allocation and continued to account for them during their lifetime in the bnobt and cnobt. Instead of trying to build a reserve for all free space management blocks that aren't rmapbt, reduce the scope of the AGFL reserve to be just the number of blocks needed to satsify a single transaction with multiple allocations that occurs close to an AG's ENOSPC.
Yes, and that's what I suggest we extend
xfs_alloc_set_aside()andmp->m_ag_max_usableto encompass. That way we don't actually need to track anything, the AGs will always have that space available to use becausemp->m_ag_max_usableprevents them from being used by anything else.
Quoted 6 lines
Quoted 2 lines
Do any of these approaches stand out as clearly better (or worse) to you?
I think I've convinced myself that we already use option 4 and the accounting just needs extending to reserve the correct amount of blocks...
I've got something that sets the mp->m_ag_max_usable and alloc_set_aside() to the values discussed above. For demonstration purposes, since I was ending up with numbers that were smaller than XFS_ALLOCBT_AGFL_RESERVE + 4, I just picked some slightly different math that inflated these numbers a bit to validate the assumptions.
I'm still able to run AG low enough on space to hit the bug with these modifcations in place, partly because mp->m_ag_max_usable seems to place an upper bound on large contiguous allocations in xfs_alloc_space_available(). E.g. if I allocate in small chunks < m_ag_max_usable, I can still run pagf_freeblks down to about the per-ag reservation. The test is explicit about only using space from a single AG, which defeats the global reservation checks, since enough space remains free in the other AGs that we don't hit any of the per-filesystem reservation limits.
It seems like we've got the right general concept, but may need to make a few more tweaks to the implementation.
In terms of where to go next, I have a few ideas, but would certainly appreciate additional input.
One was to investigate propagating the per-AG set-aside into xfs_alloc_space_available() so that it's only eligible for consumption by a dependent allocation. (Is the correct way to determine that by checking tp->t_highest_agno != NULLAGNUMBER?)
The other was to determine if I needed add the quantity from xfs_alloc_min_freelist(free space height) to the set-aside. The reason for this was that if the reserved free space can be indexed by a tree of height 2, then the full split only needs 2 blocks, but once we've split to a tree of that height, xfs_alloc_min_freelist() requires 12 blocks free (with rmap off) to continue the allocation chain, even if we're never going to allocate that many. It's that edge case that these tests always manage to hit: run the pagf_freeblks within a block or two of the per-ag reservation, and then split a free-space b-tree right before a BMBT split. IOW, I need both the blocks for the b-tree expansion and enough to satisfy the xfs_alloc_min_freelist() checks. If you explained this earlier, and I'm reading the equations too pedantically, my apologies.
I also ran into a bit of a snag in the testing department after merging with 673cd885bbbf ("xfs: honor init_xattrs in xfs_init_new_inode for !ATTR fs") I understand broadly why this is needed, but it does modify when an inode converts from extents to b-tree. I couldn't find a way to disable this behavior via mkfs or a mount option for testing purposes. Are you aware of a switch I may have missed?
Quoted 10 lines
Quoted 3 lines
Thanks again for taking the time to read through these patches and provide feedback. I appreciate all the comments, ideas, and explanations.
Don't thank me - I've got to thank you for taking the time and effort to understand this complex code well enough to ask exactly the right question. It's not often that answering a question on how to do something causes a whole bunch of not quite connected floating pieces in my head to suddenly fall and land in exactly the right places... :)
I do very much appreciate the detailed explanations and the feedback, so it seemed like an expression of gratitude was appropriate. Thanks for your willingness to answer these questions in such detail.
-K
Re: [RFC PATCH 1/4] xfs: resurrect the AGFL reservation
Quoted 28 lines · Krister Johansen
[ My turn to apologize. I had a couple of short weeks at the beginning of July, but have finally been able to get back to this. ]
Quoted 15 lines · Dave Chinner
So the worst case AGFL requirement for a data extent allocation or free will be:
1. data extent - full free space tree split * 2 + rmapbt
2. BMBT leaf split - (free space height - 2) * 2 + rmapbt
3. BMBT node split - (free space height - 2) * 2 + rmapbt
....
N. BMBT root split - (free space height - 2) * 2 + rmapbtSo the maximum number of chained allocations is likely going to be something like:
(max AGFL for one allocation) +
((max bmbt/refcountbt height) * (max agfl for dependent allocation))Quoted 6 lines
Which is likely to be in the order of...
Quoted 2 lines
Quoted 2 lines
So I wouldn't expect the AGFL reserve pool to be any larger than a couple of hundred blocks in the worst case.
... this.
Thanks for the detailed explanation. It helps.
Quoted 7 lines
I do have a few followup questions on this part.
What strategy would you recommend we use to calculate the 'rmapbt' portion of this equation? I've defaulted to the same strategy of a single full-space rmapbt tree split, plus N (height - 2) splits, but instead of using the free space height I used the maxlevel in
m_rmap_maxlevels. Does that sound correct to you?
The rmapbt already has space reservations already set aside for it, and because the rmapbt updates are run in a separate transaction reservation context (i.e. they are done via deferred ops using intent chaining), I don't think they need to be considered a dependent allocation.
i.e. the issue we have right now is multiple allocations within a single transaction context failing part way through due to not having enough space to refill the AGFL in the middle of the transaction. This is typically happening because the rmapbt reservation is causing the AG to appear empty when it actually still has lots of space free in it. When the rmapbt update occurs, all it's allocations and AGFL refills come from that reserved space that the original allocation was not allowed to dip into.
Hence I don't think that the rmapbt space requirements actually impact on the data+BMBT dependent allocation chain AGFL space requirements.
Quoted 7 lines
For trees that are short, like a free-space reservation with a max height of 2, this math actually yields a smaller number of blocks than the constants it might replace below. In the case of a b-tree with a max height of 2, do we assume then that we'd only need 2 blocks to handle the full split, and the remaining dependent allocations would not consume any more space as records are added to the tree? (It sounds like yes, but wanted to confirm)
If the max height of the btree is two, then it can only contain a root block and leaf blocks. Hence once we've gone from a single block to a root + 2 half full leaf blocks, the rest of the updates are going to fit in either of the two leaf blocks. So, yes, I think the math works out in that case, too.
Quoted 25 lines
Quoted 15 lines
<ding!>
Ah, now I get it. It's only taken me 18 years to really understand how this value was originally derived and why it is wrong.
It assumed 4 blocks for the AGFL for the initial allocation to fill and empty AGFL, and then 4 more blocks for the AGFL to allow a refill for the subsequent BMBT block allocation to refill the AGFL. IOWs, it wasn't reserving blocks for the BMBT itself, it was reserving blocks for a second AGFL refill in the allocation chain....
Right, so I think what we need to change is
XFS_ALLOCBT_AGFL_RESERVEandxfs_alloc_set_aside()to reflect the worst case size of the free space trees when we hit ENOSPC for user data, not a hard coded 4 + 4.Quoted 9 lines
The worst case free space tree size is going to be single block free records when all the per-ag reservations are at their maximum values. So we need to calculate maximum reservation sizes for the AG, then calculate how many btree blocks that will require to index as single block free space extents, then calculate the hieght of the btrees needs to index that. That gives us out "free space tree height at ENOSPC", and then we can calculate how many AGFL blocks we need at ENOSPC to handle a split of both trees. That value replaces
XFS_ALLOCBT_AGFL_RESERVE.
Quoted 3 lines
Just to confirm, this would be
xfs_btree_compute_maxlevels(mp->m_alloc_mnr, n_perag_resvd_blocks), correct?
That sounds correct.
Quoted 49 lines
Quoted 23 lines
Fair summary. this is already long, and I think what I discovered above kinda comes under:
Quoted 1 line
4. Implement a less ambitious AGFL reserve
That's what we did back in 2006 - we just carved out the smallest amount of blocks we needed from the free space pool to ensure the failing case worked.
Quoted 7 lines
The draft in this thread tried to track all AGFL blocks from their allocation and continued to account for them during their lifetime in the bnobt and cnobt. Instead of trying to build a reserve for all free space management blocks that aren't rmapbt, reduce the scope of the AGFL reserve to be just the number of blocks needed to satsify a single transaction with multiple allocations that occurs close to an AG's ENOSPC.
Yes, and that's what I suggest we extend
xfs_alloc_set_aside()andmp->m_ag_max_usableto encompass. That way we don't actually need to track anything, the AGs will always have that space available to use becausemp->m_ag_max_usableprevents them from being used by anything else.Quoted 6 lines
Quoted 2 lines
Do any of these approaches stand out as clearly better (or worse) to you?
I think I've convinced myself that we already use option 4 and the accounting just needs extending to reserve the correct amount of blocks...
I've got something that sets the
mp->m_ag_max_usableandalloc_set_aside()to the values discussed above. For demonstration purposes, since I was ending up with numbers that were smaller thanXFS_ALLOCBT_AGFL_RESERVE+ 4, I just picked some slightly different math that inflated these numbers a bit to validate the assumptions.I'm still able to run AG low enough on space to hit the bug with these modifcations in place, partly because
mp->m_ag_max_usableseems to place an upper bound on large contiguous allocations inxfs_alloc_space_available(). E.g. if I allocate in small chunks <m_ag_max_usable, I can still runpagf_freeblksdown to about the per-ag reservation. The test is explicit about only using space from a single AG, which defeats the global reservation checks, since enough space remains free in the other AGs that we don't hit any of the per-filesystem reservation limits.It seems like we've got the right general concept, but may need to make a few more tweaks to the implementation.
Quoted 7 lines
In terms of where to go next, I have a few ideas, but would certainly appreciate additional input.
One was to investigate propagating the per-AG set-aside into
xfs_alloc_space_available()so that it's only eligible for consumption by a dependent allocation. (Is the correct way to determine that by checkingtp->t_highest_agno!= NULLAGNUMBER?)
Yes, I suspect that we aren't taking into account the correct set-aside value when checking if the AG has enough space available for the allocation to proceed. i.e. xfs_alloc_space_available() isn't getting the reserved space correct - it may be that xfs_ag_resv_needed() should be taking into account the set aside amount for XFS_AG_RESV_NONE allocations.
Quoted 7 lines
The other was to determine if I needed add the quantity from
xfs_alloc_min_freelist(free space height)to the set-aside. The reason for this was that if the reserved free space can be indexed by a tree of height 2, then the full split only needs 2 blocks, but once we've split to a tree of that height,xfs_alloc_min_freelist()requires 12 blocks free (with rmap off) to continue the allocation chain, even if we're never going to allocate that many.
Yes, that is definitely -one- of the problems here.
Quoted 7 lines
It's that edge case that these tests
always manage to hit: run thepagf_freeblkswithin a block or two of the per-ag reservation, and then split a free-space b-tree right before a BMBT split. IOW, I need both the blocks for the b-tree expansion and enough to satisfy thexfs_alloc_min_freelist()checks. If you explained this earlier, and I'm reading the equations too pedantically, my apologies.
No, I think you're getting deeper into the underlying issues that we haven't really solved properly as this code has grown organically to solve corner case issue after corner case issue.
Looking at it, and considering the concept of dependent allocation chains and reserve pools for different types of allocations I've previously explained, I think the calculation in xfs_alloc_min_freelist() is wrong.
That is, xfs_alloc_min_freelist() look sto assume that all AGFL blocks for a free space modification need to be reserved up front and placed in the AGFL before we start. Historically speaking, this was how allocation used to work. Then we introduced intent based operations for freeing extents in 1998 so the BMBT modifications were in a separate transaction to the extent freeing. Each now had their own AGFL refill requirements in completely decoupled transactions.
Then we added reflink and rmapbt as additional operations that are decoupled from the BMBT allocations and transactions by intents. They all run in their own allocation contexts and require their own independent AGFL fill operations.
However, xfs_alloc_min_freelist() makes the assumption that the AGFL must be large enough to handle both free space btree and rmapbt splits for every allocation, even though the space for an rmapbt split will only ever be needed when running a XFS_AG_RESV_RMAPBT allocation. IOWs, it is over-calculating the required AGFL size for most allocations.
Further, it is calculating this number for every allocation in a transaction, without taking into account the "dependent allocation chain" context. This is more difficult to do, because the required AGFL size only goes down when a full split is done in the chain.
I think we actually need to track the number of blocks we may need and have consumed for the AGFL within a transaction. We initialise that in the first transaction and ensure that we have that amount of space remaining in the AG, and then we always check that the remaining reservation is greater than the minimum free list size required for this allocation (it should always be).
Whenever we move blocks to/from the AGFL, we account for that in the transaction. Hence we have a direct accounting of the AGFL consumption across dependent allocations within that AG. When we complete one of the dependent allocations in a chain, we can reduce the reservation held the transaction by the number of AGFL blocks reserved but not consumed by that allocation, thereby allowing us to use more the remaining free space the further through the allocation chain we get....
IOWs, we need to track the total AGFL reservation/usage within the AG across the transaction, not just individual allocations. We need xfs_alloc_min_freelist() to be aware of allocation context and not reserve RMAPBT space for allocations that aren't modifying the rmapbt. We need xfs_alloc_space_available() to initialise and use transaction context based AGFL block reservations for considering whether there is space available or not. We need to account for AGFL blocks consumed during an AGFL grow operation.
Lifting the AGFL reservation tracking to the transaction structure for dependent allocation chains should alleviate these "but we don't know what happened on the previous allocation" and "what might be needed for the next allocation" issues. If we do this correctly, then we should never need to switch AGs during a dependent allocation chain because the first allocation in an will be rejected with ENOSPC because there isn't enough space for the dependent chain to complete....
Quoted 6 lines
I also ran into a bit of a snag in the testing department after merging with
673cd885bbbf("xfs: honorinit_xattrsinxfs_init_new_inodefor !ATTR fs") I understand broadly why this is needed, but it does modify when an inode converts from extents to b-tree. I couldn't find a way to disable this behavior via mkfs or a mount option for testing purposes. Are you aware of a switch I may have missed?
Just revert it for testing purposes.
-Dave.
Signature · 2 lines
Dave Chinner [email protected]
Re: [RFC PATCH 1/4] xfs: resurrect the AGFL reservation
Quoted 113 lines · Dave Chinner
Quoted 19 lines · Krister Johansen
I've got something that sets the
mp->m_ag_max_usableandalloc_set_aside()to the values discussed above. For demonstration purposes, since I was ending up with numbers that were smaller thanXFS_ALLOCBT_AGFL_RESERVE+ 4, I just picked some slightly different math that inflated these numbers a bit to validate the assumptions.I'm still able to run AG low enough on space to hit the bug with these modifcations in place, partly because
mp->m_ag_max_usableseems to place an upper bound on large contiguous allocations inxfs_alloc_space_available(). E.g. if I allocate in small chunks <m_ag_max_usable, I can still runpagf_freeblksdown to about the per-ag reservation. The test is explicit about only using space from a single AG, which defeats the global reservation checks, since enough space remains free in the other AGs that we don't hit any of the per-filesystem reservation limits.It seems like we've got the right general concept, but may need to make a few more tweaks to the implementation.
Quoted 7 lines
In terms of where to go next, I have a few ideas, but would certainly appreciate additional input.
One was to investigate propagating the per-AG set-aside into
xfs_alloc_space_available()so that it's only eligible for consumption by a dependent allocation. (Is the correct way to determine that by checkingtp->t_highest_agno!= NULLAGNUMBER?)Yes, I suspect that we aren't taking into account the correct set-aside value when checking if the AG has enough space available for the allocation to proceed. i.e.
xfs_alloc_space_available()isn't getting the reserved space correct - it may be thatxfs_ag_resv_needed()should be taking into account the set aside amount forXFS_AG_RESV_NONEallocations.Quoted 7 lines
The other was to determine if I needed add the quantity from
xfs_alloc_min_freelist(free space height)to the set-aside. The reason for this was that if the reserved free space can be indexed by a tree of height 2, then the full split only needs 2 blocks, but once we've split to a tree of that height,xfs_alloc_min_freelist()requires 12 blocks free (with rmap off) to continue the allocation chain, even if we're never going to allocate that many.Yes, that is definitely -one- of the problems here.
Quoted 7 lines
It's that edge case that these tests
always manage to hit: run thepagf_freeblkswithin a block or two of the per-ag reservation, and then split a free-space b-tree right before a BMBT split. IOW, I need both the blocks for the b-tree expansion and enough to satisfy thexfs_alloc_min_freelist()checks. If you explained this earlier, and I'm reading the equations too pedantically, my apologies.No, I think you're getting deeper into the underlying issues that we haven't really solved properly as this code has grown organically to solve corner case issue after corner case issue.
Looking at it, and considering the concept of dependent allocation chains and reserve pools for different types of allocations I've previously explained, I think the calculation in
xfs_alloc_min_freelist()is wrong.That is,
xfs_alloc_min_freelist()looks to assume that all AGFL blocks for a free space modification need to be reserved up front and placed in the AGFL before we start. Historically speaking, this was how allocation used to work. Then we introduced intent based operations for freeing extents in 1998 so the BMBT modifications were in a separate transaction to the extent freeing. Each now had their own AGFL refill requirements in completely decoupled transactions.Then we added reflink and rmapbt as additional operations that are decoupled from the BMBT allocations and transactions by intents. They all run in their own allocation contexts and require their own independent AGFL fill operations.
However,
xfs_alloc_min_freelist()makes the assumption that the AGFL must be large enough to handle both free space btree and rmapbt splits for every allocation, even though the space for an rmapbt split will only ever be needed when running aXFS_AG_RESV_RMAPBTallocation. IOWs, it is over-calculating the required AGFL size for most allocations.Further, it is calculating this number for every allocation in a transaction, without taking into account the "dependent allocation chain" context. This is more difficult to do, because the required AGFL size only goes down when a full split is done in the chain.
I think we actually need to track the number of blocks we may need and have consumed for the AGFL within a transaction. We initialise that in the first transaction and ensure that we have that amount of space remaining in the AG, and then we always check that the remaining reservation is greater than the minimum free list size required for this allocation (it should always be).
Whenever we move blocks to/from the AGFL, we account for that in the transaction. Hence we have a direct accounting of the AGFL consumption across dependent allocations within that AG. When we complete one of the dependent allocations in a chain, we can reduce the reservation held the transaction by the number of AGFL blocks reserved but not consumed by that allocation, thereby allowing us to use more the remaining free space the further through the allocation chain we get....
IOWs, we need to track the total AGFL reservation/usage within the AG across the transaction, not just individual allocations. We need
xfs_alloc_min_freelist()to be aware of allocation context and not reserve RMAPBT space for allocations that aren't modifying the rmapbt. We needxfs_alloc_space_available()to initialise and use transaction context based AGFL block reservations for considering whether there is space available or not. We need to account for AGFL blocks consumed during an AGFL grow operation.
Quoted 8 lines
Lifting the AGFL reservation tracking to the transaction structure for dependent allocation chains should alleviate these "but we don't know what happened on the previous allocation" and "what might be needed for the next allocation" issues. If we do this correctly, then we should never need to switch AGs during a dependent allocation chain because the first allocation in an will be rejected with ENOSPC because there isn't enough space for the dependent chain to complete....
I like the idea of moving the AGFL reservation tracking into the transacation, though I'm not certain I understand all the particulars yet.
In your mental model for how this might work, is the idea that the space for the AGFL reservation will be added to the transaction once an AG is selected for the allocations? Even with this approach, it will still be necessary to make some worst-case estimates about how much space might be used in a transaction chain, correct? E.g. the worst-case AGFL equations from earlier in this thread still apply, it's just that the space would be reserved _once_ at the beginning of the first transaction.
For the rmapbt allocations, it doesn't look like code calls into the allocator with XFS_AG_RESV_RMAPBT set. The code that allocates rmapbt blocks pulls a blocks from the AGFL and then deducts that from its per-AG reservation. I tried walking myself through a few examples, but it looks like it's possible to do an rmap allocation in a dependent allocation in a transaction even if the first allocation in the chain is not allocating a rmap record.
To give a specific example: allocating bmbt blocks associate a rmap entry with the inode for which the bmbt block is being allocated, but the first allocation may well set XFS_RMAP_OINFO_SKIP_UPDATE, like xfs_bmap_btalloc does.
It might be possible to use the oinfo in the xfs_alloc_arg structure to determine if a particular allocation can allocate a rmap entry. However, it also looks like allocating blocks to refill the AGFL can itself allocate these blocks. Is this a situation where we'd need to audit the different operations and add specific attributes to their existing xfs_trans_res to account for whether or not they'd allocate rmap entries? Or is there a better way to do this that I'm overlooking?
Thanks,
-K