xfs-4.18: online repair support

From: Darrick J. Wong <[email protected]>

For repairs, we need to reserve at least as many blocks as we think we're going to need to rebuild the data structure, and we're going to need some helpers to roll transactions while maintaining locks on the AG headers so that other threads cannot wander into the middle of a repair.

Signed-off-by Darrick J. Wong <[email protected]>

---
 fs/xfs/scrub/bmap.c   |    2 -
 fs/xfs/scrub/common.c |   21 ++++++-
 fs/xfs/scrub/common.h |    2 -
 fs/xfs/scrub/inode.c  |    4 +
 fs/xfs/scrub/repair.c |  152 +++++++++++++++++++++++++++++++++++++++++++++++++
 fs/xfs/scrub/repair.h |   12 ++++
 6 files changed, 186 insertions(+), 7 deletions(-)

fs/xfs/scrub/repair.c +21 -0

+/*
+ * Figure out how many blocks to reserve for an AG repair.  We calculate the
+ * worst case estimate for the number of blocks we'd need to rebuild one of
+ * any type of per-AG btree.
+ */
+xfs_extlen_t
+xfs_repair_calc_ag_resblks(
+	struct xfs_scrub_context	*sc)
+{
+	struct xfs_mount		*mp = sc->mp;
+	struct xfs_scrub_metadata	*sm = sc->sm;
+	struct xfs_perag		*pag;
+	struct xfs_buf			*bp;
+	xfs_agino_t			icount = 0;
+	xfs_extlen_t			aglen = 0;
+	xfs_extlen_t			usedlen;
+	xfs_extlen_t			freelen;
+	xfs_extlen_t			bnobt_sz;
+	xfs_extlen_t			inobt_sz;
+	xfs_extlen_t			rmapbt_sz;
+	xfs_extlen_t			refcbt_sz;

fs/xfs/scrub/repair.c +21 -0

+
+	/*
+	 * Otherwise try to get the actual counters from disk; if not, make
+	 * some worst case assumptions.
+	 */
+	if (icount == 0) {
+		error = xfs_ialloc_read_agi(mp, NULL, sm->sm_agno, &bp);
+		if (error) {
+			icount = mp->m_sb.sb_agblocks / mp->m_sb.sb_inopblock;
+		} else {
+			pag = xfs_perag_get(mp, sm->sm_agno);
+			icount = pag->pagi_count;
+			xfs_perag_put(pag);
+			xfs_buf_relse(bp);
+		}
+	}
+
+	/* Now grab the block counters from the AGF. */
+	error = xfs_alloc_read_agf(mp, NULL, sm->sm_agno, 0, &bp);
+	if (error) {
+		aglen = mp->m_sb.sb_agblocks;

fs/xfs/scrub/repair.c +16 -0

+	trace_xfs_repair_calc_ag_resblks(mp, sm->sm_agno, icount, aglen,
+			freelen, usedlen);
+
+	/*
+	 * Figure out how many blocks we'd need worst case to rebuild
+	 * each type of btree.  Note that we can only rebuild the
+	 * bnobt/cntbt or inobt/finobt as pairs.
+	 */
+	bnobt_sz = 2 * xfs_allocbt_calc_size(mp, freelen);
+	if (xfs_sb_version_hassparseinodes(&mp->m_sb))
+		inobt_sz = xfs_iallocbt_calc_size(mp, icount /
+				XFS_INODES_PER_HOLEMASK_BIT);
+	else
+		inobt_sz = xfs_iallocbt_calc_size(mp, icount /
+				XFS_INODES_PER_CHUNK);
+	if (xfs_sb_version_hasfinobt(&mp->m_sb))

Quoted 8 lines · Darrick J. Wong

From: Darrick J. Wong <[email protected]>

For repairs, we need to reserve at least as many blocks as we think we're going to need to rebuild the data structure, and we're going to need some helpers to roll transactions while maintaining locks on the AG headers so that other threads cannot wander into the middle of a repair.

Signed-off-by Darrick J. Wong <[email protected]>

Quoted 8 lines

---
 fs/xfs/scrub/bmap.c   |    2 -
 fs/xfs/scrub/common.c |   21 ++++++-
 fs/xfs/scrub/common.h |    2 -
 fs/xfs/scrub/inode.c  |    4 +
 fs/xfs/scrub/repair.c |  152 +++++++++++++++++++++++++++++++++++++++++++++++++
 fs/xfs/scrub/repair.h |   12 ++++
 6 files changed, 186 insertions(+), 7 deletions(-)

mostly looks good.

[...]

Quoted 21 lines

fs/xfs/scrub/repair.c +21 -0

+/*
+ * Figure out how many blocks to reserve for an AG repair.  We calculate the
+ * worst case estimate for the number of blocks we'd need to rebuild one of
+ * any type of per-AG btree.
+ */
+xfs_extlen_t
+xfs_repair_calc_ag_resblks(
+	struct xfs_scrub_context	*sc)
+{
+	struct xfs_mount		*mp = sc->mp;
+	struct xfs_scrub_metadata	*sm = sc->sm;
+	struct xfs_perag		*pag;
+	struct xfs_buf			*bp;
+	xfs_agino_t			icount = 0;
+	xfs_extlen_t			aglen = 0;
+	xfs_extlen_t			usedlen;
+	xfs_extlen_t			freelen;
+	xfs_extlen_t			bnobt_sz;
+	xfs_extlen_t			inobt_sz;
+	xfs_extlen_t			rmapbt_sz;
+	xfs_extlen_t			refcbt_sz;

fs/xfs/scrub/repair.c xfs_repair_probe( · line 218

Quoted 10 lines

fs/xfs/scrub/repair.c +10 -0

+	int				error;
+
+	if (!(sm->sm_flags & XFS_SCRUB_IFLAG_REPAIR))
+		return 0;
+
+	/* Use in-core counters if possible. */
+	pag = xfs_perag_get(mp, sm->sm_agno);
+	if (pag->pagi_init)
+		icount = pag->pagi_count;
+	xfs_perag_put(pag);

Don't drop the pag here, do it ....

Quoted 25 lines

fs/xfs/scrub/repair.c +25 -0

+
+	/*
+	 * Otherwise try to get the actual counters from disk; if not, make
+	 * some worst case assumptions.
+	 */
+	if (icount == 0) {
+		error = xfs_ialloc_read_agi(mp, NULL, sm->sm_agno, &bp);
+		if (error) {
+			icount = mp->m_sb.sb_agblocks / mp->m_sb.sb_inopblock;
+		} else {
+			pag = xfs_perag_get(mp, sm->sm_agno);
+			icount = pag->pagi_count;
+			xfs_perag_put(pag);
+			xfs_buf_relse(bp);
+		}
+	}
+
+	/* Now grab the block counters from the AGF. */
+	error = xfs_alloc_read_agf(mp, NULL, sm->sm_agno, 0, &bp);
+	if (error) {
+		aglen = mp->m_sb.sb_agblocks;
+		freelen = aglen;
+		usedlen = aglen;
+	} else {
+		pag = xfs_perag_get(mp, sm->sm_agno);

fs/xfs/scrub/repair.c xfs_repair_probe( · line 249

Quoted 6 lines

fs/xfs/scrub/repair.c +6 -0

+		aglen = be32_to_cpu(XFS_BUF_TO_AGF(bp)->agf_length);
+		freelen = pag->pagf_freeblks;
+		usedlen = aglen - freelen;
+		xfs_perag_put(pag);
+		xfs_buf_relse(bp);
+	}

.... here, so we don't have to do repeated lookups.

Quoted 22 lines

fs/xfs/scrub/repair.c +22 -0

+	trace_xfs_repair_calc_ag_resblks(mp, sm->sm_agno, icount, aglen,
+			freelen, usedlen);
+
+	/*
+	 * Figure out how many blocks we'd need worst case to rebuild
+	 * each type of btree.  Note that we can only rebuild the
+	 * bnobt/cntbt or inobt/finobt as pairs.
+	 */
+	bnobt_sz = 2 * xfs_allocbt_calc_size(mp, freelen);
+	if (xfs_sb_version_hassparseinodes(&mp->m_sb))
+		inobt_sz = xfs_iallocbt_calc_size(mp, icount /
+				XFS_INODES_PER_HOLEMASK_BIT);
+	else
+		inobt_sz = xfs_iallocbt_calc_size(mp, icount /
+				XFS_INODES_PER_CHUNK);
+	if (xfs_sb_version_hasfinobt(&mp->m_sb))
+		inobt_sz *= 2;
+	if (xfs_sb_version_hasreflink(&mp->m_sb)) {
+		rmapbt_sz = xfs_rmapbt_calc_size(mp, aglen);
+		refcbt_sz = xfs_refcountbt_calc_size(mp, usedlen);
+	} else {
+		rmapbt_sz = xfs_rmapbt_calc_size(mp, usedlen);

fs/xfs/scrub/repair.c xfs_repair_probe( · line 276

Quoted 4 lines

fs/xfs/scrub/repair.c +4 -0

+		refcbt_sz = 0;
+	}
+	if (!xfs_sb_version_hasrmapbt(&mp->m_sb))
+		rmapbt_sz = 0;

This looks kinda whacky. reflink and rmapbt are different features, maybe a comment to explain why the rmapbt size calc is done all back to front?

Otherwise looks ok.

Reviewed-by Dave Chinner <[email protected]>

Signature · 6 lines

Dave Chinner
[email protected]
--
To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Quoted 42 lines · Dave Chinner

Quoted 8 lines · Darrick J. Wong

From: Darrick J. Wong <[email protected]>

For repairs, we need to reserve at least as many blocks as we think we're going to need to rebuild the data structure, and we're going to need some helpers to roll transactions while maintaining locks on the AG headers so that other threads cannot wander into the middle of a repair.

Signed-off-by Darrick J. Wong <[email protected]>

Quoted 8 lines

---
 fs/xfs/scrub/bmap.c   |    2 -
 fs/xfs/scrub/common.c |   21 ++++++-
 fs/xfs/scrub/common.h |    2 -
 fs/xfs/scrub/inode.c  |    4 +
 fs/xfs/scrub/repair.c |  152 +++++++++++++++++++++++++++++++++++++++++++++++++
 fs/xfs/scrub/repair.h |   12 ++++
 6 files changed, 186 insertions(+), 7 deletions(-)

mostly looks good.

[...]

Quoted 21 lines

fs/xfs/scrub/repair.c +21 -0

+			freelen, usedlen);
+
+	/*
+	 * Figure out how many blocks we'd need worst case to rebuild
+	 * each type of btree.  Note that we can only rebuild the
+	 * bnobt/cntbt or inobt/finobt as pairs.
+	 */
+	bnobt_sz = 2 * xfs_allocbt_calc_size(mp, freelen);
+	if (xfs_sb_version_hassparseinodes(&mp->m_sb))
+		inobt_sz = xfs_iallocbt_calc_size(mp, icount /
+				XFS_INODES_PER_HOLEMASK_BIT);
+	else
+		inobt_sz = xfs_iallocbt_calc_size(mp, icount /
+				XFS_INODES_PER_CHUNK);
+	if (xfs_sb_version_hasfinobt(&mp->m_sb))
+		inobt_sz *= 2;
+	if (xfs_sb_version_hasreflink(&mp->m_sb)) {
+		rmapbt_sz = xfs_rmapbt_calc_size(mp, aglen);
+		refcbt_sz = xfs_refcountbt_calc_size(mp, usedlen);
+	} else {
+		rmapbt_sz = xfs_rmapbt_calc_size(mp, usedlen);

Quoted 8 lines

fs/xfs/scrub/repair.c xfs_repair_probe( · line 276

Quoted 4 lines

fs/xfs/scrub/repair.c +4 -0

+		refcbt_sz = 0;
+	}
+	if (!xfs_sb_version_hasrmapbt(&mp->m_sb))
+		rmapbt_sz = 0;

This looks kinda whacky. reflink and rmapbt are different features, maybe a comment to explain why the rmapbt size calc is done all back to front?

Yeah. Replace that whole section with:

	if (xfs_sb_version_hasreflink(&mp->m_sb))
		refcbt_sz = xfs_refcountbt_calc_size(mp, usedlen);
	else
		refcbt_sz = 0;
	if (xfs_sb_version_hasrmapbt(&mp->m_sb)) {
		/*
		 * Guess how many blocks we need to rebuild the rmapbt.
		 * For non-reflink filesystems we can't have more
		 * records than used blocks.  However, with reflink it's
		 * possible to have more than one rmap record per AG
		 * block.  We don't know how many rmaps there could be
		 * in the AG, so we start off with what we hope is an
		 * generous over-estimation.
		 */

		if (xfs_sb_version_hasreflink(&mp->m_sb))
			rmapbt_sz = xfs_rmapbt_calc_size(mp,
					(unsigned long long)aglen * 2);
		else
			rmapbt_sz = xfs_rmapbt_calc_size(mp, usedlen);
	} else {
		rmapbt_sz = 0;
	}

From: Darrick J. Wong <[email protected]>

For repairs, we need to reserve at least as many blocks as we think we're going to need to rebuild the data structure, and we're going to need some helpers to roll transactions while maintaining locks on the AG headers so that other threads cannot wander into the middle of a repair.

Signed-off-by Darrick J. Wong <[email protected]>

---
  fs/xfs/scrub/bmap.c   |    2 -
  fs/xfs/scrub/common.c |   21 ++++++-
  fs/xfs/scrub/common.h |    2 -
  fs/xfs/scrub/inode.c  |    4 +
  fs/xfs/scrub/repair.c |  152 +++++++++++++++++++++++++++++++++++++++++++++++++
  fs/xfs/scrub/repair.h |   12 ++++
  6 files changed, 186 insertions(+), 7 deletions(-)

fs/xfs/scrub/bmap.c +1 -1

index 42a115e83739..eeadb33a701c 100644
@@ -74,7 +74,7 @@ xfs_scrub_setup_inode_bmap(
  	}
 
  	/* Got the inode, lock it and we're ready to go. */
-	error = xfs_scrub_trans_alloc(sc);
+	error = xfs_scrub_trans_alloc(sc, 0);
  	if (error)
  		goto out;
  	sc->ilock_flags |= XFS_ILOCK_EXCL;

fs/xfs/scrub/common.c +18 -3

index 518bff2be0c9..f1826b4b7572 100644
@@ -51,6 +51,7 @@
  #include "scrub/common.h"
  #include "scrub/trace.h"
  #include "scrub/btree.h"
+#include "scrub/repair.h"
 
  /* Common code for the metadata scrubbers. */
 

@@ -573,11 +574,22 @@ xfs_scrub_ag_init(
  /*
   * Grab an empty transaction so that we can re-grab locked buffers if
   * one of our btrees turns out to be cyclic.
+ *
+ * If we're going to repair something, we need to ask for the largest possible
+ * log reservation so that we can handle the worst case scenario for metadata
+ * updates while rebuilding a metadata item.  We also need to reserve as many
+ * blocks in the head transaction as we think we're going to need to rebuild
+ * the metadata object.
   */
  int
  xfs_scrub_trans_alloc(
-	struct xfs_scrub_context	*sc)
+	struct xfs_scrub_context	*sc,
+	uint				resblks)
  {
+	if (sc->sm->sm_flags & XFS_SCRUB_IFLAG_REPAIR)
+		return xfs_trans_alloc(sc->mp, &M_RES(sc->mp)->tr_itruncate,
+				resblks, 0, 0, &sc->tp);
+
  	return xfs_trans_alloc_empty(sc->mp, &sc->tp);
  }
 

@@ -587,7 +599,10 @@ xfs_scrub_setup_fs(
  	struct xfs_scrub_context	*sc,
  	struct xfs_inode		*ip)
  {
-	return xfs_scrub_trans_alloc(sc);
+	uint				resblks;
+
+	resblks = xfs_repair_calc_ag_resblks(sc);
+	return xfs_scrub_trans_alloc(sc, resblks);
  }
 
  /* Set us up with AG headers and btree cursors. */

@@ -717,7 +732,7 @@ xfs_scrub_setup_inode_contents(
  	/* Got the inode, lock it and we're ready to go. */
  	sc->ilock_flags = XFS_IOLOCK_EXCL | XFS_MMAPLOCK_EXCL;
  	xfs_ilock(sc->ip, sc->ilock_flags);
-	error = xfs_scrub_trans_alloc(sc);
+	error = xfs_scrub_trans_alloc(sc, resblks);
  	if (error)
  		goto out;
  	sc->ilock_flags |= XFS_ILOCK_EXCL;

fs/xfs/scrub/common.h +1 -1

index a660087b606e..6012049a8617 100644
@@ -38,7 +38,7 @@ xfs_scrub_should_terminate(
  	return false;
  }
 
-int xfs_scrub_trans_alloc(struct xfs_scrub_context *sc);
+int xfs_scrub_trans_alloc(struct xfs_scrub_context *sc, uint resblks);
  bool xfs_scrub_process_error(struct xfs_scrub_context *sc, xfs_agnumber_t agno,
  		xfs_agblock_t bno, int *error);
  bool xfs_scrub_fblock_process_error(struct xfs_scrub_context *sc, int whichfork,

fs/xfs/scrub/inode.c +2 -2

index 550c0cf70a92..0c696f7018de 100644
@@ -67,7 +67,7 @@ xfs_scrub_setup_inode(
  		break;
  	case -EFSCORRUPTED:
  	case -EFSBADCRC:
-		return xfs_scrub_trans_alloc(sc);
+		return xfs_scrub_trans_alloc(sc, 0);
  	default:
  		return error;
  	}

@@ -75,7 +75,7 @@ xfs_scrub_setup_inode(
  	/* Got the inode, lock it and we're ready to go. */
  	sc->ilock_flags = XFS_IOLOCK_EXCL | XFS_MMAPLOCK_EXCL;
  	xfs_ilock(sc->ip, sc->ilock_flags);
-	error = xfs_scrub_trans_alloc(sc);
+	error = xfs_scrub_trans_alloc(sc, 0);
  	if (error)
  		goto out;
  	sc->ilock_flags |= XFS_ILOCK_EXCL;

fs/xfs/scrub/repair.c +152 -0

index be30825c47c6..486e6e319b1f 100644
@@ -128,3 +128,155 @@ xfs_repair_probe(
 
  	return 0;
  }
+
+/*
+ * Roll a transaction, keeping the AG headers locked and reinitializing
+ * the btree cursors.
+ */
+int
+xfs_repair_roll_ag_trans(
+	struct xfs_scrub_context	*sc)
+{
+	int				error;
+
+	/* Keep the AG header buffers locked so we can keep going. */
+	xfs_trans_bhold(sc->tp, sc->sa.agi_bp);
+	xfs_trans_bhold(sc->tp, sc->sa.agf_bp);
+	xfs_trans_bhold(sc->tp, sc->sa.agfl_bp);
+
+	/* Roll the transaction. */
+	error = xfs_trans_roll(&sc->tp);
+	if (error)
+		goto out_release;
+
+	/* Join AG headers to the new transaction. */
+	xfs_trans_bjoin(sc->tp, sc->sa.agi_bp);
+	xfs_trans_bjoin(sc->tp, sc->sa.agf_bp);
+	xfs_trans_bjoin(sc->tp, sc->sa.agfl_bp);
+
+	return 0;
+
+out_release:
+	/*
+	 * Rolling failed, so release the hold on the buffers.  The
+	 * buffers will be released during teardown on our way out
+	 * of the kernel.
+	 */
+	xfs_trans_bhold_release(sc->tp, sc->sa.agi_bp);
+	xfs_trans_bhold_release(sc->tp, sc->sa.agf_bp);
+	xfs_trans_bhold_release(sc->tp, sc->sa.agfl_bp);
+
+	return error;
+}
+
+/*
+ * Does the given AG have enough space to rebuild a btree?  Neither AG
+ * reservation can be critical, and we must have enough space (factoring
+ * in AG reservations) to construct a whole btree.
+ */
+bool
+xfs_repair_ag_has_space(
+	struct xfs_perag		*pag,
+	xfs_extlen_t			nr_blocks,
+	enum xfs_ag_resv_type		type)
+{
+	return  !xfs_ag_resv_critical(pag, XFS_AG_RESV_RMAPBT) &&
+		!xfs_ag_resv_critical(pag, XFS_AG_RESV_METADATA) &&
+		pag->pagf_freeblks > xfs_ag_resv_needed(pag, type) + nr_blocks;
+}
+
+/*
+ * Figure out how many blocks to reserve for an AG repair.  We calculate the
+ * worst case estimate for the number of blocks we'd need to rebuild one of
+ * any type of per-AG btree.
+ */
+xfs_extlen_t
+xfs_repair_calc_ag_resblks(
+	struct xfs_scrub_context	*sc)
+{
+	struct xfs_mount		*mp = sc->mp;
+	struct xfs_scrub_metadata	*sm = sc->sm;
+	struct xfs_perag		*pag;
+	struct xfs_buf			*bp;
+	xfs_agino_t			icount = 0;
+	xfs_extlen_t			aglen = 0;
+	xfs_extlen_t			usedlen;
+	xfs_extlen_t			freelen;
+	xfs_extlen_t			bnobt_sz;
+	xfs_extlen_t			inobt_sz;
+	xfs_extlen_t			rmapbt_sz;
+	xfs_extlen_t			refcbt_sz;
+	int				error;
+
+	if (!(sm->sm_flags & XFS_SCRUB_IFLAG_REPAIR))
+		return 0;
+
+	/* Use in-core counters if possible. */
+	pag = xfs_perag_get(mp, sm->sm_agno);
+	if (pag->pagi_init)
+		icount = pag->pagi_count;
+	xfs_perag_put(pag);
+
+	/*
+	 * Otherwise try to get the actual counters from disk; if not, make
+	 * some worst case assumptions.
+	 */
+	if (icount == 0) {
+		error = xfs_ialloc_read_agi(mp, NULL, sm->sm_agno, &bp);
+		if (error) {
+			icount = mp->m_sb.sb_agblocks / mp->m_sb.sb_inopblock;
+		} else {
+			pag = xfs_perag_get(mp, sm->sm_agno);
+			icount = pag->pagi_count;
+			xfs_perag_put(pag);
+			xfs_buf_relse(bp);
+		}
+	}
+
+	/* Now grab the block counters from the AGF. */
+	error = xfs_alloc_read_agf(mp, NULL, sm->sm_agno, 0, &bp);
+	if (error) {
+		aglen = mp->m_sb.sb_agblocks;
+		freelen = aglen;
+		usedlen = aglen;
+	} else {
+		pag = xfs_perag_get(mp, sm->sm_agno);
+		aglen = be32_to_cpu(XFS_BUF_TO_AGF(bp)->agf_length);
+		freelen = pag->pagf_freeblks;
+		usedlen = aglen - freelen;
+		xfs_perag_put(pag);
+		xfs_buf_relse(bp);
+	}
+
+	trace_xfs_repair_calc_ag_resblks(mp, sm->sm_agno, icount, aglen,
+			freelen, usedlen);
+
+	/*
+	 * Figure out how many blocks we'd need worst case to rebuild
+	 * each type of btree.  Note that we can only rebuild the
+	 * bnobt/cntbt or inobt/finobt as pairs.
+	 */
+	bnobt_sz = 2 * xfs_allocbt_calc_size(mp, freelen);
+	if (xfs_sb_version_hassparseinodes(&mp->m_sb))
+		inobt_sz = xfs_iallocbt_calc_size(mp, icount /
+				XFS_INODES_PER_HOLEMASK_BIT);
+	else
+		inobt_sz = xfs_iallocbt_calc_size(mp, icount /
+				XFS_INODES_PER_CHUNK);
+	if (xfs_sb_version_hasfinobt(&mp->m_sb))
+		inobt_sz *= 2;
+	if (xfs_sb_version_hasreflink(&mp->m_sb)) {
+		rmapbt_sz = xfs_rmapbt_calc_size(mp, aglen);
+		refcbt_sz = xfs_refcountbt_calc_size(mp, usedlen);
+	} else {
+		rmapbt_sz = xfs_rmapbt_calc_size(mp, usedlen);
+		refcbt_sz = 0;
+	}
+	if (!xfs_sb_version_hasrmapbt(&mp->m_sb))
+		rmapbt_sz = 0;
+
+	trace_xfs_repair_calc_ag_resblks_btsize(mp, sm->sm_agno, bnobt_sz,
+			inobt_sz, rmapbt_sz, refcbt_sz);
+
+	return max(max(bnobt_sz, inobt_sz), max(rmapbt_sz, refcbt_sz));
+}

fs/xfs/scrub/repair.h +12 -1

index 83170dd3388c..8d181dce6171 100644
@@ -32,6 +32,10 @@ static inline int xfs_repair_notsupported(struct xfs_scrub_context *sc)
  int xfs_repair_attempt(struct xfs_inode *ip, struct xfs_scrub_context *sc,
  		bool *fixed);
  void xfs_repair_failure(struct xfs_mount *mp);
+int xfs_repair_roll_ag_trans(struct xfs_scrub_context *sc);
+bool xfs_repair_ag_has_space(struct xfs_perag *pag, xfs_extlen_t nr_blocks,
+		enum xfs_ag_resv_type type);
+xfs_extlen_t xfs_repair_calc_ag_resblks(struct xfs_scrub_context *sc);
 
  /* Metadata repairers */
 

@@ -49,6 +53,14 @@ static inline int xfs_repair_attempt(
 
  static inline void xfs_repair_failure(struct xfs_mount *mp) {}
 
+static inline xfs_extlen_t
+xfs_repair_calc_ag_resblks(
+	struct xfs_scrub_context	*sc)
+{
+	ASSERT(!(sc->sm->sm_flags & XFS_SCRUB_IFLAG_REPAIR));
+	return 0;
+}
+
  #define xfs_repair_probe		xfs_repair_notsupported
 
  #endif /* CONFIG_XFS_ONLINE_REPAIR */
 
--

To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
the body of a message to [email protected]
More majordomo info at https://urldefense.proofpoint.com/v2/url?u=http-3A__vger.kernel.org_majordomo-2Dinfo.html&d=DwICaQ&c=RoP1YumCXCgaWHvlZYR8PZh8Bv7qIrMUB65eapI_JnE&r=LHZQ8fHvy6wDKXGTWcm97burZH5sQKHRDMaY1UthQxc&m=TQHk1pYShWjO6ANE7iY6Bn29jiBqkeNo5IMsc5kla3U&s=vF097w5pOXeZmfX1JYpzuN-nJX8gG5B7EUcQQkONWKk&e=

From: Darrick J. Wong <[email protected]>

Add a pair of helper functions to allocate and initialize fresh btree roots. The repair functions will use these as part of recreating corrupted metadata.

Signed-off-by Darrick J. Wong <[email protected]>

---
 fs/xfs/scrub/repair.c |   81 +++++++++++++++++++++++++++++++++++++++++++++++++
 fs/xfs/scrub/repair.h |    6 ++++
 2 files changed, 87 insertions(+)

fs/xfs/scrub/repair.c +12 -0

+/* Initialize a new AG btree root block with zero entries. */
+int
+xfs_repair_init_btblock(
+	struct xfs_scrub_context	*sc,
+	xfs_fsblock_t			fsb,
+	struct xfs_buf			**bpp,
+	xfs_btnum_t			btnum,
+	const struct xfs_buf_ops	*ops)
+{
+	struct xfs_trans		*tp = sc->tp;
+	struct xfs_mount		*mp = sc->mp;
+	struct xfs_buf			*bp;

Quoted 11 lines · Darrick J. Wong

From: Darrick J. Wong <[email protected]>

Add a pair of helper functions to allocate and initialize fresh btree roots. The repair functions will use these as part of recreating corrupted metadata.

Signed-off-by Darrick J. Wong <[email protected]>

---
 fs/xfs/scrub/repair.c |   81 +++++++++++++++++++++++++++++++++++++++++++++++++
 fs/xfs/scrub/repair.h |    6 ++++
 2 files changed, 87 insertions(+)

Looks good, but....

Quoted 17 lines

fs/xfs/scrub/repair.c +17 -0

+/* Initialize a new AG btree root block with zero entries. */
+int
+xfs_repair_init_btblock(
+	struct xfs_scrub_context	*sc,
+	xfs_fsblock_t			fsb,
+	struct xfs_buf			**bpp,
+	xfs_btnum_t			btnum,
+	const struct xfs_buf_ops	*ops)
+{
+	struct xfs_trans		*tp = sc->tp;
+	struct xfs_mount		*mp = sc->mp;
+	struct xfs_buf			*bp;
+
+	trace_xfs_repair_init_btblock(mp, XFS_FSB_TO_AGNO(mp, fsb),
+			XFS_FSB_TO_AGBNO(mp, fsb), btnum);
+
+	ASSERT(XFS_FSB_TO_AGNO(mp, fsb) == sc->sa.agno);

fs/xfs/scrub/repair.c xfs_repair_calc_ag_resblks( · line 356

Quoted 5 lines

fs/xfs/scrub/repair.c +5 -0

+	bp = xfs_trans_get_buf(tp, mp->m_ddev_targp, XFS_FSB_TO_DADDR(mp, fsb),
+			XFS_FSB_TO_BB(mp, 1), 0);
+	xfs_buf_zero(bp, 0, BBTOB(bp->b_length));
+	xfs_btree_init_block(mp, bp, btnum, 0, 0, sc->sa.agno,
+			XFS_BTREE_CRC_BLOCKS);

This flag does nothing in xfs_btree_init_block(). Any reason for setting it?

With that fixed, though,

Reviewed-by Dave Chinner <[email protected]>

fs/xfs/scrub/repair.c xfs_repair_calc_ag_resblks( · line 363

Quoted 7 lines

fs/xfs/scrub/repair.c +7 -0

+	xfs_trans_buf_set_type(tp, bp, XFS_BLFT_BTREE_BUF);
+	xfs_trans_log_buf(tp, bp, 0, bp->b_length);
+	bp->b_ops = ops;
+	*bpp = bp;
+
+	return 0;
+}

For followup patches, I think there's some overlap with the new libxfs/xfs_ag.c functions for initialising new btree root blocks for growfs? e.g. Make the struct xfs_aghdr_grow_data aghdr_data[] array a static global, and then we can do something like:

	bp = xfs_ag_init_btroot(mp, tp, agno, agbno, btnum);
	xfs_trans_log_buf(tp, bp, 0, bp->b_length);

and all the details of reading the btree block and setting it up go away from this code....

-Dave.

Signature · 6 lines

Dave Chinner
[email protected]
--
To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

From: Darrick J. Wong <[email protected]>

Add a pair of helper functions to allocate and initialize fresh btree roots. The repair functions will use these as part of recreating corrupted metadata.

Signed-off-by Darrick J. Wong <[email protected]>

---
  fs/xfs/scrub/repair.c |   81 +++++++++++++++++++++++++++++++++++++++++++++++++
  fs/xfs/scrub/repair.h |    6 ++++
  2 files changed, 87 insertions(+)

fs/xfs/scrub/repair.c +81 -0

index 486e6e319b1f..72f04a717150 100644
@@ -280,3 +280,84 @@ xfs_repair_calc_ag_resblks(
 
  	return max(max(bnobt_sz, inobt_sz), max(rmapbt_sz, refcbt_sz));
  }
+
+/* Allocate a block in an AG. */
+int
+xfs_repair_alloc_ag_block(
+	struct xfs_scrub_context	*sc,
+	struct xfs_owner_info		*oinfo,
+	xfs_fsblock_t			*fsbno,
+	enum xfs_ag_resv_type		resv)
+{
+	struct xfs_alloc_arg		args = {0};
+	xfs_agblock_t			bno;
+	int				error;
+
+	switch (resv) {
+	case XFS_AG_RESV_AGFL:
+	case XFS_AG_RESV_RMAPBT:
+		error = xfs_alloc_get_freelist(sc->tp, sc->sa.agf_bp, &bno, 1);
+		if (error)
+			return error;
+		if (bno == NULLAGBLOCK)
+			return -ENOSPC;
+		xfs_extent_busy_reuse(sc->mp, sc->sa.agno, bno,
+				1, false);
+		*fsbno = XFS_AGB_TO_FSB(sc->mp, sc->sa.agno, bno);
+		if (resv == XFS_AG_RESV_RMAPBT)
+			xfs_ag_resv_rmapbt_alloc(sc->mp, sc->sa.agno);
+		return 0;
+	default:
+		break;
+	}
+
+	args.tp = sc->tp;
+	args.mp = sc->mp;
+	args.oinfo = *oinfo;
+	args.fsbno = XFS_AGB_TO_FSB(args.mp, sc->sa.agno, 0);
+	args.minlen = 1;
+	args.maxlen = 1;
+	args.prod = 1;
+	args.type = XFS_ALLOCTYPE_THIS_AG;
+	args.resv = resv;
+
+	error = xfs_alloc_vextent(&args);
+	if (error)
+		return error;
+	if (args.fsbno == NULLFSBLOCK)
+		return -ENOSPC;
+	ASSERT(args.len == 1);
+	*fsbno = args.fsbno;
+
+	return 0;
+}
+
+/* Initialize a new AG btree root block with zero entries. */
+int
+xfs_repair_init_btblock(
+	struct xfs_scrub_context	*sc,
+	xfs_fsblock_t			fsb,
+	struct xfs_buf			**bpp,
+	xfs_btnum_t			btnum,
+	const struct xfs_buf_ops	*ops)
+{
+	struct xfs_trans		*tp = sc->tp;
+	struct xfs_mount		*mp = sc->mp;
+	struct xfs_buf			*bp;
+
+	trace_xfs_repair_init_btblock(mp, XFS_FSB_TO_AGNO(mp, fsb),
+			XFS_FSB_TO_AGBNO(mp, fsb), btnum);
+
+	ASSERT(XFS_FSB_TO_AGNO(mp, fsb) == sc->sa.agno);
+	bp = xfs_trans_get_buf(tp, mp->m_ddev_targp, XFS_FSB_TO_DADDR(mp, fsb),
+			XFS_FSB_TO_BB(mp, 1), 0);
+	xfs_buf_zero(bp, 0, BBTOB(bp->b_length));
+	xfs_btree_init_block(mp, bp, btnum, 0, 0, sc->sa.agno,
+			XFS_BTREE_CRC_BLOCKS);
+	xfs_trans_buf_set_type(tp, bp, XFS_BLFT_BTREE_BUF);
+	xfs_trans_log_buf(tp, bp, 0, bp->b_length);
+	bp->b_ops = ops;
+	*bpp = bp;
+
+	return 0;
+}

fs/xfs/scrub/repair.h +6 -1

index 8d181dce6171..40990fa5f381 100644
@@ -36,6 +36,12 @@ int xfs_repair_roll_ag_trans(struct xfs_scrub_context *sc);
  bool xfs_repair_ag_has_space(struct xfs_perag *pag, xfs_extlen_t nr_blocks,
  		enum xfs_ag_resv_type type);
  xfs_extlen_t xfs_repair_calc_ag_resblks(struct xfs_scrub_context *sc);
+int xfs_repair_alloc_ag_block(struct xfs_scrub_context *sc,
+		struct xfs_owner_info *oinfo, xfs_fsblock_t *fsbno,
+		enum xfs_ag_resv_type resv);
+int xfs_repair_init_btblock(struct xfs_scrub_context *sc, xfs_fsblock_t fsb,
+		struct xfs_buf **bpp, xfs_btnum_t btnum,
+		const struct xfs_buf_ops *ops);
 
  /* Metadata repairers */
 
 
--

To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
the body of a message to [email protected]
More majordomo info at https://urldefense.proofpoint.com/v2/url?u=http-3A__vger.kernel.org_majordomo-2Dinfo.html&d=DwICaQ&c=RoP1YumCXCgaWHvlZYR8PZh8Bv7qIrMUB65eapI_JnE&r=LHZQ8fHvy6wDKXGTWcm97burZH5sQKHRDMaY1UthQxc&m=4QHdmNFIP7trSueA8XyY8TjPFBlv0bJ8UpmheOu6zJA&s=nvq_2KNHpSbVaDCf2vQai6hS8Pkmm8mnLSLrA8erFCk&e=

From: Darrick J. Wong <[email protected]>

Add some helpers to assemble a list of fs block extents. Generally, repair functions will iterate the rmapbt to make a list (1) of all extents owned by the nominal owner of the metadata structure; then they will iterate all other structures with the same rmap owner to make a list (2) of active blocks; and finally we have a subtraction function to subtract all the blocks in (2) from (1), with the result that (1) is now a list of blocks that were owned by the old btree and must be disposed.

Signed-off-by Darrick J. Wong <[email protected]>

---
 fs/xfs/scrub/repair.c |  207 +++++++++++++++++++++++++++++++++++++++++++++++++
 fs/xfs/scrub/repair.h |   31 +++++++
 2 files changed, 238 insertions(+)

fs/xfs/scrub/repair.c +8 -0

index 72f04a717150..8e8ecddd7537 100644
@@ -361,3 +361,210 @@ xfs_repair_init_btblock(
 
 	return 0;
 }
+
+/* Collect a dead btree extent for later disposal. */
+int
+xfs_repair_collect_btree_extent(
+	struct xfs_scrub_context	*sc,
+	struct xfs_repair_extent_list	*exlist,
+	xfs_fsblock_t			fsbno,
+	xfs_extlen_t			len)

fs/xfs/scrub/repair.c +7 -0

+/* Compare two btree extents. */
+static int
+xfs_repair_btree_extent_cmp(
+	void				*priv,
+	struct list_head		*a,
+	struct list_head		*b)
+{

fs/xfs/scrub/repair.c +34 -0

+ * mentioned in sublist from all the extents linked in exlist, which leaves
+ * exlist as the list of blocks that are not accounted for, which we assume
+ * are the dead blocks of the old metadata structure.  The blocks mentioned in
+ * exlist can be reaped.
+ */
+#define XFS_REPAIR_EXT_LEFT_CONTIG	(1 << 0)
+#define XFS_REPAIR_EXT_RIGHT_CONTIG	(1 << 1)
+int
+xfs_repair_subtract_extents(
+	struct xfs_scrub_context	*sc,
+	struct xfs_repair_extent_list	*exlist,
+	struct xfs_repair_extent_list	*sublist)
+{
+	struct list_head		*lp;
+	struct xfs_repair_extent	*ex;
+	struct xfs_repair_extent	*newex;
+	struct xfs_repair_extent	*subex;
+	xfs_fsblock_t			sub_fsb;
+	xfs_extlen_t			sub_len;
+	int				state;
+	int				error = 0;
+
+	if (list_empty(&exlist->list) || list_empty(&sublist->list))
+		return 0;
+	ASSERT(!list_empty(&sublist->list));
+
+	list_sort(NULL, &exlist->list, xfs_repair_btree_extent_cmp);
+	list_sort(NULL, &sublist->list, xfs_repair_btree_extent_cmp);
+
+	subex = list_first_entry(&sublist->list, struct xfs_repair_extent,
+			list);
+	lp = exlist->list.next;
+	while (lp != &exlist->list) {
+		ex = list_entry(lp, struct xfs_repair_extent, list);

fs/xfs/scrub/repair.c +10 -0

+		if (subex->fsbno >= ex->fsbno + ex->len) {
+			lp = lp->next;
+			continue;
+		}
+
+		/* trim subex to fit the extent we have */
+		sub_fsb = subex->fsbno;
+		sub_len = subex->len;
+		if (subex->fsbno < ex->fsbno) {
+			sub_len -= ex->fsbno - subex->fsbno;

fs/xfs/scrub/repair.c +18 -0

+			ex->fsbno += sub_len;
+			ex->len -= sub_len;
+			break;
+		case XFS_REPAIR_EXT_RIGHT_CONTIG:
+			/* Coincides with only the right. */
+			ex->len -= sub_len;
+			lp = lp->next;
+			break;
+		case XFS_REPAIR_EXT_LEFT_CONTIG | XFS_REPAIR_EXT_RIGHT_CONTIG:
+			/* Total overlap, just delete ex. */
+			lp = lp->next;
+			list_del(&ex->list);
+			kmem_free(ex);
+			break;
+		case 0:
+			/*
+			 * Deleting from the middle: add the new right extent
+			 * and then shrink the left extent.

Quoted 33 lines · Darrick J. Wong

From: Darrick J. Wong <[email protected]>

Add some helpers to assemble a list of fs block extents. Generally, repair functions will iterate the rmapbt to make a list (1) of all extents owned by the nominal owner of the metadata structure; then they will iterate all other structures with the same rmap owner to make a list (2) of active blocks; and finally we have a subtraction function to subtract all the blocks in (2) from (1), with the result that (1) is now a list of blocks that were owned by the old btree and must be disposed.

Signed-off-by Darrick J. Wong <[email protected]>

---
  fs/xfs/scrub/repair.c |  207 +++++++++++++++++++++++++++++++++++++++++++++++++
  fs/xfs/scrub/repair.h |   31 +++++++
  2 files changed, 238 insertions(+)

fs/xfs/scrub/repair.c +8 -0

index 72f04a717150..8e8ecddd7537 100644
@@ -361,3 +361,210 @@ xfs_repair_init_btblock(
 
  	return 0;
  }
+
+/* Collect a dead btree extent for later disposal. */
+int
+xfs_repair_collect_btree_extent(
+	struct xfs_scrub_context	*sc,
+	struct xfs_repair_extent_list	*exlist,
+	xfs_fsblock_t			fsbno,
+	xfs_extlen_t			len)

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 381

Quoted 10 lines

fs/xfs/scrub/repair.c +10 -0

+{
+	struct xfs_repair_extent	*rex;
+
+	trace_xfs_repair_collect_btree_extent(sc->mp,
+			XFS_FSB_TO_AGNO(sc->mp, fsbno),
+			XFS_FSB_TO_AGBNO(sc->mp, fsbno), len);
+
+	rex = kmem_alloc(sizeof(struct xfs_repair_extent), KM_MAYFAIL);
+	if (!rex)
+		return -ENOMEM;

Is this in transaction context? Regardless, I think we need to run the entire of scrub/repair in a memalloc_nofs_save() context so we don't have memory reclaim recursion issues...

[...]

Quoted 10 lines

fs/xfs/scrub/repair.c +10 -0

+/* Compare two btree extents. */
+static int
+xfs_repair_btree_extent_cmp(
+	void				*priv,
+	struct list_head		*a,
+	struct list_head		*b)
+{
+	struct xfs_repair_extent	*ap;
+	struct xfs_repair_extent	*bp;
+

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 450

Quoted 7 lines

fs/xfs/scrub/repair.c +7 -0

+	ap = container_of(a, struct xfs_repair_extent, list);
+	bp = container_of(b, struct xfs_repair_extent, list);
+
+	if (ap->fsbno > bp->fsbno)
+		return 1;
+	else if (ap->fsbno < bp->fsbno)
+		return -1;

No need for the else there.

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 458

Quoted 8 lines

fs/xfs/scrub/repair.c +8 -0

+	return 0;
+}
+
+/*
+ * Remove all the blocks mentioned in sublist from the extents in exlist.
+ *
+ * The intent is that callers will iterate the rmapbt for all of its records
+ * for a given owner to generate exlist; and iterate all the blocks of the

generate @exlist

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 460

Quoted 2 lines

fs/xfs/scrub/repair.c +2 -0

+ * metadata structures that are not being rebuilt and have the same rmapbt
+ * owner to generate sublist.  This routine subtracts all the extents

generate @sublist.

Quoted 34 lines

fs/xfs/scrub/repair.c +34 -0

+ * mentioned in sublist from all the extents linked in exlist, which leaves
+ * exlist as the list of blocks that are not accounted for, which we assume
+ * are the dead blocks of the old metadata structure.  The blocks mentioned in
+ * exlist can be reaped.
+ */
+#define XFS_REPAIR_EXT_LEFT_CONTIG	(1 << 0)
+#define XFS_REPAIR_EXT_RIGHT_CONTIG	(1 << 1)
+int
+xfs_repair_subtract_extents(
+	struct xfs_scrub_context	*sc,
+	struct xfs_repair_extent_list	*exlist,
+	struct xfs_repair_extent_list	*sublist)
+{
+	struct list_head		*lp;
+	struct xfs_repair_extent	*ex;
+	struct xfs_repair_extent	*newex;
+	struct xfs_repair_extent	*subex;
+	xfs_fsblock_t			sub_fsb;
+	xfs_extlen_t			sub_len;
+	int				state;
+	int				error = 0;
+
+	if (list_empty(&exlist->list) || list_empty(&sublist->list))
+		return 0;
+	ASSERT(!list_empty(&sublist->list));
+
+	list_sort(NULL, &exlist->list, xfs_repair_btree_extent_cmp);
+	list_sort(NULL, &sublist->list, xfs_repair_btree_extent_cmp);
+
+	subex = list_first_entry(&sublist->list, struct xfs_repair_extent,
+			list);
+	lp = exlist->list.next;
+	while (lp != &exlist->list) {
+		ex = list_entry(lp, struct xfs_repair_extent, list);

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 504

Quoted 10 lines

fs/xfs/scrub/repair.c +10 -0

+
+		/*
+		 * Advance subex and/or ex until we find a pair that
+		 * intersect or we run out of extents.
+		 */
+		while (subex->fsbno + subex->len <= ex->fsbno) {
+			if (list_is_last(&subex->list, &sublist->list))
+				goto out;
+			subex = list_next_entry(subex, list);
+		}

So this is a O(n^2) algorithm, right? How does it scale with large extent lists? Given that these extents are dynamically allocated, and we're already burning 16 bytes for a list head on each extent, would it be better to use a smarter structure better suited for exact lookups? e.g. an rbtree only takes an extra 8 bytes per extent, and we get O(log N) searches on the inner loop here...

I guess this isn't necessary to fix right now, but I think it's going to be an issue for maybe mark this down as "needing to be fixed before removing EXPERIMENTAL tags"?

Quoted 10 lines

fs/xfs/scrub/repair.c +10 -0

+		if (subex->fsbno >= ex->fsbno + ex->len) {
+			lp = lp->next;
+			continue;
+		}
+
+		/* trim subex to fit the extent we have */
+		sub_fsb = subex->fsbno;
+		sub_len = subex->len;
+		if (subex->fsbno < ex->fsbno) {
+			sub_len -= ex->fsbno - subex->fsbno;

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 524

Quoted 10 lines

fs/xfs/scrub/repair.c +10 -0

+			sub_fsb = ex->fsbno;
+		}
+		if (sub_len > ex->len)
+			sub_len = ex->len;
+
+		state = 0;
+		if (sub_fsb == ex->fsbno)
+			state |= XFS_REPAIR_EXT_LEFT_CONTIG;
+		if (sub_fsb + sub_len == ex->fsbno + ex->len)
+			state |= XFS_REPAIR_EXT_RIGHT_CONTIG;

Ok, I think "CONTIG" is not the right word to use here. In the BMAP btrees, the merge state flags were to tell us whether the edge of the new extent is contiguous with the left and right extents in the tree, not whether the new extents overlapped to the left/right edges.

i.e. we're checking whether extent start/end overlaps are aligned here, not whether they are contiguous with some other extent. So in this case, I'd just name the variables "LEFT_ALIGNED" and "RIGHT_ALIGNED" and drop all the namespace bits from them.

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 527

Quoted 3 lines

fs/xfs/scrub/repair.c +3 -0

+		switch (state) {
+		case XFS_REPAIR_EXT_LEFT_CONTIG:
+			/* Coincides with only the left. */

And by calling them aligned, the comments become redundant:

case LEFT_ALIGNED:

Quoted 18 lines

fs/xfs/scrub/repair.c +18 -0

+			ex->fsbno += sub_len;
+			ex->len -= sub_len;
+			break;
+		case XFS_REPAIR_EXT_RIGHT_CONTIG:
+			/* Coincides with only the right. */
+			ex->len -= sub_len;
+			lp = lp->next;
+			break;
+		case XFS_REPAIR_EXT_LEFT_CONTIG | XFS_REPAIR_EXT_RIGHT_CONTIG:
+			/* Total overlap, just delete ex. */
+			lp = lp->next;
+			list_del(&ex->list);
+			kmem_free(ex);
+			break;
+		case 0:
+			/*
+			 * Deleting from the middle: add the new right extent
+			 * and then shrink the left extent.

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 555

Quoted 10 lines

fs/xfs/scrub/repair.c +10 -0

+			 */
+			newex = kmem_alloc(sizeof(struct xfs_repair_extent),
+					KM_MAYFAIL);
+			if (!newex) {
+				error = -ENOMEM;
+				goto out;
+			}
+			INIT_LIST_HEAD(&newex->list);
+			newex->fsbno = sub_fsb + sub_len;
+			newex->len = ex->len - (sub_fsb - ex->fsbno) - sub_len;

so: new len = old len - (length of first extent) - length of overlap.

I think this is more obvious as "new len = old end - new start", i.e.:

			newex->len = ex->fsbno + ex->len - newex->fsbno;

Cheers,

Dave.

Ok, with the points Dave made:
Reviewed by: Allison Henderson <[email protected]>

Quoted 59 lines · Dave Chinner

Quoted 32 lines · Darrick J. Wong

From: Darrick J. Wong <[email protected]>

Add some helpers to assemble a list of fs block extents. Generally, repair functions will iterate the rmapbt to make a list (1) of all extents owned by the nominal owner of the metadata structure; then they will iterate all other structures with the same rmap owner to make a list (2) of active blocks; and finally we have a subtraction function to subtract all the blocks in (2) from (1), with the result that (1) is now a list of blocks that were owned by the old btree and must be disposed.

Signed-off-by Darrick J. Wong <[email protected]>

---
  fs/xfs/scrub/repair.c |  207 +++++++++++++++++++++++++++++++++++++++++++++++++
  fs/xfs/scrub/repair.h |   31 +++++++
  2 files changed, 238 insertions(+)

fs/xfs/scrub/repair.c +8 -0

index 72f04a717150..8e8ecddd7537 100644
@@ -361,3 +361,210 @@ xfs_repair_init_btblock(
  	return 0;
  }
+
+/* Collect a dead btree extent for later disposal. */
+int
+xfs_repair_collect_btree_extent(
+	struct xfs_scrub_context	*sc,
+	struct xfs_repair_extent_list	*exlist,
+	xfs_fsblock_t			fsbno,
+	xfs_extlen_t			len)

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 380

Quoted 10 lines

fs/xfs/scrub/repair.c +10 -0

+{
+	struct xfs_repair_extent	*rex;
+
+	trace_xfs_repair_collect_btree_extent(sc->mp,
+			XFS_FSB_TO_AGNO(sc->mp, fsbno),
+			XFS_FSB_TO_AGBNO(sc->mp, fsbno), len);
+
+	rex = kmem_alloc(sizeof(struct xfs_repair_extent), KM_MAYFAIL);
+	if (!rex)
+		return -ENOMEM;

Is this in transaction context? Regardless, I think we need to run the entire of scrub/repair in a memalloc_nofs_save() context so we don't have memory reclaim recursion issues...

[...]

Quoted 10 lines

fs/xfs/scrub/repair.c +10 -0

+/* Compare two btree extents. */
+static int
+xfs_repair_btree_extent_cmp(
+	void				*priv,
+	struct list_head		*a,
+	struct list_head		*b)
+{
+	struct xfs_repair_extent	*ap;
+	struct xfs_repair_extent	*bp;
+

Quoted 8 lines

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 450

Quoted 7 lines

fs/xfs/scrub/repair.c +7 -0

+	ap = container_of(a, struct xfs_repair_extent, list);
+	bp = container_of(b, struct xfs_repair_extent, list);
+
+	if (ap->fsbno > bp->fsbno)
+		return 1;
+	else if (ap->fsbno < bp->fsbno)
+		return -1;

No need for the else there.

Well, I think he meant to return 0 in the case of ap->fsbno == bp->fsbno? Am i reading that right?  caller expects 1 for greater than, -1 for less than and 0 on equivalence?

Quoted 136 lines

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 458

Quoted 8 lines

fs/xfs/scrub/repair.c +8 -0

+	return 0;
+}
+
+/*
+ * Remove all the blocks mentioned in sublist from the extents in exlist.
+ *
+ * The intent is that callers will iterate the rmapbt for all of its records
+ * for a given owner to generate exlist; and iterate all the blocks of the

generate @exlist

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 460

Quoted 2 lines

fs/xfs/scrub/repair.c +2 -0

+ * metadata structures that are not being rebuilt and have the same rmapbt
+ * owner to generate sublist.  This routine subtracts all the extents

generate @sublist.

Quoted 34 lines

fs/xfs/scrub/repair.c +34 -0

+ * mentioned in sublist from all the extents linked in exlist, which leaves
+ * exlist as the list of blocks that are not accounted for, which we assume
+ * are the dead blocks of the old metadata structure.  The blocks mentioned in
+ * exlist can be reaped.
+ */
+#define XFS_REPAIR_EXT_LEFT_CONTIG	(1 << 0)
+#define XFS_REPAIR_EXT_RIGHT_CONTIG	(1 << 1)
+int
+xfs_repair_subtract_extents(
+	struct xfs_scrub_context	*sc,
+	struct xfs_repair_extent_list	*exlist,
+	struct xfs_repair_extent_list	*sublist)
+{
+	struct list_head		*lp;
+	struct xfs_repair_extent	*ex;
+	struct xfs_repair_extent	*newex;
+	struct xfs_repair_extent	*subex;
+	xfs_fsblock_t			sub_fsb;
+	xfs_extlen_t			sub_len;
+	int				state;
+	int				error = 0;
+
+	if (list_empty(&exlist->list) || list_empty(&sublist->list))
+		return 0;
+	ASSERT(!list_empty(&sublist->list));
+
+	list_sort(NULL, &exlist->list, xfs_repair_btree_extent_cmp);
+	list_sort(NULL, &sublist->list, xfs_repair_btree_extent_cmp);
+
+	subex = list_first_entry(&sublist->list, struct xfs_repair_extent,
+			list);
+	lp = exlist->list.next;
+	while (lp != &exlist->list) {
+		ex = list_entry(lp, struct xfs_repair_extent, list);

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 504

Quoted 10 lines

fs/xfs/scrub/repair.c +10 -0

+
+		/*
+		 * Advance subex and/or ex until we find a pair that
+		 * intersect or we run out of extents.
+		 */
+		while (subex->fsbno + subex->len <= ex->fsbno) {
+			if (list_is_last(&subex->list, &sublist->list))
+				goto out;
+			subex = list_next_entry(subex, list);
+		}

So this is a O(n^2) algorithm, right? How does it scale with large extent lists? Given that these extents are dynamically allocated, and we're already burning 16 bytes for a list head on each extent, would it be better to use a smarter structure better suited for exact lookups? e.g. an rbtree only takes an extra 8 bytes per extent, and we get O(log N) searches on the inner loop here...

I guess this isn't necessary to fix right now, but I think it's going to be an issue for maybe mark this down as "needing to be fixed before removing EXPERIMENTAL tags"?

Quoted 10 lines

fs/xfs/scrub/repair.c +10 -0

+		if (subex->fsbno >= ex->fsbno + ex->len) {
+			lp = lp->next;
+			continue;
+		}
+
+		/* trim subex to fit the extent we have */
+		sub_fsb = subex->fsbno;
+		sub_len = subex->len;
+		if (subex->fsbno < ex->fsbno) {
+			sub_len -= ex->fsbno - subex->fsbno;

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 524

Quoted 10 lines

fs/xfs/scrub/repair.c +10 -0

+			sub_fsb = ex->fsbno;
+		}
+		if (sub_len > ex->len)
+			sub_len = ex->len;
+
+		state = 0;
+		if (sub_fsb == ex->fsbno)
+			state |= XFS_REPAIR_EXT_LEFT_CONTIG;
+		if (sub_fsb + sub_len == ex->fsbno + ex->len)
+			state |= XFS_REPAIR_EXT_RIGHT_CONTIG;

Ok, I think "CONTIG" is not the right word to use here. In the BMAP btrees, the merge state flags were to tell us whether the edge of the new extent is contiguous with the left and right extents in the tree, not whether the new extents overlapped to the left/right edges.

i.e. we're checking whether extent start/end overlaps are aligned here, not whether they are contiguous with some other extent. So in this case, I'd just name the variables "LEFT_ALIGNED" and "RIGHT_ALIGNED" and drop all the namespace bits from them.

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 527

Quoted 3 lines

fs/xfs/scrub/repair.c +3 -0

+		switch (state) {
+		case XFS_REPAIR_EXT_LEFT_CONTIG:
+			/* Coincides with only the left. */

And by calling them aligned, the comments become redundant:

case LEFT_ALIGNED:

Quoted 18 lines

fs/xfs/scrub/repair.c +18 -0

+			ex->fsbno += sub_len;
+			ex->len -= sub_len;
+			break;
+		case XFS_REPAIR_EXT_RIGHT_CONTIG:
+			/* Coincides with only the right. */
+			ex->len -= sub_len;
+			lp = lp->next;
+			break;
+		case XFS_REPAIR_EXT_LEFT_CONTIG | XFS_REPAIR_EXT_RIGHT_CONTIG:
+			/* Total overlap, just delete ex. */
+			lp = lp->next;
+			list_del(&ex->list);
+			kmem_free(ex);
+			break;
+		case 0:
+			/*
+			 * Deleting from the middle: add the new right extent
+			 * and then shrink the left extent.

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 555

Quoted 10 lines

fs/xfs/scrub/repair.c +10 -0

+			 */
+			newex = kmem_alloc(sizeof(struct xfs_repair_extent),
+					KM_MAYFAIL);
+			if (!newex) {
+				error = -ENOMEM;
+				goto out;
+			}
+			INIT_LIST_HEAD(&newex->list);
+			newex->fsbno = sub_fsb + sub_len;
+			newex->len = ex->len - (sub_fsb - ex->fsbno) - sub_len;

so: new len = old len - (length of first extent) - length of overlap.

Quoted 7 lines

I think this is more obvious as "new len = old end - new start", i.e.:

			newex->len = ex->fsbno + ex->len - newex->fsbno;

Cheers,

Dave.

--
To unsubscribe from this list: send the line "unsubscribe linux-xfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Quoted 71 lines · Allison Henderson

Ok, with the points Dave made:
Reviewed by: Allison Henderson <[email protected]>

Quoted 59 lines · Dave Chinner

Quoted 32 lines · Darrick J. Wong

From: Darrick J. Wong <[email protected]>

Add some helpers to assemble a list of fs block extents. Generally, repair functions will iterate the rmapbt to make a list (1) of all extents owned by the nominal owner of the metadata structure; then they will iterate all other structures with the same rmap owner to make a list (2) of active blocks; and finally we have a subtraction function to subtract all the blocks in (2) from (1), with the result that (1) is now a list of blocks that were owned by the old btree and must be disposed.

Signed-off-by Darrick J. Wong <[email protected]>

---
  fs/xfs/scrub/repair.c |  207 +++++++++++++++++++++++++++++++++++++++++++++++++
  fs/xfs/scrub/repair.h |   31 +++++++
  2 files changed, 238 insertions(+)

fs/xfs/scrub/repair.c +8 -0

index 72f04a717150..8e8ecddd7537 100644
@@ -361,3 +361,210 @@ xfs_repair_init_btblock(
  	return 0;
  }
+
+/* Collect a dead btree extent for later disposal. */
+int
+xfs_repair_collect_btree_extent(
+	struct xfs_scrub_context	*sc,
+	struct xfs_repair_extent_list	*exlist,
+	xfs_fsblock_t			fsbno,
+	xfs_extlen_t			len)

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 380

Quoted 10 lines

fs/xfs/scrub/repair.c +10 -0

+{
+	struct xfs_repair_extent	*rex;
+
+	trace_xfs_repair_collect_btree_extent(sc->mp,
+			XFS_FSB_TO_AGNO(sc->mp, fsbno),
+			XFS_FSB_TO_AGBNO(sc->mp, fsbno), len);
+
+	rex = kmem_alloc(sizeof(struct xfs_repair_extent), KM_MAYFAIL);
+	if (!rex)
+		return -ENOMEM;

Is this in transaction context? Regardless, I think we need to run the entire of scrub/repair in a memalloc_nofs_save() context so we don't have memory reclaim recursion issues...

[...]

Quoted 10 lines

fs/xfs/scrub/repair.c +10 -0

+/* Compare two btree extents. */
+static int
+xfs_repair_btree_extent_cmp(
+	void				*priv,
+	struct list_head		*a,
+	struct list_head		*b)
+{
+	struct xfs_repair_extent	*ap;
+	struct xfs_repair_extent	*bp;
+

Quoted 8 lines

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 450

Quoted 7 lines

fs/xfs/scrub/repair.c +7 -0

+	ap = container_of(a, struct xfs_repair_extent, list);
+	bp = container_of(b, struct xfs_repair_extent, list);
+
+	if (ap->fsbno > bp->fsbno)
+		return 1;
+	else if (ap->fsbno < bp->fsbno)
+		return -1;

No need for the else there.

Quoted 3 lines

Well, I think he meant to return 0 in the case of ap->fsbno == bp->fsbno? Am i reading that right?  caller expects 1 for greater than, -1 for less than and 0 on equivalence?

Correct. I think Dave was pointing out that else-after-return is unnecessary, since the following behaves equivalently:

if (a > b)

	return 1;
if (a < b)
	return -1;

return 0;

Note that gcc (7.3, anyway) generates the same asm for either version so I assume this is mostly stylistic cleanup to make the comparisons line up? I don't have a preference either way. :)

Quoted 80 lines · Darrick J. Wong

Quoted 71 lines · Allison Henderson

Ok, with the points Dave made:
Reviewed by: Allison Henderson <[email protected]>

Quoted 59 lines · Dave Chinner

Quoted 32 lines · Darrick J. Wong

From: Darrick J. Wong <[email protected]>

Add some helpers to assemble a list of fs block extents. Generally, repair functions will iterate the rmapbt to make a list (1) of all extents owned by the nominal owner of the metadata structure; then they will iterate all other structures with the same rmap owner to make a list (2) of active blocks; and finally we have a subtraction function to subtract all the blocks in (2) from (1), with the result that (1) is now a list of blocks that were owned by the old btree and must be disposed.

Signed-off-by Darrick J. Wong <[email protected]>

---
   fs/xfs/scrub/repair.c |  207 +++++++++++++++++++++++++++++++++++++++++++++++++
   fs/xfs/scrub/repair.h |   31 +++++++
   2 files changed, 238 insertions(+)

fs/xfs/scrub/repair.c +8 -0

index 72f04a717150..8e8ecddd7537 100644
@@ -361,3 +361,210 @@ xfs_repair_init_btblock(
   	return 0;
   }
+
+/* Collect a dead btree extent for later disposal. */
+int
+xfs_repair_collect_btree_extent(
+	struct xfs_scrub_context	*sc,
+	struct xfs_repair_extent_list	*exlist,
+	xfs_fsblock_t			fsbno,
+	xfs_extlen_t			len)

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 380

Quoted 10 lines

fs/xfs/scrub/repair.c +10 -0

+{
+	struct xfs_repair_extent	*rex;
+
+	trace_xfs_repair_collect_btree_extent(sc->mp,
+			XFS_FSB_TO_AGNO(sc->mp, fsbno),
+			XFS_FSB_TO_AGBNO(sc->mp, fsbno), len);
+
+	rex = kmem_alloc(sizeof(struct xfs_repair_extent), KM_MAYFAIL);
+	if (!rex)
+		return -ENOMEM;

Is this in transaction context? Regardless, I think we need to run the entire of scrub/repair in a memalloc_nofs_save() context so we don't have memory reclaim recursion issues...

[...]

Quoted 10 lines

fs/xfs/scrub/repair.c +10 -0

+/* Compare two btree extents. */
+static int
+xfs_repair_btree_extent_cmp(
+	void				*priv,
+	struct list_head		*a,
+	struct list_head		*b)
+{
+	struct xfs_repair_extent	*ap;
+	struct xfs_repair_extent	*bp;
+

Quoted 8 lines

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 450

Quoted 7 lines

fs/xfs/scrub/repair.c +7 -0

+	ap = container_of(a, struct xfs_repair_extent, list);
+	bp = container_of(b, struct xfs_repair_extent, list);
+
+	if (ap->fsbno > bp->fsbno)
+		return 1;
+	else if (ap->fsbno < bp->fsbno)
+		return -1;

No need for the else there.

Quoted 3 lines

Well, I think he meant to return 0 in the case of ap->fsbno == bp->fsbno? Am i reading that right?  caller expects 1 for greater than, -1 for less than and 0 on equivalence?

Correct. I think Dave was pointing out that else-after-return is unnecessary, since the following behaves equivalently:

if (a > b)

Quoted 8 lines

	return 1;
if (a < b)
	return -1;

return 0;

Note that gcc (7.3, anyway) generates the same asm for either version so I assume this is mostly stylistic cleanup to make the comparisons line up? I don't have a preference either way. :)

It's a style and maintenance thing. The else is redundant and could lead to future confusion, so IMO it is best to leave it out....

Cheers,

Dave.

Quoted 37 lines · Darrick J. Wong

From: Darrick J. Wong <[email protected]>

Add some helpers to assemble a list of fs block extents. Generally, repair functions will iterate the rmapbt to make a list (1) of all extents owned by the nominal owner of the metadata structure; then they will iterate all other structures with the same rmap owner to make a list (2) of active blocks; and finally we have a subtraction function to subtract all the blocks in (2) from (1), with the result that (1) is now a list of blocks that were owned by the old btree and must be disposed.

Signed-off-by Darrick J. Wong <[email protected]>

---
 fs/xfs/scrub/repair.c |  207 +++++++++++++++++++++++++++++++++++++++++++++++++
 fs/xfs/scrub/repair.h |   31 +++++++
 2 files changed, 238 insertions(+)

fs/xfs/scrub/repair.c +12 -0

index 72f04a717150..8e8ecddd7537 100644
@@ -361,3 +361,210 @@ xfs_repair_init_btblock(
 
 	return 0;
 }
+
+/* Collect a dead btree extent for later disposal. */
+int
+xfs_repair_collect_btree_extent(
+	struct xfs_scrub_context	*sc,
+	struct xfs_repair_extent_list	*exlist,
+	xfs_fsblock_t			fsbno,
+	xfs_extlen_t			len)
+{
+	struct xfs_repair_extent	*rex;
+
+	trace_xfs_repair_collect_btree_extent(sc->mp,

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 381

Quoted 6 lines

fs/xfs/scrub/repair.c +6 -0

+			XFS_FSB_TO_AGNO(sc->mp, fsbno),
+			XFS_FSB_TO_AGBNO(sc->mp, fsbno), len);
+
+	rex = kmem_alloc(sizeof(struct xfs_repair_extent), KM_MAYFAIL);
+	if (!rex)
+		return -ENOMEM;

Is this in transaction context?

Regardless, I think we need to run the entire of scrub/repair in a memalloc_nofs_save() context so we don't have memory reclaim recursion issues...

[...]

Quoted 11 lines

fs/xfs/scrub/repair.c +11 -0

+/* Compare two btree extents. */
+static int
+xfs_repair_btree_extent_cmp(
+	void				*priv,
+	struct list_head		*a,
+	struct list_head		*b)
+{
+	struct xfs_repair_extent	*ap;
+	struct xfs_repair_extent	*bp;
+
+	ap = container_of(a, struct xfs_repair_extent, list);

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 450

Quoted 6 lines

fs/xfs/scrub/repair.c +6 -0

+	bp = container_of(b, struct xfs_repair_extent, list);
+
+	if (ap->fsbno > bp->fsbno)
+		return 1;
+	else if (ap->fsbno < bp->fsbno)
+		return -1;

No need for the else there.

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 458

Quoted 8 lines

fs/xfs/scrub/repair.c +8 -0

+	return 0;
+}
+
+/*
+ * Remove all the blocks mentioned in sublist from the extents in exlist.
+ *
+ * The intent is that callers will iterate the rmapbt for all of its records
+ * for a given owner to generate exlist; and iterate all the blocks of the

generate @exlist

Quoted 2 lines

+ * metadata structures that are not being rebuilt and have the same rmapbt
+ * owner to generate sublist. This routine subtracts all the extents

generate @sublist.

Quoted 39 lines

+ * mentioned in sublist from all the extents linked in exlist, which leaves
+ * exlist as the list of blocks that are not accounted for, which we assume
+ * are the dead blocks of the old metadata structure. The blocks mentioned in
+ * exlist can be reaped.
+ */

fs/xfs/scrub/repair.c +34 -0

+#define XFS_REPAIR_EXT_LEFT_CONTIG	(1 << 0)
+#define XFS_REPAIR_EXT_RIGHT_CONTIG	(1 << 1)
+int
+xfs_repair_subtract_extents(
+	struct xfs_scrub_context	*sc,
+	struct xfs_repair_extent_list	*exlist,
+	struct xfs_repair_extent_list	*sublist)
+{
+	struct list_head		*lp;
+	struct xfs_repair_extent	*ex;
+	struct xfs_repair_extent	*newex;
+	struct xfs_repair_extent	*subex;
+	xfs_fsblock_t			sub_fsb;
+	xfs_extlen_t			sub_len;
+	int				state;
+	int				error = 0;
+
+	if (list_empty(&exlist->list) || list_empty(&sublist->list))
+		return 0;
+	ASSERT(!list_empty(&sublist->list));
+
+	list_sort(NULL, &exlist->list, xfs_repair_btree_extent_cmp);
+	list_sort(NULL, &sublist->list, xfs_repair_btree_extent_cmp);
+
+	subex = list_first_entry(&sublist->list, struct xfs_repair_extent,
+			list);
+	lp = exlist->list.next;
+	while (lp != &exlist->list) {
+		ex = list_entry(lp, struct xfs_repair_extent, list);
+
+		/*
+		 * Advance subex and/or ex until we find a pair that
+		 * intersect or we run out of extents.
+		 */

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 504

Quoted 5 lines

fs/xfs/scrub/repair.c +5 -0

+		while (subex->fsbno + subex->len <= ex->fsbno) {
+			if (list_is_last(&subex->list, &sublist->list))
+				goto out;
+			subex = list_next_entry(subex, list);
+		}

So this is a O(n^2) algorithm, right? How does it scale with large extent lists?

Given that these extents are dynamically allocated, and we're already burning 16 bytes for a list head on each extent, would it be better to use a smarter structure better suited for exact lookups? e.g. an rbtree only takes an extra 8 bytes per extent, and we get O(log N) searches on the inner loop here...

I guess this isn't necessary to fix right now, but I think it's going to be an issue for maybe mark this down as "needing to be fixed before removing EXPERIMENTAL tags"?

Quoted 10 lines

fs/xfs/scrub/repair.c +10 -0

+		if (subex->fsbno >= ex->fsbno + ex->len) {
+			lp = lp->next;
+			continue;
+		}
+
+		/* trim subex to fit the extent we have */
+		sub_fsb = subex->fsbno;
+		sub_len = subex->len;
+		if (subex->fsbno < ex->fsbno) {
+			sub_len -= ex->fsbno - subex->fsbno;

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 524

Quoted 10 lines

fs/xfs/scrub/repair.c +10 -0

+			sub_fsb = ex->fsbno;
+		}
+		if (sub_len > ex->len)
+			sub_len = ex->len;
+
+		state = 0;
+		if (sub_fsb == ex->fsbno)
+			state |= XFS_REPAIR_EXT_LEFT_CONTIG;
+		if (sub_fsb + sub_len == ex->fsbno + ex->len)
+			state |= XFS_REPAIR_EXT_RIGHT_CONTIG;

Ok, I think "CONTIG" is not the right word to use here. In the BMAP btrees, the merge state flags were to tell us whether the edge of the new extent is contiguous with the left and right extents in the tree, not whether the new extents overlapped to the left/right edges.

i.e. we're checking whether extent start/end overlaps are aligned here, not whether they are contiguous with some other extent. So in this case, I'd just name the variables "LEFT_ALIGNED" and "RIGHT_ALIGNED" and drop all the namespace bits from them.

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 527

Quoted 3 lines

fs/xfs/scrub/repair.c +3 -0

+		switch (state) {
+		case XFS_REPAIR_EXT_LEFT_CONTIG:
+			/* Coincides with only the left. */

And by calling them aligned, the comments become redundant:

case LEFT_ALIGNED:

Quoted 18 lines

fs/xfs/scrub/repair.c +18 -0

+			ex->fsbno += sub_len;
+			ex->len -= sub_len;
+			break;
+		case XFS_REPAIR_EXT_RIGHT_CONTIG:
+			/* Coincides with only the right. */
+			ex->len -= sub_len;
+			lp = lp->next;
+			break;
+		case XFS_REPAIR_EXT_LEFT_CONTIG | XFS_REPAIR_EXT_RIGHT_CONTIG:
+			/* Total overlap, just delete ex. */
+			lp = lp->next;
+			list_del(&ex->list);
+			kmem_free(ex);
+			break;
+		case 0:
+			/*
+			 * Deleting from the middle: add the new right extent
+			 * and then shrink the left extent.

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 555

Quoted 10 lines

fs/xfs/scrub/repair.c +10 -0

+			 */
+			newex = kmem_alloc(sizeof(struct xfs_repair_extent),
+					KM_MAYFAIL);
+			if (!newex) {
+				error = -ENOMEM;
+				goto out;
+			}
+			INIT_LIST_HEAD(&newex->list);
+			newex->fsbno = sub_fsb + sub_len;
+			newex->len = ex->len - (sub_fsb - ex->fsbno) - sub_len;

so: new len = old len - (length of first extent) - length of overlap.

I think this is more obvious as "new len = old end - new start", i.e.:

			newex->len = ex->fsbno + ex->len - newex->fsbno;

Cheers,

Dave.

Signature · 6 lines

Dave Chinner
[email protected]
--
To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Quoted 38 lines · Dave Chinner

Quoted 37 lines · Darrick J. Wong

From: Darrick J. Wong <[email protected]>

Add some helpers to assemble a list of fs block extents. Generally, repair functions will iterate the rmapbt to make a list (1) of all extents owned by the nominal owner of the metadata structure; then they will iterate all other structures with the same rmap owner to make a list (2) of active blocks; and finally we have a subtraction function to subtract all the blocks in (2) from (1), with the result that (1) is now a list of blocks that were owned by the old btree and must be disposed.

Signed-off-by Darrick J. Wong <[email protected]>

---
 fs/xfs/scrub/repair.c |  207 +++++++++++++++++++++++++++++++++++++++++++++++++
 fs/xfs/scrub/repair.h |   31 +++++++
 2 files changed, 238 insertions(+)

fs/xfs/scrub/repair.c +12 -0

index 72f04a717150..8e8ecddd7537 100644
@@ -361,3 +361,210 @@ xfs_repair_init_btblock(
 
 	return 0;
 }
+
+/* Collect a dead btree extent for later disposal. */
+int
+xfs_repair_collect_btree_extent(
+	struct xfs_scrub_context	*sc,
+	struct xfs_repair_extent_list	*exlist,
+	xfs_fsblock_t			fsbno,
+	xfs_extlen_t			len)
+{
+	struct xfs_repair_extent	*rex;
+
+	trace_xfs_repair_collect_btree_extent(sc->mp,

Quoted 8 lines

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 381

Quoted 6 lines

fs/xfs/scrub/repair.c +6 -0

+			XFS_FSB_TO_AGNO(sc->mp, fsbno),
+			XFS_FSB_TO_AGBNO(sc->mp, fsbno), len);
+
+	rex = kmem_alloc(sizeof(struct xfs_repair_extent), KM_MAYFAIL);
+	if (!rex)
+		return -ENOMEM;

Is this in transaction context?

Yes. After the setup function finishes we're required to own a transaction and hold a lock on whatever resource we're playing with.

Quoted 3 lines

Regardless, I think we need to run the entire of scrub/repair in a memalloc_nofs_save() context so we don't have memory reclaim recursion issues...

xfs_trans_reserve should take care of this, right? So we don't have to feed KM_NOFS to kmem_*_alloc because this is already taken care of. The MAYFAIL exists because we prefer ENOMEM'ing out to pushing on reclaim.

Quoted 7 lines

Quoted 7 lines

fs/xfs/scrub/repair.c +7 -0

+	while (lp != &exlist->list) {
+		ex = list_entry(lp, struct xfs_repair_extent, list);
+
+		/*
+		 * Advance subex and/or ex until we find a pair that
+		 * intersect or we run out of extents.
+		 */

Quoted 8 lines

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 504

Quoted 5 lines

fs/xfs/scrub/repair.c +5 -0

+		while (subex->fsbno + subex->len <= ex->fsbno) {
+			if (list_is_last(&subex->list, &sublist->list))
+				goto out;
+			subex = list_next_entry(subex, list);
+		}

So this is a O(n^2) algorithm, right? How does it scale with large extent lists?

I don't think this is O(n^2) -- each list sort is O(n log n).

Then we
iterate exlist once, rolling forward through sublist as necessary. We never reset lp to the head of exlist nor do we reset subex to the head of sublist. We're not performing random lookups on the sublist extents at all.

So far I haven't noticed /much/ heat from this routine even with deliberately aged filesystems, but that's probably due to the slab allocator eating way more time. :(

Quoted 6 lines

Given that these extents are dynamically allocated, and we're already burning 16 bytes for a list head on each extent, would it be better to use a smarter structure better suited for exact lookups? e.g. an rbtree only takes an extra 8 bytes per extent, and we get O(log N) searches on the inner loop here...

Quoted 3 lines

I guess this isn't necessary to fix right now, but I think it's going to be an issue for maybe mark this down as "needing to be fixed before removing EXPERIMENTAL tags"?

I've thought about converting this to an rbtree or something, since these are basically glorified bitmap operations.

TBH the other thing that irks me about the current orepair design is its heavy reliance on creating potentially huge linked lists of the records that need to be put into the new structure. I'd really like a data structure where I can do fast unsorted appends without list overhead, sort the data structure once, and then insert in sorted order. The slab thing I put into xfs_repair provides this, but we can't easily allocate 128M of space in the kernel. I also want to do a bulk load of an empty a btree leaf so that we log the leaf block once and update the node pointers once, kind of like what xfs_repair does during phase 5.

...all this optimization can come after merging.

Quoted 55 lines · Darrick J. Wong

Quoted 38 lines · Dave Chinner

Quoted 37 lines · Darrick J. Wong

From: Darrick J. Wong <[email protected]>

Add some helpers to assemble a list of fs block extents. Generally, repair functions will iterate the rmapbt to make a list (1) of all extents owned by the nominal owner of the metadata structure; then they will iterate all other structures with the same rmap owner to make a list (2) of active blocks; and finally we have a subtraction function to subtract all the blocks in (2) from (1), with the result that (1) is now a list of blocks that were owned by the old btree and must be disposed.

Signed-off-by Darrick J. Wong <[email protected]>

---
 fs/xfs/scrub/repair.c |  207 +++++++++++++++++++++++++++++++++++++++++++++++++
 fs/xfs/scrub/repair.h |   31 +++++++
 2 files changed, 238 insertions(+)

fs/xfs/scrub/repair.c +12 -0

index 72f04a717150..8e8ecddd7537 100644
@@ -361,3 +361,210 @@ xfs_repair_init_btblock(
 
 	return 0;
 }
+
+/* Collect a dead btree extent for later disposal. */
+int
+xfs_repair_collect_btree_extent(
+	struct xfs_scrub_context	*sc,
+	struct xfs_repair_extent_list	*exlist,
+	xfs_fsblock_t			fsbno,
+	xfs_extlen_t			len)
+{
+	struct xfs_repair_extent	*rex;
+
+	trace_xfs_repair_collect_btree_extent(sc->mp,

Quoted 8 lines

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 381

Quoted 6 lines

fs/xfs/scrub/repair.c +6 -0

+			XFS_FSB_TO_AGNO(sc->mp, fsbno),
+			XFS_FSB_TO_AGBNO(sc->mp, fsbno), len);
+
+	rex = kmem_alloc(sizeof(struct xfs_repair_extent), KM_MAYFAIL);
+	if (!rex)
+		return -ENOMEM;

Is this in transaction context?

Yes. After the setup function finishes we're required to own a transaction and hold a lock on whatever resource we're playing with.

Quoted 3 lines

Regardless, I think we need to run the entire of scrub/repair in a memalloc_nofs_save() context so we don't have memory reclaim recursion issues...

Quoted 3 lines

xfs_trans_reserve should take care of this, right? So we don't have to feed KM_NOFS to kmem_*_alloc because this is already taken care of. The MAYFAIL exists because we prefer ENOMEM'ing out to pushing on reclaim.

Right, if we have an active transaction we are under NOFS allocation conditions. I'm jus tnot sure how much of scrub/repair is covered by the transaction context (too early in the morning to go code spelunking!).

w.r.t reclaim, NOFS allocations will still push on reclaim - NOFS just means it won't push on any dirty file pages or scan/reclaim filesystem caches.

Quoted 16 lines

Quoted 7 lines

Quoted 7 lines

fs/xfs/scrub/repair.c +7 -0

+	while (lp != &exlist->list) {
+		ex = list_entry(lp, struct xfs_repair_extent, list);
+
+		/*
+		 * Advance subex and/or ex until we find a pair that
+		 * intersect or we run out of extents.
+		 */

Quoted 8 lines

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 504

Quoted 5 lines

fs/xfs/scrub/repair.c +5 -0

+		while (subex->fsbno + subex->len <= ex->fsbno) {
+			if (list_is_last(&subex->list, &sublist->list))
+				goto out;
+			subex = list_next_entry(subex, list);
+		}

So this is a O(n^2) algorithm, right? How does it scale with large extent lists?

Quoted 1 line

I don't think this is O(n^2) -- each list sort is O(n log n).

I'm not worried about the list sort. :)

Quoted 5 lines

Then we
iterate exlist once, rolling forward through sublist as necessary. We never reset lp to the head of exlist nor do we reset subex to the head of sublist. We're not performing random lookups on the sublist extents at all.

Ah, I missed the fact the loop doesn't reset the subex list to the start for each ex entry. Perhaps a better comment explaining the way the algorithm steps through both lists?

Quoted 3 lines

So far I haven't noticed /much/ heat from this routine even with deliberately aged filesystems, but that's probably due to the slab allocator eating way more time. :(

Perhaps it is worth looking at using named slab caches for some of these objects to take some heat off of the heap slabs?

Quoted 6 lines

Quoted 6 lines

Given that these extents are dynamically allocated, and we're already burning 16 bytes for a list head on each extent, would it be better to use a smarter structure better suited for exact lookups? e.g. an rbtree only takes an extra 8 bytes per extent, and we get O(log N) searches on the inner loop here...

Quoted 6 lines

Quoted 3 lines

I guess this isn't necessary to fix right now, but I think it's going to be an issue for maybe mark this down as "needing to be fixed before removing EXPERIMENTAL tags"?

I've thought about converting this to an rbtree or something, since these are basically glorified bitmap operations.

You can probably ignore that because I was thinking it was a full subex list search for each ex, which is not the case...

Quoted 11 lines

TBH the other thing that irks me about the current orepair design is its heavy reliance on creating potentially huge linked lists of the records that need to be put into the new structure. I'd really like a data structure where I can do fast unsorted appends without list overhead, sort the data structure once, and then insert in sorted order. The slab thing I put into xfs_repair provides this, but we can't easily allocate 128M of space in the kernel. I also want to do a bulk load of an empty a btree leaf so that we log the leaf block once and update the node pointers once, kind of like what xfs_repair does during phase 5.

Quoted 1 line

...all this optimization can come after merging.

*nod*.

Cheers,

Dave.

Signature · 6 lines

Dave Chinner
[email protected]
--
To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Quoted 5 lines · Dave Chinner

Quoted 3 lines · Darrick J. Wong

So far I haven't noticed /much/ heat from this routine even with deliberately aged filesystems, but that's probably due to the slab allocator eating way more time. :(

Quoted 2 lines

Perhaps it is worth looking at using named slab caches for some of these objects to take some heat off of the heap slabs?

Early versions of repair actually did that to try to avoid fragmenting the power-of-2 slabs by using named slab caches, but slub emits udev events whenever a named slab is created, and the resulting horrible

cacophony of udev rule processing ate an entire CPU core and uncovered deadlocks in the parts of the slab management code that manage /sys/kernel/slab. That code /really/ does not like you creating and removing slabs concurrently.

Quoted 9 lines · Darrick J. Wong

Quoted 7 lines · Dave Chinner

Quoted 3 lines · Darrick J. Wong

So far I haven't noticed /much/ heat from this routine even with deliberately aged filesystems, but that's probably due to the slab allocator eating way more time. :(

Perhaps it is worth looking at using named slab caches for some of these objects to take some heat off of the heap slabs?

Quoted 3 lines

Early versions of repair actually did that to try to avoid fragmenting the power-of-2 slabs by using named slab caches, but slub emits udev events whenever a named slab is created, and the resulting horrible

Really? That's so gross!

Anyway, WTF are udev events on internal kernel slab cache creation needed for?

Quoted 4 lines

cacophony of udev rule processing ate an entire CPU core and uncovered deadlocks in the parts of the slab management code that manage /sys/kernel/slab. That code /really/ does not like you creating and removing slabs concurrently.

I wasn't suggesting dynamically creating slab caches during a repair operation, just have one for the structure type created when we first initialise the XFS kernel module like we do for xfs_buf, xfs_inode, etc.

Cheers,

Dave.

Signature · 6 lines

Dave Chinner
[email protected]
--
To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

From: Darrick J. Wong <[email protected]>

Add some helpers to assemble a list of fs block extents. Generally, repair functions will iterate the rmapbt to make a list (1) of all extents owned by the nominal owner of the metadata structure; then they will iterate all other structures with the same rmap owner to make a list (2) of active blocks; and finally we have a subtraction function to subtract all the blocks in (2) from (1), with the result that (1) is now a list of blocks that were owned by the old btree and must be disposed.

Signed-off-by Darrick J. Wong <[email protected]>

---
v2: document the design of how repair functions are supposed to work,
implement review comments
---

fs/xfs/scrub/repair.c +11 -0

+/* Collect a dead btree extent for later disposal. */
+int
+xfs_repair_collect_btree_extent(
+	struct xfs_scrub_context	*sc,
+	struct xfs_repair_extent_list	*exlist,
+	xfs_fsblock_t			fsbno,
+	xfs_extlen_t			len)
+{
+	struct xfs_repair_extent	*rex;
+
+	trace_xfs_repair_collect_btree_extent(sc->mp,

fs/xfs/scrub/repair.c +10 -0

+		case LEFT_ALIGNED | RIGHT_ALIGNED:
+			/* Total overlap, just delete ex. */
+			lp = lp->next;
+			list_del(&ex->list);
+			kmem_free(ex);
+			break;
+		case 0:
+			/*
+			 * Deleting from the middle: add the new right extent
+			 * and then shrink the left extent.

Quoted 10 lines · Darrick J. Wong

From: Darrick J. Wong <[email protected]>

Add some helpers to assemble a list of fs block extents. Generally, repair functions will iterate the rmapbt to make a list (1) of all extents owned by the nominal owner of the metadata structure; then they will iterate all other structures with the same rmap owner to make a list (2) of active blocks; and finally we have a subtraction function to subtract all the blocks in (2) from (1), with the result that (1) is now a list of blocks that were owned by the old btree and must be disposed.

Quoted 5 lines

Signed-off-by Darrick J. Wong <[email protected]>

---
v2: document the design of how repair functions are supposed to work,
implement review comments
---

Much easier to understand now. Thanks!

Reviewed-by Dave Chinner <[email protected]>

One thing for a followup patch, though.

Quoted 11 lines

fs/xfs/scrub/repair.c +11 -0

+/* Collect a dead btree extent for later disposal. */
+int
+xfs_repair_collect_btree_extent(
+	struct xfs_scrub_context	*sc,
+	struct xfs_repair_extent_list	*exlist,
+	xfs_fsblock_t			fsbno,
+	xfs_extlen_t			len)
+{
+	struct xfs_repair_extent	*rex;
+
+	trace_xfs_repair_collect_btree_extent(sc->mp,

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 418

Quoted 10 lines

fs/xfs/scrub/repair.c +10 -0

+			XFS_FSB_TO_AGNO(sc->mp, fsbno),
+			XFS_FSB_TO_AGBNO(sc->mp, fsbno), len);
+
+	rex = kmem_alloc(sizeof(struct xfs_repair_extent), KM_MAYFAIL);
+	if (!rex)
+		return -ENOMEM;
+
+	INIT_LIST_HEAD(&rex->list);
+	rex->fsbno = fsbno;
+	rex->len = len;

This allocation is repeated a couple of times. Single function to do it would be nice to encapsulate alloc+setup - something like rex = alloc_rex(fsbno, len) which returns NULL if it fails.

Quoted 14 lines

fs/xfs/scrub/repair.c +14 -0

+		case LEFT_ALIGNED | RIGHT_ALIGNED:
+			/* Total overlap, just delete ex. */
+			lp = lp->next;
+			list_del(&ex->list);
+			kmem_free(ex);
+			break;
+		case 0:
+			/*
+			 * Deleting from the middle: add the new right extent
+			 * and then shrink the left extent.
+			 */
+			newex = kmem_alloc(sizeof(struct xfs_repair_extent),
+					KM_MAYFAIL);
+			if (!newex) {

fs/xfs/scrub/repair.c xfs_repair_init_btblock( · line 572

Quoted 6 lines

fs/xfs/scrub/repair.c +6 -0

+				error = -ENOMEM;
+				goto out;
+			}
+			INIT_LIST_HEAD(&newex->list);
+			newex->fsbno = sub_fsb + sub_len;
+			newex->len = ex->fsbno + ex->len - newex->fsbno;

This is the other place it is called...

Cheers,

Dave.

Signature · 6 lines

Dave Chinner
[email protected]
--
To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html