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 <[email protected]>
   5  */
   6 #include "xfs.h"
   7 #include "xfs_fs.h"
   8 #include "xfs_shared.h"
   9 #include "xfs_bit.h"
  10 #include "xfs_format.h"
  11 #include "xfs_trans_resv.h"
  12 #include "xfs_mount.h"
  13 #include "xfs_btree.h"
  14 #include "scrub/scrub.h"
  15 #include "scrub/bitmap.h"
  16
  17 #include <linux/interval_tree_generic.h>
  18
  19 /* u64 bitmap */
  20
  21 struct xbitmap64_node {
  22         struct rb_node  bn_rbnode;
  23
  24         /* First set bit of this interval and subtree. */
  25         uint64_t        bn_start;
  26
  27         /* Last set bit of this interval. */
  28         uint64_t        bn_last;
  29
  30         /* Last set bit of this subtree.  Do not touch this. */
  31         uint64_t        __bn_subtree_last;
  32 };
  33
  34 /* Define our own interval tree type with uint64_t parameters. */
  35
  36 #define START(node) ((node)->bn_start)
  37 #define LAST(node)  ((node)->bn_last)
  38
  39 /*
  40  * These functions are defined by the INTERVAL_TREE_DEFINE macro, but we'll
  41  * forward-declare them anyway for clarity.
  42  */
  43 static inline void
  44 xbitmap64_tree_insert(struct xbitmap64_node *node, struct rb_root_cached *root);
  45
  46 static inline void
  47 xbitmap64_tree_remove(struct xbitmap64_node *node, struct rb_root_cached *root);
  48
  49 static inline struct xbitmap64_node *
  50 xbitmap64_tree_iter_first(struct rb_root_cached *root, uint64_t start,
  51                         uint64_t last);
  52
  53 static inline struct xbitmap64_node *
  54 xbitmap64_tree_iter_next(struct xbitmap64_node *node, uint64_t start,
  55                        uint64_t last);
  56
  57 INTERVAL_TREE_DEFINE(struct xbitmap64_node, bn_rbnode, uint64_t,
  58                 __bn_subtree_last, START, LAST, static inline, xbitmap64_tree)
  59
  60 /* Iterate each interval of a bitmap.  Do not change the bitmap. */
  61 #define for_each_xbitmap64_extent(bn, bitmap) \
  62         for ((bn) = rb_entry_safe(rb_first(&(bitmap)->xb_root.rb_root), \
  63                                    struct xbitmap64_node, bn_rbnode); \
  64              (bn) != NULL; \
  65              (bn) = rb_entry_safe(rb_next(&(bn)->bn_rbnode), \
  66                                    struct xbitmap64_node, bn_rbnode))
  67
  68 /* Clear a range of this bitmap. */
  69 int
  70 xbitmap64_clear(
  71         struct xbitmap64        *bitmap,
  72         uint64_t                start,
  73         uint64_t                len)
  74 {
  75         struct xbitmap64_node   *bn;
  76         struct xbitmap64_node   *new_bn;
  77         uint64_t                last = start + len - 1;
  78
  79         while ((bn = xbitmap64_tree_iter_first(&bitmap->xb_root, start, last))) {
  80                 if (bn->bn_start < start && bn->bn_last > last) {
  81                         uint64_t        old_last = bn->bn_last;
  82
  83                         /* overlaps with the entire clearing range */
  84                         xbitmap64_tree_remove(bn, &bitmap->xb_root);
  85                         bn->bn_last = start - 1;
  86                         xbitmap64_tree_insert(bn, &bitmap->xb_root);
  87
  88                         /* add an extent */
  89                         new_bn = kmalloc(sizeof(struct xbitmap64_node),
  90                                         XCHK_GFP_FLAGS);
  91                         if (!new_bn)
  92                                 return -ENOMEM;
  93                         new_bn->bn_start = last + 1;
  94                         new_bn->bn_last = old_last;
  95                         xbitmap64_tree_insert(new_bn, &bitmap->xb_root);
  96                 } else if (bn->bn_start < start) {
  97                         /* overlaps with the left side of the clearing range */
  98                         xbitmap64_tree_remove(bn, &bitmap->xb_root);
  99                         bn->bn_last = start - 1;
 100                         xbitmap64_tree_insert(bn, &bitmap->xb_root);
 101                 } else if (bn->bn_last > last) {
 102                         /* overlaps with the right side of the clearing range */
 103                         xbitmap64_tree_remove(bn, &bitmap->xb_root);
 104                         bn->bn_start = last + 1;
 105                         xbitmap64_tree_insert(bn, &bitmap->xb_root);
 106                         break;
 107                 } else {
 108                         /* in the middle of the clearing range */
 109                         xbitmap64_tree_remove(bn, &bitmap->xb_root);
 110                         kfree(bn);
 111                 }
 112         }
 113
 114         return 0;
 115 }
 116
 117 /* Set a range of this bitmap. */
 118 int
 119 xbitmap64_set(
 120         struct xbitmap64        *bitmap,
 121         uint64_t                start,
 122         uint64_t                len)
 123 {
 124         struct xbitmap64_node   *left;
 125         struct xbitmap64_node   *right;
 126         uint64_t                last = start + len - 1;
 127         int                     error;
 128
 129         /* Is this whole range already set? */
 130         left = xbitmap64_tree_iter_first(&bitmap->xb_root, start, last);
 131         if (left && left->bn_start <= start && left->bn_last >= last)
 132                 return 0;
 133
 134         /* Clear out everything in the range we want to set. */
 135         error = xbitmap64_clear(bitmap, start, len);
 136         if (error)
 137                 return error;
 138
 139         /* Do we have a left-adjacent extent? */
 140         left = xbitmap64_tree_iter_first(&bitmap->xb_root, start - 1, start - 1);
 141         ASSERT(!left || left->bn_last + 1 == start);
 142
 143         /* Do we have a right-adjacent extent? */
 144         right = xbitmap64_tree_iter_first(&bitmap->xb_root, last + 1, last + 1);
 145         ASSERT(!right || right->bn_start == last + 1);
 146
 147         if (left && right) {
 148                 /* combine left and right adjacent extent */
 149                 xbitmap64_tree_remove(left, &bitmap->xb_root);
 150                 xbitmap64_tree_remove(right, &bitmap->xb_root);
 151                 left->bn_last = right->bn_last;
 152                 xbitmap64_tree_insert(left, &bitmap->xb_root);
 153                 kfree(right);
 154         } else if (left) {
 155                 /* combine with left extent */
 156                 xbitmap64_tree_remove(left, &bitmap->xb_root);
 157                 left->bn_last = last;
 158                 xbitmap64_tree_insert(left, &bitmap->xb_root);
 159         } else if (right) {
 160                 /* combine with right extent */
 161                 xbitmap64_tree_remove(right, &bitmap->xb_root);
 162                 right->bn_start = start;
 163                 xbitmap64_tree_insert(right, &bitmap->xb_root);
 164         } else {
 165                 /* add an extent */
 166                 left = kmalloc(sizeof(struct xbitmap64_node), XCHK_GFP_FLAGS);
 167                 if (!left)
 168                         return -ENOMEM;
 169                 left->bn_start = start;
 170                 left->bn_last = last;
 171                 xbitmap64_tree_insert(left, &bitmap->xb_root);
 172         }
 173
 174         return 0;
 175 }
 176
 177 /* Free everything related to this bitmap. */
 178 void
 179 xbitmap64_destroy(
 180         struct xbitmap64        *bitmap)
 181 {
 182         struct xbitmap64_node   *bn;
 183
 184         while ((bn = xbitmap64_tree_iter_first(&bitmap->xb_root, 0, -1ULL))) {
 185                 xbitmap64_tree_remove(bn, &bitmap->xb_root);
 186                 kfree(bn);
 187         }
 188 }
 189
 190 /* Set up a per-AG block bitmap. */
 191 void
 192 xbitmap64_init(
 193         struct xbitmap64        *bitmap)
 194 {
 195         bitmap->xb_root = RB_ROOT_CACHED;
 196 }
 197
 198 /*
 199  * Remove all the blocks mentioned in @sub from the extents in @bitmap.
 200  *
 201  * The intent is that callers will iterate the rmapbt for all of its records
 202  * for a given owner to generate @bitmap; and iterate all the blocks of the
 203  * metadata structures that are not being rebuilt and have the same rmapbt
 204  * owner to generate @sub.  This routine subtracts all the extents
 205  * mentioned in sub from all the extents linked in @bitmap, which leaves
 206  * @bitmap as the list of blocks that are not accounted for, which we assume
 207  * are the dead blocks of the old metadata structure.  The blocks mentioned in
 208  * @bitmap can be reaped.
 209  *
 210  * This is the logical equivalent of bitmap &= ~sub.
 211  */
 212 int
 213 xbitmap64_disunion(
 214         struct xbitmap64        *bitmap,
 215         struct xbitmap64        *sub)
 216 {
 217         struct xbitmap64_node   *bn;
 218         int                     error;
 219
 220         if (xbitmap64_empty(bitmap) || xbitmap64_empty(sub))
 221                 return 0;
 222
 223         for_each_xbitmap64_extent(bn, sub) {
 224                 error = xbitmap64_clear(bitmap, bn->bn_start,
 225                                 bn->bn_last - bn->bn_start + 1);
 226                 if (error)
 227                         return error;
 228         }
 229
 230         return 0;
 231 }
 232
 233 /* How many bits are set in this bitmap? */
 234 uint64_t
 235 xbitmap64_hweight(
 236         struct xbitmap64        *bitmap)
 237 {
 238         struct xbitmap64_node   *bn;
 239         uint64_t                ret = 0;
 240
 241         for_each_xbitmap64_extent(bn, bitmap)
 242                 ret += bn->bn_last - bn->bn_start + 1;
 243
 244         return ret;
 245 }
 246
 247 /* Call a function for every run of set bits in this bitmap. */
 248 int
 249 xbitmap64_walk(
 250         struct xbitmap64        *bitmap,
 251         xbitmap64_walk_fn               fn,
 252         void                    *priv)
 253 {
 254         struct xbitmap64_node   *bn;
 255         int                     error = 0;
 256
 257         for_each_xbitmap64_extent(bn, bitmap) {
 258                 error = fn(bn->bn_start, bn->bn_last - bn->bn_start + 1, priv);
 259                 if (error)
 260                         break;
 261         }
 262
 263         return error;
 264 }
 265
 266 /* Does this bitmap have no bits set at all? */
 267 bool
 268 xbitmap64_empty(
 269         struct xbitmap64        *bitmap)
 270 {
 271         return bitmap->xb_root.rb_root.rb_node == NULL;
 272 }
 273
 274 /* Is the start of the range set or clear?  And for how long? */
 275 bool
 276 xbitmap64_test(
 277         struct xbitmap64        *bitmap,
 278         uint64_t                start,
 279         uint64_t                *len)
 280 {
 281         struct xbitmap64_node   *bn;
 282         uint64_t                last = start + *len - 1;
 283
 284         bn = xbitmap64_tree_iter_first(&bitmap->xb_root, start, last);
 285         if (!bn)
 286                 return false;
 287         if (bn->bn_start <= start) {
 288                 if (bn->bn_last < last)
 289                         *len = bn->bn_last - start + 1;
 290                 return true;
 291         }
 292         *len = bn->bn_start - start;
 293         return false;
 294 }
 295
 296 /* u32 bitmap */
 297
 298 struct xbitmap32_node {
 299         struct rb_node  bn_rbnode;
 300
 301         /* First set bit of this interval and subtree. */
 302         uint32_t        bn_start;
 303
 304         /* Last set bit of this interval. */
 305         uint32_t        bn_last;
 306
 307         /* Last set bit of this subtree.  Do not touch this. */
 308         uint32_t        __bn_subtree_last;
 309 };
 310
 311 /* Define our own interval tree type with uint32_t parameters. */
 312
 313 /*
 314  * These functions are defined by the INTERVAL_TREE_DEFINE macro, but we'll
 315  * forward-declare them anyway for clarity.
 316  */
 317 static inline void
 318 xbitmap32_tree_insert(struct xbitmap32_node *node, struct rb_root_cached *root);
 319
 320 static inline void
 321 xbitmap32_tree_remove(struct xbitmap32_node *node, struct rb_root_cached *root);
 322
 323 static inline struct xbitmap32_node *
 324 xbitmap32_tree_iter_first(struct rb_root_cached *root, uint32_t start,
 325                           uint32_t last);
 326
 327 static inline struct xbitmap32_node *
 328 xbitmap32_tree_iter_next(struct xbitmap32_node *node, uint32_t start,
 329                          uint32_t last);
 330
 331 INTERVAL_TREE_DEFINE(struct xbitmap32_node, bn_rbnode, uint32_t,
 332                 __bn_subtree_last, START, LAST, static inline, xbitmap32_tree)
 333
 334 /* Iterate each interval of a bitmap.  Do not change the bitmap. */
 335 #define for_each_xbitmap32_extent(bn, bitmap) \
 336         for ((bn) = rb_entry_safe(rb_first(&(bitmap)->xb_root.rb_root), \
 337                                    struct xbitmap32_node, bn_rbnode); \
 338              (bn) != NULL; \
 339              (bn) = rb_entry_safe(rb_next(&(bn)->bn_rbnode), \
 340                                    struct xbitmap32_node, bn_rbnode))
 341
 342 /* Clear a range of this bitmap. */
 343 int
 344 xbitmap32_clear(
 345         struct xbitmap32        *bitmap,
 346         uint32_t                start,
 347         uint32_t                len)
 348 {
 349         struct xbitmap32_node   *bn;
 350         struct xbitmap32_node   *new_bn;
 351         uint32_t                last = start + len - 1;
 352
 353         while ((bn = xbitmap32_tree_iter_first(&bitmap->xb_root, start, last))) {
 354                 if (bn->bn_start < start && bn->bn_last > last) {
 355                         uint32_t        old_last = bn->bn_last;
 356
 357                         /* overlaps with the entire clearing range */
 358                         xbitmap32_tree_remove(bn, &bitmap->xb_root);
 359                         bn->bn_last = start - 1;
 360                         xbitmap32_tree_insert(bn, &bitmap->xb_root);
 361
 362                         /* add an extent */
 363                         new_bn = kmalloc(sizeof(struct xbitmap32_node),
 364                                         XCHK_GFP_FLAGS);
 365                         if (!new_bn)
 366                                 return -ENOMEM;
 367                         new_bn->bn_start = last + 1;
 368                         new_bn->bn_last = old_last;
 369                         xbitmap32_tree_insert(new_bn, &bitmap->xb_root);
 370                 } else if (bn->bn_start < start) {
 371                         /* overlaps with the left side of the clearing range */
 372                         xbitmap32_tree_remove(bn, &bitmap->xb_root);
 373                         bn->bn_last = start - 1;
 374                         xbitmap32_tree_insert(bn, &bitmap->xb_root);
 375                 } else if (bn->bn_last > last) {
 376                         /* overlaps with the right side of the clearing range */
 377                         xbitmap32_tree_remove(bn, &bitmap->xb_root);
 378                         bn->bn_start = last + 1;
 379                         xbitmap32_tree_insert(bn, &bitmap->xb_root);
 380                         break;
 381                 } else {
 382                         /* in the middle of the clearing range */
 383                         xbitmap32_tree_remove(bn, &bitmap->xb_root);
 384                         kfree(bn);
 385                 }
 386         }
 387
 388         return 0;
 389 }
 390
 391 /* Set a range of this bitmap. */
 392 int
 393 xbitmap32_set(
 394         struct xbitmap32        *bitmap,
 395         uint32_t                start,
 396         uint32_t                len)
 397 {
 398         struct xbitmap32_node   *left;
 399         struct xbitmap32_node   *right;
 400         uint32_t                last = start + len - 1;
 401         int                     error;
 402
 403         /* Is this whole range already set? */
 404         left = xbitmap32_tree_iter_first(&bitmap->xb_root, start, last);
 405         if (left && left->bn_start <= start && left->bn_last >= last)
 406                 return 0;
 407
 408         /* Clear out everything in the range we want to set. */
 409         error = xbitmap32_clear(bitmap, start, len);
 410         if (error)
 411                 return error;
 412
 413         /* Do we have a left-adjacent extent? */
 414         left = xbitmap32_tree_iter_first(&bitmap->xb_root, start - 1, start - 1);
 415         ASSERT(!left || left->bn_last + 1 == start);
 416
 417         /* Do we have a right-adjacent extent? */
 418         right = xbitmap32_tree_iter_first(&bitmap->xb_root, last + 1, last + 1);
 419         ASSERT(!right || right->bn_start == last + 1);
 420
 421         if (left && right) {
 422                 /* combine left and right adjacent extent */
 423                 xbitmap32_tree_remove(left, &bitmap->xb_root);
 424                 xbitmap32_tree_remove(right, &bitmap->xb_root);
 425                 left->bn_last = right->bn_last;
 426                 xbitmap32_tree_insert(left, &bitmap->xb_root);
 427                 kfree(right);
 428         } else if (left) {
 429                 /* combine with left extent */
 430                 xbitmap32_tree_remove(left, &bitmap->xb_root);
 431                 left->bn_last = last;
 432                 xbitmap32_tree_insert(left, &bitmap->xb_root);
 433         } else if (right) {
 434                 /* combine with right extent */
 435                 xbitmap32_tree_remove(right, &bitmap->xb_root);
 436                 right->bn_start = start;
 437                 xbitmap32_tree_insert(right, &bitmap->xb_root);
 438         } else {
 439                 /* add an extent */
 440                 left = kmalloc(sizeof(struct xbitmap32_node), XCHK_GFP_FLAGS);
 441                 if (!left)
 442                         return -ENOMEM;
 443                 left->bn_start = start;
 444                 left->bn_last = last;
 445                 xbitmap32_tree_insert(left, &bitmap->xb_root);
 446         }
 447
 448         return 0;
 449 }
 450
 451 /* Free everything related to this bitmap. */
 452 void
 453 xbitmap32_destroy(
 454         struct xbitmap32        *bitmap)
 455 {
 456         struct xbitmap32_node   *bn;
 457
 458         while ((bn = xbitmap32_tree_iter_first(&bitmap->xb_root, 0, -1U))) {
 459                 xbitmap32_tree_remove(bn, &bitmap->xb_root);
 460                 kfree(bn);
 461         }
 462 }
 463
 464 /* Set up a per-AG block bitmap. */
 465 void
 466 xbitmap32_init(
 467         struct xbitmap32        *bitmap)
 468 {
 469         bitmap->xb_root = RB_ROOT_CACHED;
 470 }
 471
 472 /*
 473  * Remove all the blocks mentioned in @sub from the extents in @bitmap.
 474  *
 475  * The intent is that callers will iterate the rmapbt for all of its records
 476  * for a given owner to generate @bitmap; and iterate all the blocks of the
 477  * metadata structures that are not being rebuilt and have the same rmapbt
 478  * owner to generate @sub.  This routine subtracts all the extents
 479  * mentioned in sub from all the extents linked in @bitmap, which leaves
 480  * @bitmap as the list of blocks that are not accounted for, which we assume
 481  * are the dead blocks of the old metadata structure.  The blocks mentioned in
 482  * @bitmap can be reaped.
 483  *
 484  * This is the logical equivalent of bitmap &= ~sub.
 485  */
 486 int
 487 xbitmap32_disunion(
 488         struct xbitmap32        *bitmap,
 489         struct xbitmap32        *sub)
 490 {
 491         struct xbitmap32_node   *bn;
 492         int                     error;
 493
 494         if (xbitmap32_empty(bitmap) || xbitmap32_empty(sub))
 495                 return 0;
 496
 497         for_each_xbitmap32_extent(bn, sub) {
 498                 error = xbitmap32_clear(bitmap, bn->bn_start,
 499                                 bn->bn_last - bn->bn_start + 1);
 500                 if (error)
 501                         return error;
 502         }
 503
 504         return 0;
 505 }
 506
 507 /* How many bits are set in this bitmap? */
 508 uint32_t
 509 xbitmap32_hweight(
 510         struct xbitmap32        *bitmap)
 511 {
 512         struct xbitmap32_node   *bn;
 513         uint32_t                ret = 0;
 514
 515         for_each_xbitmap32_extent(bn, bitmap)
 516                 ret += bn->bn_last - bn->bn_start + 1;
 517
 518         return ret;
 519 }
 520
 521 /* Call a function for every run of set bits in this bitmap. */
 522 int
 523 xbitmap32_walk(
 524         struct xbitmap32        *bitmap,
 525         xbitmap32_walk_fn       fn,
 526         void                    *priv)
 527 {
 528         struct xbitmap32_node   *bn;
 529         int                     error = 0;
 530
 531         for_each_xbitmap32_extent(bn, bitmap) {
 532                 error = fn(bn->bn_start, bn->bn_last - bn->bn_start + 1, priv);
 533                 if (error)
 534                         break;
 535         }
 536
 537         return error;
 538 }
 539
 540 /* Does this bitmap have no bits set at all? */
 541 bool
 542 xbitmap32_empty(
 543         struct xbitmap32        *bitmap)
 544 {
 545         return bitmap->xb_root.rb_root.rb_node == NULL;
 546 }
 547
 548 /* Is the start of the range set or clear?  And for how long? */
 549 bool
 550 xbitmap32_test(
 551         struct xbitmap32        *bitmap,
 552         uint32_t                start,
 553         uint32_t                *len)
 554 {
 555         struct xbitmap32_node   *bn;
 556         uint32_t                last = start + *len - 1;
 557
 558         bn = xbitmap32_tree_iter_first(&bitmap->xb_root, start, last);
 559         if (!bn)
 560                 return false;
 561         if (bn->bn_start <= start) {
 562                 if (bn->bn_last < last)
 563                         *len = bn->bn_last - start + 1;
 564                 return true;
 565         }
 566         *len = bn->bn_start - start;
 567         return false;
 568 }
 569
 570 /* Count the number of set regions in this bitmap. */
 571 uint32_t
 572 xbitmap32_count_set_regions(
 573         struct xbitmap32        *bitmap)
 574 {
 575         struct xbitmap32_node   *bn;
 576         uint32_t                nr = 0;
 577
 578         for_each_xbitmap32_extent(bn, bitmap)
 579                 nr++;
 580
 581         return nr;
 582 }