| Message ID | 20230829065710.938039-1-david@fromorbit.com (mailing list archive) |
|---|---|
| State | Superseded, archived |
| Headers | show |
| Series | [RFC] xfs: reduce AGF hold times during fstrim operations | expand |
On Tue, Aug 29, 2023 at 04:57:10PM +1000, Dave Chinner wrote: > From: Dave Chinner <dchinner@redhat.com> > > fstrim will hold the AGF lock for as long as it takes to walk and > discard all the free space in the AG that meets the userspace trim > criteria.i For AGs with lots of free space extents (e.g. millions) > or the underlying device is really slow at processing discard > requests (e.g. Ceph RBD), this means the AGF hold time is often > measured in minutes to hours, not a few milliseconds as we normal > see with non-discard based operations. > > THis can result in the entire filesystem hanging whilst the > long-running fstrim is in progress. We can have transactions get > stuck waiting for the AGF lock (data or metadata extent allocation > and freeing), and then more transactions get stuck waiting on the > locks those transactions hold. We can get to the point where fstrim > blocks an extent allocation or free operation long enough that it > ends up pinning the tail of the log and the log then runs out of > space. At this point, every modification in the filesystem gets > blocked. This includes read operations, if atime updates need to be > made. > > To fix this problem, we need to be able to discard free space > extents safely without holding the AGF lock. Fortunately, we already > do this with online discard via busy extents. We can makr free space s/makr/mark/ > extents as "busy being discarded" under the AGF lock and then unlock > the AGF, knowing that nobody will be able to allocate that free > space extent until we remove it from the busy tree. > > Modify xfs_trim_extents to use the same asynchronous discard > mechanism backed by busy extents as is used with online discard. > This results in the AGF only needing to be held for short periods of > time and it is never held while we issue discards. Hence if discard > submission gets throttled because it is slow and/or there are lots > of them, we aren't preventing other operations from being performed > on AGF while we wait for discards to complete... Oh good, because FSTRIM is dog slow even when you don't have other threads impatiently waiting on the AGF. :) (Hello, QVO...) > This is an RFC because it's just the patch I've written to implement > the functionality and smoke test it. It isn't polished, I haven't > broken it up into fine-grained patches, etc. It's just a chunk of > code that fixes the problem so people can comment on the approach > and maybe spot something wrong that I haven't. IOWs, I'm looking for > comments on the functionality change, not the code itself.... IOWs I don't have to wade through six patches of code golf just to figure out what this does. Much easier to review, thank you. > Signed-off-by: Dave Chinner <dchinner@redhat.com> > --- > fs/xfs/xfs_discard.c | 274 ++++++++++++++++++++++++++++++++++++--- > fs/xfs/xfs_extent_busy.c | 33 ++++- > fs/xfs/xfs_extent_busy.h | 4 + > 3 files changed, 286 insertions(+), 25 deletions(-) > > diff --git a/fs/xfs/xfs_discard.c b/fs/xfs/xfs_discard.c > index afc4c78b9eed..c2eec29c02d1 100644 > --- a/fs/xfs/xfs_discard.c > +++ b/fs/xfs/xfs_discard.c > @@ -1,6 +1,6 @@ > // SPDX-License-Identifier: GPL-2.0 > /* > - * Copyright (C) 2010 Red Hat, Inc. > + * Copyright (C) 2010, 2023 Red Hat, Inc. > * All Rights Reserved. > */ > #include "xfs.h" > @@ -19,21 +19,81 @@ > #include "xfs_log.h" > #include "xfs_ag.h" > > -STATIC int > -xfs_trim_extents( > +/* > + * Notes on an efficient, low latency fstrim algorithm > + * > + * We need to walk the filesystem free space and issue discards on the free > + * space that meet the search criteria (size and location). We cannot issue > + * discards on extents that might be in use, or are so recently in use they are > + * still marked as busy. To serialise against extent state changes whilst we are > + * gathering extents to trim, we must hold the AGF lock to lock out other > + * allocations and extent free operations that might change extent state. > + * > + * However, we cannot just hold the AGF for the entire AG free space walk whilst > + * we issue discards on each free space that is found. Storage devices can have > + * extremely slow discard implementations (e.g. ceph RBD) and so walking a > + * couple of million free extents and issuing synchronous discards on each > + * extent can take a *long* time. Whilst we are doing this walk, nothing else > + * can access the AGF, and we can stall transactions and hence the log whilst > + * modifications wait for the AGF lock to be released. This can lead hung tasks > + * kicking the hung task timer and rebooting the system. This is bad. > + * > + * Hence we need to take a leaf from the bulkstat playbook. It takes the AGI > + * lock, gathers a range of inode cluster buffers that are allocated, drops the > + * AGI lock and then reads all the inode cluster buffers and processes them. It > + * loops doing this, using a cursor to keep track of where it is up to in the AG > + * for each iteration to restart the INOBT lookup from. > + * > + * We can't do this exactly with free space - once we drop the AGF lock, the > + * state of the free extent is out of our control and we cannot run a discard > + * safely on it in this situation. Unless, of course, we've marked the free > + * extent as busy and undergoing a discard operation whilst we held the AGF > + * locked. > + * > + * This is exactly how online discard works - free extents are marked busy when > + * they are freed, and once the extent free has been committed to the journal, > + * the busy extent record is marked as "undergoing discard" and the discard is > + * then issued on the free extent. Once the discard completes, the busy extent > + * record is removed and the extent is able to be allocated again. > + * > + * In the context of fstrim, if we find a free extent we need to discard, we > + * don't have to discard it immediately. All we need to do it record that free > + * extent as being busy and under discard, and all the allocation routines will > + * now avoid trying to allocate it. Hence if we mark the extent as busy under > + * the AGF lock, we can safely discard it without holding the AGF lock because > + * nothing will attempt to allocate that free space until the discard completes. ...and if the cntbt search encounters a busy extent, it'll skip it. I think that means that two FITRIM invocations running in lockstep can miss the extents being discarded by the other, right? I think this can happen with your patch? T0: T1: xfs_alloc_read_agf walk cntbt, add free space to busy list relse agf issue discards xfs_alloc_read_agf ...still waiting... walk cntbt, see all free space on busy list relse agf ...still waiting... "done" (despite discard in progress) ...still waiting... io completion done Whereas currently I think T1 will stubbornly wait for the AGF and then re-discard everything again. I wonder, should FITRIM call xfs_extent_busy_flush if it finds already-busy extents? > + * > + * Hence we can makr fstrim behave much more like bulkstat and online discard s/makr/make/ > + * w.r.t. AG header locking. By keeping the batch size low, we can minimise the > + * AGF lock holdoffs whilst still safely being able to issue discards similar to > + * bulkstat. We can also issue discards asynchronously like we do with online Can we rearrange that "Similar to bulkstat's inode batching behavior, we can minimise the AGF lock holdoffs [hold times?] whilst safely issuing discards." My hot take on that sentence was "bulkstat doesn't do discards" :) > + * discard, and so for fast devices fstrim will run much faster as we can > + * pipeline the free extent search with in flight discard IO. > + */ > + > +struct xfs_trim_work { > + struct xfs_perag *pag; > + struct list_head busy_extents; > + uint64_t blocks_trimmed; > + struct work_struct discard_endio_work; > +}; > + > +static int > +xfs_trim_gather_extents( > struct xfs_perag *pag, > xfs_daddr_t start, > xfs_daddr_t end, > xfs_daddr_t minlen, > - uint64_t *blocks_trimmed) > + xfs_extlen_t *longest, What is this @longest value? Is that a cursor for however far we've walked through the cntbt? > + struct xfs_trim_work *twork) > { > struct xfs_mount *mp = pag->pag_mount; > - struct block_device *bdev = mp->m_ddev_targp->bt_bdev; > struct xfs_btree_cur *cur; > struct xfs_buf *agbp; > struct xfs_agf *agf; > int error; > int i; > + int batch = 100; > > /* > * Force out the log. This means any transactions that might have freed > @@ -50,17 +110,27 @@ xfs_trim_extents( > cur = xfs_allocbt_init_cursor(mp, NULL, agbp, pag, XFS_BTNUM_CNT); > > /* > - * Look up the longest btree in the AGF and start with it. > + * Look up the extent length requested in the AGF and start with it. > + * > + * XXX: continuations really want a lt lookup here, so we get the > + * largest extent adjacent to the size finished off in the last batch. > + * The ge search here results in the extent discarded in the last batch > + * being discarded again before we move on to the smaller size... > */ > - error = xfs_alloc_lookup_ge(cur, 0, be32_to_cpu(agf->agf_longest), &i); > + error = xfs_alloc_lookup_ge(cur, 0, *longest, &i); Aha, it /is/ a cursor for the cntbt walk. In that case, why not pass around a xfs_alloc_rec_incore_t as the cursor, since cntbt lookups are capable of searching by blockcount and startblock? Then you'd initialize it with struct xfs_alloc_rec_incore tcur = { .ar_blockcount = pag->pagf_longest; }; and the XXX above turns into: if (!tcur->ar_startblock) error = xfs_alloc_lookup_ge(cur, 0, tcur->ar_blockcount, &i); else error = xfs_alloc_lookup_lt(cur, tcur->ar_startblock, tcur->ar_blockcount, &i); > if (error) > goto out_del_cursor; > + if (i == 0) { > + /* nothing of that length left in the AG, we are done */ > + *longest = 0; > + goto out_del_cursor; > + } > > /* > * Loop until we are done with all extents that are large > - * enough to be worth discarding. > + * enough to be worth discarding or we hit batch limits. > */ > - while (i) { > + while (i && batch-- > 0) { > xfs_agblock_t fbno; > xfs_extlen_t flen; > xfs_daddr_t dbno; > @@ -75,6 +145,20 @@ xfs_trim_extents( > } > ASSERT(flen <= be32_to_cpu(agf->agf_longest)); > > + /* > + * Keep going on this batch until we hit the record size > + * changes. That way we will start the next batch with the new > + * extent size and we don't get stuck on an extent size when > + * there are more extents of that size than the batch size. > + */ > + if (batch == 0) { > + if (flen != *longest) > + break; > + batch++; Hmm. So if the cntbt records are: [N1, 100000] [N2, 1] [N3, 1] ... [N100001, 1] Does that mean batch 1 is: [N1, 100000] and batch 2 is: <100,000 single block extents> (where presumably N1..N100001 do not overlap)? That seems poorly balanced, especially for (bad) SSDs whose per-discard runtime is y = mx + b with a small m and huge b. (Yes I have an SSD like that...) I think if you changed the cursor to a cntbt record, then you could bound the batch size by number of blocks, or number of busy extents, or both, right? > + } else { > + *longest = flen; > + } > + > /* > * use daddr format for all range/len calculations as that is > * the format the range/len variables are supplied in by > @@ -88,6 +172,7 @@ xfs_trim_extents( > */ > if (dlen < minlen) { > trace_xfs_discard_toosmall(mp, pag->pag_agno, fbno, flen); > + *longest = 0; > break; > } > > @@ -110,29 +195,180 @@ xfs_trim_extents( > goto next_extent; > } > > - trace_xfs_discard_extent(mp, pag->pag_agno, fbno, flen); > - error = blkdev_issue_discard(bdev, dbno, dlen, GFP_NOFS); > - if (error) > - break; > - *blocks_trimmed += flen; > - > + xfs_extent_busy_insert_discard(pag, fbno, flen, > + &twork->busy_extents); > + twork->blocks_trimmed += flen; > next_extent: > error = xfs_btree_decrement(cur, 0, &i); > if (error) > break; > > - if (fatal_signal_pending(current)) { > - error = -ERESTARTSYS; > - break; > - } > + /* > + * If there's no more records in the tree, we are done. Set > + * longest to 0 to indicate to the caller that there is no more > + * extents to search. > + */ > + if (i == 0) > + *longest = 0; > } > > + /* > + * If there was an error, release all the gathered busy extents because > + * we aren't going to issue a discard on them any more. If we ran out of > + * records, set *longest to zero to tell the caller there is nothing > + * left in this AG. > + */ > + if (error) > + xfs_extent_busy_clear(pag->pag_mount, &twork->busy_extents, > + false); > out_del_cursor: > xfs_btree_del_cursor(cur, error); > xfs_buf_relse(agbp); > return error; > } > > +static void > +xfs_trim_discard_endio_work( > + struct work_struct *work) > +{ > + struct xfs_trim_work *twork = > + container_of(work, struct xfs_trim_work, discard_endio_work); > + struct xfs_perag *pag = twork->pag; > + > + xfs_extent_busy_clear(pag->pag_mount, &twork->busy_extents, false); > + kmem_free(twork); > + xfs_perag_rele(pag); > +} > + > +/* > + * Queue up the actual completion to a thread to avoid IRQ-safe locking for > + * pagb_lock. > + */ > +static void > +xfs_trim_discard_endio( > + struct bio *bio) > +{ > + struct xfs_trim_work *twork = bio->bi_private; > + > + INIT_WORK(&twork->discard_endio_work, xfs_trim_discard_endio_work); > + queue_work(xfs_discard_wq, &twork->discard_endio_work); > + bio_put(bio); > +} > + > +/* > + * Walk the discard list and issue discards on all the busy extents in the > + * list. We plug and chain the bios so that we only need a single completion > + * call to clear all the busy extents once the discards are complete. > + * > + * XXX: This is largely a copy of xlog_discard_busy_extents(), opportunity for > + * a common implementation there. Indeed. :) > + */ > +static int > +xfs_trim_discard_extents( > + struct xfs_perag *pag, > + struct xfs_trim_work *twork) > +{ > + struct xfs_mount *mp = pag->pag_mount; > + struct xfs_extent_busy *busyp; > + struct bio *bio = NULL; > + struct blk_plug plug; > + int error = 0; > + > + blk_start_plug(&plug); > + list_for_each_entry(busyp, &twork->busy_extents, list) { > + trace_xfs_discard_extent(mp, busyp->agno, busyp->bno, > + busyp->length); > + > + error = __blkdev_issue_discard(mp->m_ddev_targp->bt_bdev, > + XFS_AGB_TO_DADDR(mp, busyp->agno, busyp->bno), > + XFS_FSB_TO_BB(mp, busyp->length), > + GFP_NOFS, &bio); > + if (error && error != -EOPNOTSUPP) { > + xfs_info(mp, > + "discard failed for extent [0x%llx,%u], error %d", > + (unsigned long long)busyp->bno, > + busyp->length, > + error); > + break; > + } > + } > + > + if (bio) { > + bio->bi_private = twork; > + bio->bi_end_io = xfs_trim_discard_endio; > + submit_bio(bio); > + } else { > + xfs_trim_discard_endio_work(&twork->discard_endio_work); > + } > + blk_finish_plug(&plug); > + > + return error; > +} > + > +/* > + * Iterate the free list gathering extents and discarding them. We need a cursor > + * for the repeated iteration of gather/discard loop, so use the longest extent > + * we found in the last batch as the key to start the next. > + */ > +static int > +xfs_trim_extents( > + struct xfs_perag *pag, > + xfs_daddr_t start, > + xfs_daddr_t end, > + xfs_daddr_t minlen, > + uint64_t *blocks_trimmed) > +{ > + struct xfs_trim_work *twork; > + xfs_extlen_t longest = pag->pagf_longest; > + int error = 0; > + > + do { > + LIST_HEAD(extents); > + > + twork = kzalloc(sizeof(*twork), GFP_KERNEL); > + if (!twork) { > + error = -ENOMEM; > + break; > + } > + > + atomic_inc(&pag->pag_active_ref); > + twork->pag = pag; twork->pag = xfs_perag_hold(pag); ? > + INIT_LIST_HEAD(&twork->busy_extents); > + > + error = xfs_trim_gather_extents(pag, start, end, minlen, > + &longest, twork); > + if (error) { > + kfree(twork); > + xfs_perag_rele(pag); > + break; > + } > + > + /* > + * We hand the trim work to the discard function here so that > + * the busy list can be walked when the discards complete and > + * removed from the busy extent list. This allows the discards > + * to run asynchronously with gathering the next round of > + * extents to discard. > + * > + * However, we must ensure that we do not reference twork after > + * this function call, as it may have been freed by the time it > + * returns control to us. > + */ > + *blocks_trimmed += twork->blocks_trimmed; > + error = xfs_trim_discard_extents(pag, twork); > + if (error) > + break; > + > + if (fatal_signal_pending(current)) { > + error = -ERESTARTSYS; > + break; > + } > + } while (longest != 0); > + > + return error; > + > +} > + > /* > * trim a range of the filesystem. > * > diff --git a/fs/xfs/xfs_extent_busy.c b/fs/xfs/xfs_extent_busy.c > index 7c2fdc71e42d..53c49b47daca 100644 > --- a/fs/xfs/xfs_extent_busy.c > +++ b/fs/xfs/xfs_extent_busy.c > @@ -19,13 +19,13 @@ > #include "xfs_log.h" > #include "xfs_ag.h" > > -void > -xfs_extent_busy_insert( > - struct xfs_trans *tp, > +static void > +xfs_extent_busy_insert_list( > struct xfs_perag *pag, > xfs_agblock_t bno, > xfs_extlen_t len, > - unsigned int flags) > + unsigned int flags, > + struct list_head *busy_list) > { > struct xfs_extent_busy *new; > struct xfs_extent_busy *busyp; > @@ -40,7 +40,7 @@ xfs_extent_busy_insert( > new->flags = flags; > > /* trace before insert to be able to see failed inserts */ > - trace_xfs_extent_busy(tp->t_mountp, pag->pag_agno, bno, len); > + trace_xfs_extent_busy(pag->pag_mount, pag->pag_agno, bno, len); > > spin_lock(&pag->pagb_lock); > rbp = &pag->pagb_tree.rb_node; > @@ -62,10 +62,31 @@ xfs_extent_busy_insert( > rb_link_node(&new->rb_node, parent, rbp); > rb_insert_color(&new->rb_node, &pag->pagb_tree); > > - list_add(&new->list, &tp->t_busy); > + list_add(&new->list, busy_list); > spin_unlock(&pag->pagb_lock); > } > > +void > +xfs_extent_busy_insert( > + struct xfs_trans *tp, > + struct xfs_perag *pag, > + xfs_agblock_t bno, > + xfs_extlen_t len, > + unsigned int flags) > +{ > + xfs_extent_busy_insert_list(pag, bno, len, flags, &tp->t_busy); > +} > + > +void xfs_extent_busy_insert_discard( Function name on newline. > + struct xfs_perag *pag, > + xfs_agblock_t bno, > + xfs_extlen_t len, > + struct list_head *busy_list) > +{ > + xfs_extent_busy_insert_list(pag, bno, len, XFS_EXTENT_BUSY_DISCARDED, > + busy_list); > +} > + > /* > * Search for a busy extent within the range of the extent we are about to > * allocate. You need to be holding the busy extent tree lock when calling > diff --git a/fs/xfs/xfs_extent_busy.h b/fs/xfs/xfs_extent_busy.h > index c37bf87e6781..f99073208770 100644 > --- a/fs/xfs/xfs_extent_busy.h > +++ b/fs/xfs/xfs_extent_busy.h > @@ -35,6 +35,10 @@ void > xfs_extent_busy_insert(struct xfs_trans *tp, struct xfs_perag *pag, > xfs_agblock_t bno, xfs_extlen_t len, unsigned int flags); > > +void > +xfs_extent_busy_insert_discard(struct xfs_perag *pag, xfs_agblock_t bno, > + xfs_extlen_t len, struct list_head *busy_list); > + > void > xfs_extent_busy_clear(struct xfs_mount *mp, struct list_head *list, > bool do_discard); > -- > 2.40.1 >
On Tue, Aug 29, 2023 at 08:50:08AM -0700, Darrick J. Wong wrote: > On Tue, Aug 29, 2023 at 04:57:10PM +1000, Dave Chinner wrote: > > +/* > > + * Notes on an efficient, low latency fstrim algorithm > > + * > > + * We need to walk the filesystem free space and issue discards on the free > > + * space that meet the search criteria (size and location). We cannot issue > > + * discards on extents that might be in use, or are so recently in use they are > > + * still marked as busy. To serialise against extent state changes whilst we are > > + * gathering extents to trim, we must hold the AGF lock to lock out other > > + * allocations and extent free operations that might change extent state. > > + * > > + * However, we cannot just hold the AGF for the entire AG free space walk whilst > > + * we issue discards on each free space that is found. Storage devices can have > > + * extremely slow discard implementations (e.g. ceph RBD) and so walking a > > + * couple of million free extents and issuing synchronous discards on each > > + * extent can take a *long* time. Whilst we are doing this walk, nothing else > > + * can access the AGF, and we can stall transactions and hence the log whilst > > + * modifications wait for the AGF lock to be released. This can lead hung tasks > > + * kicking the hung task timer and rebooting the system. This is bad. > > + * > > + * Hence we need to take a leaf from the bulkstat playbook. It takes the AGI > > + * lock, gathers a range of inode cluster buffers that are allocated, drops the > > + * AGI lock and then reads all the inode cluster buffers and processes them. It > > + * loops doing this, using a cursor to keep track of where it is up to in the AG > > + * for each iteration to restart the INOBT lookup from. > > + * > > + * We can't do this exactly with free space - once we drop the AGF lock, the > > + * state of the free extent is out of our control and we cannot run a discard > > + * safely on it in this situation. Unless, of course, we've marked the free > > + * extent as busy and undergoing a discard operation whilst we held the AGF > > + * locked. > > + * > > + * This is exactly how online discard works - free extents are marked busy when > > + * they are freed, and once the extent free has been committed to the journal, > > + * the busy extent record is marked as "undergoing discard" and the discard is > > + * then issued on the free extent. Once the discard completes, the busy extent > > + * record is removed and the extent is able to be allocated again. > > + * > > + * In the context of fstrim, if we find a free extent we need to discard, we > > + * don't have to discard it immediately. All we need to do it record that free > > + * extent as being busy and under discard, and all the allocation routines will > > + * now avoid trying to allocate it. Hence if we mark the extent as busy under > > + * the AGF lock, we can safely discard it without holding the AGF lock because > > + * nothing will attempt to allocate that free space until the discard completes. > > ...and if the cntbt search encounters a busy extent, it'll skip it. I > think that means that two FITRIM invocations running in lockstep can > miss the extents being discarded by the other, right? Yes. > I think this can happen with your patch? > > T0: T1: > xfs_alloc_read_agf > walk cntbt, > add free space to busy list > relse agf > issue discards > > xfs_alloc_read_agf > ...still waiting... > walk cntbt, > see all free space on busy list > relse agf > ...still waiting... > "done" (despite discard in progress) > > ...still waiting... > io completion > done Yes, though it doesn't actually wait for discards to complete. It issues discards without blocking until the submission queue is full, then the discard being submitted then waits for a free slot (i.e. waits for io completion). So submission of new discards is effectively throttled to whatever speed discards are completing, without having to have anything explicitly wait for completion. > Whereas currently I think T1 will stubbornly wait for the AGF and then > re-discard everything again. Yes, that is the current behaviour, and it isn't good. > I wonder, should FITRIM call > xfs_extent_busy_flush if it finds already-busy extents? Perhaps. Maybe we can replace the log force before we grab the AGF lock with a flush if we see non-discard busy extents in the walk, but I'm not sure we really care that much because fstrim is advisory... > > + * w.r.t. AG header locking. By keeping the batch size low, we can minimise the > > + * AGF lock holdoffs whilst still safely being able to issue discards similar to > > + * bulkstat. We can also issue discards asynchronously like we do with online > > Can we rearrange that "Similar to bulkstat's inode batching behavior, we > can minimise the AGF lock holdoffs [hold times?] whilst safely issuing > discards." > > My hot take on that sentence was "bulkstat doesn't do discards" :) Sure. I knew what it meant, maybe not everyone else :) > > + * discard, and so for fast devices fstrim will run much faster as we can > > + * pipeline the free extent search with in flight discard IO. > > + */ > > + > > +struct xfs_trim_work { > > + struct xfs_perag *pag; > > + struct list_head busy_extents; > > + uint64_t blocks_trimmed; > > + struct work_struct discard_endio_work; > > +}; > > + > > +static int > > +xfs_trim_gather_extents( > > struct xfs_perag *pag, > > xfs_daddr_t start, > > xfs_daddr_t end, > > xfs_daddr_t minlen, > > - uint64_t *blocks_trimmed) > > + xfs_extlen_t *longest, > > What is this @longest value? Is that a cursor for however far we've > walked through the cntbt? *nod* > > + struct xfs_trim_work *twork) > > { > > struct xfs_mount *mp = pag->pag_mount; > > - struct block_device *bdev = mp->m_ddev_targp->bt_bdev; > > struct xfs_btree_cur *cur; > > struct xfs_buf *agbp; > > struct xfs_agf *agf; > > int error; > > int i; > > + int batch = 100; > > > > /* > > * Force out the log. This means any transactions that might have freed > > @@ -50,17 +110,27 @@ xfs_trim_extents( > > cur = xfs_allocbt_init_cursor(mp, NULL, agbp, pag, XFS_BTNUM_CNT); > > > > /* > > - * Look up the longest btree in the AGF and start with it. > > + * Look up the extent length requested in the AGF and start with it. > > + * > > + * XXX: continuations really want a lt lookup here, so we get the > > + * largest extent adjacent to the size finished off in the last batch. > > + * The ge search here results in the extent discarded in the last batch > > + * being discarded again before we move on to the smaller size... > > */ > > - error = xfs_alloc_lookup_ge(cur, 0, be32_to_cpu(agf->agf_longest), &i); > > + error = xfs_alloc_lookup_ge(cur, 0, *longest, &i); > > Aha, it /is/ a cursor for the cntbt walk. In that case, why not pass > around a xfs_alloc_rec_incore_t as the cursor, since cntbt lookups are > capable of searching by blockcount and startblock? > > Then you'd initialize it with > > struct xfs_alloc_rec_incore tcur = { > .ar_blockcount = pag->pagf_longest; > }; > > and the XXX above turns into: > > if (!tcur->ar_startblock) > error = xfs_alloc_lookup_ge(cur, 0, tcur->ar_blockcount, &i); > else > error = xfs_alloc_lookup_lt(cur, tcur->ar_startblock, > tcur->ar_blockcount, &i); Yup, that's a good idea, and it solves the lookup problem I was working around with the whacky batch handling.... > > if (error) > > goto out_del_cursor; > > + if (i == 0) { > > + /* nothing of that length left in the AG, we are done */ > > + *longest = 0; > > + goto out_del_cursor; > > + } > > > > /* > > * Loop until we are done with all extents that are large > > - * enough to be worth discarding. > > + * enough to be worth discarding or we hit batch limits. > > */ > > - while (i) { > > + while (i && batch-- > 0) { > > xfs_agblock_t fbno; > > xfs_extlen_t flen; > > xfs_daddr_t dbno; > > @@ -75,6 +145,20 @@ xfs_trim_extents( > > } > > ASSERT(flen <= be32_to_cpu(agf->agf_longest)); > > > > + /* > > + * Keep going on this batch until we hit the record size > > + * changes. That way we will start the next batch with the new > > + * extent size and we don't get stuck on an extent size when > > + * there are more extents of that size than the batch size. > > + */ > > + if (batch == 0) { > > + if (flen != *longest) > > + break; > > + batch++; .... here. > > Hmm. So if the cntbt records are: > > [N1, 100000] > [N2, 1] > [N3, 1] > ... > [N100001, 1] > > Does that mean batch 1 is: > > [N1, 100000] > > and batch 2 is: > > <100,000 single block extents> > > (where presumably N1..N100001 do not overlap)? > > That seems poorly balanced, especially for (bad) SSDs whose per-discard > runtime is y = mx + b with a small m and huge b. Yes, it is poorly balanced - I hadn't thought hard enough about how to optimise the cursor and lookup yet (which your suggestion above does nicely) and so I just made it so it doesn't get stuck and doesn't skip random extents... > (Yes I have an SSD like that...) > > I think if you changed the cursor to a cntbt record, then you could > bound the batch size by number of blocks, or number of busy extents, > or both, right? I think just batching by the number of busy extents is fine - we don't actually care how long the discards take anymore because we aren't holding the AGF lock and so the block count spanned by the discards is irrelevant. Doing it in batches of 50-100 busy extents means the gather operation is confined to a single btree block.... .... and so maybe the right batch size is "gather all the free extents in a single btree leaf" to discard.... > > +static int > > +xfs_trim_extents( > > + struct xfs_perag *pag, > > + xfs_daddr_t start, > > + xfs_daddr_t end, > > + xfs_daddr_t minlen, > > + uint64_t *blocks_trimmed) > > +{ > > + struct xfs_trim_work *twork; > > + xfs_extlen_t longest = pag->pagf_longest; > > + int error = 0; > > + > > + do { > > + LIST_HEAD(extents); > > + > > + twork = kzalloc(sizeof(*twork), GFP_KERNEL); > > + if (!twork) { > > + error = -ENOMEM; > > + break; > > + } > > + > > + atomic_inc(&pag->pag_active_ref); > > + twork->pag = pag; > > twork->pag = xfs_perag_hold(pag); ? hold() takes a passive ref, but because we don't wait for discards to complete, we need to hold an active ref on the AG until all the discards are done and and cleared from perag. Thanks for looking at this and solving problems I didn't have good solutions to yet. -Dave.
diff --git a/fs/xfs/xfs_discard.c b/fs/xfs/xfs_discard.c index afc4c78b9eed..c2eec29c02d1 100644 --- a/fs/xfs/xfs_discard.c +++ b/fs/xfs/xfs_discard.c @@ -1,6 +1,6 @@ // SPDX-License-Identifier: GPL-2.0 /* - * Copyright (C) 2010 Red Hat, Inc. + * Copyright (C) 2010, 2023 Red Hat, Inc. * All Rights Reserved. */ #include "xfs.h" @@ -19,21 +19,81 @@ #include "xfs_log.h" #include "xfs_ag.h" -STATIC int -xfs_trim_extents( +/* + * Notes on an efficient, low latency fstrim algorithm + * + * We need to walk the filesystem free space and issue discards on the free + * space that meet the search criteria (size and location). We cannot issue + * discards on extents that might be in use, or are so recently in use they are + * still marked as busy. To serialise against extent state changes whilst we are + * gathering extents to trim, we must hold the AGF lock to lock out other + * allocations and extent free operations that might change extent state. + * + * However, we cannot just hold the AGF for the entire AG free space walk whilst + * we issue discards on each free space that is found. Storage devices can have + * extremely slow discard implementations (e.g. ceph RBD) and so walking a + * couple of million free extents and issuing synchronous discards on each + * extent can take a *long* time. Whilst we are doing this walk, nothing else + * can access the AGF, and we can stall transactions and hence the log whilst + * modifications wait for the AGF lock to be released. This can lead hung tasks + * kicking the hung task timer and rebooting the system. This is bad. + * + * Hence we need to take a leaf from the bulkstat playbook. It takes the AGI + * lock, gathers a range of inode cluster buffers that are allocated, drops the + * AGI lock and then reads all the inode cluster buffers and processes them. It + * loops doing this, using a cursor to keep track of where it is up to in the AG + * for each iteration to restart the INOBT lookup from. + * + * We can't do this exactly with free space - once we drop the AGF lock, the + * state of the free extent is out of our control and we cannot run a discard + * safely on it in this situation. Unless, of course, we've marked the free + * extent as busy and undergoing a discard operation whilst we held the AGF + * locked. + * + * This is exactly how online discard works - free extents are marked busy when + * they are freed, and once the extent free has been committed to the journal, + * the busy extent record is marked as "undergoing discard" and the discard is + * then issued on the free extent. Once the discard completes, the busy extent + * record is removed and the extent is able to be allocated again. + * + * In the context of fstrim, if we find a free extent we need to discard, we + * don't have to discard it immediately. All we need to do it record that free + * extent as being busy and under discard, and all the allocation routines will + * now avoid trying to allocate it. Hence if we mark the extent as busy under + * the AGF lock, we can safely discard it without holding the AGF lock because + * nothing will attempt to allocate that free space until the discard completes. + * + * Hence we can makr fstrim behave much more like bulkstat and online discard + * w.r.t. AG header locking. By keeping the batch size low, we can minimise the + * AGF lock holdoffs whilst still safely being able to issue discards similar to + * bulkstat. We can also issue discards asynchronously like we do with online + * discard, and so for fast devices fstrim will run much faster as we can + * pipeline the free extent search with in flight discard IO. + */ + +struct xfs_trim_work { + struct xfs_perag *pag; + struct list_head busy_extents; + uint64_t blocks_trimmed; + struct work_struct discard_endio_work; +}; + +static int +xfs_trim_gather_extents( struct xfs_perag *pag, xfs_daddr_t start, xfs_daddr_t end, xfs_daddr_t minlen, - uint64_t *blocks_trimmed) + xfs_extlen_t *longest, + struct xfs_trim_work *twork) { struct xfs_mount *mp = pag->pag_mount; - struct block_device *bdev = mp->m_ddev_targp->bt_bdev; struct xfs_btree_cur *cur; struct xfs_buf *agbp; struct xfs_agf *agf; int error; int i; + int batch = 100; /* * Force out the log. This means any transactions that might have freed @@ -50,17 +110,27 @@ xfs_trim_extents( cur = xfs_allocbt_init_cursor(mp, NULL, agbp, pag, XFS_BTNUM_CNT); /* - * Look up the longest btree in the AGF and start with it. + * Look up the extent length requested in the AGF and start with it. + * + * XXX: continuations really want a lt lookup here, so we get the + * largest extent adjacent to the size finished off in the last batch. + * The ge search here results in the extent discarded in the last batch + * being discarded again before we move on to the smaller size... */ - error = xfs_alloc_lookup_ge(cur, 0, be32_to_cpu(agf->agf_longest), &i); + error = xfs_alloc_lookup_ge(cur, 0, *longest, &i); if (error) goto out_del_cursor; + if (i == 0) { + /* nothing of that length left in the AG, we are done */ + *longest = 0; + goto out_del_cursor; + } /* * Loop until we are done with all extents that are large - * enough to be worth discarding. + * enough to be worth discarding or we hit batch limits. */ - while (i) { + while (i && batch-- > 0) { xfs_agblock_t fbno; xfs_extlen_t flen; xfs_daddr_t dbno; @@ -75,6 +145,20 @@ xfs_trim_extents( } ASSERT(flen <= be32_to_cpu(agf->agf_longest)); + /* + * Keep going on this batch until we hit the record size + * changes. That way we will start the next batch with the new + * extent size and we don't get stuck on an extent size when + * there are more extents of that size than the batch size. + */ + if (batch == 0) { + if (flen != *longest) + break; + batch++; + } else { + *longest = flen; + } + /* * use daddr format for all range/len calculations as that is * the format the range/len variables are supplied in by @@ -88,6 +172,7 @@ xfs_trim_extents( */ if (dlen < minlen) { trace_xfs_discard_toosmall(mp, pag->pag_agno, fbno, flen); + *longest = 0; break; } @@ -110,29 +195,180 @@ xfs_trim_extents( goto next_extent; } - trace_xfs_discard_extent(mp, pag->pag_agno, fbno, flen); - error = blkdev_issue_discard(bdev, dbno, dlen, GFP_NOFS); - if (error) - break; - *blocks_trimmed += flen; - + xfs_extent_busy_insert_discard(pag, fbno, flen, + &twork->busy_extents); + twork->blocks_trimmed += flen; next_extent: error = xfs_btree_decrement(cur, 0, &i); if (error) break; - if (fatal_signal_pending(current)) { - error = -ERESTARTSYS; - break; - } + /* + * If there's no more records in the tree, we are done. Set + * longest to 0 to indicate to the caller that there is no more + * extents to search. + */ + if (i == 0) + *longest = 0; } + /* + * If there was an error, release all the gathered busy extents because + * we aren't going to issue a discard on them any more. If we ran out of + * records, set *longest to zero to tell the caller there is nothing + * left in this AG. + */ + if (error) + xfs_extent_busy_clear(pag->pag_mount, &twork->busy_extents, + false); out_del_cursor: xfs_btree_del_cursor(cur, error); xfs_buf_relse(agbp); return error; } +static void +xfs_trim_discard_endio_work( + struct work_struct *work) +{ + struct xfs_trim_work *twork = + container_of(work, struct xfs_trim_work, discard_endio_work); + struct xfs_perag *pag = twork->pag; + + xfs_extent_busy_clear(pag->pag_mount, &twork->busy_extents, false); + kmem_free(twork); + xfs_perag_rele(pag); +} + +/* + * Queue up the actual completion to a thread to avoid IRQ-safe locking for + * pagb_lock. + */ +static void +xfs_trim_discard_endio( + struct bio *bio) +{ + struct xfs_trim_work *twork = bio->bi_private; + + INIT_WORK(&twork->discard_endio_work, xfs_trim_discard_endio_work); + queue_work(xfs_discard_wq, &twork->discard_endio_work); + bio_put(bio); +} + +/* + * Walk the discard list and issue discards on all the busy extents in the + * list. We plug and chain the bios so that we only need a single completion + * call to clear all the busy extents once the discards are complete. + * + * XXX: This is largely a copy of xlog_discard_busy_extents(), opportunity for + * a common implementation there. + */ +static int +xfs_trim_discard_extents( + struct xfs_perag *pag, + struct xfs_trim_work *twork) +{ + struct xfs_mount *mp = pag->pag_mount; + struct xfs_extent_busy *busyp; + struct bio *bio = NULL; + struct blk_plug plug; + int error = 0; + + blk_start_plug(&plug); + list_for_each_entry(busyp, &twork->busy_extents, list) { + trace_xfs_discard_extent(mp, busyp->agno, busyp->bno, + busyp->length); + + error = __blkdev_issue_discard(mp->m_ddev_targp->bt_bdev, + XFS_AGB_TO_DADDR(mp, busyp->agno, busyp->bno), + XFS_FSB_TO_BB(mp, busyp->length), + GFP_NOFS, &bio); + if (error && error != -EOPNOTSUPP) { + xfs_info(mp, + "discard failed for extent [0x%llx,%u], error %d", + (unsigned long long)busyp->bno, + busyp->length, + error); + break; + } + } + + if (bio) { + bio->bi_private = twork; + bio->bi_end_io = xfs_trim_discard_endio; + submit_bio(bio); + } else { + xfs_trim_discard_endio_work(&twork->discard_endio_work); + } + blk_finish_plug(&plug); + + return error; +} + +/* + * Iterate the free list gathering extents and discarding them. We need a cursor + * for the repeated iteration of gather/discard loop, so use the longest extent + * we found in the last batch as the key to start the next. + */ +static int +xfs_trim_extents( + struct xfs_perag *pag, + xfs_daddr_t start, + xfs_daddr_t end, + xfs_daddr_t minlen, + uint64_t *blocks_trimmed) +{ + struct xfs_trim_work *twork; + xfs_extlen_t longest = pag->pagf_longest; + int error = 0; + + do { + LIST_HEAD(extents); + + twork = kzalloc(sizeof(*twork), GFP_KERNEL); + if (!twork) { + error = -ENOMEM; + break; + } + + atomic_inc(&pag->pag_active_ref); + twork->pag = pag; + INIT_LIST_HEAD(&twork->busy_extents); + + error = xfs_trim_gather_extents(pag, start, end, minlen, + &longest, twork); + if (error) { + kfree(twork); + xfs_perag_rele(pag); + break; + } + + /* + * We hand the trim work to the discard function here so that + * the busy list can be walked when the discards complete and + * removed from the busy extent list. This allows the discards + * to run asynchronously with gathering the next round of + * extents to discard. + * + * However, we must ensure that we do not reference twork after + * this function call, as it may have been freed by the time it + * returns control to us. + */ + *blocks_trimmed += twork->blocks_trimmed; + error = xfs_trim_discard_extents(pag, twork); + if (error) + break; + + if (fatal_signal_pending(current)) { + error = -ERESTARTSYS; + break; + } + } while (longest != 0); + + return error; + +} + /* * trim a range of the filesystem. * diff --git a/fs/xfs/xfs_extent_busy.c b/fs/xfs/xfs_extent_busy.c index 7c2fdc71e42d..53c49b47daca 100644 --- a/fs/xfs/xfs_extent_busy.c +++ b/fs/xfs/xfs_extent_busy.c @@ -19,13 +19,13 @@ #include "xfs_log.h" #include "xfs_ag.h" -void -xfs_extent_busy_insert( - struct xfs_trans *tp, +static void +xfs_extent_busy_insert_list( struct xfs_perag *pag, xfs_agblock_t bno, xfs_extlen_t len, - unsigned int flags) + unsigned int flags, + struct list_head *busy_list) { struct xfs_extent_busy *new; struct xfs_extent_busy *busyp; @@ -40,7 +40,7 @@ xfs_extent_busy_insert( new->flags = flags; /* trace before insert to be able to see failed inserts */ - trace_xfs_extent_busy(tp->t_mountp, pag->pag_agno, bno, len); + trace_xfs_extent_busy(pag->pag_mount, pag->pag_agno, bno, len); spin_lock(&pag->pagb_lock); rbp = &pag->pagb_tree.rb_node; @@ -62,10 +62,31 @@ xfs_extent_busy_insert( rb_link_node(&new->rb_node, parent, rbp); rb_insert_color(&new->rb_node, &pag->pagb_tree); - list_add(&new->list, &tp->t_busy); + list_add(&new->list, busy_list); spin_unlock(&pag->pagb_lock); } +void +xfs_extent_busy_insert( + struct xfs_trans *tp, + struct xfs_perag *pag, + xfs_agblock_t bno, + xfs_extlen_t len, + unsigned int flags) +{ + xfs_extent_busy_insert_list(pag, bno, len, flags, &tp->t_busy); +} + +void xfs_extent_busy_insert_discard( + struct xfs_perag *pag, + xfs_agblock_t bno, + xfs_extlen_t len, + struct list_head *busy_list) +{ + xfs_extent_busy_insert_list(pag, bno, len, XFS_EXTENT_BUSY_DISCARDED, + busy_list); +} + /* * Search for a busy extent within the range of the extent we are about to * allocate. You need to be holding the busy extent tree lock when calling diff --git a/fs/xfs/xfs_extent_busy.h b/fs/xfs/xfs_extent_busy.h index c37bf87e6781..f99073208770 100644 --- a/fs/xfs/xfs_extent_busy.h +++ b/fs/xfs/xfs_extent_busy.h @@ -35,6 +35,10 @@ void xfs_extent_busy_insert(struct xfs_trans *tp, struct xfs_perag *pag, xfs_agblock_t bno, xfs_extlen_t len, unsigned int flags); +void +xfs_extent_busy_insert_discard(struct xfs_perag *pag, xfs_agblock_t bno, + xfs_extlen_t len, struct list_head *busy_list); + void xfs_extent_busy_clear(struct xfs_mount *mp, struct list_head *list, bool do_discard);