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