xfs/scrub/bitmap.c

0001 // SPDX-License-Identifier: GPL-2.0+
0002 /*
0003  * Copyright (C) 2018 Oracle.  All Rights Reserved.
0004  * Author: Darrick J. Wong <darrick.wong@oracle.com>
0005  */
0006 #include "xfs.h"
0007 #include "xfs_fs.h"
0008 #include "xfs_shared.h"
0009 #include "xfs_format.h"
0010 #include "xfs_trans_resv.h"
0011 #include "xfs_mount.h"
0012 #include "xfs_btree.h"
0013 #include "scrub/bitmap.h"
0014
0015 /*
0016  * Set a range of this bitmap.  Caller must ensure the range is not set.
0017  *
0018  * This is the logical equivalent of bitmap |= mask(start, len).
0019  */
0020 int
0021 xbitmap_set(
0022     struct xbitmap      *bitmap,
0023     uint64_t        start,
0024     uint64_t        len)
0025 {
0026     struct xbitmap_range    *bmr;
0027
0028     bmr = kmem_alloc(sizeof(struct xbitmap_range), KM_MAYFAIL);
0029     if (!bmr)
0030         return -ENOMEM;
0031
0032     INIT_LIST_HEAD(&bmr->list);
0033     bmr->start = start;
0034     bmr->len = len;
0035     list_add_tail(&bmr->list, &bitmap->list);
0036
0037     return 0;
0038 }
0039
0040 /* Free everything related to this bitmap. */
0041 void
0042 xbitmap_destroy(
0043     struct xbitmap      *bitmap)
0044 {
0045     struct xbitmap_range    *bmr;
0046     struct xbitmap_range    *n;
0047
0048     for_each_xbitmap_extent(bmr, n, bitmap) {
0049         list_del(&bmr->list);
0050         kmem_free(bmr);
0051     }
0052 }
0053
0054 /* Set up a per-AG block bitmap. */
0055 void
0056 xbitmap_init(
0057     struct xbitmap      *bitmap)
0058 {
0059     INIT_LIST_HEAD(&bitmap->list);
0060 }
0061
0062 /* Compare two btree extents. */
0063 static int
0064 xbitmap_range_cmp(
0065     void            *priv,
0066     const struct list_head  *a,
0067     const struct list_head  *b)
0068 {
0069     struct xbitmap_range    *ap;
0070     struct xbitmap_range    *bp;
0071
0072     ap = container_of(a, struct xbitmap_range, list);
0073     bp = container_of(b, struct xbitmap_range, list);
0074
0075     if (ap->start > bp->start)
0076         return 1;
0077     if (ap->start < bp->start)
0078         return -1;
0079     return 0;
0080 }
0081
0082 /*
0083  * Remove all the blocks mentioned in @sub from the extents in @bitmap.
0084  *
0085  * The intent is that callers will iterate the rmapbt for all of its records
0086  * for a given owner to generate @bitmap; and iterate all the blocks of the
0087  * metadata structures that are not being rebuilt and have the same rmapbt
0088  * owner to generate @sub.  This routine subtracts all the extents
0089  * mentioned in sub from all the extents linked in @bitmap, which leaves
0090  * @bitmap as the list of blocks that are not accounted for, which we assume
0091  * are the dead blocks of the old metadata structure.  The blocks mentioned in
0092  * @bitmap can be reaped.
0093  *
0094  * This is the logical equivalent of bitmap &= ~sub.
0095  */
0096 #define LEFT_ALIGNED    (1 << 0)
0097 #define RIGHT_ALIGNED   (1 << 1)
0098 int
0099 xbitmap_disunion(
0100     struct xbitmap      *bitmap,
0101     struct xbitmap      *sub)
0102 {
0103     struct list_head    *lp;
0104     struct xbitmap_range    *br;
0105     struct xbitmap_range    *new_br;
0106     struct xbitmap_range    *sub_br;
0107     uint64_t        sub_start;
0108     uint64_t        sub_len;
0109     int         state;
0110     int         error = 0;
0111
0112     if (list_empty(&bitmap->list) || list_empty(&sub->list))
0113         return 0;
0114     ASSERT(!list_empty(&sub->list));
0115
0116     list_sort(NULL, &bitmap->list, xbitmap_range_cmp);
0117     list_sort(NULL, &sub->list, xbitmap_range_cmp);
0118
0119     /*
0120      * Now that we've sorted both lists, we iterate bitmap once, rolling
0121      * forward through sub and/or bitmap as necessary until we find an
0122      * overlap or reach the end of either list.  We do not reset lp to the
0123      * head of bitmap nor do we reset sub_br to the head of sub.  The
0124      * list traversal is similar to merge sort, but we're deleting
0125      * instead.  In this manner we avoid O(n^2) operations.
0126      */
0127     sub_br = list_first_entry(&sub->list, struct xbitmap_range,
0128             list);
0129     lp = bitmap->list.next;
0130     while (lp != &bitmap->list) {
0131         br = list_entry(lp, struct xbitmap_range, list);
0132
0133         /*
0134          * Advance sub_br and/or br until we find a pair that
0135          * intersect or we run out of extents.
0136          */
0137         while (sub_br->start + sub_br->len <= br->start) {
0138             if (list_is_last(&sub_br->list, &sub->list))
0139                 goto out;
0140             sub_br = list_next_entry(sub_br, list);
0141         }
0142         if (sub_br->start >= br->start + br->len) {
0143             lp = lp->next;
0144             continue;
0145         }
0146
0147         /* trim sub_br to fit the extent we have */
0148         sub_start = sub_br->start;
0149         sub_len = sub_br->len;
0150         if (sub_br->start < br->start) {
0151             sub_len -= br->start - sub_br->start;
0152             sub_start = br->start;
0153         }
0154         if (sub_len > br->len)
0155             sub_len = br->len;
0156
0157         state = 0;
0158         if (sub_start == br->start)
0159             state |= LEFT_ALIGNED;
0160         if (sub_start + sub_len == br->start + br->len)
0161             state |= RIGHT_ALIGNED;
0162         switch (state) {
0163         case LEFT_ALIGNED:
0164             /* Coincides with only the left. */
0165             br->start += sub_len;
0166             br->len -= sub_len;
0167             break;
0168         case RIGHT_ALIGNED:
0169             /* Coincides with only the right. */
0170             br->len -= sub_len;
0171             lp = lp->next;
0172             break;
0173         case LEFT_ALIGNED | RIGHT_ALIGNED:
0174             /* Total overlap, just delete ex. */
0175             lp = lp->next;
0176             list_del(&br->list);
0177             kmem_free(br);
0178             break;
0179         case 0:
0180             /*
0181              * Deleting from the middle: add the new right extent
0182              * and then shrink the left extent.
0183              */
0184             new_br = kmem_alloc(sizeof(struct xbitmap_range),
0185                     KM_MAYFAIL);
0186             if (!new_br) {
0187                 error = -ENOMEM;
0188                 goto out;
0189             }
0190             INIT_LIST_HEAD(&new_br->list);
0191             new_br->start = sub_start + sub_len;
0192             new_br->len = br->start + br->len - new_br->start;
0193             list_add(&new_br->list, &br->list);
0194             br->len = sub_start - br->start;
0195             lp = lp->next;
0196             break;
0197         default:
0198             ASSERT(0);
0199             break;
0200         }
0201     }
0202
0203 out:
0204     return error;
0205 }
0206 #undef LEFT_ALIGNED
0207 #undef RIGHT_ALIGNED
0208
0209 /*
0210  * Record all btree blocks seen while iterating all records of a btree.
0211  *
0212  * We know that the btree query_all function starts at the left edge and walks
0213  * towards the right edge of the tree.  Therefore, we know that we can walk up
0214  * the btree cursor towards the root; if the pointer for a given level points
0215  * to the first record/key in that block, we haven't seen this block before;
0216  * and therefore we need to remember that we saw this block in the btree.
0217  *
0218  * So if our btree is:
0219  *
0220  *    4
0221  *  / | \
0222  * 1  2  3
0223  *
0224  * Pretend for this example that each leaf block has 100 btree records.  For
0225  * the first btree record, we'll observe that bc_levels[0].ptr == 1, so we
0226  * record that we saw block 1.  Then we observe that bc_levels[1].ptr == 1, so
0227  * we record block 4.  The list is [1, 4].
0228  *
0229  * For the second btree record, we see that bc_levels[0].ptr == 2, so we exit
0230  * the loop.  The list remains [1, 4].
0231  *
0232  * For the 101st btree record, we've moved onto leaf block 2.  Now
0233  * bc_levels[0].ptr == 1 again, so we record that we saw block 2.  We see that
0234  * bc_levels[1].ptr == 2, so we exit the loop.  The list is now [1, 4, 2].
0235  *
0236  * For the 102nd record, bc_levels[0].ptr == 2, so we continue.
0237  *
0238  * For the 201st record, we've moved on to leaf block 3.
0239  * bc_levels[0].ptr == 1, so we add 3 to the list.  Now it is [1, 4, 2, 3].
0240  *
0241  * For the 300th record we just exit, with the list being [1, 4, 2, 3].
0242  */
0243
0244 /*
0245  * Record all the buffers pointed to by the btree cursor.  Callers already
0246  * engaged in a btree walk should call this function to capture the list of
0247  * blocks going from the leaf towards the root.
0248  */
0249 int
0250 xbitmap_set_btcur_path(
0251     struct xbitmap      *bitmap,
0252     struct xfs_btree_cur    *cur)
0253 {
0254     struct xfs_buf      *bp;
0255     xfs_fsblock_t       fsb;
0256     int         i;
0257     int         error;
0258
0259     for (i = 0; i < cur->bc_nlevels && cur->bc_levels[i].ptr == 1; i++) {
0260         xfs_btree_get_block(cur, i, &bp);
0261         if (!bp)
0262             continue;
0263         fsb = XFS_DADDR_TO_FSB(cur->bc_mp, xfs_buf_daddr(bp));
0264         error = xbitmap_set(bitmap, fsb, 1);
0265         if (error)
0266             return error;
0267     }
0268
0269     return 0;
0270 }
0271
0272 /* Collect a btree's block in the bitmap. */
0273 STATIC int
0274 xbitmap_collect_btblock(
0275     struct xfs_btree_cur    *cur,
0276     int         level,
0277     void            *priv)
0278 {
0279     struct xbitmap      *bitmap = priv;
0280     struct xfs_buf      *bp;
0281     xfs_fsblock_t       fsbno;
0282
0283     xfs_btree_get_block(cur, level, &bp);
0284     if (!bp)
0285         return 0;
0286
0287     fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, xfs_buf_daddr(bp));
0288     return xbitmap_set(bitmap, fsbno, 1);
0289 }
0290
0291 /* Walk the btree and mark the bitmap wherever a btree block is found. */
0292 int
0293 xbitmap_set_btblocks(
0294     struct xbitmap      *bitmap,
0295     struct xfs_btree_cur    *cur)
0296 {
0297     return xfs_btree_visit_blocks(cur, xbitmap_collect_btblock,
0298             XFS_BTREE_VISIT_ALL, bitmap);
0299 }
0300
0301 /* How many bits are set in this bitmap? */
0302 uint64_t
0303 xbitmap_hweight(
0304     struct xbitmap      *bitmap)
0305 {
0306     struct xbitmap_range    *bmr;
0307     struct xbitmap_range    *n;
0308     uint64_t        ret = 0;
0309
0310     for_each_xbitmap_extent(bmr, n, bitmap)
0311         ret += bmr->len;
0312
0313     return ret;
0314 }