fs/xfs/scrub/bitmap.c

   1 // SPDX-License-Identifier: GPL-2.0+
   2 /*
   3  * Copyright (C) 2018 Oracle.  All Rights Reserved.
   4  * Author: Darrick J. Wong <darrick.wong@oracle.com>
   5  */
   6 #include "xfs.h"
   7 #include "xfs_fs.h"
   8 #include "xfs_shared.h"
   9 #include "xfs_format.h"
  10 #include "xfs_trans_resv.h"
  11 #include "xfs_mount.h"
  12 #include "xfs_btree.h"
  13 #include "scrub/xfs_scrub.h"
  14 #include "scrub/scrub.h"
  15 #include "scrub/common.h"
  16 #include "scrub/trace.h"
  17 #include "scrub/repair.h"
  18 #include "scrub/bitmap.h"
  19
  20 /*
  21  * Set a range of this bitmap.  Caller must ensure the range is not set.
  22  *
  23  * This is the logical equivalent of bitmap |= mask(start, len).
  24  */
  25 int
  26 xfs_bitmap_set(
  27         struct xfs_bitmap       *bitmap,
  28         uint64_t                start,
  29         uint64_t                len)
  30 {
  31         struct xfs_bitmap_range *bmr;
  32
  33         bmr = kmem_alloc(sizeof(struct xfs_bitmap_range), KM_MAYFAIL);
  34         if (!bmr)
  35                 return -ENOMEM;
  36
  37         INIT_LIST_HEAD(&bmr->list);
  38         bmr->start = start;
  39         bmr->len = len;
  40         list_add_tail(&bmr->list, &bitmap->list);
  41
  42         return 0;
  43 }
  44
  45 /* Free everything related to this bitmap. */
  46 void
  47 xfs_bitmap_destroy(
  48         struct xfs_bitmap       *bitmap)
  49 {
  50         struct xfs_bitmap_range *bmr;
  51         struct xfs_bitmap_range *n;
  52
  53         for_each_xfs_bitmap_extent(bmr, n, bitmap) {
  54                 list_del(&bmr->list);
  55                 kmem_free(bmr);
  56         }
  57 }
  58
  59 /* Set up a per-AG block bitmap. */
  60 void
  61 xfs_bitmap_init(
  62         struct xfs_bitmap       *bitmap)
  63 {
  64         INIT_LIST_HEAD(&bitmap->list);
  65 }
  66
  67 /* Compare two btree extents. */
  68 static int
  69 xfs_bitmap_range_cmp(
  70         void                    *priv,
  71         struct list_head        *a,
  72         struct list_head        *b)
  73 {
  74         struct xfs_bitmap_range *ap;
  75         struct xfs_bitmap_range *bp;
  76
  77         ap = container_of(a, struct xfs_bitmap_range, list);
  78         bp = container_of(b, struct xfs_bitmap_range, list);
  79
  80         if (ap->start > bp->start)
  81                 return 1;
  82         if (ap->start < bp->start)
  83                 return -1;
  84         return 0;
  85 }
  86
  87 /*
  88  * Remove all the blocks mentioned in @sub from the extents in @bitmap.
  89  *
  90  * The intent is that callers will iterate the rmapbt for all of its records
  91  * for a given owner to generate @bitmap; and iterate all the blocks of the
  92  * metadata structures that are not being rebuilt and have the same rmapbt
  93  * owner to generate @sub.  This routine subtracts all the extents
  94  * mentioned in sub from all the extents linked in @bitmap, which leaves
  95  * @bitmap as the list of blocks that are not accounted for, which we assume
  96  * are the dead blocks of the old metadata structure.  The blocks mentioned in
  97  * @bitmap can be reaped.
  98  *
  99  * This is the logical equivalent of bitmap &= ~sub.
 100  */
 101 #define LEFT_ALIGNED    (1 << 0)
 102 #define RIGHT_ALIGNED   (1 << 1)
 103 int
 104 xfs_bitmap_disunion(
 105         struct xfs_bitmap       *bitmap,
 106         struct xfs_bitmap       *sub)
 107 {
 108         struct list_head        *lp;
 109         struct xfs_bitmap_range *br;
 110         struct xfs_bitmap_range *new_br;
 111         struct xfs_bitmap_range *sub_br;
 112         uint64_t                sub_start;
 113         uint64_t                sub_len;
 114         int                     state;
 115         int                     error = 0;
 116
 117         if (list_empty(&bitmap->list) || list_empty(&sub->list))
 118                 return 0;
 119         ASSERT(!list_empty(&sub->list));
 120
 121         list_sort(NULL, &bitmap->list, xfs_bitmap_range_cmp);
 122         list_sort(NULL, &sub->list, xfs_bitmap_range_cmp);
 123
 124         /*
 125          * Now that we've sorted both lists, we iterate bitmap once, rolling
 126          * forward through sub and/or bitmap as necessary until we find an
 127          * overlap or reach the end of either list.  We do not reset lp to the
 128          * head of bitmap nor do we reset sub_br to the head of sub.  The
 129          * list traversal is similar to merge sort, but we're deleting
 130          * instead.  In this manner we avoid O(n^2) operations.
 131          */
 132         sub_br = list_first_entry(&sub->list, struct xfs_bitmap_range,
 133                         list);
 134         lp = bitmap->list.next;
 135         while (lp != &bitmap->list) {
 136                 br = list_entry(lp, struct xfs_bitmap_range, list);
 137
 138                 /*
 139                  * Advance sub_br and/or br until we find a pair that
 140                  * intersect or we run out of extents.
 141                  */
 142                 while (sub_br->start + sub_br->len <= br->start) {
 143                         if (list_is_last(&sub_br->list, &sub->list))
 144                                 goto out;
 145                         sub_br = list_next_entry(sub_br, list);
 146                 }
 147                 if (sub_br->start >= br->start + br->len) {
 148                         lp = lp->next;
 149                         continue;
 150                 }
 151
 152                 /* trim sub_br to fit the extent we have */
 153                 sub_start = sub_br->start;
 154                 sub_len = sub_br->len;
 155                 if (sub_br->start < br->start) {
 156                         sub_len -= br->start - sub_br->start;
 157                         sub_start = br->start;
 158                 }
 159                 if (sub_len > br->len)
 160                         sub_len = br->len;
 161
 162                 state = 0;
 163                 if (sub_start == br->start)
 164                         state |= LEFT_ALIGNED;
 165                 if (sub_start + sub_len == br->start + br->len)
 166                         state |= RIGHT_ALIGNED;
 167                 switch (state) {
 168                 case LEFT_ALIGNED:
 169                         /* Coincides with only the left. */
 170                         br->start += sub_len;
 171                         br->len -= sub_len;
 172                         break;
 173                 case RIGHT_ALIGNED:
 174                         /* Coincides with only the right. */
 175                         br->len -= sub_len;
 176                         lp = lp->next;
 177                         break;
 178                 case LEFT_ALIGNED | RIGHT_ALIGNED:
 179                         /* Total overlap, just delete ex. */
 180                         lp = lp->next;
 181                         list_del(&br->list);
 182                         kmem_free(br);
 183                         break;
 184                 case 0:
 185                         /*
 186                          * Deleting from the middle: add the new right extent
 187                          * and then shrink the left extent.
 188                          */
 189                         new_br = kmem_alloc(sizeof(struct xfs_bitmap_range),
 190                                         KM_MAYFAIL);
 191                         if (!new_br) {
 192                                 error = -ENOMEM;
 193                                 goto out;
 194                         }
 195                         INIT_LIST_HEAD(&new_br->list);
 196                         new_br->start = sub_start + sub_len;
 197                         new_br->len = br->start + br->len - new_br->start;
 198                         list_add(&new_br->list, &br->list);
 199                         br->len = sub_start - br->start;
 200                         lp = lp->next;
 201                         break;
 202                 default:
 203                         ASSERT(0);
 204                         break;
 205                 }
 206         }
 207
 208 out:
 209         return error;
 210 }
 211 #undef LEFT_ALIGNED
 212 #undef RIGHT_ALIGNED
 213
 214 /*
 215  * Record all btree blocks seen while iterating all records of a btree.
 216  *
 217  * We know that the btree query_all function starts at the left edge and walks
 218  * towards the right edge of the tree.  Therefore, we know that we can walk up
 219  * the btree cursor towards the root; if the pointer for a given level points
 220  * to the first record/key in that block, we haven't seen this block before;
 221  * and therefore we need to remember that we saw this block in the btree.
 222  *
 223  * So if our btree is:
 224  *
 225  *    4
 226  *  / | \
 227  * 1  2  3
 228  *
 229  * Pretend for this example that each leaf block has 100 btree records.  For
 230  * the first btree record, we'll observe that bc_ptrs[0] == 1, so we record
 231  * that we saw block 1.  Then we observe that bc_ptrs[1] == 1, so we record
 232  * block 4.  The list is [1, 4].
 233  *
 234  * For the second btree record, we see that bc_ptrs[0] == 2, so we exit the
 235  * loop.  The list remains [1, 4].
 236  *
 237  * For the 101st btree record, we've moved onto leaf block 2.  Now
 238  * bc_ptrs[0] == 1 again, so we record that we saw block 2.  We see that
 239  * bc_ptrs[1] == 2, so we exit the loop.  The list is now [1, 4, 2].
 240  *
 241  * For the 102nd record, bc_ptrs[0] == 2, so we continue.
 242  *
 243  * For the 201st record, we've moved on to leaf block 3.  bc_ptrs[0] == 1, so
 244  * we add 3 to the list.  Now it is [1, 4, 2, 3].
 245  *
 246  * For the 300th record we just exit, with the list being [1, 4, 2, 3].
 247  */
 248
 249 /*
 250  * Record all the buffers pointed to by the btree cursor.  Callers already
 251  * engaged in a btree walk should call this function to capture the list of
 252  * blocks going from the leaf towards the root.
 253  */
 254 int
 255 xfs_bitmap_set_btcur_path(
 256         struct xfs_bitmap       *bitmap,
 257         struct xfs_btree_cur    *cur)
 258 {
 259         struct xfs_buf          *bp;
 260         xfs_fsblock_t           fsb;
 261         int                     i;
 262         int                     error;
 263
 264         for (i = 0; i < cur->bc_nlevels && cur->bc_ptrs[i] == 1; i++) {
 265                 xfs_btree_get_block(cur, i, &bp);
 266                 if (!bp)
 267                         continue;
 268                 fsb = XFS_DADDR_TO_FSB(cur->bc_mp, bp->b_bn);
 269                 error = xfs_bitmap_set(bitmap, fsb, 1);
 270                 if (error)
 271                         return error;
 272         }
 273
 274         return 0;
 275 }
 276
 277 /* Collect a btree's block in the bitmap. */
 278 STATIC int
 279 xfs_bitmap_collect_btblock(
 280         struct xfs_btree_cur    *cur,
 281         int                     level,
 282         void                    *priv)
 283 {
 284         struct xfs_bitmap       *bitmap = priv;
 285         struct xfs_buf          *bp;
 286         xfs_fsblock_t           fsbno;
 287
 288         xfs_btree_get_block(cur, level, &bp);
 289         if (!bp)
 290                 return 0;
 291
 292         fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, bp->b_bn);
 293         return xfs_bitmap_set(bitmap, fsbno, 1);
 294 }
 295
 296 /* Walk the btree and mark the bitmap wherever a btree block is found. */
 297 int
 298 xfs_bitmap_set_btblocks(
 299         struct xfs_bitmap       *bitmap,
 300         struct xfs_btree_cur    *cur)
 301 {
 302         return xfs_btree_visit_blocks(cur, xfs_bitmap_collect_btblock, bitmap);
 303 }