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