Re: [PATCH 03/16] xfs: refactor the xrep_extent_list into xfs_bitmap

["Darrick J. Wong" <darrick.wong@oracle.com>]

On Fri, Jul 27, 2018 at 10:21:35AM -0400, Brian Foster wrote:
> On Wed, Jul 25, 2018 at 05:19:48PM -0700, Darrick J. Wong wrote:
> > From: Darrick J. Wong <darrick.wong@oracle.com>
> > 
> > As mentioned previously, the xrep_extent_list basically implements a
> > bitmap with two functions: set and disjoint union.  Rename all these
> > functions to xfs_bitmap to shorten the name and make it more obvious
> > what we're doing.
> > 
> > Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
> > ---
> >  fs/xfs/scrub/bitmap.c |  173 +++++++++++++++++++++++++------------------------
> >  fs/xfs/scrub/bitmap.h |   34 ++++------
> >  fs/xfs/scrub/repair.c |   85 +++++++++++-------------
> >  fs/xfs/scrub/repair.h |    8 +-
> >  fs/xfs/scrub/trace.h  |    1 
> >  5 files changed, 144 insertions(+), 157 deletions(-)
> > 
> > 
> > diff --git a/fs/xfs/scrub/bitmap.c b/fs/xfs/scrub/bitmap.c
> > index a7c2f4773f98..4840f5a1e179 100644
> > --- a/fs/xfs/scrub/bitmap.c
> > +++ b/fs/xfs/scrub/bitmap.c
> ...
> > @@ -82,117 +84,118 @@ xrep_btree_extent_cmp(
> >  }
> >  
> >  /*
> > - * Remove all the blocks mentioned in @sublist from the extents in @exlist.
> > + * Remove all the blocks mentioned in @sub from the extents in @bitmap.
> >   *
> >   * 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
> > + * for a given owner to generate @bitmap; and iterate all the blocks of the
> >   * metadata structures that are not being rebuilt and have the same rmapbt
> > - * owner to generate @sublist.  This routine subtracts all the extents
> > - * 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
> > + * owner to generate @sub.  This routine subtracts all the extents
> > + * mentioned in sub from all the extents linked in @bitmap, which leaves
> > + * @bitmap 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.
> > + * @bitmap can be reaped.
> > + *
> > + * This is the logical equivalent of bitmap &= ~sub.
> >   */
> >  #define LEFT_ALIGNED	(1 << 0)
> >  #define RIGHT_ALIGNED	(1 << 1)
> >  int
> > -xrep_subtract_extents(
> > -	struct xfs_scrub	*sc,
> > -	struct xrep_extent_list	*exlist,
> > -	struct xrep_extent_list	*sublist)
> > +xfs_bitmap_disunion(
> > +	struct xfs_bitmap	*bitmap,
> > +	struct xfs_bitmap	*sub)
> >  {
> >  	struct list_head	*lp;
> > -	struct xrep_extent	*ex;
> > -	struct xrep_extent	*newex;
> > -	struct xrep_extent	*subex;
> > +	struct xfs_bitmap_range	*br;
> > +	struct xfs_bitmap_range	*new_br;
> > +	struct xfs_bitmap_range	*sub_br;
> >  	xfs_fsblock_t		sub_fsb;
> > -	xfs_extlen_t		sub_len;
> > +	xfs_fsblock_t		sub_len;
> >  	int			state;
> >  	int			error = 0;
> >  
> > -	if (list_empty(&exlist->list) || list_empty(&sublist->list))
> > +	if (list_empty(&bitmap->list) || list_empty(&sub->list))
> >  		return 0;
> > -	ASSERT(!list_empty(&sublist->list));
> > +	ASSERT(!list_empty(&sub->list));
> >  
> > -	list_sort(NULL, &exlist->list, xrep_btree_extent_cmp);
> > -	list_sort(NULL, &sublist->list, xrep_btree_extent_cmp);
> > +	list_sort(NULL, &bitmap->list, xrep_btree_extent_cmp);
> > +	list_sort(NULL, &sub->list, xrep_btree_extent_cmp);
> 
> Still a couple xrep_ function names here.

Oops, I'll fix that.

> I guess I'm not clear on how generic this is intended to be..? FWIW,
> the xfs_bitmap->fsbno name stood out a bit to me as well (as opposed
> to something more generic like ->key or whatever).

I suppose if I ever want to turn this into a generic 64-bit bitmap
(right now it's just a fsblock bitmap) I should probably change the
type to uint64_t and rename the parameter fsbno->start or something.

It probably won't make this patch that much fatter so I'll take that
care of that too.

--D

> Brian
> 
> >  
> >  	/*
> > -	 * Now that we've sorted both lists, we iterate exlist once, rolling
> > -	 * forward through sublist and/or exlist as necessary until we find an
> > +	 * Now that we've sorted both lists, we iterate bitmap once, rolling
> > +	 * forward through sub and/or bitmap as necessary until we find an
> >  	 * overlap or reach the end of either list.  We do not reset lp to the
> > -	 * head of exlist nor do we reset subex to the head of sublist.  The
> > +	 * head of bitmap nor do we reset sub_br to the head of sub.  The
> >  	 * list traversal is similar to merge sort, but we're deleting
> >  	 * instead.  In this manner we avoid O(n^2) operations.
> >  	 */
> > -	subex = list_first_entry(&sublist->list, struct xrep_extent,
> > +	sub_br = list_first_entry(&sub->list, struct xfs_bitmap_range,
> >  			list);
> > -	lp = exlist->list.next;
> > -	while (lp != &exlist->list) {
> > -		ex = list_entry(lp, struct xrep_extent, list);
> > +	lp = bitmap->list.next;
> > +	while (lp != &bitmap->list) {
> > +		br = list_entry(lp, struct xfs_bitmap_range, list);
> >  
> >  		/*
> > -		 * Advance subex and/or ex until we find a pair that
> > +		 * Advance sub_br and/or br 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))
> > +		while (sub_br->fsbno + sub_br->len <= br->fsbno) {
> > +			if (list_is_last(&sub_br->list, &sub->list))
> >  				goto out;
> > -			subex = list_next_entry(subex, list);
> > +			sub_br = list_next_entry(sub_br, list);
> >  		}
> > -		if (subex->fsbno >= ex->fsbno + ex->len) {
> > +		if (sub_br->fsbno >= br->fsbno + br->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;
> > -			sub_fsb = ex->fsbno;
> > +		/* trim sub_br to fit the extent we have */
> > +		sub_fsb = sub_br->fsbno;
> > +		sub_len = sub_br->len;
> > +		if (sub_br->fsbno < br->fsbno) {
> > +			sub_len -= br->fsbno - sub_br->fsbno;
> > +			sub_fsb = br->fsbno;
> >  		}
> > -		if (sub_len > ex->len)
> > -			sub_len = ex->len;
> > +		if (sub_len > br->len)
> > +			sub_len = br->len;
> >  
> >  		state = 0;
> > -		if (sub_fsb == ex->fsbno)
> > +		if (sub_fsb == br->fsbno)
> >  			state |= LEFT_ALIGNED;
> > -		if (sub_fsb + sub_len == ex->fsbno + ex->len)
> > +		if (sub_fsb + sub_len == br->fsbno + br->len)
> >  			state |= RIGHT_ALIGNED;
> >  		switch (state) {
> >  		case LEFT_ALIGNED:
> >  			/* Coincides with only the left. */
> > -			ex->fsbno += sub_len;
> > -			ex->len -= sub_len;
> > +			br->fsbno += sub_len;
> > +			br->len -= sub_len;
> >  			break;
> >  		case RIGHT_ALIGNED:
> >  			/* Coincides with only the right. */
> > -			ex->len -= sub_len;
> > +			br->len -= sub_len;
> >  			lp = lp->next;
> >  			break;
> >  		case LEFT_ALIGNED | RIGHT_ALIGNED:
> >  			/* Total overlap, just delete ex. */
> >  			lp = lp->next;
> > -			list_del(&ex->list);
> > -			kmem_free(ex);
> > +			list_del(&br->list);
> > +			kmem_free(br);
> >  			break;
> >  		case 0:
> >  			/*
> >  			 * Deleting from the middle: add the new right extent
> >  			 * and then shrink the left extent.
> >  			 */
> > -			newex = kmem_alloc(sizeof(struct xrep_extent),
> > +			new_br = kmem_alloc(sizeof(struct xfs_bitmap_range),
> >  					KM_MAYFAIL);
> > -			if (!newex) {
> > +			if (!new_br) {
> >  				error = -ENOMEM;
> >  				goto out;
> >  			}
> > -			INIT_LIST_HEAD(&newex->list);
> > -			newex->fsbno = sub_fsb + sub_len;
> > -			newex->len = ex->fsbno + ex->len - newex->fsbno;
> > -			list_add(&newex->list, &ex->list);
> > -			ex->len = sub_fsb - ex->fsbno;
> > +			INIT_LIST_HEAD(&new_br->list);
> > +			new_br->fsbno = sub_fsb + sub_len;
> > +			new_br->len = br->fsbno + br->len - new_br->fsbno;
> > +			list_add(&new_br->list, &br->list);
> > +			br->len = sub_fsb - br->fsbno;
> >  			lp = lp->next;
> >  			break;
> >  		default:
> > diff --git a/fs/xfs/scrub/bitmap.h b/fs/xfs/scrub/bitmap.h
> > index 1038157695a8..3c39900e9269 100644
> > --- a/fs/xfs/scrub/bitmap.h
> > +++ b/fs/xfs/scrub/bitmap.h
> > @@ -6,32 +6,28 @@
> >  #ifndef __XFS_SCRUB_BITMAP_H__
> >  #define __XFS_SCRUB_BITMAP_H__
> >  
> > -struct xrep_extent {
> > +struct xfs_bitmap_range {
> >  	struct list_head	list;
> >  	xfs_fsblock_t		fsbno;
> > -	xfs_extlen_t		len;
> > +	xfs_fsblock_t		len;
> >  };
> >  
> > -struct xrep_extent_list {
> > +struct xfs_bitmap {
> >  	struct list_head	list;
> >  };
> >  
> > -static inline void
> > -xrep_init_extent_list(
> > -	struct xrep_extent_list		*exlist)
> > -{
> > -	INIT_LIST_HEAD(&exlist->list);
> > -}
> > +void xfs_bitmap_init(struct xfs_bitmap *bitmap);
> > +void xfs_bitmap_destroy(struct xfs_bitmap *bitmap);
> >  
> > -#define for_each_xrep_extent_safe(rbe, n, exlist) \
> > -	list_for_each_entry_safe((rbe), (n), &(exlist)->list, list)
> > -int xrep_collect_btree_extent(struct xfs_scrub *sc,
> > -		struct xrep_extent_list *btlist, xfs_fsblock_t fsbno,
> > -		xfs_extlen_t len);
> > -void xrep_cancel_btree_extents(struct xfs_scrub *sc,
> > -		struct xrep_extent_list *btlist);
> > -int xrep_subtract_extents(struct xfs_scrub *sc,
> > -		struct xrep_extent_list *exlist,
> > -		struct xrep_extent_list *sublist);
> > +#define for_each_xfs_bitmap_extent(bex, n, bitmap) \
> > +	list_for_each_entry_safe((bex), (n), &(bitmap)->list, list)
> > +
> > +#define for_each_xfs_bitmap_block(fsbno, bex, n, bitmap) \
> > +	list_for_each_entry_safe((bex), (n), &(bitmap)->list, list) \
> > +		for (fsbno = bex->fsbno; fsbno < bex->fsbno + bex->len; fsbno++)
> > +
> > +int xfs_bitmap_set(struct xfs_bitmap *bitmap, xfs_fsblock_t fsbno,
> > +		xfs_fsblock_t len);
> > +int xfs_bitmap_disunion(struct xfs_bitmap *bitmap, struct xfs_bitmap *sub);
> >  
> >  #endif	/* __XFS_SCRUB_BITMAP_H__ */
> > diff --git a/fs/xfs/scrub/repair.c b/fs/xfs/scrub/repair.c
> > index 27a904ef6189..85b048b341a0 100644
> > --- a/fs/xfs/scrub/repair.c
> > +++ b/fs/xfs/scrub/repair.c
> > @@ -368,17 +368,17 @@ xrep_init_btblock(
> >   *
> >   * However, that leaves the matter of removing all the metadata describing the
> >   * old broken structure.  For primary metadata we use the rmap data to collect
> > - * every extent with a matching rmap owner (exlist); we then iterate all other
> > + * every extent with a matching rmap owner (bitmap); we then iterate all other
> >   * metadata structures with the same rmap owner to collect the extents that
> > - * cannot be removed (sublist).  We then subtract sublist from exlist to
> > + * cannot be removed (sublist).  We then subtract sublist from bitmap to
> >   * derive the blocks that were used by the old btree.  These blocks can be
> >   * reaped.
> >   *
> >   * For rmapbt reconstructions we must use different tactics for extent
> >   * collection.  First we iterate all primary metadata (this excludes the old
> >   * rmapbt, obviously) to generate new rmap records.  The gaps in the rmap
> > - * records are collected as exlist.  The bnobt records are collected as
> > - * sublist.  As with the other btrees we subtract sublist from exlist, and the
> > + * records are collected as bitmap.  The bnobt records are collected as
> > + * sublist.  As with the other btrees we subtract sublist from bitmap, and the
> >   * result (since the rmapbt lives in the free space) are the blocks from the
> >   * old rmapbt.
> >   *
> > @@ -386,11 +386,11 @@ xrep_init_btblock(
> >   *
> >   * Now that we've constructed a new btree to replace the damaged one, we want
> >   * to dispose of the blocks that (we think) the old btree was using.
> > - * Previously, we used the rmapbt to collect the extents (exlist) with the
> > + * Previously, we used the rmapbt to collect the extents (bitmap) with the
> >   * rmap owner corresponding to the tree we rebuilt, collected extents for any
> >   * blocks with the same rmap owner that are owned by another data structure
> > - * (sublist), and subtracted sublist from exlist.  In theory the extents
> > - * remaining in exlist are the old btree's blocks.
> > + * (sublist), and subtracted sublist from bitmap.  In theory the extents
> > + * remaining in bitmap are the old btree's blocks.
> >   *
> >   * Unfortunately, it's possible that the btree was crosslinked with other
> >   * blocks on disk.  The rmap data can tell us if there are multiple owners, so
> > @@ -406,7 +406,7 @@ xrep_init_btblock(
> >   * If there are no rmap records at all, we also free the block.  If the btree
> >   * being rebuilt lives in the free space (bnobt/cntbt/rmapbt) then there isn't
> >   * supposed to be a rmap record and everything is ok.  For other btrees there
> > - * had to have been an rmap entry for the block to have ended up on @exlist,
> > + * had to have been an rmap entry for the block to have ended up on @bitmap,
> >   * so if it's gone now there's something wrong and the fs will shut down.
> >   *
> >   * Note: If there are multiple rmap records with only the same rmap owner as
> > @@ -419,7 +419,7 @@ xrep_init_btblock(
> >   * The caller is responsible for locking the AG headers for the entire rebuild
> >   * operation so that nothing else can sneak in and change the AG state while
> >   * we're not looking.  We also assume that the caller already invalidated any
> > - * buffers associated with @exlist.
> > + * buffers associated with @bitmap.
> >   */
> >  
> >  /*
> > @@ -429,13 +429,12 @@ xrep_init_btblock(
> >  int
> >  xrep_invalidate_blocks(
> >  	struct xfs_scrub	*sc,
> > -	struct xrep_extent_list	*exlist)
> > +	struct xfs_bitmap	*bitmap)
> >  {
> > -	struct xrep_extent	*rex;
> > -	struct xrep_extent	*n;
> > +	struct xfs_bitmap_range	*bmr;
> > +	struct xfs_bitmap_range	*n;
> >  	struct xfs_buf		*bp;
> >  	xfs_fsblock_t		fsbno;
> > -	xfs_agblock_t		i;
> >  
> >  	/*
> >  	 * For each block in each extent, see if there's an incore buffer for
> > @@ -445,18 +444,16 @@ xrep_invalidate_blocks(
> >  	 * because we never own those; and if we can't TRYLOCK the buffer we
> >  	 * assume it's owned by someone else.
> >  	 */
> > -	for_each_xrep_extent_safe(rex, n, exlist) {
> > -		for (fsbno = rex->fsbno, i = rex->len; i > 0; fsbno++, i--) {
> > -			/* Skip AG headers and post-EOFS blocks */
> > -			if (!xfs_verify_fsbno(sc->mp, fsbno))
> > -				continue;
> > -			bp = xfs_buf_incore(sc->mp->m_ddev_targp,
> > -					XFS_FSB_TO_DADDR(sc->mp, fsbno),
> > -					XFS_FSB_TO_BB(sc->mp, 1), XBF_TRYLOCK);
> > -			if (bp) {
> > -				xfs_trans_bjoin(sc->tp, bp);
> > -				xfs_trans_binval(sc->tp, bp);
> > -			}
> > +	for_each_xfs_bitmap_block(fsbno, bmr, n, bitmap) {
> > +		/* Skip AG headers and post-EOFS blocks */
> > +		if (!xfs_verify_fsbno(sc->mp, fsbno))
> > +			continue;
> > +		bp = xfs_buf_incore(sc->mp->m_ddev_targp,
> > +				XFS_FSB_TO_DADDR(sc->mp, fsbno),
> > +				XFS_FSB_TO_BB(sc->mp, 1), XBF_TRYLOCK);
> > +		if (bp) {
> > +			xfs_trans_bjoin(sc->tp, bp);
> > +			xfs_trans_binval(sc->tp, bp);
> >  		}
> >  	}
> >  
> > @@ -519,9 +516,9 @@ xrep_put_freelist(
> >  	return 0;
> >  }
> >  
> > -/* Dispose of a single metadata block. */
> > +/* Dispose of a single block. */
> >  STATIC int
> > -xrep_dispose_btree_block(
> > +xrep_reap_block(
> >  	struct xfs_scrub	*sc,
> >  	xfs_fsblock_t		fsbno,
> >  	struct xfs_owner_info	*oinfo,
> > @@ -593,41 +590,35 @@ xrep_dispose_btree_block(
> >  	return error;
> >  }
> >  
> > -/* Dispose of btree blocks from an old per-AG btree. */
> > +/* Dispose of every block of every extent in the bitmap. */
> >  int
> > -xrep_reap_btree_extents(
> > +xrep_reap_extents(
> >  	struct xfs_scrub	*sc,
> > -	struct xrep_extent_list	*exlist,
> > +	struct xfs_bitmap	*bitmap,
> >  	struct xfs_owner_info	*oinfo,
> >  	enum xfs_ag_resv_type	type)
> >  {
> > -	struct xrep_extent	*rex;
> > -	struct xrep_extent	*n;
> > +	struct xfs_bitmap_range	*bmr;
> > +	struct xfs_bitmap_range	*n;
> > +	xfs_fsblock_t		fsbno;
> >  	int			error = 0;
> >  
> >  	ASSERT(xfs_sb_version_hasrmapbt(&sc->mp->m_sb));
> >  
> > -	/* Dispose of every block from the old btree. */
> > -	for_each_xrep_extent_safe(rex, n, exlist) {
> > +	for_each_xfs_bitmap_block(fsbno, bmr, n, bitmap) {
> >  		ASSERT(sc->ip != NULL ||
> > -		       XFS_FSB_TO_AGNO(sc->mp, rex->fsbno) == sc->sa.agno);
> > -
> > +		       XFS_FSB_TO_AGNO(sc->mp, fsbno) == sc->sa.agno);
> >  		trace_xrep_dispose_btree_extent(sc->mp,
> > -				XFS_FSB_TO_AGNO(sc->mp, rex->fsbno),
> > -				XFS_FSB_TO_AGBNO(sc->mp, rex->fsbno), rex->len);
> > +				XFS_FSB_TO_AGNO(sc->mp, fsbno),
> > +				XFS_FSB_TO_AGBNO(sc->mp, fsbno), 1);
> >  
> > -		for (; rex->len > 0; rex->len--, rex->fsbno++) {
> > -			error = xrep_dispose_btree_block(sc, rex->fsbno,
> > -					oinfo, type);
> > -			if (error)
> > -				goto out;
> > -		}
> > -		list_del(&rex->list);
> > -		kmem_free(rex);
> > +		error = xrep_reap_block(sc, fsbno, oinfo, type);
> > +		if (error)
> > +			goto out;
> >  	}
> >  
> >  out:
> > -	xrep_cancel_btree_extents(sc, exlist);
> > +	xfs_bitmap_destroy(bitmap);
> >  	return error;
> >  }
> >  
> > diff --git a/fs/xfs/scrub/repair.h b/fs/xfs/scrub/repair.h
> > index a3d491a438f4..5a4e92221916 100644
> > --- a/fs/xfs/scrub/repair.h
> > +++ b/fs/xfs/scrub/repair.h
> > @@ -27,13 +27,11 @@ int xrep_init_btblock(struct xfs_scrub *sc, xfs_fsblock_t fsb,
> >  		struct xfs_buf **bpp, xfs_btnum_t btnum,
> >  		const struct xfs_buf_ops *ops);
> >  
> > -struct xrep_extent_list;
> > +struct xfs_bitmap;
> >  
> >  int xrep_fix_freelist(struct xfs_scrub *sc, bool can_shrink);
> > -int xrep_invalidate_blocks(struct xfs_scrub *sc,
> > -		struct xrep_extent_list *btlist);
> > -int xrep_reap_btree_extents(struct xfs_scrub *sc,
> > -		struct xrep_extent_list *exlist,
> > +int xrep_invalidate_blocks(struct xfs_scrub *sc, struct xfs_bitmap *btlist);
> > +int xrep_reap_extents(struct xfs_scrub *sc, struct xfs_bitmap *exlist,
> >  		struct xfs_owner_info *oinfo, enum xfs_ag_resv_type type);
> >  
> >  struct xrep_find_ag_btree {
> > diff --git a/fs/xfs/scrub/trace.h b/fs/xfs/scrub/trace.h
> > index 93db22c39b51..4e20f0e48232 100644
> > --- a/fs/xfs/scrub/trace.h
> > +++ b/fs/xfs/scrub/trace.h
> > @@ -511,7 +511,6 @@ DEFINE_EVENT(xrep_extent_class, name, \
> >  		 xfs_agblock_t agbno, xfs_extlen_t len), \
> >  	TP_ARGS(mp, agno, agbno, len))
> >  DEFINE_REPAIR_EXTENT_EVENT(xrep_dispose_btree_extent);
> > -DEFINE_REPAIR_EXTENT_EVENT(xrep_collect_btree_extent);
> >  DEFINE_REPAIR_EXTENT_EVENT(xrep_agfl_insert);
> >  
> >  DECLARE_EVENT_CLASS(xrep_rmap_class,
> > 
> > --
> > To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> --
> To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html