fs/xfs/scrub/bitmap.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  * Copyright (C) 2018-2023 Oracle.  All Rights Reserved.
   4  * Author: Darrick J. Wong <djwong@kernel.org>
   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/scrub.h"
  14 #include "scrub/bitmap.h"
  15
  16 #include <linux/interval_tree_generic.h>
  17
  18 struct xbitmap_node {
  19         struct rb_node  bn_rbnode;
  20
  21         /* First set bit of this interval and subtree. */
  22         uint64_t        bn_start;
  23
  24         /* Last set bit of this interval. */
  25         uint64_t        bn_last;
  26
  27         /* Last set bit of this subtree.  Do not touch this. */
  28         uint64_t        __bn_subtree_last;
  29 };
  30
  31 /* Define our own interval tree type with uint64_t parameters. */
  32
  33 #define START(node) ((node)->bn_start)
  34 #define LAST(node)  ((node)->bn_last)
  35
  36 /*
  37  * These functions are defined by the INTERVAL_TREE_DEFINE macro, but we'll
  38  * forward-declare them anyway for clarity.
  39  */
  40 static inline void
  41 xbitmap_tree_insert(struct xbitmap_node *node, struct rb_root_cached *root);
  42
  43 static inline void
  44 xbitmap_tree_remove(struct xbitmap_node *node, struct rb_root_cached *root);
  45
  46 static inline struct xbitmap_node *
  47 xbitmap_tree_iter_first(struct rb_root_cached *root, uint64_t start,
  48                         uint64_t last);
  49
  50 static inline struct xbitmap_node *
  51 xbitmap_tree_iter_next(struct xbitmap_node *node, uint64_t start,
  52                        uint64_t last);
  53
  54 INTERVAL_TREE_DEFINE(struct xbitmap_node, bn_rbnode, uint64_t,
  55                 __bn_subtree_last, START, LAST, static inline, xbitmap_tree)
  56
  57 /* Iterate each interval of a bitmap.  Do not change the bitmap. */
  58 #define for_each_xbitmap_extent(bn, bitmap) \
  59         for ((bn) = rb_entry_safe(rb_first(&(bitmap)->xb_root.rb_root), \
  60                                    struct xbitmap_node, bn_rbnode); \
  61              (bn) != NULL; \
  62              (bn) = rb_entry_safe(rb_next(&(bn)->bn_rbnode), \
  63                                    struct xbitmap_node, bn_rbnode))
  64
  65 /* Clear a range of this bitmap. */
  66 int
  67 xbitmap_clear(
  68         struct xbitmap          *bitmap,
  69         uint64_t                start,
  70         uint64_t                len)
  71 {
  72         struct xbitmap_node     *bn;
  73         struct xbitmap_node     *new_bn;
  74         uint64_t                last = start + len - 1;
  75
  76         while ((bn = xbitmap_tree_iter_first(&bitmap->xb_root, start, last))) {
  77                 if (bn->bn_start < start && bn->bn_last > last) {
  78                         uint64_t        old_last = bn->bn_last;
  79
  80                         /* overlaps with the entire clearing range */
  81                         xbitmap_tree_remove(bn, &bitmap->xb_root);
  82                         bn->bn_last = start - 1;
  83                         xbitmap_tree_insert(bn, &bitmap->xb_root);
  84
  85                         /* add an extent */
  86                         new_bn = kmalloc(sizeof(struct xbitmap_node),
  87                                         XCHK_GFP_FLAGS);
  88                         if (!new_bn)
  89                                 return -ENOMEM;
  90                         new_bn->bn_start = last + 1;
  91                         new_bn->bn_last = old_last;
  92                         xbitmap_tree_insert(new_bn, &bitmap->xb_root);
  93                 } else if (bn->bn_start < start) {
  94                         /* overlaps with the left side of the clearing range */
  95                         xbitmap_tree_remove(bn, &bitmap->xb_root);
  96                         bn->bn_last = start - 1;
  97                         xbitmap_tree_insert(bn, &bitmap->xb_root);
  98                 } else if (bn->bn_last > last) {
  99                         /* overlaps with the right side of the clearing range */
 100                         xbitmap_tree_remove(bn, &bitmap->xb_root);
 101                         bn->bn_start = last + 1;
 102                         xbitmap_tree_insert(bn, &bitmap->xb_root);
 103                         break;
 104                 } else {
 105                         /* in the middle of the clearing range */
 106                         xbitmap_tree_remove(bn, &bitmap->xb_root);
 107                         kfree(bn);
 108                 }
 109         }
 110
 111         return 0;
 112 }
 113
 114 /* Set a range of this bitmap. */
 115 int
 116 xbitmap_set(
 117         struct xbitmap          *bitmap,
 118         uint64_t                start,
 119         uint64_t                len)
 120 {
 121         struct xbitmap_node     *left;
 122         struct xbitmap_node     *right;
 123         uint64_t                last = start + len - 1;
 124         int                     error;
 125
 126         /* Is this whole range already set? */
 127         left = xbitmap_tree_iter_first(&bitmap->xb_root, start, last);
 128         if (left && left->bn_start <= start && left->bn_last >= last)
 129                 return 0;
 130
 131         /* Clear out everything in the range we want to set. */
 132         error = xbitmap_clear(bitmap, start, len);
 133         if (error)
 134                 return error;
 135
 136         /* Do we have a left-adjacent extent? */
 137         left = xbitmap_tree_iter_first(&bitmap->xb_root, start - 1, start - 1);
 138         ASSERT(!left || left->bn_last + 1 == start);
 139
 140         /* Do we have a right-adjacent extent? */
 141         right = xbitmap_tree_iter_first(&bitmap->xb_root, last + 1, last + 1);
 142         ASSERT(!right || right->bn_start == last + 1);
 143
 144         if (left && right) {
 145                 /* combine left and right adjacent extent */
 146                 xbitmap_tree_remove(left, &bitmap->xb_root);
 147                 xbitmap_tree_remove(right, &bitmap->xb_root);
 148                 left->bn_last = right->bn_last;
 149                 xbitmap_tree_insert(left, &bitmap->xb_root);
 150                 kfree(right);
 151         } else if (left) {
 152                 /* combine with left extent */
 153                 xbitmap_tree_remove(left, &bitmap->xb_root);
 154                 left->bn_last = last;
 155                 xbitmap_tree_insert(left, &bitmap->xb_root);
 156         } else if (right) {
 157                 /* combine with right extent */
 158                 xbitmap_tree_remove(right, &bitmap->xb_root);
 159                 right->bn_start = start;
 160                 xbitmap_tree_insert(right, &bitmap->xb_root);
 161         } else {
 162                 /* add an extent */
 163                 left = kmalloc(sizeof(struct xbitmap_node), XCHK_GFP_FLAGS);
 164                 if (!left)
 165                         return -ENOMEM;
 166                 left->bn_start = start;
 167                 left->bn_last = last;
 168                 xbitmap_tree_insert(left, &bitmap->xb_root);
 169         }
 170
 171         return 0;
 172 }
 173
 174 /* Free everything related to this bitmap. */
 175 void
 176 xbitmap_destroy(
 177         struct xbitmap          *bitmap)
 178 {
 179         struct xbitmap_node     *bn;
 180
 181         while ((bn = xbitmap_tree_iter_first(&bitmap->xb_root, 0, -1ULL))) {
 182                 xbitmap_tree_remove(bn, &bitmap->xb_root);
 183                 kfree(bn);
 184         }
 185 }
 186
 187 /* Set up a per-AG block bitmap. */
 188 void
 189 xbitmap_init(
 190         struct xbitmap          *bitmap)
 191 {
 192         bitmap->xb_root = RB_ROOT_CACHED;
 193 }
 194
 195 /*
 196  * Remove all the blocks mentioned in @sub from the extents in @bitmap.
 197  *
 198  * The intent is that callers will iterate the rmapbt for all of its records
 199  * for a given owner to generate @bitmap; and iterate all the blocks of the
 200  * metadata structures that are not being rebuilt and have the same rmapbt
 201  * owner to generate @sub.  This routine subtracts all the extents
 202  * mentioned in sub from all the extents linked in @bitmap, which leaves
 203  * @bitmap as the list of blocks that are not accounted for, which we assume
 204  * are the dead blocks of the old metadata structure.  The blocks mentioned in
 205  * @bitmap can be reaped.
 206  *
 207  * This is the logical equivalent of bitmap &= ~sub.
 208  */
 209 int
 210 xbitmap_disunion(
 211         struct xbitmap          *bitmap,
 212         struct xbitmap          *sub)
 213 {
 214         struct xbitmap_node     *bn;
 215         int                     error;
 216
 217         if (xbitmap_empty(bitmap) || xbitmap_empty(sub))
 218                 return 0;
 219
 220         for_each_xbitmap_extent(bn, sub) {
 221                 error = xbitmap_clear(bitmap, bn->bn_start,
 222                                 bn->bn_last - bn->bn_start + 1);
 223                 if (error)
 224                         return error;
 225         }
 226
 227         return 0;
 228 }
 229
 230 /*
 231  * Record all btree blocks seen while iterating all records of a btree.
 232  *
 233  * We know that the btree query_all function starts at the left edge and walks
 234  * towards the right edge of the tree.  Therefore, we know that we can walk up
 235  * the btree cursor towards the root; if the pointer for a given level points
 236  * to the first record/key in that block, we haven't seen this block before;
 237  * and therefore we need to remember that we saw this block in the btree.
 238  *
 239  * So if our btree is:
 240  *
 241  *    4
 242  *  / | \
 243  * 1  2  3
 244  *
 245  * Pretend for this example that each leaf block has 100 btree records.  For
 246  * the first btree record, we'll observe that bc_levels[0].ptr == 1, so we
 247  * record that we saw block 1.  Then we observe that bc_levels[1].ptr == 1, so
 248  * we record block 4.  The list is [1, 4].
 249  *
 250  * For the second btree record, we see that bc_levels[0].ptr == 2, so we exit
 251  * the loop.  The list remains [1, 4].
 252  *
 253  * For the 101st btree record, we've moved onto leaf block 2.  Now
 254  * bc_levels[0].ptr == 1 again, so we record that we saw block 2.  We see that
 255  * bc_levels[1].ptr == 2, so we exit the loop.  The list is now [1, 4, 2].
 256  *
 257  * For the 102nd record, bc_levels[0].ptr == 2, so we continue.
 258  *
 259  * For the 201st record, we've moved on to leaf block 3.
 260  * bc_levels[0].ptr == 1, so we add 3 to the list.  Now it is [1, 4, 2, 3].
 261  *
 262  * For the 300th record we just exit, with the list being [1, 4, 2, 3].
 263  */
 264
 265 /*
 266  * Record all the buffers pointed to by the btree cursor.  Callers already
 267  * engaged in a btree walk should call this function to capture the list of
 268  * blocks going from the leaf towards the root.
 269  */
 270 int
 271 xbitmap_set_btcur_path(
 272         struct xbitmap          *bitmap,
 273         struct xfs_btree_cur    *cur)
 274 {
 275         struct xfs_buf          *bp;
 276         xfs_fsblock_t           fsb;
 277         int                     i;
 278         int                     error;
 279
 280         for (i = 0; i < cur->bc_nlevels && cur->bc_levels[i].ptr == 1; i++) {
 281                 xfs_btree_get_block(cur, i, &bp);
 282                 if (!bp)
 283                         continue;
 284                 fsb = XFS_DADDR_TO_FSB(cur->bc_mp, xfs_buf_daddr(bp));
 285                 error = xbitmap_set(bitmap, fsb, 1);
 286                 if (error)
 287                         return error;
 288         }
 289
 290         return 0;
 291 }
 292
 293 /* Collect a btree's block in the bitmap. */
 294 STATIC int
 295 xbitmap_collect_btblock(
 296         struct xfs_btree_cur    *cur,
 297         int                     level,
 298         void                    *priv)
 299 {
 300         struct xbitmap          *bitmap = priv;
 301         struct xfs_buf          *bp;
 302         xfs_fsblock_t           fsbno;
 303
 304         xfs_btree_get_block(cur, level, &bp);
 305         if (!bp)
 306                 return 0;
 307
 308         fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, xfs_buf_daddr(bp));
 309         return xbitmap_set(bitmap, fsbno, 1);
 310 }
 311
 312 /* Walk the btree and mark the bitmap wherever a btree block is found. */
 313 int
 314 xbitmap_set_btblocks(
 315         struct xbitmap          *bitmap,
 316         struct xfs_btree_cur    *cur)
 317 {
 318         return xfs_btree_visit_blocks(cur, xbitmap_collect_btblock,
 319                         XFS_BTREE_VISIT_ALL, bitmap);
 320 }
 321
 322 /* How many bits are set in this bitmap? */
 323 uint64_t
 324 xbitmap_hweight(
 325         struct xbitmap          *bitmap)
 326 {
 327         struct xbitmap_node     *bn;
 328         uint64_t                ret = 0;
 329
 330         for_each_xbitmap_extent(bn, bitmap)
 331                 ret += bn->bn_last - bn->bn_start + 1;
 332
 333         return ret;
 334 }
 335
 336 /* Call a function for every run of set bits in this bitmap. */
 337 int
 338 xbitmap_walk(
 339         struct xbitmap          *bitmap,
 340         xbitmap_walk_fn         fn,
 341         void                    *priv)
 342 {
 343         struct xbitmap_node     *bn;
 344         int                     error = 0;
 345
 346         for_each_xbitmap_extent(bn, bitmap) {
 347                 error = fn(bn->bn_start, bn->bn_last - bn->bn_start + 1, priv);
 348                 if (error)
 349                         break;
 350         }
 351
 352         return error;
 353 }
 354
 355 struct xbitmap_walk_bits {
 356         xbitmap_walk_bits_fn    fn;
 357         void                    *priv;
 358 };
 359
 360 /* Walk all the bits in a run. */
 361 static int
 362 xbitmap_walk_bits_in_run(
 363         uint64_t                        start,
 364         uint64_t                        len,
 365         void                            *priv)
 366 {
 367         struct xbitmap_walk_bits        *wb = priv;
 368         uint64_t                        i;
 369         int                             error = 0;
 370
 371         for (i = start; i < start + len; i++) {
 372                 error = wb->fn(i, wb->priv);
 373                 if (error)
 374                         break;
 375         }
 376
 377         return error;
 378 }
 379
 380 /* Call a function for every set bit in this bitmap. */
 381 int
 382 xbitmap_walk_bits(
 383         struct xbitmap                  *bitmap,
 384         xbitmap_walk_bits_fn            fn,
 385         void                            *priv)
 386 {
 387         struct xbitmap_walk_bits        wb = {.fn = fn, .priv = priv};
 388
 389         return xbitmap_walk(bitmap, xbitmap_walk_bits_in_run, &wb);
 390 }
 391
 392 /* Does this bitmap have no bits set at all? */
 393 bool
 394 xbitmap_empty(
 395         struct xbitmap          *bitmap)
 396 {
 397         return bitmap->xb_root.rb_root.rb_node == NULL;
 398 }
 399
 400 /* Is the start of the range set or clear?  And for how long? */
 401 bool
 402 xbitmap_test(
 403         struct xbitmap          *bitmap,
 404         uint64_t                start,
 405         uint64_t                *len)
 406 {
 407         struct xbitmap_node     *bn;
 408         uint64_t                last = start + *len - 1;
 409
 410         bn = xbitmap_tree_iter_first(&bitmap->xb_root, start, last);
 411         if (!bn)
 412                 return false;
 413         if (bn->bn_start <= start) {
 414                 if (bn->bn_last < last)
 415                         *len = bn->bn_last - start + 1;
 416                 return true;
 417         }
 418         *len = bn->bn_start - start;
 419         return false;
 420 }