585 lines · c
1// SPDX-License-Identifier: GPL-2.0-or-later2/*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 21struct 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'll41 * forward-declare them anyway for clarity.42 */43static inline __maybe_unused void44xbitmap64_tree_insert(struct xbitmap64_node *node, struct rb_root_cached *root);45 46static inline __maybe_unused void47xbitmap64_tree_remove(struct xbitmap64_node *node, struct rb_root_cached *root);48 49static inline __maybe_unused struct xbitmap64_node *50xbitmap64_tree_iter_first(struct rb_root_cached *root, uint64_t start,51 uint64_t last);52 53static inline __maybe_unused struct xbitmap64_node *54xbitmap64_tree_iter_next(struct xbitmap64_node *node, uint64_t start,55 uint64_t last);56 57INTERVAL_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. */70int71xbitmap64_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. */119int120xbitmap64_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. */179void180xbitmap64_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. */192void193xbitmap64_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 records203 * for a given owner to generate @bitmap; and iterate all the blocks of the204 * metadata structures that are not being rebuilt and have the same rmapbt205 * owner to generate @sub. This routine subtracts all the extents206 * mentioned in sub from all the extents linked in @bitmap, which leaves207 * @bitmap as the list of blocks that are not accounted for, which we assume208 * are the dead blocks of the old metadata structure. The blocks mentioned in209 * @bitmap can be reaped.210 *211 * This is the logical equivalent of bitmap &= ~sub.212 */213int214xbitmap64_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? */235uint64_t236xbitmap64_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. */249int250xbitmap64_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? */268bool269xbitmap64_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? */276bool277xbitmap64_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 299struct 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'll316 * forward-declare them anyway for clarity.317 */318static inline __maybe_unused void319xbitmap32_tree_insert(struct xbitmap32_node *node, struct rb_root_cached *root);320 321static inline __maybe_unused void322xbitmap32_tree_remove(struct xbitmap32_node *node, struct rb_root_cached *root);323 324static inline __maybe_unused struct xbitmap32_node *325xbitmap32_tree_iter_first(struct rb_root_cached *root, uint32_t start,326 uint32_t last);327 328static inline __maybe_unused struct xbitmap32_node *329xbitmap32_tree_iter_next(struct xbitmap32_node *node, uint32_t start,330 uint32_t last);331 332INTERVAL_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. */345int346xbitmap32_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. */394int395xbitmap32_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. */454void455xbitmap32_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. */467void468xbitmap32_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 records478 * for a given owner to generate @bitmap; and iterate all the blocks of the479 * metadata structures that are not being rebuilt and have the same rmapbt480 * owner to generate @sub. This routine subtracts all the extents481 * mentioned in sub from all the extents linked in @bitmap, which leaves482 * @bitmap as the list of blocks that are not accounted for, which we assume483 * are the dead blocks of the old metadata structure. The blocks mentioned in484 * @bitmap can be reaped.485 *486 * This is the logical equivalent of bitmap &= ~sub.487 */488int489xbitmap32_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? */510uint32_t511xbitmap32_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. */524int525xbitmap32_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? */543bool544xbitmap32_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? */551bool552xbitmap32_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. */573uint32_t574xbitmap32_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}585