| Message ID | 153292967384.24509.6676118910447905441.stgit@magnolia (mailing list archive) |
|---|---|
| State | Accepted |
| Headers | show |
| Series | xfs-4.19: online repair support | expand |
On Sun, Jul 29, 2018 at 10:47:54PM -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> > --- Reviewed-by: Brian Foster <bfoster@redhat.com> > fs/xfs/scrub/bitmap.c | 183 +++++++++++++++++++++++++------------------------ > fs/xfs/scrub/bitmap.h | 35 ++++----- > fs/xfs/scrub/repair.c | 85 ++++++++++------------- > fs/xfs/scrub/repair.h | 8 +- > fs/xfs/scrub/trace.h | 1 > 5 files changed, 149 insertions(+), 163 deletions(-) > > > diff --git a/fs/xfs/scrub/bitmap.c b/fs/xfs/scrub/bitmap.c > index a7c2f4773f98..c770e2d0b6aa 100644 > --- a/fs/xfs/scrub/bitmap.c > +++ b/fs/xfs/scrub/bitmap.c > @@ -16,183 +16,186 @@ > #include "scrub/repair.h" > #include "scrub/bitmap.h" > > -/* Collect a dead btree extent for later disposal. */ > +/* > + * Set a range of this bitmap. Caller must ensure the range is not set. > + * > + * This is the logical equivalent of bitmap |= mask(start, len). > + */ > int > -xrep_collect_btree_extent( > - struct xfs_scrub *sc, > - struct xrep_extent_list *exlist, > - xfs_fsblock_t fsbno, > - xfs_extlen_t len) > +xfs_bitmap_set( > + struct xfs_bitmap *bitmap, > + uint64_t start, > + uint64_t len) > { > - struct xrep_extent *rex; > + struct xfs_bitmap_range *bmr; > > - 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) > + bmr = kmem_alloc(sizeof(struct xfs_bitmap_range), KM_MAYFAIL); > + if (!bmr) > return -ENOMEM; > > - INIT_LIST_HEAD(&rex->list); > - rex->fsbno = fsbno; > - rex->len = len; > - list_add_tail(&rex->list, &exlist->list); > + INIT_LIST_HEAD(&bmr->list); > + bmr->start = start; > + bmr->len = len; > + list_add_tail(&bmr->list, &bitmap->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. > - */ > +/* Free everything related to this bitmap. */ > void > -xrep_cancel_btree_extents( > - struct xfs_scrub *sc, > - struct xrep_extent_list *exlist) > +xfs_bitmap_destroy( > + struct xfs_bitmap *bitmap) > { > - struct xrep_extent *rex; > - struct xrep_extent *n; > + struct xfs_bitmap_range *bmr; > + struct xfs_bitmap_range *n; > > - for_each_xrep_extent_safe(rex, n, exlist) { > - list_del(&rex->list); > - kmem_free(rex); > + for_each_xfs_bitmap_extent(bmr, n, bitmap) { > + list_del(&bmr->list); > + kmem_free(bmr); > } > } > > +/* Set up a per-AG block bitmap. */ > +void > +xfs_bitmap_init( > + struct xfs_bitmap *bitmap) > +{ > + INIT_LIST_HEAD(&bitmap->list); > +} > + > /* Compare two btree extents. */ > static int > -xrep_btree_extent_cmp( > +xfs_bitmap_range_cmp( > void *priv, > struct list_head *a, > struct list_head *b) > { > - struct xrep_extent *ap; > - struct xrep_extent *bp; > + struct xfs_bitmap_range *ap; > + struct xfs_bitmap_range *bp; > > - ap = container_of(a, struct xrep_extent, list); > - bp = container_of(b, struct xrep_extent, list); > + ap = container_of(a, struct xfs_bitmap_range, list); > + bp = container_of(b, struct xfs_bitmap_range, list); > > - if (ap->fsbno > bp->fsbno) > + if (ap->start > bp->start) > return 1; > - if (ap->fsbno < bp->fsbno) > + if (ap->start < bp->start) > return -1; > return 0; > } > > /* > - * 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; > - xfs_fsblock_t sub_fsb; > - xfs_extlen_t sub_len; > + struct xfs_bitmap_range *br; > + struct xfs_bitmap_range *new_br; > + struct xfs_bitmap_range *sub_br; > + uint64_t sub_start; > + uint64_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, xfs_bitmap_range_cmp); > + list_sort(NULL, &sub->list, xfs_bitmap_range_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 > + * 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->start + sub_br->len <= br->start) { > + 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->start >= br->start + 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_start = sub_br->start; > + sub_len = sub_br->len; > + if (sub_br->start < br->start) { > + sub_len -= br->start - sub_br->start; > + sub_start = br->start; > } > - 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_start == br->start) > state |= LEFT_ALIGNED; > - if (sub_fsb + sub_len == ex->fsbno + ex->len) > + if (sub_start + sub_len == br->start + br->len) > state |= RIGHT_ALIGNED; > switch (state) { > case LEFT_ALIGNED: > /* Coincides with only the left. */ > - ex->fsbno += sub_len; > - ex->len -= sub_len; > + br->start += 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->start = sub_start + sub_len; > + new_br->len = br->start + br->len - new_br->start; > + list_add(&new_br->list, &br->list); > + br->len = sub_start - br->start; > lp = lp->next; > break; > default: > diff --git a/fs/xfs/scrub/bitmap.h b/fs/xfs/scrub/bitmap.h > index 1038157695a8..dad652ee9177 100644 > --- a/fs/xfs/scrub/bitmap.h > +++ b/fs/xfs/scrub/bitmap.h > @@ -6,32 +6,27 @@ > #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; > + uint64_t start; > + uint64_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(b, bex, n, bitmap) \ > + list_for_each_entry_safe((bex), (n), &(bitmap)->list, list) \ > + for ((b) = bex->start; (b) < bex->start + bex->len; (b)++) > + > +int xfs_bitmap_set(struct xfs_bitmap *bitmap, uint64_t start, uint64_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
diff --git a/fs/xfs/scrub/bitmap.c b/fs/xfs/scrub/bitmap.c index a7c2f4773f98..c770e2d0b6aa 100644 --- a/fs/xfs/scrub/bitmap.c +++ b/fs/xfs/scrub/bitmap.c @@ -16,183 +16,186 @@ #include "scrub/repair.h" #include "scrub/bitmap.h" -/* Collect a dead btree extent for later disposal. */ +/* + * Set a range of this bitmap. Caller must ensure the range is not set. + * + * This is the logical equivalent of bitmap |= mask(start, len). + */ int -xrep_collect_btree_extent( - struct xfs_scrub *sc, - struct xrep_extent_list *exlist, - xfs_fsblock_t fsbno, - xfs_extlen_t len) +xfs_bitmap_set( + struct xfs_bitmap *bitmap, + uint64_t start, + uint64_t len) { - struct xrep_extent *rex; + struct xfs_bitmap_range *bmr; - 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) + bmr = kmem_alloc(sizeof(struct xfs_bitmap_range), KM_MAYFAIL); + if (!bmr) return -ENOMEM; - INIT_LIST_HEAD(&rex->list); - rex->fsbno = fsbno; - rex->len = len; - list_add_tail(&rex->list, &exlist->list); + INIT_LIST_HEAD(&bmr->list); + bmr->start = start; + bmr->len = len; + list_add_tail(&bmr->list, &bitmap->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. - */ +/* Free everything related to this bitmap. */ void -xrep_cancel_btree_extents( - struct xfs_scrub *sc, - struct xrep_extent_list *exlist) +xfs_bitmap_destroy( + struct xfs_bitmap *bitmap) { - struct xrep_extent *rex; - struct xrep_extent *n; + struct xfs_bitmap_range *bmr; + struct xfs_bitmap_range *n; - for_each_xrep_extent_safe(rex, n, exlist) { - list_del(&rex->list); - kmem_free(rex); + for_each_xfs_bitmap_extent(bmr, n, bitmap) { + list_del(&bmr->list); + kmem_free(bmr); } } +/* Set up a per-AG block bitmap. */ +void +xfs_bitmap_init( + struct xfs_bitmap *bitmap) +{ + INIT_LIST_HEAD(&bitmap->list); +} + /* Compare two btree extents. */ static int -xrep_btree_extent_cmp( +xfs_bitmap_range_cmp( void *priv, struct list_head *a, struct list_head *b) { - struct xrep_extent *ap; - struct xrep_extent *bp; + struct xfs_bitmap_range *ap; + struct xfs_bitmap_range *bp; - ap = container_of(a, struct xrep_extent, list); - bp = container_of(b, struct xrep_extent, list); + ap = container_of(a, struct xfs_bitmap_range, list); + bp = container_of(b, struct xfs_bitmap_range, list); - if (ap->fsbno > bp->fsbno) + if (ap->start > bp->start) return 1; - if (ap->fsbno < bp->fsbno) + if (ap->start < bp->start) return -1; return 0; } /* - * 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; - xfs_fsblock_t sub_fsb; - xfs_extlen_t sub_len; + struct xfs_bitmap_range *br; + struct xfs_bitmap_range *new_br; + struct xfs_bitmap_range *sub_br; + uint64_t sub_start; + uint64_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, xfs_bitmap_range_cmp); + list_sort(NULL, &sub->list, xfs_bitmap_range_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 + * 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->start + sub_br->len <= br->start) { + 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->start >= br->start + 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_start = sub_br->start; + sub_len = sub_br->len; + if (sub_br->start < br->start) { + sub_len -= br->start - sub_br->start; + sub_start = br->start; } - 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_start == br->start) state |= LEFT_ALIGNED; - if (sub_fsb + sub_len == ex->fsbno + ex->len) + if (sub_start + sub_len == br->start + br->len) state |= RIGHT_ALIGNED; switch (state) { case LEFT_ALIGNED: /* Coincides with only the left. */ - ex->fsbno += sub_len; - ex->len -= sub_len; + br->start += 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->start = sub_start + sub_len; + new_br->len = br->start + br->len - new_br->start; + list_add(&new_br->list, &br->list); + br->len = sub_start - br->start; lp = lp->next; break; default: diff --git a/fs/xfs/scrub/bitmap.h b/fs/xfs/scrub/bitmap.h index 1038157695a8..dad652ee9177 100644 --- a/fs/xfs/scrub/bitmap.h +++ b/fs/xfs/scrub/bitmap.h @@ -6,32 +6,27 @@ #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; + uint64_t start; + uint64_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(b, bex, n, bitmap) \ + list_for_each_entry_safe((bex), (n), &(bitmap)->list, list) \ + for ((b) = bex->start; (b) < bex->start + bex->len; (b)++) + +int xfs_bitmap_set(struct xfs_bitmap *bitmap, uint64_t start, uint64_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,