| 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 | } |