Lines Matching +full:sub +full:- +full:blocks
1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * Copyright (C) 2018-2023 Oracle. All Rights Reserved.
36 #define START(node) ((node)->bn_start)
37 #define LAST(node) ((node)->bn_last)
41 * forward-declare them anyway for clarity.
62 for ((bn) = rb_entry_safe(rb_first(&(bitmap)->xb_root.rb_root), \ in INTERVAL_TREE_DEFINE()
65 (bn) = rb_entry_safe(rb_next(&(bn)->bn_rbnode), \
77 uint64_t last = start + len - 1;
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;
84 xbitmap64_tree_remove(bn, &bitmap->xb_root);
85 bn->bn_last = start - 1;
86 xbitmap64_tree_insert(bn, &bitmap->xb_root);
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) {
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) {
103 xbitmap64_tree_remove(bn, &bitmap->xb_root);
104 bn->bn_start = last + 1;
105 xbitmap64_tree_insert(bn, &bitmap->xb_root);
109 xbitmap64_tree_remove(bn, &bitmap->xb_root);
126 uint64_t last = start + len - 1; in xbitmap64_set()
130 left = xbitmap64_tree_iter_first(&bitmap->xb_root, start, last); in xbitmap64_set()
131 if (left && left->bn_start <= start && left->bn_last >= last) in xbitmap64_set()
139 /* Do we have a left-adjacent extent? */ in xbitmap64_set()
140 left = xbitmap64_tree_iter_first(&bitmap->xb_root, start - 1, start - 1); in xbitmap64_set()
141 ASSERT(!left || left->bn_last + 1 == start); in xbitmap64_set()
143 /* Do we have a right-adjacent extent? */ in xbitmap64_set()
144 right = xbitmap64_tree_iter_first(&bitmap->xb_root, last + 1, last + 1); in xbitmap64_set()
145 ASSERT(!right || right->bn_start == last + 1); in xbitmap64_set()
149 xbitmap64_tree_remove(left, &bitmap->xb_root); in xbitmap64_set()
150 xbitmap64_tree_remove(right, &bitmap->xb_root); in xbitmap64_set()
151 left->bn_last = right->bn_last; in xbitmap64_set()
152 xbitmap64_tree_insert(left, &bitmap->xb_root); in xbitmap64_set()
156 xbitmap64_tree_remove(left, &bitmap->xb_root); in xbitmap64_set()
157 left->bn_last = last; in xbitmap64_set()
158 xbitmap64_tree_insert(left, &bitmap->xb_root); in xbitmap64_set()
161 xbitmap64_tree_remove(right, &bitmap->xb_root); in xbitmap64_set()
162 right->bn_start = start; in xbitmap64_set()
163 xbitmap64_tree_insert(right, &bitmap->xb_root); in xbitmap64_set()
168 return -ENOMEM; in xbitmap64_set()
169 left->bn_start = start; in xbitmap64_set()
170 left->bn_last = last; in xbitmap64_set()
171 xbitmap64_tree_insert(left, &bitmap->xb_root); in xbitmap64_set()
184 while ((bn = xbitmap64_tree_iter_first(&bitmap->xb_root, 0, -1ULL))) { in xbitmap64_destroy()
185 xbitmap64_tree_remove(bn, &bitmap->xb_root); in xbitmap64_destroy()
190 /* Set up a per-AG block bitmap. */
195 bitmap->xb_root = RB_ROOT_CACHED; in xbitmap64_init()
199 * Remove all the blocks mentioned in @sub from the extents in @bitmap.
202 * for a given owner to generate @bitmap; and iterate all the blocks of the
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
210 * This is the logical equivalent of bitmap &= ~sub.
215 struct xbitmap64 *sub) in xbitmap64_disunion() argument
220 if (xbitmap64_empty(bitmap) || xbitmap64_empty(sub)) in xbitmap64_disunion()
223 for_each_xbitmap64_extent(bn, sub) { in xbitmap64_disunion()
224 error = xbitmap64_clear(bitmap, bn->bn_start, in xbitmap64_disunion()
225 bn->bn_last - bn->bn_start + 1); in xbitmap64_disunion()
242 ret += bn->bn_last - bn->bn_start + 1; in xbitmap64_hweight()
258 error = fn(bn->bn_start, bn->bn_last - bn->bn_start + 1, priv); in xbitmap64_walk()
271 return bitmap->xb_root.rb_root.rb_node == NULL; in xbitmap64_empty()
282 uint64_t last = start + *len - 1; in xbitmap64_test()
284 bn = xbitmap64_tree_iter_first(&bitmap->xb_root, start, last); in xbitmap64_test()
287 if (bn->bn_start <= start) { in xbitmap64_test()
288 if (bn->bn_last < last) in xbitmap64_test()
289 *len = bn->bn_last - start + 1; in xbitmap64_test()
292 *len = bn->bn_start - start; in xbitmap64_test()
315 * forward-declare them anyway for clarity.
336 for ((bn) = rb_entry_safe(rb_first(&(bitmap)->xb_root.rb_root), \ in INTERVAL_TREE_DEFINE()
339 (bn) = rb_entry_safe(rb_next(&(bn)->bn_rbnode), \
351 uint32_t last = start + len - 1;
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;
358 xbitmap32_tree_remove(bn, &bitmap->xb_root);
359 bn->bn_last = start - 1;
360 xbitmap32_tree_insert(bn, &bitmap->xb_root);
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) {
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) {
377 xbitmap32_tree_remove(bn, &bitmap->xb_root);
378 bn->bn_start = last + 1;
379 xbitmap32_tree_insert(bn, &bitmap->xb_root);
383 xbitmap32_tree_remove(bn, &bitmap->xb_root);
400 uint32_t last = start + len - 1; in xbitmap32_set()
404 left = xbitmap32_tree_iter_first(&bitmap->xb_root, start, last); in xbitmap32_set()
405 if (left && left->bn_start <= start && left->bn_last >= last) in xbitmap32_set()
413 /* Do we have a left-adjacent extent? */ in xbitmap32_set()
414 left = xbitmap32_tree_iter_first(&bitmap->xb_root, start - 1, start - 1); in xbitmap32_set()
415 ASSERT(!left || left->bn_last + 1 == start); in xbitmap32_set()
417 /* Do we have a right-adjacent extent? */ in xbitmap32_set()
418 right = xbitmap32_tree_iter_first(&bitmap->xb_root, last + 1, last + 1); in xbitmap32_set()
419 ASSERT(!right || right->bn_start == last + 1); in xbitmap32_set()
423 xbitmap32_tree_remove(left, &bitmap->xb_root); in xbitmap32_set()
424 xbitmap32_tree_remove(right, &bitmap->xb_root); in xbitmap32_set()
425 left->bn_last = right->bn_last; in xbitmap32_set()
426 xbitmap32_tree_insert(left, &bitmap->xb_root); in xbitmap32_set()
430 xbitmap32_tree_remove(left, &bitmap->xb_root); in xbitmap32_set()
431 left->bn_last = last; in xbitmap32_set()
432 xbitmap32_tree_insert(left, &bitmap->xb_root); in xbitmap32_set()
435 xbitmap32_tree_remove(right, &bitmap->xb_root); in xbitmap32_set()
436 right->bn_start = start; in xbitmap32_set()
437 xbitmap32_tree_insert(right, &bitmap->xb_root); in xbitmap32_set()
442 return -ENOMEM; in xbitmap32_set()
443 left->bn_start = start; in xbitmap32_set()
444 left->bn_last = last; in xbitmap32_set()
445 xbitmap32_tree_insert(left, &bitmap->xb_root); in xbitmap32_set()
458 while ((bn = xbitmap32_tree_iter_first(&bitmap->xb_root, 0, -1U))) { in xbitmap32_destroy()
459 xbitmap32_tree_remove(bn, &bitmap->xb_root); in xbitmap32_destroy()
464 /* Set up a per-AG block bitmap. */
469 bitmap->xb_root = RB_ROOT_CACHED; in xbitmap32_init()
473 * Remove all the blocks mentioned in @sub from the extents in @bitmap.
476 * for a given owner to generate @bitmap; and iterate all the blocks of the
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
484 * This is the logical equivalent of bitmap &= ~sub.
489 struct xbitmap32 *sub) in xbitmap32_disunion() argument
494 if (xbitmap32_empty(bitmap) || xbitmap32_empty(sub)) in xbitmap32_disunion()
497 for_each_xbitmap32_extent(bn, sub) { in xbitmap32_disunion()
498 error = xbitmap32_clear(bitmap, bn->bn_start, in xbitmap32_disunion()
499 bn->bn_last - bn->bn_start + 1); in xbitmap32_disunion()
516 ret += bn->bn_last - bn->bn_start + 1; in xbitmap32_hweight()
532 error = fn(bn->bn_start, bn->bn_last - bn->bn_start + 1, priv); in xbitmap32_walk()
545 return bitmap->xb_root.rb_root.rb_node == NULL; in xbitmap32_empty()
556 uint32_t last = start + *len - 1; in xbitmap32_test()
558 bn = xbitmap32_tree_iter_first(&bitmap->xb_root, start, last); in xbitmap32_test()
561 if (bn->bn_start <= start) { in xbitmap32_test()
562 if (bn->bn_last < last) in xbitmap32_test()
563 *len = bn->bn_last - start + 1; in xbitmap32_test()
566 *len = bn->bn_start - start; in xbitmap32_test()