xfs: create a shadow rmap btree during realtime rmap repair

Create an in-memory btree of rmap records instead of an array.  This
enables us to do live record collection instead of freezing the fs.

Signed-off-by: Darrick J. Wong <djwong@kernel.org>

3 files changed, 180 insertions, 82 deletions

diff --git a/fs/xfs/libxfs/xfs_rtrmap_btree.c b/fs/xfs/libxfs/xfs_rtrmap_btree.c
index a1584784991e..29de9bfbde20 100644
--- a/fs/xfs/libxfs/xfs_rtrmap_btree.c
+++ b/fs/xfs/libxfs/xfs_rtrmap_btree.c
@@ -18,6 +18,7 @@
 #include "xfs_alloc.h"
 #include "xfs_btree.h"
 #include "xfs_btree_staging.h"
+#include "xfs_btree_mem.h"
 #include "xfs_rmap.h"
 #include "xfs_rtrmap_btree.h"
 #include "xfs_trace.h"
@@ -499,6 +500,75 @@ xfs_rtrmapbt_stage_cursor(
 	return cur;
 }
 
+STATIC int
+xfs_rtrmapbt_get_mem_minrecs(
+	struct xfs_btree_cur	*cur,
+	int			level)
+{
+	return cur->bc_mp->m_rtrmap_mnr[level != 0];
+}
+
+STATIC int
+xfs_rtrmapbt_get_mem_maxrecs(
+	struct xfs_btree_cur	*cur,
+	int			level)
+{
+	return cur->bc_mp->m_rtrmap_mxr[level != 0];
+}
+
+static const struct xfs_btree_ops xfs_rtrmapbt_mem_ops = {
+	.rec_len		= sizeof(struct xfs_rtrmap_rec),
+	.key_len		= 2 * sizeof(struct xfs_rtrmap_key),
+
+	.dup_cursor		= xfs_btree_mem_dup_cursor,
+	.set_root		= xfs_btree_mem_set_root,
+	.alloc_block		= xfbtree_alloc_block,
+	.free_block		= xfbtree_free_block,
+	.get_minrecs		= xfs_rtrmapbt_get_mem_minrecs,
+	.get_maxrecs		= xfs_rtrmapbt_get_mem_maxrecs,
+	.init_key_from_rec	= xfs_rtrmapbt_init_key_from_rec,
+	.init_high_key_from_rec	= xfs_rtrmapbt_init_high_key_from_rec,
+	.init_rec_from_cur	= xfs_rtrmapbt_init_rec_from_cur,
+	.init_ptr_from_cur	= xfs_btree_mem_init_ptr_from_cur,
+	.key_diff		= xfs_rtrmapbt_key_diff,
+	.buf_ops		= &xfs_rtrmapbt_buf_ops,
+	.diff_two_keys		= xfs_rtrmapbt_diff_two_keys,
+	.keys_inorder		= xfs_rtrmapbt_keys_inorder,
+	.recs_inorder		= xfs_rtrmapbt_recs_inorder,
+};
+
+/* Create a cursor for an in-memory btree. */
+struct xfs_btree_cur *
+xfs_rtrmapbt_mem_cursor(
+	struct xfs_mount	*mp,
+	struct xfs_trans	*tp,
+	struct xfs_buf		*head_bp,
+	struct xfbtree		*xfbtree)
+{
+	struct xfs_btree_cur	*cur;
+
+	/* Overlapping btree; 2 keys per pointer. */
+	cur = xfs_btree_alloc_cursor(mp, tp, XFS_BTNUM_RTRMAP);
+	cur->bc_flags = XFS_BTREE_CRC_BLOCKS | XFS_BTREE_OVERLAPPING |
+			XFS_BTREE_LONG_PTRS | XFS_BTREE_IN_MEMORY;
+	cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_rmap_2);
+	cur->bc_ops = &xfs_rtrmapbt_mem_ops;
+	cur->bc_mem.xfbtree = xfbtree;
+	cur->bc_mem.head_bp = head_bp;
+	cur->bc_nlevels = xfs_btree_mem_head_nlevels(head_bp);
+
+	return cur;
+}
+
+struct xfbtree *
+xfs_rtrmapbt_mem_create(
+	struct xfs_mount	*mp,
+	const char		*name)
+{
+	return xfbtree_create(mp, XFS_BTNUM_RTRMAP, &xfs_rtrmapbt_buf_ops,
+			XFBTREE_CREATE_LONG_PTRS, name);
+}
+
 /*
  * Install a new rt reverse mapping btree root.  Caller is responsible for
  * invalidating and freeing the old btree blocks.
diff --git a/fs/xfs/libxfs/xfs_rtrmap_btree.h b/fs/xfs/libxfs/xfs_rtrmap_btree.h
index d1ae7bc1d7e8..40226138413f 100644
--- a/fs/xfs/libxfs/xfs_rtrmap_btree.h
+++ b/fs/xfs/libxfs/xfs_rtrmap_btree.h
@@ -193,4 +193,10 @@ struct xfs_imeta_end;
 int xfs_rtrmapbt_create(struct xfs_trans **tpp, struct xfs_imeta_end *ic,
 		struct xfs_inode **ipp);
 
+struct xfbtree;
+struct xfs_btree_cur *xfs_rtrmapbt_mem_cursor(struct xfs_mount *mp,
+		struct xfs_trans *tp, struct xfs_buf *mhead_bp,
+		struct xfbtree *xfbtree);
+struct xfbtree *xfs_rtrmapbt_mem_create(struct xfs_mount *mp, const char *name);
+
 #endif	/* __XFS_RTRMAP_BTREE_H__ */
diff --git a/fs/xfs/scrub/rtrmap_repair.c b/fs/xfs/scrub/rtrmap_repair.c
index d68ef4d1ec16..b8e53895dfa4 100644
--- a/fs/xfs/scrub/rtrmap_repair.c
+++ b/fs/xfs/scrub/rtrmap_repair.c
@@ -11,6 +11,7 @@
 #include "xfs_mount.h"
 #include "xfs_defer.h"
 #include "xfs_btree.h"
+#include "xfs_btree_mem.h"
 #include "xfs_bit.h"
 #include "xfs_log_format.h"
 #include "xfs_trans.h"
@@ -34,9 +35,9 @@
 #include "scrub/trace.h"
 #include "scrub/repair.h"
 #include "scrub/bitmap.h"
-#include "scrub/xfarray.h"
 #include "scrub/xfile.h"
 #include "scrub/iscan.h"
+#include "scrub/xfbtree.h"
 
 /*
  * Realtime Reverse Mapping Btree Repair
@@ -60,17 +61,6 @@
  * We use the 'xrep_rtrmap' prefix for all the rmap functions.
  */
 
-/*
- * Packed rmap record.  The UNWRITTEN flags are hidden in the upper bits of
- * offset, just like the on-disk record.
- */
-struct xrep_rtrmap_extent {
-	xfs_rtblock_t	startblock;
-	xfs_filblks_t	blockcount;
-	uint64_t	owner;
-	uint64_t	offset;
-} __packed;
-
 /* Context for collecting rmaps */
 struct xrep_rtrmap {
 	/* new rtrmapbt information */
@@ -78,7 +68,9 @@ struct xrep_rtrmap {
 	struct xfs_btree_bload	rtrmap_bload;
 
 	/* rmap records generated from primary metadata */
-	struct xfarray		*rtrmap_records;
+	struct xfbtree		*rtrmap_btree;
+	/* in-memory btree cursor for the ->get_blocks walk */
+	struct xfs_btree_cur	*mcur;
 
 	struct xfs_scrub	*sc;
 
@@ -88,41 +80,10 @@ struct xrep_rtrmap {
 	/* inode scan cursor */
 	struct xchk_iscan	iscan;
 
-	/* get_record()'s position in the free space record array. */
-	uint64_t		iter;
+	/* Number of records we're staging in the new btree. */
+	uint64_t		nr_records;
 };
 
-/* Compare two rtrmapbt extents. */
-static int
-xrep_rtrmap_extent_cmp(
-	const void			*a,
-	const void			*b)
-{
-	const struct xrep_rtrmap_extent	*ap = a;
-	const struct xrep_rtrmap_extent	*bp = b;
-	struct xfs_rmap_irec		ar = {
-		.rm_startblock		= ap->startblock,
-		.rm_blockcount		= ap->blockcount,
-		.rm_owner		= ap->owner,
-	};
-	struct xfs_rmap_irec		br = {
-		.rm_startblock		= bp->startblock,
-		.rm_blockcount		= bp->blockcount,
-		.rm_owner		= bp->owner,
-	};
-	int				error;
-
-	error = xfs_rmap_irec_offset_unpack(ap->offset, &ar);
-	if (error)
-		ASSERT(error == 0);
-
-	error = xfs_rmap_irec_offset_unpack(bp->offset, &br);
-	if (error)
-		ASSERT(error == 0);
-
-	return xfs_rmap_compare(&ar, &br);
-}
-
 /* Make sure there's nothing funny about this mapping. */
 STATIC int
 xrep_rtrmap_check_mapping(
@@ -152,11 +113,6 @@ xrep_rtrmap_stash(
 	uint64_t		offset,
 	unsigned int		flags)
 {
-	struct xrep_rtrmap_extent	rre = {
-		.startblock	= startblock,
-		.blockcount	= blockcount,
-		.owner		= owner,
-	};
 	struct xfs_rmap_irec	rmap = {
 		.rm_startblock	= startblock,
 		.rm_blockcount	= blockcount,
@@ -165,6 +121,8 @@ xrep_rtrmap_stash(
 		.rm_flags	= flags,
 	};
 	struct xfs_scrub	*sc = rr->sc;
+	struct xfs_btree_cur	*mcur;
+	struct xfs_buf		*mhead_bp;
 	int			error = 0;
 
 	if (xchk_should_terminate(sc, &error))
@@ -172,8 +130,24 @@ xrep_rtrmap_stash(
 
 	trace_xrep_rtrmap_found(sc->mp, &rmap);
 
-	rre.offset = xfs_rmap_irec_offset_pack(&rmap);
-	return xfarray_append(rr->rtrmap_records, &rre);
+	/* Add entry to in-memory btree. */
+	error = xfs_btree_mem_head_read_buf(rr->rtrmap_btree->target, sc->tp,
+			&mhead_bp);
+	if (error)
+		return error;
+
+	mcur = xfs_rtrmapbt_mem_cursor(sc->mp, sc->tp, mhead_bp,
+			rr->rtrmap_btree);
+	error = xfs_rmap_map_immediate(mcur, &rmap);
+	xfs_btree_del_cursor(mcur, error);
+	if (error)
+		goto out_cancel;
+
+	return xfbtree_trans_commit(rr->rtrmap_btree, sc->tp);
+
+out_cancel:
+	xfbtree_trans_cancel(rr->rtrmap_btree, sc->tp);
+	return error;
 }
 
 /* Finding all file and bmbt extents. */
@@ -499,6 +473,24 @@ out_bitmap:
 	return error;
 }
 
+/* Count and check all collected records. */
+STATIC int
+xrep_rtrmap_check_record(
+	struct xfs_btree_cur		*cur,
+	const struct xfs_rmap_irec	*rec,
+	void				*priv)
+{
+	struct xrep_rtrmap		*rr = priv;
+	int				error;
+
+	error = xrep_rtrmap_check_mapping(rr->sc, rec);
+	if (error)
+		return error;
+
+	rr->nr_records++;
+	return 0;
+}
+
 /* Generate all the reverse-mappings for the realtime device. */
 STATIC int
 xrep_rtrmap_find_rmaps(
@@ -507,6 +499,8 @@ xrep_rtrmap_find_rmaps(
 	struct xfs_scrub	*sc = rr->sc;
 	struct xchk_iscan	*iscan = &rr->iscan;
 	struct xfs_perag	*pag;
+	struct xfs_buf		*mhead_bp;
+	struct xfs_btree_cur	*mcur;
 	xfs_agnumber_t		agno;
 	int			error;
 
@@ -582,7 +576,26 @@ xrep_rtrmap_find_rmaps(
 		}
 	}
 
-	return 0;
+	/*
+	 * Now that we have everything locked again, we need to count the
+	 * number of rmap records stashed in the btree.  This should reflect
+	 * all actively-owned rt files in the filesystem.  At the same time,
+	 * check all our records before we start building a new btree, which
+	 * requires the rtbitmap lock.
+	 */
+	error = xfs_btree_mem_head_read_buf(rr->rtrmap_btree->target, NULL,
+			&mhead_bp);
+	if (error)
+		return error;
+
+	mcur = xfs_rtrmapbt_mem_cursor(rr->sc->mp, NULL, mhead_bp,
+			rr->rtrmap_btree);
+	rr->nr_records = 0;
+	error = xfs_rmap_query_all(mcur, xrep_rtrmap_check_record, rr);
+	xfs_btree_del_cursor(mcur, error);
+	xfs_buf_relse(mhead_bp);
+
+	return error;
 }
 
 /* Building the new rtrmap btree. */
@@ -628,24 +641,23 @@ xrep_rtrmap_get_record(
 	struct xfs_btree_cur	*cur,
 	void			*priv)
 {
-	struct xrep_rtrmap_extent	rec;
-	struct xfs_rmap_irec	*irec = &cur->bc_rec.r;
 	struct xrep_rtrmap	*rr = priv;
+	int			stat = 0;
 	int			error;
 
-	error = xfarray_load_next(rr->rtrmap_records, &rr->iter, &rec);
+	error = xfs_btree_increment(rr->mcur, 0, &stat);
 	if (error)
 		return error;
+	if (!stat)
+		return -EFSCORRUPTED;
 
-	irec->rm_startblock = rec.startblock;
-	irec->rm_blockcount = rec.blockcount;
-	irec->rm_owner = rec.owner;
-
-	error = xfs_rmap_irec_offset_unpack(rec.offset, irec);
+	error = xfs_rmap_get_rec(rr->mcur, &cur->bc_rec.r, &stat);
 	if (error)
 		return error;
+	if (!stat)
+		return -EFSCORRUPTED;
 
-	return xrep_rtrmap_check_mapping(rr->sc, irec);
+	return 0;
 }
 
 /* Feed one of the new btree blocks to the bulk loader. */
@@ -685,7 +697,7 @@ xrep_rtrmap_build_new_tree(
 	struct xfs_scrub	*sc = rr->sc;
 	struct xfs_mount	*mp = sc->mp;
 	struct xfs_btree_cur	*cur;
-	uint64_t		nr_records;
+	struct xfs_buf		*mhead_bp;
 	int			error;
 
 	rr->rtrmap_bload.get_record = xrep_rtrmap_get_record;
@@ -694,14 +706,6 @@ xrep_rtrmap_build_new_tree(
 	xrep_bload_estimate_slack(sc, &rr->rtrmap_bload);
 
 	/*
-	 * Sort the rmap records by startblock or else the btree records
-	 * will be in the wrong order.
-	 */
-	error = xfarray_sort(rr->rtrmap_records, xrep_rtrmap_extent_cmp);
-	if (error)
-		return error;
-
-	/*
 	 * Prepare to construct the new btree by reserving disk space for the
 	 * new btree and setting up all the accounting information we'll need
 	 * to root the new btree while it's under construction and before we
@@ -712,11 +716,9 @@ xrep_rtrmap_build_new_tree(
 	cur = xfs_rtrmapbt_stage_cursor(sc->mp, mp->m_rrmapip,
 			&rr->new_btree_info.ifake);
 
-	nr_records = xfarray_length(rr->rtrmap_records);
-
 	/* Compute how many blocks we'll need for the rmaps collected. */
 	error = xfs_btree_bload_compute_geometry(cur, &rr->rtrmap_bload,
-			nr_records);
+			rr->nr_records);
 	if (error)
 		goto err_cur;
 
@@ -736,12 +738,26 @@ xrep_rtrmap_build_new_tree(
 	if (error)
 		goto err_cur;
 
+	/*
+	 * Create a cursor to the in-memory btree so that we can bulk load the
+	 * new btree.
+	 */
+	error = xfs_btree_mem_head_read_buf(rr->rtrmap_btree->target, NULL,
+			&mhead_bp);
+	if (error)
+		goto err_cur;
+
+	rr->mcur = xfs_rtrmapbt_mem_cursor(mp, NULL, mhead_bp,
+			rr->rtrmap_btree);
+	error = xfs_btree_goto_left_edge(rr->mcur);
+	if (error)
+		goto err_mcur;
+
 	/* Add all observed rmap records. */
 	rr->new_btree_info.ifake.if_fork->if_format = XFS_DINODE_FMT_RMAP;
-	rr->iter = 0;
 	error = xfs_btree_bload(cur, &rr->rtrmap_bload, rr);
 	if (error)
-		goto err_cur;
+		goto err_mcur;
 
 	/*
 	 * Install the new rtrmap btree in the inode.  After this point the old
@@ -750,6 +766,9 @@ xrep_rtrmap_build_new_tree(
 	 */
 	xfs_rtrmapbt_commit_staged_btree(cur, sc->tp);
 	xfs_btree_del_cursor(cur, 0);
+	xfs_btree_del_cursor(rr->mcur, 0);
+	rr->mcur = NULL;
+	xfs_buf_relse(mhead_bp);
 
 	/* Reset the inode counters now that we've changed the btree shape. */
 	error = xrep_rtrmap_reset_counters(rr);
@@ -758,8 +777,12 @@ xrep_rtrmap_build_new_tree(
 
 	/* Dispose of any unused blocks and the accounting information. */
 	xrep_newbt_destroy(&rr->new_btree_info, error);
+
 	return xrep_roll_trans(sc);
 
+err_mcur:
+	xfs_btree_del_cursor(rr->mcur, error);
+	xfs_buf_relse(mhead_bp);
 err_cur:
 	xfs_btree_del_cursor(cur, error);
 err_newbt:
@@ -810,10 +833,9 @@ xrep_rtrmapbt(
 	xbitmap_init(&rr->old_rtrmapbt_blocks);
 
 	/* Set up some storage */
-	rr->rtrmap_records = xfarray_create("rtrmap records",
-			sizeof(struct xrep_rtrmap_extent));
-	if (IS_ERR(rr->rtrmap_records)) {
-		error = PTR_ERR(rr->rtrmap_records);
+	rr->rtrmap_btree = xfs_rtrmapbt_mem_create(sc->mp, "rtrmap btree");
+	if (IS_ERR(rr->rtrmap_btree)) {
+		error = PTR_ERR(rr->rtrmap_btree);
 		goto out_bitmap;
 	}
 	rr->iscan.iget_tries = 20;
@@ -840,7 +862,7 @@ xrep_rtrmapbt(
 
 out_records:
 	xchk_iscan_finish(&rr->iscan);
-	xfarray_destroy(rr->rtrmap_records);
+	xfbtree_destroy(rr->rtrmap_btree);
 out_bitmap:
 	xbitmap_destroy(&rr->old_rtrmapbt_blocks);
 	kmem_free(rr);