| Message ID | 153256437975.29021.14919845411774307079.stgit@magnolia (mailing list archive) |
|---|---|
| State | Accepted |
| Headers | show |
| Series | xfs-4.19: online repair support | expand |
On Wed, Jul 25, 2018 at 05:19:39PM -0700, Darrick J. Wong wrote: > From: Darrick J. Wong <darrick.wong@oracle.com> > > Move the xrep_extent_list code into a separate file. Logically, this > data structure is really just a clumsy bitmap, and in the next patch > we'll make this more obvious. No functional changes. > > Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com> > --- I'm not terribly familiar with the existing code, but looks like a straight move: Reviewed-by: Brian Foster <bfoster@redhat.com> > fs/xfs/Makefile | 1 > fs/xfs/scrub/bitmap.c | 208 +++++++++++++++++++++++++++++++++++++++++++++++++ > fs/xfs/scrub/bitmap.h | 37 +++++++++ > fs/xfs/scrub/repair.c | 194 ---------------------------------------------- > fs/xfs/scrub/repair.h | 27 ------ > 5 files changed, 248 insertions(+), 219 deletions(-) > create mode 100644 fs/xfs/scrub/bitmap.c > create mode 100644 fs/xfs/scrub/bitmap.h > > > diff --git a/fs/xfs/Makefile b/fs/xfs/Makefile > index a36cccbec169..57ec46951ede 100644 > --- a/fs/xfs/Makefile > +++ b/fs/xfs/Makefile > @@ -164,6 +164,7 @@ xfs-$(CONFIG_XFS_QUOTA) += scrub/quota.o > ifeq ($(CONFIG_XFS_ONLINE_REPAIR),y) > xfs-y += $(addprefix scrub/, \ > agheader_repair.o \ > + bitmap.o \ > repair.o \ > ) > endif > diff --git a/fs/xfs/scrub/bitmap.c b/fs/xfs/scrub/bitmap.c > new file mode 100644 > index 000000000000..a7c2f4773f98 > --- /dev/null > +++ b/fs/xfs/scrub/bitmap.c > @@ -0,0 +1,208 @@ > +// SPDX-License-Identifier: GPL-2.0+ > +/* > + * Copyright (C) 2018 Oracle. All Rights Reserved. > + * Author: Darrick J. Wong <darrick.wong@oracle.com> > + */ > +#include "xfs.h" > +#include "xfs_fs.h" > +#include "xfs_shared.h" > +#include "xfs_format.h" > +#include "xfs_trans_resv.h" > +#include "xfs_mount.h" > +#include "scrub/xfs_scrub.h" > +#include "scrub/scrub.h" > +#include "scrub/common.h" > +#include "scrub/trace.h" > +#include "scrub/repair.h" > +#include "scrub/bitmap.h" > + > +/* Collect a dead btree extent for later disposal. */ > +int > +xrep_collect_btree_extent( > + struct xfs_scrub *sc, > + struct xrep_extent_list *exlist, > + xfs_fsblock_t fsbno, > + xfs_extlen_t len) > +{ > + struct xrep_extent *rex; > + > + trace_xrep_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 xrep_extent), KM_MAYFAIL); > + if (!rex) > + return -ENOMEM; > + > + INIT_LIST_HEAD(&rex->list); > + rex->fsbno = fsbno; > + rex->len = len; > + list_add_tail(&rex->list, &exlist->list); > + > + return 0; > +} > + > +/* > + * An error happened during the rebuild so the transaction will be cancelled. > + * The fs will shut down, and the administrator has to unmount and run repair. > + * Therefore, free all the memory associated with the list so we can die. > + */ > +void > +xrep_cancel_btree_extents( > + struct xfs_scrub *sc, > + struct xrep_extent_list *exlist) > +{ > + struct xrep_extent *rex; > + struct xrep_extent *n; > + > + for_each_xrep_extent_safe(rex, n, exlist) { > + list_del(&rex->list); > + kmem_free(rex); > + } > +} > + > +/* Compare two btree extents. */ > +static int > +xrep_btree_extent_cmp( > + void *priv, > + struct list_head *a, > + struct list_head *b) > +{ > + struct xrep_extent *ap; > + struct xrep_extent *bp; > + > + ap = container_of(a, struct xrep_extent, list); > + bp = container_of(b, struct xrep_extent, list); > + > + if (ap->fsbno > bp->fsbno) > + return 1; > + if (ap->fsbno < bp->fsbno) > + return -1; > + 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 > + * 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 > + * are the dead blocks of the old metadata structure. The blocks mentioned in > + * @exlist can be reaped. > + */ > +#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) > +{ > + struct list_head *lp; > + struct xrep_extent *ex; > + struct xrep_extent *newex; > + struct xrep_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, xrep_btree_extent_cmp); > + list_sort(NULL, &sublist->list, xrep_btree_extent_cmp); > + > + /* > + * Now that we've sorted both lists, we iterate exlist once, rolling > + * forward through sublist and/or exlist 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 > + * 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, > + list); > + lp = exlist->list.next; > + while (lp != &exlist->list) { > + ex = list_entry(lp, struct xrep_extent, list); > + > + /* > + * 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); > + } > + 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; > + sub_fsb = ex->fsbno; > + } > + if (sub_len > ex->len) > + sub_len = ex->len; > + > + state = 0; > + if (sub_fsb == ex->fsbno) > + state |= LEFT_ALIGNED; > + if (sub_fsb + sub_len == ex->fsbno + ex->len) > + state |= RIGHT_ALIGNED; > + switch (state) { > + case LEFT_ALIGNED: > + /* Coincides with only the left. */ > + ex->fsbno += sub_len; > + ex->len -= sub_len; > + break; > + case RIGHT_ALIGNED: > + /* Coincides with only the right. */ > + ex->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); > + 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), > + KM_MAYFAIL); > + if (!newex) { > + 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; > + lp = lp->next; > + break; > + default: > + ASSERT(0); > + break; > + } > + } > + > +out: > + return error; > +} > +#undef LEFT_ALIGNED > +#undef RIGHT_ALIGNED > diff --git a/fs/xfs/scrub/bitmap.h b/fs/xfs/scrub/bitmap.h > new file mode 100644 > index 000000000000..1038157695a8 > --- /dev/null > +++ b/fs/xfs/scrub/bitmap.h > @@ -0,0 +1,37 @@ > +// SPDX-License-Identifier: GPL-2.0+ > +/* > + * Copyright (C) 2018 Oracle. All Rights Reserved. > + * Author: Darrick J. Wong <darrick.wong@oracle.com> > + */ > +#ifndef __XFS_SCRUB_BITMAP_H__ > +#define __XFS_SCRUB_BITMAP_H__ > + > +struct xrep_extent { > + struct list_head list; > + xfs_fsblock_t fsbno; > + xfs_extlen_t len; > +}; > + > +struct xrep_extent_list { > + struct list_head list; > +}; > + > +static inline void > +xrep_init_extent_list( > + struct xrep_extent_list *exlist) > +{ > + INIT_LIST_HEAD(&exlist->list); > +} > + > +#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); > + > +#endif /* __XFS_SCRUB_BITMAP_H__ */ > diff --git a/fs/xfs/scrub/repair.c b/fs/xfs/scrub/repair.c > index 5de1cac424ec..27a904ef6189 100644 > --- a/fs/xfs/scrub/repair.c > +++ b/fs/xfs/scrub/repair.c > @@ -34,6 +34,7 @@ > #include "scrub/common.h" > #include "scrub/trace.h" > #include "scrub/repair.h" > +#include "scrub/bitmap.h" > > /* > * Attempt to repair some metadata, if the metadata is corrupt and userspace > @@ -380,200 +381,7 @@ xrep_init_btblock( > * sublist. As with the other btrees we subtract sublist from exlist, and the > * result (since the rmapbt lives in the free space) are the blocks from the > * old rmapbt. > - */ > - > -/* Collect a dead btree extent for later disposal. */ > -int > -xrep_collect_btree_extent( > - struct xfs_scrub *sc, > - struct xrep_extent_list *exlist, > - xfs_fsblock_t fsbno, > - xfs_extlen_t len) > -{ > - struct xrep_extent *rex; > - > - trace_xrep_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 xrep_extent), KM_MAYFAIL); > - if (!rex) > - return -ENOMEM; > - > - INIT_LIST_HEAD(&rex->list); > - rex->fsbno = fsbno; > - rex->len = len; > - list_add_tail(&rex->list, &exlist->list); > - > - return 0; > -} > - > -/* > - * An error happened during the rebuild so the transaction will be cancelled. > - * The fs will shut down, and the administrator has to unmount and run repair. > - * Therefore, free all the memory associated with the list so we can die. > - */ > -void > -xrep_cancel_btree_extents( > - struct xfs_scrub *sc, > - struct xrep_extent_list *exlist) > -{ > - struct xrep_extent *rex; > - struct xrep_extent *n; > - > - for_each_xrep_extent_safe(rex, n, exlist) { > - list_del(&rex->list); > - kmem_free(rex); > - } > -} > - > -/* Compare two btree extents. */ > -static int > -xrep_btree_extent_cmp( > - void *priv, > - struct list_head *a, > - struct list_head *b) > -{ > - struct xrep_extent *ap; > - struct xrep_extent *bp; > - > - ap = container_of(a, struct xrep_extent, list); > - bp = container_of(b, struct xrep_extent, list); > - > - if (ap->fsbno > bp->fsbno) > - return 1; > - if (ap->fsbno < bp->fsbno) > - return -1; > - 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 > - * 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 > - * are the dead blocks of the old metadata structure. The blocks mentioned in > - * @exlist can be reaped. > - */ > -#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) > -{ > - struct list_head *lp; > - struct xrep_extent *ex; > - struct xrep_extent *newex; > - struct xrep_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, xrep_btree_extent_cmp); > - list_sort(NULL, &sublist->list, xrep_btree_extent_cmp); > - > - /* > - * Now that we've sorted both lists, we iterate exlist once, rolling > - * forward through sublist and/or exlist 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 > - * 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, > - list); > - lp = exlist->list.next; > - while (lp != &exlist->list) { > - ex = list_entry(lp, struct xrep_extent, list); > - > - /* > - * 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); > - } > - 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; > - sub_fsb = ex->fsbno; > - } > - if (sub_len > ex->len) > - sub_len = ex->len; > - > - state = 0; > - if (sub_fsb == ex->fsbno) > - state |= LEFT_ALIGNED; > - if (sub_fsb + sub_len == ex->fsbno + ex->len) > - state |= RIGHT_ALIGNED; > - switch (state) { > - case LEFT_ALIGNED: > - /* Coincides with only the left. */ > - ex->fsbno += sub_len; > - ex->len -= sub_len; > - break; > - case RIGHT_ALIGNED: > - /* Coincides with only the right. */ > - ex->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); > - 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), > - KM_MAYFAIL); > - if (!newex) { > - 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; > - lp = lp->next; > - break; > - default: > - ASSERT(0); > - break; > - } > - } > - > -out: > - return error; > -} > -#undef LEFT_ALIGNED > -#undef RIGHT_ALIGNED > - > -/* > * Disposal of Blocks from Old per-AG Btrees > * > * Now that we've constructed a new btree to replace the damaged one, we want > diff --git a/fs/xfs/scrub/repair.h b/fs/xfs/scrub/repair.h > index 91355f6b0087..a3d491a438f4 100644 > --- a/fs/xfs/scrub/repair.h > +++ b/fs/xfs/scrub/repair.h > @@ -27,33 +27,8 @@ 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 { > - struct list_head list; > - xfs_fsblock_t fsbno; > - xfs_extlen_t len; > -}; > - > -struct xrep_extent_list { > - struct list_head list; > -}; > - > -static inline void > -xrep_init_extent_list( > - struct xrep_extent_list *exlist) > -{ > - INIT_LIST_HEAD(&exlist->list); > -} > +struct xrep_extent_list; > > -#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); > int xrep_fix_freelist(struct xfs_scrub *sc, bool can_shrink); > int xrep_invalidate_blocks(struct xfs_scrub *sc, > struct xrep_extent_list *btlist); > > -- > 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
diff --git a/fs/xfs/Makefile b/fs/xfs/Makefile index a36cccbec169..57ec46951ede 100644 --- a/fs/xfs/Makefile +++ b/fs/xfs/Makefile @@ -164,6 +164,7 @@ xfs-$(CONFIG_XFS_QUOTA) += scrub/quota.o ifeq ($(CONFIG_XFS_ONLINE_REPAIR),y) xfs-y += $(addprefix scrub/, \ agheader_repair.o \ + bitmap.o \ repair.o \ ) endif diff --git a/fs/xfs/scrub/bitmap.c b/fs/xfs/scrub/bitmap.c new file mode 100644 index 000000000000..a7c2f4773f98 --- /dev/null +++ b/fs/xfs/scrub/bitmap.c @@ -0,0 +1,208 @@ +// SPDX-License-Identifier: GPL-2.0+ +/* + * Copyright (C) 2018 Oracle. All Rights Reserved. + * Author: Darrick J. Wong <darrick.wong@oracle.com> + */ +#include "xfs.h" +#include "xfs_fs.h" +#include "xfs_shared.h" +#include "xfs_format.h" +#include "xfs_trans_resv.h" +#include "xfs_mount.h" +#include "scrub/xfs_scrub.h" +#include "scrub/scrub.h" +#include "scrub/common.h" +#include "scrub/trace.h" +#include "scrub/repair.h" +#include "scrub/bitmap.h" + +/* Collect a dead btree extent for later disposal. */ +int +xrep_collect_btree_extent( + struct xfs_scrub *sc, + struct xrep_extent_list *exlist, + xfs_fsblock_t fsbno, + xfs_extlen_t len) +{ + struct xrep_extent *rex; + + trace_xrep_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 xrep_extent), KM_MAYFAIL); + if (!rex) + return -ENOMEM; + + INIT_LIST_HEAD(&rex->list); + rex->fsbno = fsbno; + rex->len = len; + list_add_tail(&rex->list, &exlist->list); + + return 0; +} + +/* + * An error happened during the rebuild so the transaction will be cancelled. + * The fs will shut down, and the administrator has to unmount and run repair. + * Therefore, free all the memory associated with the list so we can die. + */ +void +xrep_cancel_btree_extents( + struct xfs_scrub *sc, + struct xrep_extent_list *exlist) +{ + struct xrep_extent *rex; + struct xrep_extent *n; + + for_each_xrep_extent_safe(rex, n, exlist) { + list_del(&rex->list); + kmem_free(rex); + } +} + +/* Compare two btree extents. */ +static int +xrep_btree_extent_cmp( + void *priv, + struct list_head *a, + struct list_head *b) +{ + struct xrep_extent *ap; + struct xrep_extent *bp; + + ap = container_of(a, struct xrep_extent, list); + bp = container_of(b, struct xrep_extent, list); + + if (ap->fsbno > bp->fsbno) + return 1; + if (ap->fsbno < bp->fsbno) + return -1; + 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 + * 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 + * are the dead blocks of the old metadata structure. The blocks mentioned in + * @exlist can be reaped. + */ +#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) +{ + struct list_head *lp; + struct xrep_extent *ex; + struct xrep_extent *newex; + struct xrep_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, xrep_btree_extent_cmp); + list_sort(NULL, &sublist->list, xrep_btree_extent_cmp); + + /* + * Now that we've sorted both lists, we iterate exlist once, rolling + * forward through sublist and/or exlist 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 + * 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, + list); + lp = exlist->list.next; + while (lp != &exlist->list) { + ex = list_entry(lp, struct xrep_extent, list); + + /* + * 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); + } + 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; + sub_fsb = ex->fsbno; + } + if (sub_len > ex->len) + sub_len = ex->len; + + state = 0; + if (sub_fsb == ex->fsbno) + state |= LEFT_ALIGNED; + if (sub_fsb + sub_len == ex->fsbno + ex->len) + state |= RIGHT_ALIGNED; + switch (state) { + case LEFT_ALIGNED: + /* Coincides with only the left. */ + ex->fsbno += sub_len; + ex->len -= sub_len; + break; + case RIGHT_ALIGNED: + /* Coincides with only the right. */ + ex->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); + 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), + KM_MAYFAIL); + if (!newex) { + 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; + lp = lp->next; + break; + default: + ASSERT(0); + break; + } + } + +out: + return error; +} +#undef LEFT_ALIGNED +#undef RIGHT_ALIGNED diff --git a/fs/xfs/scrub/bitmap.h b/fs/xfs/scrub/bitmap.h new file mode 100644 index 000000000000..1038157695a8 --- /dev/null +++ b/fs/xfs/scrub/bitmap.h @@ -0,0 +1,37 @@ +// SPDX-License-Identifier: GPL-2.0+ +/* + * Copyright (C) 2018 Oracle. All Rights Reserved. + * Author: Darrick J. Wong <darrick.wong@oracle.com> + */ +#ifndef __XFS_SCRUB_BITMAP_H__ +#define __XFS_SCRUB_BITMAP_H__ + +struct xrep_extent { + struct list_head list; + xfs_fsblock_t fsbno; + xfs_extlen_t len; +}; + +struct xrep_extent_list { + struct list_head list; +}; + +static inline void +xrep_init_extent_list( + struct xrep_extent_list *exlist) +{ + INIT_LIST_HEAD(&exlist->list); +} + +#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); + +#endif /* __XFS_SCRUB_BITMAP_H__ */ diff --git a/fs/xfs/scrub/repair.c b/fs/xfs/scrub/repair.c index 5de1cac424ec..27a904ef6189 100644 --- a/fs/xfs/scrub/repair.c +++ b/fs/xfs/scrub/repair.c @@ -34,6 +34,7 @@ #include "scrub/common.h" #include "scrub/trace.h" #include "scrub/repair.h" +#include "scrub/bitmap.h" /* * Attempt to repair some metadata, if the metadata is corrupt and userspace @@ -380,200 +381,7 @@ xrep_init_btblock( * sublist. As with the other btrees we subtract sublist from exlist, and the * result (since the rmapbt lives in the free space) are the blocks from the * old rmapbt. - */ - -/* Collect a dead btree extent for later disposal. */ -int -xrep_collect_btree_extent( - struct xfs_scrub *sc, - struct xrep_extent_list *exlist, - xfs_fsblock_t fsbno, - xfs_extlen_t len) -{ - struct xrep_extent *rex; - - trace_xrep_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 xrep_extent), KM_MAYFAIL); - if (!rex) - return -ENOMEM; - - INIT_LIST_HEAD(&rex->list); - rex->fsbno = fsbno; - rex->len = len; - list_add_tail(&rex->list, &exlist->list); - - return 0; -} - -/* - * An error happened during the rebuild so the transaction will be cancelled. - * The fs will shut down, and the administrator has to unmount and run repair. - * Therefore, free all the memory associated with the list so we can die. - */ -void -xrep_cancel_btree_extents( - struct xfs_scrub *sc, - struct xrep_extent_list *exlist) -{ - struct xrep_extent *rex; - struct xrep_extent *n; - - for_each_xrep_extent_safe(rex, n, exlist) { - list_del(&rex->list); - kmem_free(rex); - } -} - -/* Compare two btree extents. */ -static int -xrep_btree_extent_cmp( - void *priv, - struct list_head *a, - struct list_head *b) -{ - struct xrep_extent *ap; - struct xrep_extent *bp; - - ap = container_of(a, struct xrep_extent, list); - bp = container_of(b, struct xrep_extent, list); - - if (ap->fsbno > bp->fsbno) - return 1; - if (ap->fsbno < bp->fsbno) - return -1; - 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 - * 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 - * are the dead blocks of the old metadata structure. The blocks mentioned in - * @exlist can be reaped. - */ -#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) -{ - struct list_head *lp; - struct xrep_extent *ex; - struct xrep_extent *newex; - struct xrep_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, xrep_btree_extent_cmp); - list_sort(NULL, &sublist->list, xrep_btree_extent_cmp); - - /* - * Now that we've sorted both lists, we iterate exlist once, rolling - * forward through sublist and/or exlist 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 - * 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, - list); - lp = exlist->list.next; - while (lp != &exlist->list) { - ex = list_entry(lp, struct xrep_extent, list); - - /* - * 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); - } - 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; - sub_fsb = ex->fsbno; - } - if (sub_len > ex->len) - sub_len = ex->len; - - state = 0; - if (sub_fsb == ex->fsbno) - state |= LEFT_ALIGNED; - if (sub_fsb + sub_len == ex->fsbno + ex->len) - state |= RIGHT_ALIGNED; - switch (state) { - case LEFT_ALIGNED: - /* Coincides with only the left. */ - ex->fsbno += sub_len; - ex->len -= sub_len; - break; - case RIGHT_ALIGNED: - /* Coincides with only the right. */ - ex->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); - 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), - KM_MAYFAIL); - if (!newex) { - 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; - lp = lp->next; - break; - default: - ASSERT(0); - break; - } - } - -out: - return error; -} -#undef LEFT_ALIGNED -#undef RIGHT_ALIGNED - -/* * Disposal of Blocks from Old per-AG Btrees * * Now that we've constructed a new btree to replace the damaged one, we want diff --git a/fs/xfs/scrub/repair.h b/fs/xfs/scrub/repair.h index 91355f6b0087..a3d491a438f4 100644 --- a/fs/xfs/scrub/repair.h +++ b/fs/xfs/scrub/repair.h @@ -27,33 +27,8 @@ 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 { - struct list_head list; - xfs_fsblock_t fsbno; - xfs_extlen_t len; -}; - -struct xrep_extent_list { - struct list_head list; -}; - -static inline void -xrep_init_extent_list( - struct xrep_extent_list *exlist) -{ - INIT_LIST_HEAD(&exlist->list); -} +struct xrep_extent_list; -#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); int xrep_fix_freelist(struct xfs_scrub *sc, bool can_shrink); int xrep_invalidate_blocks(struct xfs_scrub *sc, struct xrep_extent_list *btlist);