* [PATCH 1/2] xfs: Introduce XFS_EXTENT_BUSY_IN_TRANS busy extent flag @ 2021-04-28 6:51 Chandan Babu R 2021-04-28 6:51 ` [PATCH 2/2] xfs: Prevent deadlock when allocating blocks for AGFL Chandan Babu R 0 siblings, 1 reply; 14+ messages in thread From: Chandan Babu R @ 2021-04-28 6:51 UTC (permalink / raw) To: linux-xfs; +Cc: Chandan Babu R This commit adds the busy extent flag XFS_EXTENT_BUSY_IN_TRANS which can be used to check if a busy extent is still on a transaction's t_busy list. The flag will be set when an extent is freed by __xfs_free_extent() and it is cleared when the busy extent is moved to CIL's busy extent list. This flag will be used in a future commit to prevent a deadlock when populating an AG's AGFL. Signed-off-by: Chandan Babu R <chandanrlinux@gmail.com> --- fs/xfs/libxfs/xfs_alloc.c | 2 +- fs/xfs/xfs_extent_busy.h | 1 + fs/xfs/xfs_log_cil.c | 4 ++++ 3 files changed, 6 insertions(+), 1 deletion(-) diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c index aaa19101bb2a..7dc50a435cf4 100644 --- a/fs/xfs/libxfs/xfs_alloc.c +++ b/fs/xfs/libxfs/xfs_alloc.c @@ -3332,7 +3332,7 @@ __xfs_free_extent( xfs_agblock_t agbno = XFS_FSB_TO_AGBNO(mp, bno); struct xfs_agf *agf; int error; - unsigned int busy_flags = 0; + unsigned int busy_flags = XFS_EXTENT_BUSY_IN_TRANS; ASSERT(len != 0); ASSERT(type != XFS_AG_RESV_AGFL); diff --git a/fs/xfs/xfs_extent_busy.h b/fs/xfs/xfs_extent_busy.h index 8aea07100092..929f72d1c699 100644 --- a/fs/xfs/xfs_extent_busy.h +++ b/fs/xfs/xfs_extent_busy.h @@ -28,6 +28,7 @@ struct xfs_extent_busy { unsigned int flags; #define XFS_EXTENT_BUSY_DISCARDED 0x01 /* undergoing a discard op. */ #define XFS_EXTENT_BUSY_SKIP_DISCARD 0x02 /* do not discard */ +#define XFS_EXTENT_BUSY_IN_TRANS 0x04 }; void diff --git a/fs/xfs/xfs_log_cil.c b/fs/xfs/xfs_log_cil.c index b0ef071b3cb5..f91b69e92b85 100644 --- a/fs/xfs/xfs_log_cil.c +++ b/fs/xfs/xfs_log_cil.c @@ -390,6 +390,7 @@ xlog_cil_insert_items( struct xfs_cil *cil = log->l_cilp; struct xfs_cil_ctx *ctx = cil->xc_ctx; struct xfs_log_item *lip; + struct xfs_extent_busy *busy; int len = 0; int diff_iovecs = 0; int iclog_space; @@ -410,6 +411,9 @@ xlog_cil_insert_items( len += iovhdr_res; ctx->nvecs += diff_iovecs; + list_for_each_entry(busy, &tp->t_busy, list) + busy->flags &= ~XFS_EXTENT_BUSY_IN_TRANS; + /* attach the transaction to the CIL if it has any busy extents */ if (!list_empty(&tp->t_busy)) list_splice_init(&tp->t_busy, &ctx->busy_extents); -- 2.30.2 ^ permalink raw reply related [flat|nested] 14+ messages in thread
* [PATCH 2/2] xfs: Prevent deadlock when allocating blocks for AGFL 2021-04-28 6:51 [PATCH 1/2] xfs: Introduce XFS_EXTENT_BUSY_IN_TRANS busy extent flag Chandan Babu R @ 2021-04-28 6:51 ` Chandan Babu R 2021-04-29 1:12 ` Dave Chinner 0 siblings, 1 reply; 14+ messages in thread From: Chandan Babu R @ 2021-04-28 6:51 UTC (permalink / raw) To: linux-xfs; +Cc: Chandan Babu R Executing xfs/538 after disabling injection of bmap_alloc_minlen_extent error can cause several tasks to trigger hung task timeout. Most of the tasks are blocked on getting a lock on an AG's AGF buffer. However, The task which has the lock on the AG's AGF buffer has the following call trace, PID: 1341 TASK: ffff8881073f3700 CPU: 1 COMMAND: "fsstress" __schedule+0x22f at ffffffff81f75e8f schedule+0x46 at ffffffff81f76366 xfs_extent_busy_flush+0x69 at ffffffff81477d99 xfs_alloc_ag_vextent_size+0x16a at ffffffff8141711a xfs_alloc_ag_vextent+0x19b at ffffffff81417edb xfs_alloc_fix_freelist+0x22f at ffffffff8141896f xfs_free_extent_fix_freelist+0x6a at ffffffff8141939a __xfs_free_extent+0x99 at ffffffff81419499 xfs_trans_free_extent+0x3e at ffffffff814a6fee xfs_extent_free_finish_item+0x24 at ffffffff814a70d4 xfs_defer_finish_noroll+0x1f7 at ffffffff81441407 xfs_defer_finish+0x11 at ffffffff814417e1 xfs_itruncate_extents_flags+0x13d at ffffffff8148b7dd xfs_inactive_truncate+0xb9 at ffffffff8148bb89 xfs_inactive+0x227 at ffffffff8148c4f7 xfs_fs_destroy_inode+0xb8 at ffffffff81496898 destroy_inode+0x3b at ffffffff8127d2ab do_unlinkat+0x1d1 at ffffffff81270df1 do_syscall_64+0x40 at ffffffff81f6b5f0 entry_SYSCALL_64_after_hwframe+0x44 at ffffffff8200007c The following sequence of events lead to the above listed call trace, 1. The task frees atleast two extents belonging to the file being truncated. 2. The corresponding xfs_extent_free_items are stored in the list pointed to by xfs_defer_pending->dfp_work. 3. When executing the next step of the rolling transaction, The first of the above mentioned extents is freed. The corresponding busy extent entry is added to the current transaction's tp->t_busy list as well as to the perag rb tree at xfs_perag->pagb_tree. 4. When trying to free the second extent, XFS determines that the AGFL needs to be populated and hence tries to allocate free blocks. 5. The only free extent whose size is >= xfs_alloc_arg->maxlen happens to be the first extent that was freed by the current transaction. 6. Hence xfs_alloc_ag_vextent_size() flushes the CIL in the hope of clearing the busy status of the extent and waits for the busy generation number to change. 7. However, flushing the CIL is futile since the busy extent is still in the current transaction's tp->t_busy list. Here the task ends up waiting indefinitely. This commit fixes the bug by preventing a CIL flush if all free extents are busy and all of them are in the transaction's tp->t_busy list. Signed-off-by: Chandan Babu R <chandanrlinux@gmail.com> --- fs/xfs/libxfs/xfs_alloc.c | 59 +++++++++++++++++++++++++++++---------- fs/xfs/xfs_extent_busy.c | 6 +++- fs/xfs/xfs_extent_busy.h | 2 +- 3 files changed, 51 insertions(+), 16 deletions(-) diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c index 7dc50a435cf4..8e5c91bd3031 100644 --- a/fs/xfs/libxfs/xfs_alloc.c +++ b/fs/xfs/libxfs/xfs_alloc.c @@ -274,7 +274,8 @@ xfs_alloc_compute_aligned( xfs_extlen_t foundlen, /* length in found extent */ xfs_agblock_t *resbno, /* result block number */ xfs_extlen_t *reslen, /* result length */ - unsigned *busy_gen) + unsigned *busy_gen, + bool *busy_in_trans) { xfs_agblock_t bno = foundbno; xfs_extlen_t len = foundlen; @@ -282,7 +283,7 @@ xfs_alloc_compute_aligned( bool busy; /* Trim busy sections out of found extent */ - busy = xfs_extent_busy_trim(args, &bno, &len, busy_gen); + busy = xfs_extent_busy_trim(args, &bno, &len, busy_gen, busy_in_trans); /* * If we have a largish extent that happens to start before min_agbno, @@ -852,7 +853,7 @@ xfs_alloc_cur_check( } busy = xfs_alloc_compute_aligned(args, bno, len, &bnoa, &lena, - &busy_gen); + &busy_gen, NULL); acur->busy |= busy; if (busy) acur->busy_gen = busy_gen; @@ -1248,7 +1249,7 @@ xfs_alloc_ag_vextent_exact( */ tbno = fbno; tlen = flen; - xfs_extent_busy_trim(args, &tbno, &tlen, &busy_gen); + xfs_extent_busy_trim(args, &tbno, &tlen, &busy_gen, NULL); /* * Give up if the start of the extent is busy, or the freespace isn't @@ -1669,6 +1670,9 @@ xfs_alloc_ag_vextent_size( xfs_extlen_t rlen; /* length of returned extent */ bool busy; unsigned busy_gen; + bool busy_in_trans; + bool all_busy_in_trans; + bool alloc_small_extent; restart: /* @@ -1677,6 +1681,10 @@ xfs_alloc_ag_vextent_size( cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp, args->agno, XFS_BTNUM_CNT); bno_cur = NULL; + alloc_small_extent = false; + all_busy_in_trans = true; + +restart_alloc_small_extent: busy = false; /* @@ -1687,13 +1695,14 @@ xfs_alloc_ag_vextent_size( goto error0; /* - * If none then we have to settle for a smaller extent. In the case that - * there are no large extents, this will return the last entry in the - * tree unless the tree is empty. In the case that there are only busy - * large extents, this will return the largest small extent unless there - * are no smaller extents available. + * We have to settle for a smaller extent if there are no maxlen + + * alignment - 1 sized extents or if all larger free extents are still + * in current transaction's busy list. In either case, this will return + * the last entry in the tree unless the tree is empty. In the case that + * there are only busy large extents, this will return the largest small + * extent unless there are no smaller extents available. */ - if (!i) { + if (!i || alloc_small_extent) { error = xfs_alloc_ag_vextent_small(args, cnt_cur, &fbno, &flen, &i); if (error) @@ -1705,7 +1714,9 @@ xfs_alloc_ag_vextent_size( } ASSERT(i == 1); busy = xfs_alloc_compute_aligned(args, fbno, flen, &rbno, - &rlen, &busy_gen); + &rlen, &busy_gen, &busy_in_trans); + if (busy && !busy_in_trans) + all_busy_in_trans = false; } else { /* * Search for a non-busy extent that is large enough. @@ -1720,15 +1731,32 @@ xfs_alloc_ag_vextent_size( } busy = xfs_alloc_compute_aligned(args, fbno, flen, - &rbno, &rlen, &busy_gen); + &rbno, &rlen, &busy_gen, + &busy_in_trans); if (rlen >= args->maxlen) break; + if (busy && !busy_in_trans) + all_busy_in_trans = false; + error = xfs_btree_increment(cnt_cur, 0, &i); if (error) goto error0; if (i == 0) { + /* + * All of the large free extents are busy in the + * current transaction's t->t_busy + * list. Hence, flushing the CIL's busy extent list + * will be futile and also leads to the current + * task waiting indefinitely. Hence try to + * allocate smaller extents. + */ + if (all_busy_in_trans) { + alloc_small_extent = true; + goto restart_alloc_small_extent; + } + /* * Our only valid extents must have been busy. * Make it unbusy by forcing the log out and @@ -1783,7 +1811,10 @@ xfs_alloc_ag_vextent_size( if (flen < bestrlen) break; busy = xfs_alloc_compute_aligned(args, fbno, flen, - &rbno, &rlen, &busy_gen); + &rbno, &rlen, &busy_gen, + &busy_in_trans); + if (busy && !busy_in_trans) + all_busy_in_trans = false; rlen = XFS_EXTLEN_MIN(args->maxlen, rlen); if (XFS_IS_CORRUPT(args->mp, rlen != 0 && @@ -1819,7 +1850,7 @@ xfs_alloc_ag_vextent_size( */ args->len = rlen; if (rlen < args->minlen) { - if (busy) { + if (busy && !all_busy_in_trans) { xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR); trace_xfs_alloc_size_busy(args); xfs_extent_busy_flush(args->mp, args->pag, busy_gen); diff --git a/fs/xfs/xfs_extent_busy.c b/fs/xfs/xfs_extent_busy.c index a4075685d9eb..16ba514f9e81 100644 --- a/fs/xfs/xfs_extent_busy.c +++ b/fs/xfs/xfs_extent_busy.c @@ -334,7 +334,8 @@ xfs_extent_busy_trim( struct xfs_alloc_arg *args, xfs_agblock_t *bno, xfs_extlen_t *len, - unsigned *busy_gen) + unsigned *busy_gen, + bool *busy_in_trans) { xfs_agblock_t fbno; xfs_extlen_t flen; @@ -362,6 +363,9 @@ xfs_extent_busy_trim( continue; } + if (busy_in_trans) + *busy_in_trans = busyp->flags & XFS_EXTENT_BUSY_IN_TRANS; + if (bbno <= fbno) { /* start overlap */ diff --git a/fs/xfs/xfs_extent_busy.h b/fs/xfs/xfs_extent_busy.h index 929f72d1c699..dcdc70821622 100644 --- a/fs/xfs/xfs_extent_busy.h +++ b/fs/xfs/xfs_extent_busy.h @@ -49,7 +49,7 @@ xfs_extent_busy_reuse(struct xfs_mount *mp, xfs_agnumber_t agno, bool xfs_extent_busy_trim(struct xfs_alloc_arg *args, xfs_agblock_t *bno, - xfs_extlen_t *len, unsigned *busy_gen); + xfs_extlen_t *len, unsigned *busy_gen, bool *busy_in_trans); void xfs_extent_busy_flush(struct xfs_mount *mp, struct xfs_perag *pag, -- 2.30.2 ^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH 2/2] xfs: Prevent deadlock when allocating blocks for AGFL 2021-04-28 6:51 ` [PATCH 2/2] xfs: Prevent deadlock when allocating blocks for AGFL Chandan Babu R @ 2021-04-29 1:12 ` Dave Chinner 2021-04-30 13:40 ` Chandan Babu R 0 siblings, 1 reply; 14+ messages in thread From: Dave Chinner @ 2021-04-29 1:12 UTC (permalink / raw) To: Chandan Babu R; +Cc: linux-xfs On Wed, Apr 28, 2021 at 12:21:52PM +0530, Chandan Babu R wrote: > Executing xfs/538 after disabling injection of bmap_alloc_minlen_extent error > can cause several tasks to trigger hung task timeout. Most of the tasks are > blocked on getting a lock on an AG's AGF buffer. However, The task which has > the lock on the AG's AGF buffer has the following call trace, > > PID: 1341 TASK: ffff8881073f3700 CPU: 1 COMMAND: "fsstress" > __schedule+0x22f at ffffffff81f75e8f > schedule+0x46 at ffffffff81f76366 > xfs_extent_busy_flush+0x69 at ffffffff81477d99 > xfs_alloc_ag_vextent_size+0x16a at ffffffff8141711a > xfs_alloc_ag_vextent+0x19b at ffffffff81417edb > xfs_alloc_fix_freelist+0x22f at ffffffff8141896f > xfs_free_extent_fix_freelist+0x6a at ffffffff8141939a > __xfs_free_extent+0x99 at ffffffff81419499 > xfs_trans_free_extent+0x3e at ffffffff814a6fee > xfs_extent_free_finish_item+0x24 at ffffffff814a70d4 > xfs_defer_finish_noroll+0x1f7 at ffffffff81441407 > xfs_defer_finish+0x11 at ffffffff814417e1 > xfs_itruncate_extents_flags+0x13d at ffffffff8148b7dd > xfs_inactive_truncate+0xb9 at ffffffff8148bb89 > xfs_inactive+0x227 at ffffffff8148c4f7 > xfs_fs_destroy_inode+0xb8 at ffffffff81496898 > destroy_inode+0x3b at ffffffff8127d2ab > do_unlinkat+0x1d1 at ffffffff81270df1 > do_syscall_64+0x40 at ffffffff81f6b5f0 > entry_SYSCALL_64_after_hwframe+0x44 at ffffffff8200007c > > The following sequence of events lead to the above listed call trace, > > 1. The task frees atleast two extents belonging to the file being truncated. > 2. The corresponding xfs_extent_free_items are stored in the list pointed to > by xfs_defer_pending->dfp_work. > 3. When executing the next step of the rolling transaction, The first of the > above mentioned extents is freed. The corresponding busy extent entry is > added to the current transaction's tp->t_busy list as well as to the perag > rb tree at xfs_perag->pagb_tree. > 4. When trying to free the second extent, XFS determines that the AGFL needs > to be populated and hence tries to allocate free blocks. > 5. The only free extent whose size is >= xfs_alloc_arg->maxlen > happens to be the first extent that was freed by the current transaction. > 6. Hence xfs_alloc_ag_vextent_size() flushes the CIL in the hope of clearing > the busy status of the extent and waits for the busy generation number to > change. > 7. However, flushing the CIL is futile since the busy extent is still in the > current transaction's tp->t_busy list. > > Here the task ends up waiting indefinitely. > > This commit fixes the bug by preventing a CIL flush if all free extents are > busy and all of them are in the transaction's tp->t_busy list. Hmmm. I don't doubt that this fixes the symptom you are seeing, but the way it is being fixed doesn't seem right to me at all. We're rtying to populate the AGFL here, and the fact is that a multi-block allocation is simply an optimisation to minimise the number of extents we need to allocate to fill the AGFL. The extent that gets allocated gets broken up into single blocks to be inserted into the AGFL, so we don't actually need a continuguous extent to be allocated here. Hence, if the extent we find is busy when allocating for the AGFL, we should just skip it and choose another extent. args->minlen is set to zero for the allocation, so we can actually return any extent that has a length <= args->maxlen. We know this is an AGFL allocation because args->resv == XFS_AG_RESV_AGFL, so if we find a busy extent that would require a log force to be able to use before we can place it in the AGFL, we should just skip it entirely and select another extent to allocate from. Adding another two boolean conditionals to the already complex extent selection for this specific case makes the code much harder to follow and reason about. I'd much prefer that we just do something like: if (busy && args->resv == XFS_AG_RESV_AGFL) { /* * Extent might have just been freed in this * transaction so we can't use it. Move to the next * best extent candidate and try that instead. */ <increment/decrement and continue the search loop> } IOWs, we should not be issuing a log force to flush busy extents if we can't use the largest candidate free extent for the AGFL - we should just keep searching until we find one we can use.... Cheers, Dave. -- Dave Chinner david@fromorbit.com ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH 2/2] xfs: Prevent deadlock when allocating blocks for AGFL 2021-04-29 1:12 ` Dave Chinner @ 2021-04-30 13:40 ` Chandan Babu R 2021-04-30 22:44 ` Dave Chinner 0 siblings, 1 reply; 14+ messages in thread From: Chandan Babu R @ 2021-04-30 13:40 UTC (permalink / raw) To: Dave Chinner; +Cc: linux-xfs On 29 Apr 2021 at 06:42, Dave Chinner wrote: > On Wed, Apr 28, 2021 at 12:21:52PM +0530, Chandan Babu R wrote: >> Executing xfs/538 after disabling injection of bmap_alloc_minlen_extent error >> can cause several tasks to trigger hung task timeout. Most of the tasks are >> blocked on getting a lock on an AG's AGF buffer. However, The task which has >> the lock on the AG's AGF buffer has the following call trace, >> [..] > Hmmm. I don't doubt that this fixes the symptom you are seeing, but > the way it is being fixed doesn't seem right to me at all. > > We're rtying to populate the AGFL here, and the fact is that a > multi-block allocation is simply an optimisation to minimise the > number of extents we need to allocate to fill the AGFL. The extent > that gets allocated gets broken up into single blocks to be inserted > into the AGFL, so we don't actually need a continuguous extent to be > allocated here. > > Hence, if the extent we find is busy when allocating for the AGFL, > we should just skip it and choose another extent. args->minlen is > set to zero for the allocation, so we can actually return any extent > that has a length <= args->maxlen. We know this is an AGFL > allocation because args->resv == XFS_AG_RESV_AGFL, so if we find a > busy extent that would require a log force to be able to use before > we can place it in the AGFL, we should just skip it entirely and > select another extent to allocate from. > > Adding another two boolean conditionals to the already complex > extent selection for this specific case makes the code much harder > to follow and reason about. I'd much prefer that we just do > something like: > > if (busy && args->resv == XFS_AG_RESV_AGFL) { > /* > * Extent might have just been freed in this > * transaction so we can't use it. Move to the next > * best extent candidate and try that instead. > */ > <increment/decrement and continue the search loop> > } > > IOWs, we should not be issuing a log force to flush busy extents if > we can't use the largest candidate free extent for the AGFL - we > should just keep searching until we find one we can use.... IIUC, the following patch implements the solution that has been suggested above, diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c index aaa19101bb2a..25456dbff767 100644 --- a/fs/xfs/libxfs/xfs_alloc.c +++ b/fs/xfs/libxfs/xfs_alloc.c @@ -1694,6 +1694,7 @@ xfs_alloc_ag_vextent_size( * are no smaller extents available. */ if (!i) { +alloc_small_extent: error = xfs_alloc_ag_vextent_small(args, cnt_cur, &fbno, &flen, &i); if (error) @@ -1707,6 +1708,8 @@ xfs_alloc_ag_vextent_size( busy = xfs_alloc_compute_aligned(args, fbno, flen, &rbno, &rlen, &busy_gen); } else { + xfs_agblock_t orig_fbno = NULLAGBLOCK; + xfs_extlen_t orig_flen; /* * Search for a non-busy extent that is large enough. */ @@ -1719,6 +1722,11 @@ xfs_alloc_ag_vextent_size( goto error0; } + if (orig_fbno == NULLAGBLOCK) { + orig_fbno = fbno; + orig_flen = flen; + } + busy = xfs_alloc_compute_aligned(args, fbno, flen, &rbno, &rlen, &busy_gen); @@ -1734,6 +1742,14 @@ xfs_alloc_ag_vextent_size( * Make it unbusy by forcing the log out and * retrying. */ + if (args->resv == XFS_AG_RESV_AGFL) { + error = xfs_alloc_lookup_eq(cnt_cur, + orig_fbno, orig_flen, &i); + ASSERT(!error && i); + + goto alloc_small_extent; + } + xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR); trace_xfs_alloc_size_busy(args); @@ -1819,7 +1835,7 @@ xfs_alloc_ag_vextent_size( */ args->len = rlen; if (rlen < args->minlen) { - if (busy) { + if (busy && args->resv != XFS_AG_RESV_AGFL) { xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR); trace_xfs_alloc_size_busy(args); xfs_extent_busy_flush(args->mp, args->pag, busy_gen); i.e. when we end up at the right most edge of the cntbt during allocation of blocks for refilling AGFL, the above patch backtracks and continues search towards the left edge of the cntbt instead of flushing the CIL. If the leftmost edge is reached without finding any suitable free extent and the blocks are being allocated for AGFL, the function returns back to the caller instead of flushing the CIL and retrying once again. With the above patch, a workload which consists of, 1. Filling up 90% of the free space of the filesystem. 2. Punch alternate blocks of files. .. would cause failure when inserting records into either cntbt/bnobt due to unavailability of AGFL blocks. This happens because most of the free blocks resulting from punching out alternate blocks would be residing in the CIL's extent busy list. xfs/538 creates 1G sized scratch filesystem and the "punch alternate blocks" workload creates a little more than 8000 entries in the CIL extent busy list. So, may be there are no other alternatives other than to flush the CIL. To that end, I have tried to slightly simplify the patch that I had originally sent (i.e. [PATCH 2/2] xfs: Prevent deadlock when allocating blocks for AGFL). The new patch removes one the boolean variables (i.e. alloc_small_extent) and also skips redundant searching of extent records when backtracking in preparation for searching smaller extents. diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c index 7dc50a435cf4..ea01c2674247 100644 --- a/fs/xfs/libxfs/xfs_alloc.c +++ b/fs/xfs/libxfs/xfs_alloc.c @@ -274,7 +274,8 @@ xfs_alloc_compute_aligned( xfs_extlen_t foundlen, /* length in found extent */ xfs_agblock_t *resbno, /* result block number */ xfs_extlen_t *reslen, /* result length */ - unsigned *busy_gen) + unsigned *busy_gen, + bool *busy_in_trans) { xfs_agblock_t bno = foundbno; xfs_extlen_t len = foundlen; @@ -282,7 +283,7 @@ xfs_alloc_compute_aligned( bool busy; /* Trim busy sections out of found extent */ - busy = xfs_extent_busy_trim(args, &bno, &len, busy_gen); + busy = xfs_extent_busy_trim(args, &bno, &len, busy_gen, busy_in_trans); /* * If we have a largish extent that happens to start before min_agbno, @@ -852,7 +853,7 @@ xfs_alloc_cur_check( } busy = xfs_alloc_compute_aligned(args, bno, len, &bnoa, &lena, - &busy_gen); + &busy_gen, NULL); acur->busy |= busy; if (busy) acur->busy_gen = busy_gen; @@ -1248,7 +1249,7 @@ xfs_alloc_ag_vextent_exact( */ tbno = fbno; tlen = flen; - xfs_extent_busy_trim(args, &tbno, &tlen, &busy_gen); + xfs_extent_busy_trim(args, &tbno, &tlen, &busy_gen, NULL); /* * Give up if the start of the extent is busy, or the freespace isn't @@ -1669,6 +1670,8 @@ xfs_alloc_ag_vextent_size( xfs_extlen_t rlen; /* length of returned extent */ bool busy; unsigned busy_gen; + bool busy_in_trans; + bool all_busy_in_trans; restart: /* @@ -1677,6 +1680,7 @@ xfs_alloc_ag_vextent_size( cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp, args->agno, XFS_BTNUM_CNT); bno_cur = NULL; + all_busy_in_trans = true; busy = false; /* @@ -1687,13 +1691,15 @@ xfs_alloc_ag_vextent_size( goto error0; /* - * If none then we have to settle for a smaller extent. In the case that - * there are no large extents, this will return the last entry in the - * tree unless the tree is empty. In the case that there are only busy - * large extents, this will return the largest small extent unless there - * are no smaller extents available. + * We have to settle for a smaller extent if there are no maxlen + + * alignment - 1 sized extents or if all larger free extents are still + * in current transaction's busy list. In either case, this will return + * the last entry in the tree unless the tree is empty. In the case that + * there are only busy large extents, this will return the largest small + * extent unless there are no smaller extents available. */ if (!i) { +alloc_small_extent: error = xfs_alloc_ag_vextent_small(args, cnt_cur, &fbno, &flen, &i); if (error) @@ -1705,8 +1711,12 @@ xfs_alloc_ag_vextent_size( } ASSERT(i == 1); busy = xfs_alloc_compute_aligned(args, fbno, flen, &rbno, - &rlen, &busy_gen); + &rlen, &busy_gen, &busy_in_trans); + if (busy && !busy_in_trans) + all_busy_in_trans = false; } else { + xfs_agblock_t orig_fbno = NULLAGBLOCK; + xfs_extlen_t orig_flen; /* * Search for a non-busy extent that is large enough. */ @@ -1719,27 +1729,52 @@ xfs_alloc_ag_vextent_size( goto error0; } + if (orig_fbno == NULLAGBLOCK) { + orig_fbno = fbno; + orig_flen = flen; + } + busy = xfs_alloc_compute_aligned(args, fbno, flen, - &rbno, &rlen, &busy_gen); + &rbno, &rlen, &busy_gen, + &busy_in_trans); if (rlen >= args->maxlen) break; + if (busy && !busy_in_trans) + all_busy_in_trans = false; + error = xfs_btree_increment(cnt_cur, 0, &i); if (error) goto error0; if (i == 0) { + if (!all_busy_in_trans) { + /* + * Our only valid extents must have been busy. + * Make it unbusy by forcing the log out and + * retrying. + */ + xfs_btree_del_cursor(cnt_cur, + XFS_BTREE_NOERROR); + trace_xfs_alloc_size_busy(args); + xfs_extent_busy_flush(args->mp, + args->pag, busy_gen); + goto restart; + } + /* - * Our only valid extents must have been busy. - * Make it unbusy by forcing the log out and - * retrying. + * All the large free extents are busy in the + * current transaction's t->t_busy list. Hence + * forcing the log will will be futile and also + * leads to the current task waiting + * indefinitely. Hence try to allocate smaller + * extents. */ - xfs_btree_del_cursor(cnt_cur, - XFS_BTREE_NOERROR); - trace_xfs_alloc_size_busy(args); - xfs_extent_busy_flush(args->mp, - args->pag, busy_gen); - goto restart; + error = xfs_alloc_lookup_eq(cnt_cur, orig_fbno, + orig_flen, &i); + ASSERT(!error && i); + + goto alloc_small_extent; } } } @@ -1783,7 +1818,10 @@ xfs_alloc_ag_vextent_size( if (flen < bestrlen) break; busy = xfs_alloc_compute_aligned(args, fbno, flen, - &rbno, &rlen, &busy_gen); + &rbno, &rlen, &busy_gen, + &busy_in_trans); + if (busy && !busy_in_trans) + all_busy_in_trans = false; rlen = XFS_EXTLEN_MIN(args->maxlen, rlen); if (XFS_IS_CORRUPT(args->mp, rlen != 0 && @@ -1819,7 +1857,7 @@ xfs_alloc_ag_vextent_size( */ args->len = rlen; if (rlen < args->minlen) { - if (busy) { + if (busy && !all_busy_in_trans) { xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR); trace_xfs_alloc_size_busy(args); xfs_extent_busy_flush(args->mp, args->pag, busy_gen); diff --git a/fs/xfs/xfs_extent_busy.c b/fs/xfs/xfs_extent_busy.c index a4075685d9eb..16ba514f9e81 100644 --- a/fs/xfs/xfs_extent_busy.c +++ b/fs/xfs/xfs_extent_busy.c @@ -334,7 +334,8 @@ xfs_extent_busy_trim( struct xfs_alloc_arg *args, xfs_agblock_t *bno, xfs_extlen_t *len, - unsigned *busy_gen) + unsigned *busy_gen, + bool *busy_in_trans) { xfs_agblock_t fbno; xfs_extlen_t flen; @@ -362,6 +363,9 @@ xfs_extent_busy_trim( continue; } + if (busy_in_trans) + *busy_in_trans = busyp->flags & XFS_EXTENT_BUSY_IN_TRANS; + if (bbno <= fbno) { /* start overlap */ diff --git a/fs/xfs/xfs_extent_busy.h b/fs/xfs/xfs_extent_busy.h index 929f72d1c699..dcdc70821622 100644 --- a/fs/xfs/xfs_extent_busy.h +++ b/fs/xfs/xfs_extent_busy.h @@ -49,7 +49,7 @@ xfs_extent_busy_reuse(struct xfs_mount *mp, xfs_agnumber_t agno, bool xfs_extent_busy_trim(struct xfs_alloc_arg *args, xfs_agblock_t *bno, - xfs_extlen_t *len, unsigned *busy_gen); + xfs_extlen_t *len, unsigned *busy_gen, bool *busy_in_trans); void xfs_extent_busy_flush(struct xfs_mount *mp, struct xfs_perag *pag, Please let me know your views on this. -- chandan ^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH 2/2] xfs: Prevent deadlock when allocating blocks for AGFL 2021-04-30 13:40 ` Chandan Babu R @ 2021-04-30 22:44 ` Dave Chinner 2021-05-03 9:52 ` Chandan Babu R 0 siblings, 1 reply; 14+ messages in thread From: Dave Chinner @ 2021-04-30 22:44 UTC (permalink / raw) To: Chandan Babu R; +Cc: linux-xfs On Fri, Apr 30, 2021 at 07:10:31PM +0530, Chandan Babu R wrote: > On 29 Apr 2021 at 06:42, Dave Chinner wrote: > > On Wed, Apr 28, 2021 at 12:21:52PM +0530, Chandan Babu R wrote: > >> Executing xfs/538 after disabling injection of bmap_alloc_minlen_extent error > >> can cause several tasks to trigger hung task timeout. Most of the tasks are > >> blocked on getting a lock on an AG's AGF buffer. However, The task which has > >> the lock on the AG's AGF buffer has the following call trace, > >> > [..] > > Hmmm. I don't doubt that this fixes the symptom you are seeing, but > > the way it is being fixed doesn't seem right to me at all. > > > > We're rtying to populate the AGFL here, and the fact is that a > > multi-block allocation is simply an optimisation to minimise the > > number of extents we need to allocate to fill the AGFL. The extent > > that gets allocated gets broken up into single blocks to be inserted > > into the AGFL, so we don't actually need a continuguous extent to be > > allocated here. > > > > Hence, if the extent we find is busy when allocating for the AGFL, > > we should just skip it and choose another extent. args->minlen is > > set to zero for the allocation, so we can actually return any extent > > that has a length <= args->maxlen. We know this is an AGFL > > allocation because args->resv == XFS_AG_RESV_AGFL, so if we find a > > busy extent that would require a log force to be able to use before > > we can place it in the AGFL, we should just skip it entirely and > > select another extent to allocate from. > > > > Adding another two boolean conditionals to the already complex > > extent selection for this specific case makes the code much harder > > to follow and reason about. I'd much prefer that we just do > > something like: > > > > if (busy && args->resv == XFS_AG_RESV_AGFL) { > > /* > > * Extent might have just been freed in this > > * transaction so we can't use it. Move to the next > > * best extent candidate and try that instead. > > */ > > <increment/decrement and continue the search loop> > > } > > > > IOWs, we should not be issuing a log force to flush busy extents if > > we can't use the largest candidate free extent for the AGFL - we > > should just keep searching until we find one we can use.... > > IIUC, the following patch implements the solution that has been suggested > above, > > diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c > index aaa19101bb2a..25456dbff767 100644 > --- a/fs/xfs/libxfs/xfs_alloc.c > +++ b/fs/xfs/libxfs/xfs_alloc.c > @@ -1694,6 +1694,7 @@ xfs_alloc_ag_vextent_size( > * are no smaller extents available. > */ > if (!i) { > +alloc_small_extent: > error = xfs_alloc_ag_vextent_small(args, cnt_cur, > &fbno, &flen, &i); > if (error) > @@ -1707,6 +1708,8 @@ xfs_alloc_ag_vextent_size( > busy = xfs_alloc_compute_aligned(args, fbno, flen, &rbno, > &rlen, &busy_gen); > } else { > + xfs_agblock_t orig_fbno = NULLAGBLOCK; > + xfs_extlen_t orig_flen; > /* > * Search for a non-busy extent that is large enough. > */ > @@ -1719,6 +1722,11 @@ xfs_alloc_ag_vextent_size( > goto error0; > } > > + if (orig_fbno == NULLAGBLOCK) { > + orig_fbno = fbno; > + orig_flen = flen; > + } > + > busy = xfs_alloc_compute_aligned(args, fbno, flen, > &rbno, &rlen, &busy_gen); > > @@ -1734,6 +1742,14 @@ xfs_alloc_ag_vextent_size( > * Make it unbusy by forcing the log out and > * retrying. > */ > + if (args->resv == XFS_AG_RESV_AGFL) { > + error = xfs_alloc_lookup_eq(cnt_cur, > + orig_fbno, orig_flen, &i); > + ASSERT(!error && i); > + > + goto alloc_small_extent; > + } > + > xfs_btree_del_cursor(cnt_cur, > XFS_BTREE_NOERROR); > trace_xfs_alloc_size_busy(args); > @@ -1819,7 +1835,7 @@ xfs_alloc_ag_vextent_size( > */ > args->len = rlen; > if (rlen < args->minlen) { > - if (busy) { > + if (busy && args->resv != XFS_AG_RESV_AGFL) { > xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR); > trace_xfs_alloc_size_busy(args); > xfs_extent_busy_flush(args->mp, args->pag, busy_gen); > > i.e. when we end up at the right most edge of the cntbt during allocation of > blocks for refilling AGFL, the above patch backtracks and continues search > towards the left edge of the cntbt instead of flushing the CIL. If the > leftmost edge is reached without finding any suitable free extent and the > blocks are being allocated for AGFL, the function returns back to the caller > instead of flushing the CIL and retrying once again. At which point, we know that all the free extents in that AG are either busy or we are truly out of space. Hence if this search fails, it makes sense to call xfs_extent_busy_flush() to wait for all the busy extents in the AG to complete their processing before trying again. > With the above patch, a workload which consists of, > 1. Filling up 90% of the free space of the filesystem. > 2. Punch alternate blocks of files. > > .. would cause failure when inserting records into either cntbt/bnobt due to > unavailability of AGFL blocks. > > This happens because most of the free blocks resulting from punching out > alternate blocks would be residing in the CIL's extent busy list. xfs/538 > creates 1G sized scratch filesystem and the "punch alternate blocks" workload > creates a little more than 8000 entries in the CIL extent busy list. Seems like you broke the existing handling of this situation by preventing the AGFL filling code from flushing the busy extents when all the AG can find is busy extents. > So, may be there are no other alternatives other than to flush the CIL. To Sure, I never suggested that we completely elide log forces. What I said is that we -shouldn't immediately resort to a log force- because the first maxlen extent match we come across is busy and can't immediately be reused. That is, the code still needs to call xfs_extent_busy_flush() and try the allocation again, it just needs to do it when no candidate extent can be found instead of after the first candidate is found to be busy. > that end, I have tried to slightly simplify the patch that I had originally > sent (i.e. [PATCH 2/2] xfs: Prevent deadlock when allocating blocks for > AGFL). The new patch removes one the boolean variables > (i.e. alloc_small_extent) and also skips redundant searching of extent records > when backtracking in preparation for searching smaller extents. I still don't think this is right approach because it tries to correct a bad decision (use a busy extent instead of trying the next free extent) with another bad decision (log force might not unbusy the extent we are trying to allocate). We should not do either of these things in this situation, nor do we need to mark busy extents as being in a transaction to avoid deadlocks. That is, if all free extents are busy and there is nothing we can allocate in the AG for the AGFL, then flush the busy extents and try again while we hold the AGF locked. Because we hold the AGF locked, nobody else can create new busy extents in the AG while we wait. That means after a busy extent flush any remaining busy extents in this AG are ones that we hold busy in this transaction and are the ones we need to avoid allocating from in the first place. IOWs, we don't need to mark busy extents as being in a transaction at all - we know that this is the only way we can have a busy extent in the AG after we flush busy extents while holding the AGF locked. And that means if we still can't find a free extent after a busy extent flush, then we're definitely at ENOSPC in that AG as there are no free extents we can safely allocate from in the AG.... Cheers, Dave. -- Dave Chinner david@fromorbit.com ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH 2/2] xfs: Prevent deadlock when allocating blocks for AGFL 2021-04-30 22:44 ` Dave Chinner @ 2021-05-03 9:52 ` Chandan Babu R 2021-05-04 0:03 ` Dave Chinner 0 siblings, 1 reply; 14+ messages in thread From: Chandan Babu R @ 2021-05-03 9:52 UTC (permalink / raw) To: Dave Chinner; +Cc: linux-xfs On 01 May 2021 at 04:14, Dave Chinner wrote: > On Fri, Apr 30, 2021 at 07:10:31PM +0530, Chandan Babu R wrote: >> On 29 Apr 2021 at 06:42, Dave Chinner wrote: >> > On Wed, Apr 28, 2021 at 12:21:52PM +0530, Chandan Babu R wrote: >> >> Executing xfs/538 after disabling injection of bmap_alloc_minlen_extent error >> >> can cause several tasks to trigger hung task timeout. Most of the tasks are >> >> blocked on getting a lock on an AG's AGF buffer. However, The task which has >> >> the lock on the AG's AGF buffer has the following call trace, >> >> >> [..] >> > Hmmm. I don't doubt that this fixes the symptom you are seeing, but >> > the way it is being fixed doesn't seem right to me at all. >> > >> > We're rtying to populate the AGFL here, and the fact is that a >> > multi-block allocation is simply an optimisation to minimise the >> > number of extents we need to allocate to fill the AGFL. The extent >> > that gets allocated gets broken up into single blocks to be inserted >> > into the AGFL, so we don't actually need a continuguous extent to be >> > allocated here. >> > >> > Hence, if the extent we find is busy when allocating for the AGFL, >> > we should just skip it and choose another extent. args->minlen is >> > set to zero for the allocation, so we can actually return any extent >> > that has a length <= args->maxlen. We know this is an AGFL >> > allocation because args->resv == XFS_AG_RESV_AGFL, so if we find a >> > busy extent that would require a log force to be able to use before >> > we can place it in the AGFL, we should just skip it entirely and >> > select another extent to allocate from. >> > >> > Adding another two boolean conditionals to the already complex >> > extent selection for this specific case makes the code much harder >> > to follow and reason about. I'd much prefer that we just do >> > something like: >> > >> > if (busy && args->resv == XFS_AG_RESV_AGFL) { >> > /* >> > * Extent might have just been freed in this >> > * transaction so we can't use it. Move to the next >> > * best extent candidate and try that instead. >> > */ >> > <increment/decrement and continue the search loop> >> > } >> > >> > IOWs, we should not be issuing a log force to flush busy extents if >> > we can't use the largest candidate free extent for the AGFL - we >> > should just keep searching until we find one we can use.... >> >> IIUC, the following patch implements the solution that has been suggested >> above, >> >> diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c >> index aaa19101bb2a..25456dbff767 100644 >> --- a/fs/xfs/libxfs/xfs_alloc.c >> +++ b/fs/xfs/libxfs/xfs_alloc.c >> @@ -1694,6 +1694,7 @@ xfs_alloc_ag_vextent_size( >> * are no smaller extents available. >> */ >> if (!i) { >> +alloc_small_extent: >> error = xfs_alloc_ag_vextent_small(args, cnt_cur, >> &fbno, &flen, &i); >> if (error) >> @@ -1707,6 +1708,8 @@ xfs_alloc_ag_vextent_size( >> busy = xfs_alloc_compute_aligned(args, fbno, flen, &rbno, >> &rlen, &busy_gen); >> } else { >> + xfs_agblock_t orig_fbno = NULLAGBLOCK; >> + xfs_extlen_t orig_flen; >> /* >> * Search for a non-busy extent that is large enough. >> */ >> @@ -1719,6 +1722,11 @@ xfs_alloc_ag_vextent_size( >> goto error0; >> } >> >> + if (orig_fbno == NULLAGBLOCK) { >> + orig_fbno = fbno; >> + orig_flen = flen; >> + } >> + >> busy = xfs_alloc_compute_aligned(args, fbno, flen, >> &rbno, &rlen, &busy_gen); >> >> @@ -1734,6 +1742,14 @@ xfs_alloc_ag_vextent_size( >> * Make it unbusy by forcing the log out and >> * retrying. >> */ >> + if (args->resv == XFS_AG_RESV_AGFL) { >> + error = xfs_alloc_lookup_eq(cnt_cur, >> + orig_fbno, orig_flen, &i); >> + ASSERT(!error && i); >> + >> + goto alloc_small_extent; >> + } >> + >> xfs_btree_del_cursor(cnt_cur, >> XFS_BTREE_NOERROR); >> trace_xfs_alloc_size_busy(args); >> @@ -1819,7 +1835,7 @@ xfs_alloc_ag_vextent_size( >> */ >> args->len = rlen; >> if (rlen < args->minlen) { >> - if (busy) { >> + if (busy && args->resv != XFS_AG_RESV_AGFL) { >> xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR); >> trace_xfs_alloc_size_busy(args); >> xfs_extent_busy_flush(args->mp, args->pag, busy_gen); >> >> i.e. when we end up at the right most edge of the cntbt during allocation of >> blocks for refilling AGFL, the above patch backtracks and continues search >> towards the left edge of the cntbt instead of flushing the CIL. If the >> leftmost edge is reached without finding any suitable free extent and the >> blocks are being allocated for AGFL, the function returns back to the caller >> instead of flushing the CIL and retrying once again. > > At which point, we know that all the free extents in that AG are > either busy or we are truly out of space. Hence if this search > fails, it makes sense to call xfs_extent_busy_flush() to wait for > all the busy extents in the AG to complete their processing before > trying again. > >> With the above patch, a workload which consists of, >> 1. Filling up 90% of the free space of the filesystem. >> 2. Punch alternate blocks of files. >> >> .. would cause failure when inserting records into either cntbt/bnobt due to >> unavailability of AGFL blocks. >> >> This happens because most of the free blocks resulting from punching out >> alternate blocks would be residing in the CIL's extent busy list. xfs/538 >> creates 1G sized scratch filesystem and the "punch alternate blocks" workload >> creates a little more than 8000 entries in the CIL extent busy list. > > Seems like you broke the existing handling of this situation by > preventing the AGFL filling code from flushing the busy extents when > all the AG can find is busy extents. > >> So, may be there are no other alternatives other than to flush the CIL. To > > Sure, I never suggested that we completely elide log forces. What I > said is that we -shouldn't immediately resort to a log force- because > the first maxlen extent match we come across is busy and can't > immediately be reused. > > That is, the code still needs to call xfs_extent_busy_flush() and > try the allocation again, it just needs to do it when no candidate > extent can be found instead of after the first candidate is found to > be busy. You are right. When allocating blocks to replenish the AGFL, if searching for free extents whose length is >= xfs_alloc_args->maxlen yields only busy extents, we should backtrack and search for extents of smaller length since AGFL does not need individual blocks to be contiguous. However, If the search among the smaller length extents again yields only busy extents, we should invoke xfs_extent_busy_flush() to mark the corresponding extents as unbusy and restarting the search. However, AFAICT there is one nit ... > >> that end, I have tried to slightly simplify the patch that I had originally >> sent (i.e. [PATCH 2/2] xfs: Prevent deadlock when allocating blocks for >> AGFL). The new patch removes one the boolean variables >> (i.e. alloc_small_extent) and also skips redundant searching of extent records >> when backtracking in preparation for searching smaller extents. > > I still don't think this is right approach because it tries to > correct a bad decision (use a busy extent instead of trying the next > free extent) with another bad decision (log force might not unbusy > the extent we are trying to allocate). We should not do either of > these things in this situation, nor do we need to mark busy extents > as being in a transaction to avoid deadlocks. > > That is, if all free extents are busy and there is nothing we can > allocate in the AG for the AGFL, then flush the busy extents and try > again while we hold the AGF locked. Because we hold the AGF locked, > nobody else can create new busy extents in the AG while we wait. > That means after a busy extent flush any remaining busy extents in > this AG are ones that we hold busy in this transaction and are the > ones we need to avoid allocating from in the first place. > > IOWs, we don't need to mark busy extents as being in a transaction > at all - we know that this is the only way we can have a busy extent > in the AG after we flush busy extents while holding the AGF locked. > And that means if we still can't find a free extent after a busy > extent flush, then we're definitely at ENOSPC in that AG as there > are no free extents we can safely allocate from in the AG.... ... Assume that there is one free busy extent in an AG and that it is 1 block in length. Also assume that the free extent is busy in the current transaction. An extent free operation corresponding to the 2nd xfs_extent_free_item will invoke xfs_alloc_ag_extent_size() with the following results, 1. Search starts at the only free extent and proceeds towards the left most edge of the cntbt. 2. Since there is only one free extent and that it is also busy, we now invoke xfs_extent_busy_flush(). 3. xfs_extent_busy_flush() flushes the CIL and waits for the "busy generation" number to change. This event will never occur since the only free extent is busy in the current transaction. Hence the task will now wait indefinitely. PS: I am not 100% sure if the above mentioned scenario (i.e. having only one extent free in an AG and also it being marked as busy) is actually possible. After going through the corresponding source code, I could not find any evidence to the contrary. -- chandan ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH 2/2] xfs: Prevent deadlock when allocating blocks for AGFL 2021-05-03 9:52 ` Chandan Babu R @ 2021-05-04 0:03 ` Dave Chinner 2021-05-05 12:42 ` Chandan Babu R 0 siblings, 1 reply; 14+ messages in thread From: Dave Chinner @ 2021-05-04 0:03 UTC (permalink / raw) To: Chandan Babu R; +Cc: linux-xfs On Mon, May 03, 2021 at 03:22:10PM +0530, Chandan Babu R wrote: > On 01 May 2021 at 04:14, Dave Chinner wrote: > >> that end, I have tried to slightly simplify the patch that I had originally > >> sent (i.e. [PATCH 2/2] xfs: Prevent deadlock when allocating blocks for > >> AGFL). The new patch removes one the boolean variables > >> (i.e. alloc_small_extent) and also skips redundant searching of extent records > >> when backtracking in preparation for searching smaller extents. > > > > I still don't think this is right approach because it tries to > > correct a bad decision (use a busy extent instead of trying the next > > free extent) with another bad decision (log force might not unbusy > > the extent we are trying to allocate). We should not do either of > > these things in this situation, nor do we need to mark busy extents > > as being in a transaction to avoid deadlocks. > > > > That is, if all free extents are busy and there is nothing we can > > allocate in the AG for the AGFL, then flush the busy extents and try > > again while we hold the AGF locked. Because we hold the AGF locked, > > nobody else can create new busy extents in the AG while we wait. > > That means after a busy extent flush any remaining busy extents in > > this AG are ones that we hold busy in this transaction and are the > > ones we need to avoid allocating from in the first place. > > > > IOWs, we don't need to mark busy extents as being in a transaction > > at all - we know that this is the only way we can have a busy extent > > in the AG after we flush busy extents while holding the AGF locked. > > And that means if we still can't find a free extent after a busy > > extent flush, then we're definitely at ENOSPC in that AG as there > > are no free extents we can safely allocate from in the AG.... > > ... Assume that there is one free busy extent in an AG and that it is 1 block > in length. Also assume that the free extent is busy in the current > transaction. ISTR that this won't happen during extent allocation because the transaction reservation and the AG selection code is supposed to ensure there are sufficient free blocks both globally and in the AG for the entire operation, not just one part of it. Also, the extent freeing path is this: ... __xfs_free_extent() xfs_free_extent_fix_freelist() xfs_alloc_fix_freelist(XFS_ALLOC_FLAG_FREEING) And that XFS_ALLOC_FLAG_FREEING is special - it means that we: a) always say there is space available in the AG for the freeing operation to take place, and b) only perform best effort allocation to fill up the free list. Case b) triggers this code: /* * Stop if we run out. Won't happen if callers are obeying * the restrictions correctly. Can happen for free calls * on a completely full ag. */ if (targs.agbno == NULLAGBLOCK) { if (flags & XFS_ALLOC_FLAG_FREEING) break; goto out_agflbp_relse; } That is, if we fail to fix up the free list, we still go ahead with the operation because freeing extents when we are at ENOSPC means that, by definition, we don't need to allocate blocks to track the new free space because the new free space records will fit inside the root btree blocks that are already allocated. Hence when doing allocation for the free list, we need to fail the allocation rather than block on the only remaining free extent in the AG. If we are freeing extents, the AGFL not being full is not an issue at all. And if we are allocating extents, the transaction reservations should have ensured that the AG had sufficient space in it to complete the entire operation without deadlocking waiting for space. Either way, I don't see a problem with making sure the AGFL allocations just skip busy extents and fail if the only free extents are ones this transaction has freed itself. Cheers, Dave. -- Dave Chinner david@fromorbit.com ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH 2/2] xfs: Prevent deadlock when allocating blocks for AGFL 2021-05-04 0:03 ` Dave Chinner @ 2021-05-05 12:42 ` Chandan Babu R 2021-05-06 3:27 ` Dave Chinner 0 siblings, 1 reply; 14+ messages in thread From: Chandan Babu R @ 2021-05-05 12:42 UTC (permalink / raw) To: Dave Chinner; +Cc: linux-xfs On 04 May 2021 at 05:33, Dave Chinner wrote: > On Mon, May 03, 2021 at 03:22:10PM +0530, Chandan Babu R wrote: >> On 01 May 2021 at 04:14, Dave Chinner wrote: >> >> that end, I have tried to slightly simplify the patch that I had originally >> >> sent (i.e. [PATCH 2/2] xfs: Prevent deadlock when allocating blocks for >> >> AGFL). The new patch removes one the boolean variables >> >> (i.e. alloc_small_extent) and also skips redundant searching of extent records >> >> when backtracking in preparation for searching smaller extents. >> > >> > I still don't think this is right approach because it tries to >> > correct a bad decision (use a busy extent instead of trying the next >> > free extent) with another bad decision (log force might not unbusy >> > the extent we are trying to allocate). We should not do either of >> > these things in this situation, nor do we need to mark busy extents >> > as being in a transaction to avoid deadlocks. >> > >> > That is, if all free extents are busy and there is nothing we can >> > allocate in the AG for the AGFL, then flush the busy extents and try >> > again while we hold the AGF locked. Because we hold the AGF locked, >> > nobody else can create new busy extents in the AG while we wait. >> > That means after a busy extent flush any remaining busy extents in >> > this AG are ones that we hold busy in this transaction and are the >> > ones we need to avoid allocating from in the first place. >> > >> > IOWs, we don't need to mark busy extents as being in a transaction >> > at all - we know that this is the only way we can have a busy extent >> > in the AG after we flush busy extents while holding the AGF locked. >> > And that means if we still can't find a free extent after a busy >> > extent flush, then we're definitely at ENOSPC in that AG as there >> > are no free extents we can safely allocate from in the AG.... >> >> ... Assume that there is one free busy extent in an AG and that it is 1 block >> in length. Also assume that the free extent is busy in the current >> transaction. > > ISTR that this won't happen during extent allocation because the > transaction reservation and the AG selection code is supposed to > ensure there are sufficient free blocks both globally and in the AG > for the entire operation, not just one part of it. > > Also, the extent freeing path is this: > > ... > __xfs_free_extent() > xfs_free_extent_fix_freelist() > xfs_alloc_fix_freelist(XFS_ALLOC_FLAG_FREEING) > > And that XFS_ALLOC_FLAG_FREEING is special - it means that we: > > a) always say there is space available in the AG for the freeing > operation to take place, and > b) only perform best effort allocation to fill up the free list. > > Case b) triggers this code: > > /* > * Stop if we run out. Won't happen if callers are obeying > * the restrictions correctly. Can happen for free calls > * on a completely full ag. > */ > if (targs.agbno == NULLAGBLOCK) { > if (flags & XFS_ALLOC_FLAG_FREEING) > break; > goto out_agflbp_relse; > } > > > That is, if we fail to fix up the free list, we still go ahead with > the operation because freeing extents when we are at ENOSPC means > that, by definition, we don't need to allocate blocks to track the > new free space because the new free space records will fit inside > the root btree blocks that are already allocated. > > Hence when doing allocation for the free list, we need to fail the > allocation rather than block on the only remaining free extent in > the AG. If we are freeing extents, the AGFL not being full is not an > issue at all. And if we are allocating extents, the transaction > reservations should have ensured that the AG had sufficient space in > it to complete the entire operation without deadlocking waiting for > space. > > Either way, I don't see a problem with making sure the AGFL > allocations just skip busy extents and fail if the only free extents > are ones this transaction has freed itself. > Hmm. In the scenario where *all* free extents in the AG were originally freed by the current transaction (and hence busy in the transaction), we would need to be able to recognize this situation and skip invoking xfs_extent_busy_flush() altogether. Otherwise, xfs_extent_busy_flush() invokes xfs_log_force() and keeps waiting for busy generation number to change. Hence, IMHO we would need an extent busy flag (e.g. XFS_EXTENT_BUSY_IN_TRANS) to correctly determine if all the busy extents are indeed busy in the current transaction. -- chandan ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH 2/2] xfs: Prevent deadlock when allocating blocks for AGFL 2021-05-05 12:42 ` Chandan Babu R @ 2021-05-06 3:27 ` Dave Chinner 2021-05-11 11:49 ` Chandan Babu R 0 siblings, 1 reply; 14+ messages in thread From: Dave Chinner @ 2021-05-06 3:27 UTC (permalink / raw) To: Chandan Babu R; +Cc: linux-xfs On Wed, May 05, 2021 at 06:12:41PM +0530, Chandan Babu R wrote: > > Hence when doing allocation for the free list, we need to fail the > > allocation rather than block on the only remaining free extent in > > the AG. If we are freeing extents, the AGFL not being full is not an > > issue at all. And if we are allocating extents, the transaction > > reservations should have ensured that the AG had sufficient space in > > it to complete the entire operation without deadlocking waiting for > > space. > > > > Either way, I don't see a problem with making sure the AGFL > > allocations just skip busy extents and fail if the only free extents > > are ones this transaction has freed itself. > > > > Hmm. In the scenario where *all* free extents in the AG were originally freed > by the current transaction (and hence busy in the transaction), How does that happen? > we would need > to be able to recognize this situation and skip invoking > xfs_extent_busy_flush() altogether. If we are freeing extents (i.e XFS_ALLOC_FLAG_FREEING is set) and we are doing allocation for AGFL and we only found busy extents, then it's OK to fail the allocation. We have options here - once we get to the end of the btree and haven't found a candidate that isn't busy, we could fail immediately. Or maybe we try an optimisitic flush which forces the log and waits for as short while (instead of forever) for the generation to change and then fail if we get a timeout response. Or maybe there's a more elegant way of doing this that hasn't yet rattled out of my poor, overloaded brain right now. Just because we currently do a blocking flush doesn't mean we always must do a blocking flush.... Cheers, Dave. -- Dave Chinner david@fromorbit.com ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH 2/2] xfs: Prevent deadlock when allocating blocks for AGFL 2021-05-06 3:27 ` Dave Chinner @ 2021-05-11 11:49 ` Chandan Babu R 2021-06-17 4:48 ` Chandan Babu R 0 siblings, 1 reply; 14+ messages in thread From: Chandan Babu R @ 2021-05-11 11:49 UTC (permalink / raw) To: Dave Chinner; +Cc: linux-xfs On 06 May 2021 at 08:57, Dave Chinner wrote: > On Wed, May 05, 2021 at 06:12:41PM +0530, Chandan Babu R wrote: >> > Hence when doing allocation for the free list, we need to fail the >> > allocation rather than block on the only remaining free extent in >> > the AG. If we are freeing extents, the AGFL not being full is not an >> > issue at all. And if we are allocating extents, the transaction >> > reservations should have ensured that the AG had sufficient space in >> > it to complete the entire operation without deadlocking waiting for >> > space. >> > >> > Either way, I don't see a problem with making sure the AGFL >> > allocations just skip busy extents and fail if the only free extents >> > are ones this transaction has freed itself. >> > >> >> Hmm. In the scenario where *all* free extents in the AG were originally freed >> by the current transaction (and hence busy in the transaction), > > How does that happen? I tried in vain to arrive at the above mentioned scenario by consuming away as many blocks as possible from the filesystem. At best, I could arrive at an AG with just one free extent record in the cntbt (NOTE: I had to disable global reservation by invoking "xfs_io -x -c 'resblks 0' $mntpnt"): recs[1] = [startblock,blockcount] 1:[32767,1] For each AG available in an FS instance, we take away 8 (i.e. XFS_ALLOC_AGFL_RESERVE + 4) blocks from the global free data blocks counter. This reservation is applied to the FS as a whole rather than each AG individually. Hence we could get to a scenario where an AG could have less than 8 free blocks. I could not find any other restriction in the code that explicitly prevents an AG from having zero free extents. However, I could not create such an AG because any fs operation that needs extent allocation to be done would try to reserve more than 1 extent causing the above cited AG to not be chosen. > >> we would need >> to be able to recognize this situation and skip invoking >> xfs_extent_busy_flush() altogether. > > If we are freeing extents (i.e XFS_ALLOC_FLAG_FREEING is set) and > we are doing allocation for AGFL and we only found busy extents, > then it's OK to fail the allocation. When freeing an extent, the following patch skips allocation of blocks to AGFL if all the free extents found are busy, diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c index aaa19101bb2a..5310e311d5c6 100644 --- a/fs/xfs/libxfs/xfs_alloc.c +++ b/fs/xfs/libxfs/xfs_alloc.c @@ -1694,6 +1694,7 @@ xfs_alloc_ag_vextent_size( * are no smaller extents available. */ if (!i) { +alloc_small_extent: error = xfs_alloc_ag_vextent_small(args, cnt_cur, &fbno, &flen, &i); if (error) @@ -1710,6 +1711,9 @@ xfs_alloc_ag_vextent_size( /* * Search for a non-busy extent that is large enough. */ + xfs_agblock_t orig_fbno = NULLAGBLOCK; + xfs_extlen_t orig_flen; + for (;;) { error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen, &i); if (error) @@ -1719,6 +1723,11 @@ xfs_alloc_ag_vextent_size( goto error0; } + if (orig_fbno == NULLAGBLOCK) { + orig_fbno = fbno; + orig_flen = flen; + } + busy = xfs_alloc_compute_aligned(args, fbno, flen, &rbno, &rlen, &busy_gen); @@ -1729,6 +1738,13 @@ xfs_alloc_ag_vextent_size( if (error) goto error0; if (i == 0) { + if (args->freeing_extent) { + error = xfs_alloc_lookup_eq(cnt_cur, + orig_fbno, orig_flen, &i); + ASSERT(!error && i); + goto alloc_small_extent; + } + /* * Our only valid extents must have been busy. * Make it unbusy by forcing the log out and @@ -1819,7 +1835,7 @@ xfs_alloc_ag_vextent_size( */ args->len = rlen; if (rlen < args->minlen) { - if (busy) { + if (busy && !args->freeing_extent) { xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR); trace_xfs_alloc_size_busy(args); xfs_extent_busy_flush(args->mp, args->pag, busy_gen); @@ -2641,6 +2657,7 @@ xfs_alloc_fix_freelist( targs.alignment = targs.minlen = targs.prod = 1; targs.type = XFS_ALLOCTYPE_THIS_AG; targs.pag = pag; + targs.freeing_extent = flags & XFS_ALLOC_FLAG_FREEING; error = xfs_alloc_read_agfl(mp, tp, targs.agno, &agflbp); if (error) goto out_agbp_relse; diff --git a/fs/xfs/libxfs/xfs_alloc.h b/fs/xfs/libxfs/xfs_alloc.h index a4427c5775c2..1e0fc28ef87a 100644 --- a/fs/xfs/libxfs/xfs_alloc.h +++ b/fs/xfs/libxfs/xfs_alloc.h @@ -78,6 +78,7 @@ typedef struct xfs_alloc_arg { #ifdef DEBUG bool alloc_minlen_only; /* allocate exact minlen extent */ #endif + bool freeing_extent; } xfs_alloc_arg_t; /* With the above patch, xfs/538 cause the following call trace to be printed, XFS (vdc2): Internal error i != 1 at line 3426 of file fs/xfs/libxfs/xfs_btree.c. Caller xfs_btree_insert+0x15c/0x1f0 CPU: 2 PID: 1284 Comm: punch-alternati Not tainted 5.12.0-rc8-next-20210419-chandan #19 Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.12.0-1 04/01/2014 Call Trace: dump_stack+0x64/0x7c xfs_corruption_error+0x85/0x90 ? xfs_btree_insert+0x15c/0x1f0 xfs_btree_insert+0x18d/0x1f0 ? xfs_btree_insert+0x15c/0x1f0 ? xfs_allocbt_init_common+0x30/0xf0 xfs_free_ag_extent+0x463/0x9d0 __xfs_free_extent+0xe5/0x200 xfs_trans_free_extent+0x3e/0x100 xfs_extent_free_finish_item+0x24/0x40 xfs_defer_finish_noroll+0x1f7/0x5c0 __xfs_trans_commit+0x12f/0x300 xfs_free_file_space+0x1af/0x2c0 xfs_file_fallocate+0x1ca/0x430 ? __cond_resched+0x16/0x40 ? inode_security+0x22/0x60 ? selinux_file_permission+0xe2/0x120 vfs_fallocate+0x146/0x2e0 __x64_sys_fallocate+0x3e/0x70 do_syscall_64+0x40/0x80 entry_SYSCALL_64_after_hwframe+0x44/0xae The above call trace occurs during execution of the step #2 listed below, 1. Filling up 90% of the free space of the filesystem. 2. Punch alternate blocks of files. Just before the failure, the filesystem had ~9000 busy extents. So I think we have to flush busy extents even when refilling AGFL for the purpose of freeing an extent. > > We have options here - once we get to the end of the btree and > haven't found a candidate that isn't busy, we could fail > immediately. Or maybe we try an optimisitic flush which forces the > log and waits for as short while (instead of forever) for the > generation to change and then fail if we get a timeout response. Or > maybe there's a more elegant way of doing this that hasn't yet > rattled out of my poor, overloaded brain right now. > > Just because we currently do a blocking flush doesn't mean we always > must do a blocking flush.... I will try to work out a solution. -- chandan ^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH 2/2] xfs: Prevent deadlock when allocating blocks for AGFL 2021-05-11 11:49 ` Chandan Babu R @ 2021-06-17 4:48 ` Chandan Babu R 0 siblings, 0 replies; 14+ messages in thread From: Chandan Babu R @ 2021-06-17 4:48 UTC (permalink / raw) To: Dave Chinner; +Cc: linux-xfs On 11 May 2021 at 17:19, Chandan Babu R wrote: > On 06 May 2021 at 08:57, Dave Chinner wrote: >> On Wed, May 05, 2021 at 06:12:41PM +0530, Chandan Babu R wrote: >>> > Hence when doing allocation for the free list, we need to fail the >>> > allocation rather than block on the only remaining free extent in >>> > the AG. If we are freeing extents, the AGFL not being full is not an >>> > issue at all. And if we are allocating extents, the transaction >>> > reservations should have ensured that the AG had sufficient space in >>> > it to complete the entire operation without deadlocking waiting for >>> > space. >>> > >>> > Either way, I don't see a problem with making sure the AGFL >>> > allocations just skip busy extents and fail if the only free extents >>> > are ones this transaction has freed itself. >>> > >>> >>> Hmm. In the scenario where *all* free extents in the AG were originally freed >>> by the current transaction (and hence busy in the transaction), >> >> How does that happen? > > I tried in vain to arrive at the above mentioned scenario by consuming away as > many blocks as possible from the filesystem. At best, I could arrive at an AG > with just one free extent record in the cntbt (NOTE: I had to disable global > reservation by invoking "xfs_io -x -c 'resblks 0' $mntpnt"): > > recs[1] = [startblock,blockcount] > 1:[32767,1] > > For each AG available in an FS instance, we take away 8 > (i.e. XFS_ALLOC_AGFL_RESERVE + 4) blocks from the global free data blocks > counter. This reservation is applied to the FS as a whole rather than each AG > individually. Hence we could get to a scenario where an AG could have less > than 8 free blocks. I could not find any other restriction in the code that > explicitly prevents an AG from having zero free extents. > > However, I could not create such an AG because any fs operation that needs > extent allocation to be done would try to reserve more than 1 extent causing > the above cited AG to not be chosen. > >> >>> we would need >>> to be able to recognize this situation and skip invoking >>> xfs_extent_busy_flush() altogether. >> >> If we are freeing extents (i.e XFS_ALLOC_FLAG_FREEING is set) and >> we are doing allocation for AGFL and we only found busy extents, >> then it's OK to fail the allocation. > > When freeing an extent, the following patch skips allocation of blocks to AGFL > if all the free extents found are busy, > > diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c > index aaa19101bb2a..5310e311d5c6 100644 > --- a/fs/xfs/libxfs/xfs_alloc.c > +++ b/fs/xfs/libxfs/xfs_alloc.c > @@ -1694,6 +1694,7 @@ xfs_alloc_ag_vextent_size( > * are no smaller extents available. > */ > if (!i) { > +alloc_small_extent: > error = xfs_alloc_ag_vextent_small(args, cnt_cur, > &fbno, &flen, &i); > if (error) > @@ -1710,6 +1711,9 @@ xfs_alloc_ag_vextent_size( > /* > * Search for a non-busy extent that is large enough. > */ > + xfs_agblock_t orig_fbno = NULLAGBLOCK; > + xfs_extlen_t orig_flen; > + > for (;;) { > error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen, &i); > if (error) > @@ -1719,6 +1723,11 @@ xfs_alloc_ag_vextent_size( > goto error0; > } > > + if (orig_fbno == NULLAGBLOCK) { > + orig_fbno = fbno; > + orig_flen = flen; > + } > + > busy = xfs_alloc_compute_aligned(args, fbno, flen, > &rbno, &rlen, &busy_gen); > > @@ -1729,6 +1738,13 @@ xfs_alloc_ag_vextent_size( > if (error) > goto error0; > if (i == 0) { > + if (args->freeing_extent) { > + error = xfs_alloc_lookup_eq(cnt_cur, > + orig_fbno, orig_flen, &i); > + ASSERT(!error && i); > + goto alloc_small_extent; > + } > + > /* > * Our only valid extents must have been busy. > * Make it unbusy by forcing the log out and > @@ -1819,7 +1835,7 @@ xfs_alloc_ag_vextent_size( > */ > args->len = rlen; > if (rlen < args->minlen) { > - if (busy) { > + if (busy && !args->freeing_extent) { > xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR); > trace_xfs_alloc_size_busy(args); > xfs_extent_busy_flush(args->mp, args->pag, busy_gen); > @@ -2641,6 +2657,7 @@ xfs_alloc_fix_freelist( > targs.alignment = targs.minlen = targs.prod = 1; > targs.type = XFS_ALLOCTYPE_THIS_AG; > targs.pag = pag; > + targs.freeing_extent = flags & XFS_ALLOC_FLAG_FREEING; > error = xfs_alloc_read_agfl(mp, tp, targs.agno, &agflbp); > if (error) > goto out_agbp_relse; > diff --git a/fs/xfs/libxfs/xfs_alloc.h b/fs/xfs/libxfs/xfs_alloc.h > index a4427c5775c2..1e0fc28ef87a 100644 > --- a/fs/xfs/libxfs/xfs_alloc.h > +++ b/fs/xfs/libxfs/xfs_alloc.h > @@ -78,6 +78,7 @@ typedef struct xfs_alloc_arg { > #ifdef DEBUG > bool alloc_minlen_only; /* allocate exact minlen extent */ > #endif > + bool freeing_extent; > } xfs_alloc_arg_t; > > /* > > With the above patch, xfs/538 cause the following call trace to be printed, > > XFS (vdc2): Internal error i != 1 at line 3426 of file fs/xfs/libxfs/xfs_btree.c. Caller xfs_btree_insert+0x15c/0x1f0 > CPU: 2 PID: 1284 Comm: punch-alternati Not tainted 5.12.0-rc8-next-20210419-chandan #19 > Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.12.0-1 04/01/2014 > Call Trace: > dump_stack+0x64/0x7c > xfs_corruption_error+0x85/0x90 > ? xfs_btree_insert+0x15c/0x1f0 > xfs_btree_insert+0x18d/0x1f0 > ? xfs_btree_insert+0x15c/0x1f0 > ? xfs_allocbt_init_common+0x30/0xf0 > xfs_free_ag_extent+0x463/0x9d0 > __xfs_free_extent+0xe5/0x200 > xfs_trans_free_extent+0x3e/0x100 > xfs_extent_free_finish_item+0x24/0x40 > xfs_defer_finish_noroll+0x1f7/0x5c0 > __xfs_trans_commit+0x12f/0x300 > xfs_free_file_space+0x1af/0x2c0 > xfs_file_fallocate+0x1ca/0x430 > ? __cond_resched+0x16/0x40 > ? inode_security+0x22/0x60 > ? selinux_file_permission+0xe2/0x120 > vfs_fallocate+0x146/0x2e0 > __x64_sys_fallocate+0x3e/0x70 > do_syscall_64+0x40/0x80 > entry_SYSCALL_64_after_hwframe+0x44/0xae > > The above call trace occurs during execution of the step #2 listed below, > 1. Filling up 90% of the free space of the filesystem. > 2. Punch alternate blocks of files. > > Just before the failure, the filesystem had ~9000 busy extents. So I think we > have to flush busy extents even when refilling AGFL for the purpose of freeing > an extent. > >> >> We have options here - once we get to the end of the btree and >> haven't found a candidate that isn't busy, we could fail >> immediately. Or maybe we try an optimisitic flush which forces the >> log and waits for as short while (instead of forever) for the >> generation to change and then fail if we get a timeout response. Or >> maybe there's a more elegant way of doing this that hasn't yet >> rattled out of my poor, overloaded brain right now. >> >> Just because we currently do a blocking flush doesn't mean we always >> must do a blocking flush.... > > I will try to work out a solution. I believe the following should be taken into consideration to design an "optimistic flush delay" based solution, 1. Time consumed to perform a discard operation on a filesystem's block. 2. The size of extents that are being discarded. 3. Number of discard operation requests contained in a bio. AFAICT, The combinations resulting from the above make it impossible to calculate a time delay during which sufficient number of busy extents are guaranteed to have been freed so as to fill up the AGFL to the required levels. In other words, sufficent number of busy extents may not have been discarded even after the optimistic delay interval elapses. The other solution that I had thought about was to introduce a new flag for the second argument of xfs_log_force(). The new flag will cause xlog_state_do_iclog_callbacks() to wait on completion of all of the CIL ctxs associated with the iclog that xfs_log_force() would be waiting on. Hence, a call to xfs_log_force(mp, NEW_SYNC_FLAG) will return only after all the busy extents associated with the iclog are discarded. However, this method is also flawed as described below. ---------------------------------------------------------- Task A Task B ---------------------------------------------------------- Submit a filled up iclog for write operation (Assume that the iclog has non-zero number of CIL ctxs associated with it). On completion of iclog write operation, discard requests for busy extents are issued. Write log records (including commit record) into another iclog. A task which is trying to fill AGFL will now invoke xfs_log_force() with the new sync flag. Submit the 2nd iclog which was partially filled by Task A. If there are no discard requests associated this iclog, xfs_log_force() will return. As the discard requests associated with the first iclog are yet to be completed, we end up incorrectly concluding that all busy extents have been processed. ---------------------------------------------------------- The inconsistency indicated above could also occur when discard requests issued against second iclog get processed before discard requests associated with the first iclog. XFS_EXTENT_BUSY_IN_TRANS flag based solution is the only method that I can think of that can solve this problem correctly. However I do agree with your earlier observation that we should not flush busy extents unless we have checked for presence of free extents in the btree records present on the left side of the btree cursor. -- chandan ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH 2/2] xfs: Prevent deadlock when allocating blocks for AGFL
@ 2023-01-10 12:24 Xiao Guangrong
2023-01-10 12:48 ` Chandan Babu R
0 siblings, 1 reply; 14+ messages in thread
From: Xiao Guangrong @ 2023-01-10 12:24 UTC (permalink / raw)
To: chandanrlinux, david; +Cc: linux-xfs
On 6/17/21 12:48, Chandan Babu R wrote:
>>>
>>> Just because we currently do a blocking flush doesn't mean we always
>>> must do a blocking flush....
>>
>> I will try to work out a solution.
>
> I believe the following should be taken into consideration to design an
> "optimistic flush delay" based solution,
> 1. Time consumed to perform a discard operation on a filesystem's block.
> 2. The size of extents that are being discarded.
> 3. Number of discard operation requests contained in a bio.
>
> AFAICT, The combinations resulting from the above make it impossible to
> calculate a time delay during which sufficient number of busy extents are
> guaranteed to have been freed so as to fill up the AGFL to the required
> levels. In other words, sufficent number of busy extents may not have been
> discarded even after the optimistic delay interval elapses.
>
> The other solution that I had thought about was to introduce a new flag for
> the second argument of xfs_log_force(). The new flag will cause
> xlog_state_do_iclog_callbacks() to wait on completion of all of the CIL ctxs
> associated with the iclog that xfs_log_force() would be waiting on. Hence, a
> call to xfs_log_force(mp, NEW_SYNC_FLAG) will return only after all the busy
> extents associated with the iclog are discarded.
>
> However, this method is also flawed as described below.
>
> ----------------------------------------------------------
> Task A Task B
> ----------------------------------------------------------
> Submit a filled up iclog
> for write operation
> (Assume that the iclog
> has non-zero number of CIL
> ctxs associated with it).
> On completion of iclog write
> operation, discard requests
> for busy extents are issued.
>
> Write log records (including
> commit record) into another
> iclog.
>
> A task which is trying
> to fill AGFL will now
> invoke xfs_log_force()
> with the new sync
> flag.
> Submit the 2nd iclog which
> was partially filled by
> Task A.
> If there are no
> discard requests
> associated this iclog,
> xfs_log_force() will
> return. As the discard
> requests associated with
> the first iclog are yet
> to be completed,
> we end up incorrectly
> concluding that
> all busy extents
> have been processed.
> ----------------------------------------------------------
>
> The inconsistency indicated above could also occur when discard requests
> issued against second iclog get processed before discard requests associated
> with the first iclog.
>
> XFS_EXTENT_BUSY_IN_TRANS flag based solution is the only method that I can
> think of that can solve this problem correctly. However I do agree with your
> earlier observation that we should not flush busy extents unless we have
> checked for presence of free extents in the btree records present on the left
> side of the btree cursor.
>
Hi Chandan,
Thanks for your great work. Do you have any update on these patches?
We met the same issue on the 4.19 kernel, I am not sure if the work has already
been merged in the upstream kernel.
^ permalink raw reply [flat|nested] 14+ messages in thread* Re: [PATCH 2/2] xfs: Prevent deadlock when allocating blocks for AGFL 2023-01-10 12:24 Xiao Guangrong @ 2023-01-10 12:48 ` Chandan Babu R 2023-01-11 3:14 ` Xiao Guangrong 0 siblings, 1 reply; 14+ messages in thread From: Chandan Babu R @ 2023-01-10 12:48 UTC (permalink / raw) To: Xiao Guangrong; +Cc: chandanrlinux, david, linux-xfs On Tue, Jan 10, 2023 at 08:24:41 PM +0800, Xiao Guangrong wrote: > On 6/17/21 12:48, Chandan Babu R wrote: > >>>> >>>> Just because we currently do a blocking flush doesn't mean we always >>>> must do a blocking flush.... >>> >>> I will try to work out a solution. >> >> I believe the following should be taken into consideration to design an >> "optimistic flush delay" based solution, >> 1. Time consumed to perform a discard operation on a filesystem's block. >> 2. The size of extents that are being discarded. >> 3. Number of discard operation requests contained in a bio. >> >> AFAICT, The combinations resulting from the above make it impossible to >> calculate a time delay during which sufficient number of busy extents are >> guaranteed to have been freed so as to fill up the AGFL to the required >> levels. In other words, sufficent number of busy extents may not have been >> discarded even after the optimistic delay interval elapses. >> >> The other solution that I had thought about was to introduce a new flag for >> the second argument of xfs_log_force(). The new flag will cause >> xlog_state_do_iclog_callbacks() to wait on completion of all of the CIL ctxs >> associated with the iclog that xfs_log_force() would be waiting on. Hence, a >> call to xfs_log_force(mp, NEW_SYNC_FLAG) will return only after all the busy >> extents associated with the iclog are discarded. >> >> However, this method is also flawed as described below. >> >> ---------------------------------------------------------- >> Task A Task B >> ---------------------------------------------------------- >> Submit a filled up iclog >> for write operation >> (Assume that the iclog >> has non-zero number of CIL >> ctxs associated with it). >> On completion of iclog write >> operation, discard requests >> for busy extents are issued. >> >> Write log records (including >> commit record) into another >> iclog. >> >> A task which is trying >> to fill AGFL will now >> invoke xfs_log_force() >> with the new sync >> flag. >> Submit the 2nd iclog which >> was partially filled by >> Task A. >> If there are no >> discard requests >> associated this iclog, >> xfs_log_force() will >> return. As the discard >> requests associated with >> the first iclog are yet >> to be completed, >> we end up incorrectly >> concluding that >> all busy extents >> have been processed. >> ---------------------------------------------------------- >> >> The inconsistency indicated above could also occur when discard requests >> issued against second iclog get processed before discard requests associated >> with the first iclog. >> >> XFS_EXTENT_BUSY_IN_TRANS flag based solution is the only method that I can >> think of that can solve this problem correctly. However I do agree with your >> earlier observation that we should not flush busy extents unless we have >> checked for presence of free extents in the btree records present on the left >> side of the btree cursor. >> > > Hi Chandan, > > Thanks for your great work. Do you have any update on these patches? > > We met the same issue on the 4.19 kernel, I am not sure if the work has already > been merged in the upstream kernel. Sorry, The machine on which the problem was created broke and I wasn't able to recreate this bug on my new work setup. Hence, I didn't pursue working on this bug. -- chandan ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH 2/2] xfs: Prevent deadlock when allocating blocks for AGFL 2023-01-10 12:48 ` Chandan Babu R @ 2023-01-11 3:14 ` Xiao Guangrong 0 siblings, 0 replies; 14+ messages in thread From: Xiao Guangrong @ 2023-01-11 3:14 UTC (permalink / raw) To: Chandan Babu R; +Cc: chandanrlinux, david, linux-xfs Okay :) I am going to reproduce it, and will return to this thread if I get something. Thanks! On Tue, Jan 10, 2023 at 8:52 PM Chandan Babu R <chandan.babu@oracle.com> wrote: > > On Tue, Jan 10, 2023 at 08:24:41 PM +0800, Xiao Guangrong wrote: > > On 6/17/21 12:48, Chandan Babu R wrote: > > > >>>> > >>>> Just because we currently do a blocking flush doesn't mean we always > >>>> must do a blocking flush.... > >>> > >>> I will try to work out a solution. > >> > >> I believe the following should be taken into consideration to design an > >> "optimistic flush delay" based solution, > >> 1. Time consumed to perform a discard operation on a filesystem's block. > >> 2. The size of extents that are being discarded. > >> 3. Number of discard operation requests contained in a bio. > >> > >> AFAICT, The combinations resulting from the above make it impossible to > >> calculate a time delay during which sufficient number of busy extents are > >> guaranteed to have been freed so as to fill up the AGFL to the required > >> levels. In other words, sufficent number of busy extents may not have been > >> discarded even after the optimistic delay interval elapses. > >> > >> The other solution that I had thought about was to introduce a new flag for > >> the second argument of xfs_log_force(). The new flag will cause > >> xlog_state_do_iclog_callbacks() to wait on completion of all of the CIL ctxs > >> associated with the iclog that xfs_log_force() would be waiting on. Hence, a > >> call to xfs_log_force(mp, NEW_SYNC_FLAG) will return only after all the busy > >> extents associated with the iclog are discarded. > >> > >> However, this method is also flawed as described below. > >> > >> ---------------------------------------------------------- > >> Task A Task B > >> ---------------------------------------------------------- > >> Submit a filled up iclog > >> for write operation > >> (Assume that the iclog > >> has non-zero number of CIL > >> ctxs associated with it). > >> On completion of iclog write > >> operation, discard requests > >> for busy extents are issued. > >> > >> Write log records (including > >> commit record) into another > >> iclog. > >> > >> A task which is trying > >> to fill AGFL will now > >> invoke xfs_log_force() > >> with the new sync > >> flag. > >> Submit the 2nd iclog which > >> was partially filled by > >> Task A. > >> If there are no > >> discard requests > >> associated this iclog, > >> xfs_log_force() will > >> return. As the discard > >> requests associated with > >> the first iclog are yet > >> to be completed, > >> we end up incorrectly > >> concluding that > >> all busy extents > >> have been processed. > >> ---------------------------------------------------------- > >> > >> The inconsistency indicated above could also occur when discard requests > >> issued against second iclog get processed before discard requests associated > >> with the first iclog. > >> > >> XFS_EXTENT_BUSY_IN_TRANS flag based solution is the only method that I can > >> think of that can solve this problem correctly. However I do agree with your > >> earlier observation that we should not flush busy extents unless we have > >> checked for presence of free extents in the btree records present on the left > >> side of the btree cursor. > >> > > > > Hi Chandan, > > > > Thanks for your great work. Do you have any update on these patches? > > > > We met the same issue on the 4.19 kernel, I am not sure if the work has already > > been merged in the upstream kernel. > > Sorry, The machine on which the problem was created broke and I wasn't able to > recreate this bug on my new work setup. Hence, I didn't pursue working on this > bug. > > -- > chandan ^ permalink raw reply [flat|nested] 14+ messages in thread
end of thread, other threads:[~2023-01-11 3:14 UTC | newest] Thread overview: 14+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2021-04-28 6:51 [PATCH 1/2] xfs: Introduce XFS_EXTENT_BUSY_IN_TRANS busy extent flag Chandan Babu R 2021-04-28 6:51 ` [PATCH 2/2] xfs: Prevent deadlock when allocating blocks for AGFL Chandan Babu R 2021-04-29 1:12 ` Dave Chinner 2021-04-30 13:40 ` Chandan Babu R 2021-04-30 22:44 ` Dave Chinner 2021-05-03 9:52 ` Chandan Babu R 2021-05-04 0:03 ` Dave Chinner 2021-05-05 12:42 ` Chandan Babu R 2021-05-06 3:27 ` Dave Chinner 2021-05-11 11:49 ` Chandan Babu R 2021-06-17 4:48 ` Chandan Babu R -- strict thread matches above, loose matches on Subject: below -- 2023-01-10 12:24 Xiao Guangrong 2023-01-10 12:48 ` Chandan Babu R 2023-01-11 3:14 ` Xiao Guangrong
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox