Re: [PATCH 03/14] xfs: repair free space btrees

Dave Chinner
2018-06-04T02:12:38Z

On Wed, May 30, 2018 at 12:30:58PM -0700, Darrick J. Wong wrote:
> From: Darrick J. Wong <darrick.wong@oracle.com>
>
> Rebuild the free space btrees from the gaps in the rmap btree.
>
> Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
> ---
> fs/xfs/Makefile | 1
> fs/xfs/scrub/alloc.c | 1
> fs/xfs/scrub/alloc_repair.c | 430 +++++++++++++++++++++++++++++++++++++++++++
> fs/xfs/scrub/common.c | 8 +
> fs/xfs/scrub/repair.h | 2
> fs/xfs/scrub/scrub.c | 4
> 6 files changed, 442 insertions(+), 4 deletions(-)
> create mode 100644 fs/xfs/scrub/alloc_repair.c
>
>
> diff --git a/fs/xfs/Makefile b/fs/xfs/Makefile
> index 29fe115f29d5..abe035ad0aa4 100644
> --- a/fs/xfs/Makefile
> +++ b/fs/xfs/Makefile
> @@ -175,6 +175,7 @@ xfs-$(CONFIG_XFS_QUOTA) += scrub/quota.o
> ifeq ($(CONFIG_XFS_ONLINE_REPAIR),y)
> xfs-y += $(addprefix scrub/, \
> agheader_repair.o \
> + alloc_repair.o \
> repair.o \
> )
> endif
> diff --git a/fs/xfs/scrub/alloc.c b/fs/xfs/scrub/alloc.c
> index 941a0a55224e..fe7e8bdf4a52 100644
> --- a/fs/xfs/scrub/alloc.c
> +++ b/fs/xfs/scrub/alloc.c
> @@ -29,7 +29,6 @@
> #include "xfs_log_format.h"
> #include "xfs_trans.h"
> #include "xfs_sb.h"
> -#include "xfs_alloc.h"
> #include "xfs_rmap.h"
> #include "xfs_alloc.h"
> #include "scrub/xfs_scrub.h"
> diff --git a/fs/xfs/scrub/alloc_repair.c b/fs/xfs/scrub/alloc_repair.c
> new file mode 100644
> index 000000000000..5a81713a69cd
> --- /dev/null
> +++ b/fs/xfs/scrub/alloc_repair.c
> @@ -0,0 +1,430 @@
> +/*
> + * Copyright (C) 2017 Oracle. All Rights Reserved.
> + *
> + * Author: Darrick J. Wong <darrick.wong@oracle.com>
> + *
> + * This program is free software; you can redistribute it and/or
> + * modify it under the terms of the GNU General Public License
> + * as published by the Free Software Foundation; either version 2
> + * of the License, or (at your option) any later version.
> + *
> + * This program is distributed in the hope that it would be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
> + * GNU General Public License for more details.
> + *
> + * You should have received a copy of the GNU General Public License
> + * along with this program; if not, write the Free Software Foundation,
> + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
> + */
> +#include "xfs.h"
> +#include "xfs_fs.h"
> +#include "xfs_shared.h"
> +#include "xfs_format.h"
> +#include "xfs_trans_resv.h"
> +#include "xfs_mount.h"
> +#include "xfs_defer.h"
> +#include "xfs_btree.h"
> +#include "xfs_bit.h"
> +#include "xfs_log_format.h"
> +#include "xfs_trans.h"
> +#include "xfs_sb.h"
> +#include "xfs_alloc.h"
> +#include "xfs_alloc_btree.h"
> +#include "xfs_rmap.h"
> +#include "xfs_rmap_btree.h"
> +#include "xfs_inode.h"
> +#include "xfs_refcount.h"
> +#include "scrub/xfs_scrub.h"
> +#include "scrub/scrub.h"
> +#include "scrub/common.h"
> +#include "scrub/btree.h"
> +#include "scrub/trace.h"
> +#include "scrub/repair.h"
> +
> +/* Free space btree repair. */

Can you add a decription of the algorithm used here.

> +
> +struct xfs_repair_alloc_extent {
> + struct list_head list;
> + xfs_agblock_t bno;
> + xfs_extlen_t len;
> +};
> +
> +struct xfs_repair_alloc {
> + struct list_head extlist;
> + struct xfs_repair_extent_list btlist; /* OWN_AG blocks */
> + struct xfs_repair_extent_list nobtlist; /* rmapbt/agfl blocks */
> + struct xfs_scrub_context *sc;
> + xfs_agblock_t next_bno;
> + uint64_t nr_records;
> +};
> +
> +/* Record extents that aren't in use from gaps in the rmap records. */
> +STATIC int
> +xfs_repair_alloc_extent_fn(
> + struct xfs_btree_cur *cur,
> + struct xfs_rmap_irec *rec,
> + void *priv)
> +{
> + struct xfs_repair_alloc *ra = priv;
> + struct xfs_repair_alloc_extent *rae;
> + struct xfs_buf *bp;
> + xfs_fsblock_t fsb;
> + int i;
> + int error;
> +
> + /* Record all the OWN_AG blocks... */
> + if (rec->rm_owner == XFS_RMAP_OWN_AG) {
> + fsb = XFS_AGB_TO_FSB(cur->bc_mp, cur->bc_private.a.agno,
> + rec->rm_startblock);
> + error = xfs_repair_collect_btree_extent(ra->sc,
> + &ra->btlist, fsb, rec->rm_blockcount);
> + if (error)
> + return error;
> + }
> +
> + /* ...and all the rmapbt blocks... */
> + for (i = 0; i < cur->bc_nlevels && cur->bc_ptrs[i] == 1; i++) {
> + xfs_btree_get_block(cur, i, &bp);
> + if (!bp)
> + continue;
> + fsb = XFS_DADDR_TO_FSB(cur->bc_mp, bp->b_bn);
> + error = xfs_repair_collect_btree_extent(ra->sc,
> + &ra->nobtlist, fsb, 1);
> + if (error)
> + return error;
> + }

This looks familiar from previous patches, including the magic
bc_ptrs check. factoring opportunity?

> +
> + /* ...and all the free space. */
> + if (rec->rm_startblock > ra->next_bno) {
> + trace_xfs_repair_alloc_extent_fn(cur->bc_mp,
> + cur->bc_private.a.agno,
> + ra->next_bno, rec->rm_startblock - ra->next_bno,
> + XFS_RMAP_OWN_NULL, 0, 0);
> +
> + rae = kmem_alloc(sizeof(struct xfs_repair_alloc_extent),
> + KM_MAYFAIL);
> + if (!rae)
> + return -ENOMEM;
> + INIT_LIST_HEAD(&rae->list);
> + rae->bno = ra->next_bno;
> + rae->len = rec->rm_startblock - ra->next_bno;
> + list_add_tail(&rae->list, &ra->extlist);
> + ra->nr_records++;
> + }
> + ra->next_bno = max_t(xfs_agblock_t, ra->next_bno,
> + rec->rm_startblock + rec->rm_blockcount);
> + return 0;
> +}

[....]

> +/* Allocate a block from the (cached) longest extent in the AG. */
> +STATIC xfs_fsblock_t
> +xfs_repair_allocbt_alloc_from_longest(
> + struct xfs_repair_alloc *ra,
> + struct xfs_repair_alloc_extent **longest)
> +{
> + xfs_fsblock_t fsb;
> +
> + if (*longest && (*longest)->len == 0) {
> + list_del(&(*longest)->list);
> + kmem_free(*longest);
> + *longest = NULL;
> + }
> +
> + if (*longest == NULL) {
> + *longest = xfs_repair_allocbt_get_longest(ra);
> + if (*longest == NULL)
> + return NULLFSBLOCK;
> + }
> +
> + fsb = XFS_AGB_TO_FSB(ra->sc->mp, ra->sc->sa.agno, (*longest)->bno);
> + (*longest)->bno++;
> + (*longest)->len--;

What if this makes the longest extent no longer the longest on the
extent list?

> + return fsb;
> +}
> +
> +/* Repair the freespace btrees for some AG. */
> +int
> +xfs_repair_allocbt(
> + struct xfs_scrub_context *sc)
> +{
> + struct xfs_repair_alloc ra;
> + struct xfs_owner_info oinfo;
> + struct xfs_mount *mp = sc->mp;
> + struct xfs_btree_cur *cur = NULL;
> + struct xfs_repair_alloc_extent *longest = NULL;
> + struct xfs_repair_alloc_extent *rae;
> + struct xfs_repair_alloc_extent *n;
> + struct xfs_perag *pag;
> + struct xfs_agf *agf;
> + struct xfs_buf *bp;
> + xfs_fsblock_t bnofsb;
> + xfs_fsblock_t cntfsb;
> + xfs_extlen_t oldf;
> + xfs_extlen_t nr_blocks;
> + xfs_agblock_t agend;
> + int error;
> +
> + /* We require the rmapbt to rebuild anything. */
> + if (!xfs_sb_version_hasrmapbt(&mp->m_sb))
> + return -EOPNOTSUPP;
> +
> + xfs_scrub_perag_get(sc->mp, &sc->sa);
> + pag = sc->sa.pag;

Probably shoulld make xfs_scrub_perag_get() return the pag directly.

> + /*
> + * Make sure the busy extent list is clear because we can't put
> + * extents on there twice.
> + */
> + spin_lock(&pag->pagb_lock);
> + if (pag->pagb_tree.rb_node) {
> + spin_unlock(&pag->pagb_lock);
> + return -EDEADLOCK;
> + }
> + spin_unlock(&pag->pagb_lock);

Can you wrap that up a helper, say, xfs_extent_busy_list_empty()?

if (!xfs_extent_busy_list_empty(pag))
return -EDEADLOCK;

> + /*
> + * Collect all reverse mappings for free extents, and the rmapbt
> + * blocks. We can discover the rmapbt blocks completely from a
> + * query_all handler because there are always rmapbt entries.
> + * (One cannot use on query_all to visit all of a btree's blocks
> + * unless that btree is guaranteed to have at least one entry.)
> + */
> + INIT_LIST_HEAD(&ra.extlist);
> + xfs_repair_init_extent_list(&ra.btlist);
> + xfs_repair_init_extent_list(&ra.nobtlist);
> + ra.next_bno = 0;
> + ra.nr_records = 0;
> + ra.sc = sc;
> +
> + cur = xfs_rmapbt_init_cursor(mp, sc->tp, sc->sa.agf_bp, sc->sa.agno);
> + error = xfs_rmap_query_all(cur, xfs_repair_alloc_extent_fn, &ra);
> + if (error)
> + goto out;
> + xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
> + cur = NULL;
> +
> + /* Insert a record for space between the last rmap and EOAG. */
> + agf = XFS_BUF_TO_AGF(sc->sa.agf_bp);
> + agend = be32_to_cpu(agf->agf_length);
> + if (ra.next_bno < agend) {
> + rae = kmem_alloc(sizeof(struct xfs_repair_alloc_extent),
> + KM_MAYFAIL);
> + if (!rae) {
> + error = -ENOMEM;
> + goto out;
> + }
> + INIT_LIST_HEAD(&rae->list);
> + rae->bno = ra.next_bno;
> + rae->len = agend - ra.next_bno;
> + list_add_tail(&rae->list, &ra.extlist);
> + ra.nr_records++;
> + }
> +
> + /* Collect all the AGFL blocks. */
> + error = xfs_agfl_walk(sc->mp, XFS_BUF_TO_AGF(sc->sa.agf_bp),
> + sc->sa.agfl_bp, xfs_repair_collect_agfl_block, &ra);
> + if (error)
> + goto out;
> +
> + /* Do we actually have enough space to do this? */
> + nr_blocks = 2 * xfs_allocbt_calc_size(mp, ra.nr_records);
> + if (!xfs_repair_ag_has_space(pag, nr_blocks, XFS_AG_RESV_NONE)) {
> + error = -ENOSPC;
> + goto out;
> + }
> +
> + /* Invalidate all the bnobt/cntbt blocks in btlist. */
> + error = xfs_repair_subtract_extents(sc, &ra.btlist, &ra.nobtlist);
> + if (error)
> + goto out;
> + xfs_repair_cancel_btree_extents(sc, &ra.nobtlist);
> + error = xfs_repair_invalidate_blocks(sc, &ra.btlist);
> + if (error)
> + goto out;

So this could be factored in xfs_repair_allocbt_get_free_extents().

> +
> + /* Allocate new bnobt root. */
> + bnofsb = xfs_repair_allocbt_alloc_from_longest(&ra, &longest);
> + if (bnofsb == NULLFSBLOCK) {
> + error = -ENOSPC;
> + goto out;
> + }
> +
> + /* Allocate new cntbt root. */
> + cntfsb = xfs_repair_allocbt_alloc_from_longest(&ra, &longest);
> + if (cntfsb == NULLFSBLOCK) {
> + error = -ENOSPC;
> + goto out;
> + }
> +
> + agf = XFS_BUF_TO_AGF(sc->sa.agf_bp);
> + /* Initialize new bnobt root. */
> + error = xfs_repair_init_btblock(sc, bnofsb, &bp, XFS_BTNUM_BNO,
> + &xfs_allocbt_buf_ops);
> + if (error)
> + goto out;
> + agf->agf_roots[XFS_BTNUM_BNOi] =
> + cpu_to_be32(XFS_FSB_TO_AGBNO(mp, bnofsb));
> + agf->agf_levels[XFS_BTNUM_BNOi] = cpu_to_be32(1);
> +
> + /* Initialize new cntbt root. */
> + error = xfs_repair_init_btblock(sc, cntfsb, &bp, XFS_BTNUM_CNT,
> + &xfs_allocbt_buf_ops);
> + if (error)
> + goto out;
> + agf->agf_roots[XFS_BTNUM_CNTi] =
> + cpu_to_be32(XFS_FSB_TO_AGBNO(mp, cntfsb));
> + agf->agf_levels[XFS_BTNUM_CNTi] = cpu_to_be32(1);

xfs_repair_allocbt_new_btree_roots()

> +
> + /*
> + * Since we're abandoning the old bnobt/cntbt, we have to
> + * decrease fdblocks by the # of blocks in those trees.
> + * btreeblks counts the non-root blocks of the free space
> + * and rmap btrees. Do this before resetting the AGF counters.
> + */
> + oldf = pag->pagf_btreeblks + 2;
> + oldf -= (be32_to_cpu(agf->agf_rmap_blocks) - 1);
> + error = xfs_mod_fdblocks(mp, -(int64_t)oldf, false);
> + if (error)
> + goto out;
> +
> + /* Reset the perag info. */
> + pag->pagf_btreeblks = be32_to_cpu(agf->agf_rmap_blocks) - 1;
> + pag->pagf_freeblks = 0;
> + pag->pagf_longest = 0;
> + pag->pagf_levels[XFS_BTNUM_BNOi] =
> + be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]);
> + pag->pagf_levels[XFS_BTNUM_CNTi] =
> + be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]);
> +
> + /* Now reset the AGF counters. */
> + agf->agf_btreeblks = cpu_to_be32(pag->pagf_btreeblks);
> + agf->agf_freeblks = cpu_to_be32(pag->pagf_freeblks);
> + agf->agf_longest = cpu_to_be32(pag->pagf_longest);
> + xfs_alloc_log_agf(sc->tp, sc->sa.agf_bp,
> + XFS_AGF_ROOTS | XFS_AGF_LEVELS | XFS_AGF_BTREEBLKS |
> + XFS_AGF_LONGEST | XFS_AGF_FREEBLKS);
> + error = xfs_repair_roll_ag_trans(sc);
> + if (error)
> + goto out;

xfs_repair_allocbt_reset_counters()?

> + /*
> + * Insert the longest free extent in case it's necessary to
> + * refresh the AGFL with multiple blocks.
> + */
> + xfs_rmap_skip_owner_update(&oinfo);
> + if (longest && longest->len == 0) {
> + error = xfs_repair_allocbt_free_extent(sc,
> + XFS_AGB_TO_FSB(sc->mp, sc->sa.agno,
> + longest->bno),
> + longest->len, &oinfo);
> + if (error)
> + goto out;
> + list_del(&longest->list);
> + kmem_free(longest);
> + }
> +
> + /* Insert records into the new btrees. */
> + list_sort(NULL, &ra.extlist, xfs_repair_allocbt_extent_cmp);
> + list_for_each_entry_safe(rae, n, &ra.extlist, list) {
> + error = xfs_repair_allocbt_free_extent(sc,
> + XFS_AGB_TO_FSB(sc->mp, sc->sa.agno, rae->bno),
> + rae->len, &oinfo);
> + if (error)
> + goto out;
> + list_del(&rae->list);
> + kmem_free(rae);
> + }
> +
> + /* Add rmap records for the btree roots */
> + xfs_rmap_ag_owner(&oinfo, XFS_RMAP_OWN_AG);
> + error = xfs_rmap_alloc(sc->tp, sc->sa.agf_bp, sc->sa.agno,
> + XFS_FSB_TO_AGBNO(mp, bnofsb), 1, &oinfo);
> + if (error)
> + goto out;
> + error = xfs_rmap_alloc(sc->tp, sc->sa.agf_bp, sc->sa.agno,
> + XFS_FSB_TO_AGBNO(mp, cntfsb), 1, &oinfo);
> + if (error)
> + goto out;

xfs_repair_allocbt_rebuild_tree()

> +
> + /* Free all the OWN_AG blocks that are not in the rmapbt/agfl. */
> + return xfs_repair_reap_btree_extents(sc, &ra.btlist, &oinfo,
> + XFS_AG_RESV_NONE);
> +out:
> + xfs_repair_cancel_btree_extents(sc, &ra.btlist);
> + xfs_repair_cancel_btree_extents(sc, &ra.nobtlist);
> + if (cur)
> + xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
> + list_for_each_entry_safe(rae, n, &ra.extlist, list) {
> + list_del(&rae->list);
> + kmem_free(rae);
> + }
> + return error;
> +}

-Dave.
--
Dave Chinner
david@fromorbit.com