15 #include "scrub/bitmap.h"
19 /* u64 bitmap */
61 /* Iterate each interval of a bitmap.  Do not change the bitmap. */  in INTERVAL_TREE_DEFINE()
62 #define for_each_xbitmap64_extent(bn, bitmap) \  in INTERVAL_TREE_DEFINE()  argument
63 	for ((bn) = rb_entry_safe(rb_first(&(bitmap)->xb_root.rb_root), \  in INTERVAL_TREE_DEFINE()
69 /* Clear a range of this bitmap. */
72 	struct xbitmap64	*bitmap,
80 	while ((bn = xbitmap64_tree_iter_first(&bitmap->xb_root, start, last))) {
85 			xbitmap64_tree_remove(bn, &bitmap->xb_root);
87 			xbitmap64_tree_insert(bn, &bitmap->xb_root);
96 			xbitmap64_tree_insert(new_bn, &bitmap->xb_root);
99 			xbitmap64_tree_remove(bn, &bitmap->xb_root);
101 			xbitmap64_tree_insert(bn, &bitmap->xb_root);
104 			xbitmap64_tree_remove(bn, &bitmap->xb_root);
106 			xbitmap64_tree_insert(bn, &bitmap->xb_root);
110 			xbitmap64_tree_remove(bn, &bitmap->xb_root);
118 /* Set a range of this bitmap. */
121 	struct xbitmap64	*bitmap,  in xbitmap64_set()  argument
131 	left = xbitmap64_tree_iter_first(&bitmap->xb_root, start, last);  in xbitmap64_set()
136 	error = xbitmap64_clear(bitmap, start, len);  in xbitmap64_set()
141 	left = xbitmap64_tree_iter_first(&bitmap->xb_root, start - 1, start - 1);  in xbitmap64_set()
145 	right = xbitmap64_tree_iter_first(&bitmap->xb_root, last + 1, last + 1);  in xbitmap64_set()
150 		xbitmap64_tree_remove(left, &bitmap->xb_root);  in xbitmap64_set()
151 		xbitmap64_tree_remove(right, &bitmap->xb_root);  in xbitmap64_set()
153 		xbitmap64_tree_insert(left, &bitmap->xb_root);  in xbitmap64_set()
157 		xbitmap64_tree_remove(left, &bitmap->xb_root);  in xbitmap64_set()
159 		xbitmap64_tree_insert(left, &bitmap->xb_root);  in xbitmap64_set()
162 		xbitmap64_tree_remove(right, &bitmap->xb_root);  in xbitmap64_set()
164 		xbitmap64_tree_insert(right, &bitmap->xb_root);  in xbitmap64_set()
172 		xbitmap64_tree_insert(left, &bitmap->xb_root);  in xbitmap64_set()
178 /* Free everything related to this bitmap. */
181 	struct xbitmap64	*bitmap)  in xbitmap64_destroy()  argument
185 	while ((bn = xbitmap64_tree_iter_first(&bitmap->xb_root, 0, -1ULL))) {  in xbitmap64_destroy()
186 		xbitmap64_tree_remove(bn, &bitmap->xb_root);  in xbitmap64_destroy()
191 /* Set up a per-AG block bitmap. */
194 	struct xbitmap64	*bitmap)  in xbitmap64_init()  argument
196 	bitmap->xb_root = RB_ROOT_CACHED;  in xbitmap64_init()
200  * Remove all the blocks mentioned in @sub from the extents in @bitmap.
203  * for a given owner to generate @bitmap; and iterate all the blocks of the
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
209  * @bitmap can be reaped.
211  * This is the logical equivalent of bitmap &= ~sub.
215 	struct xbitmap64	*bitmap,  in xbitmap64_disunion()  argument
221 	if (xbitmap64_empty(bitmap) || xbitmap64_empty(sub))  in xbitmap64_disunion()
225 		error = xbitmap64_clear(bitmap, bn->bn_start,  in xbitmap64_disunion()
234 /* How many bits are set in this bitmap? */
237 	struct xbitmap64	*bitmap)  in xbitmap64_hweight()  argument
242 	for_each_xbitmap64_extent(bn, bitmap)  in xbitmap64_hweight()
248 /* Call a function for every run of set bits in this bitmap. */
251 	struct xbitmap64	*bitmap,  in xbitmap64_walk()  argument
258 	for_each_xbitmap64_extent(bn, bitmap) {  in xbitmap64_walk()
267 /* Does this bitmap have no bits set at all? */
270 	struct xbitmap64	*bitmap)  in xbitmap64_empty()  argument
272 	return bitmap->xb_root.rb_root.rb_node == NULL;  in xbitmap64_empty()
278 	struct xbitmap64	*bitmap,  in xbitmap64_test()  argument
285 	bn = xbitmap64_tree_iter_first(&bitmap->xb_root, start, last);  in xbitmap64_test()
297 /* u32 bitmap */
336 /* Iterate each interval of a bitmap.  Do not change the bitmap. */  in INTERVAL_TREE_DEFINE()
337 #define for_each_xbitmap32_extent(bn, bitmap) \  in INTERVAL_TREE_DEFINE()  argument
338 	for ((bn) = rb_entry_safe(rb_first(&(bitmap)->xb_root.rb_root), \  in INTERVAL_TREE_DEFINE()
344 /* Clear a range of this bitmap. */
347 	struct xbitmap32	*bitmap,
355 	while ((bn = xbitmap32_tree_iter_first(&bitmap->xb_root, start, last))) {
360 			xbitmap32_tree_remove(bn, &bitmap->xb_root);
362 			xbitmap32_tree_insert(bn, &bitmap->xb_root);
371 			xbitmap32_tree_insert(new_bn, &bitmap->xb_root);
374 			xbitmap32_tree_remove(bn, &bitmap->xb_root);
376 			xbitmap32_tree_insert(bn, &bitmap->xb_root);
379 			xbitmap32_tree_remove(bn, &bitmap->xb_root);
381 			xbitmap32_tree_insert(bn, &bitmap->xb_root);
385 			xbitmap32_tree_remove(bn, &bitmap->xb_root);
393 /* Set a range of this bitmap. */
396 	struct xbitmap32	*bitmap,  in xbitmap32_set()  argument
406 	left = xbitmap32_tree_iter_first(&bitmap->xb_root, start, last);  in xbitmap32_set()
411 	error = xbitmap32_clear(bitmap, start, len);  in xbitmap32_set()
416 	left = xbitmap32_tree_iter_first(&bitmap->xb_root, start - 1, start - 1);  in xbitmap32_set()
420 	right = xbitmap32_tree_iter_first(&bitmap->xb_root, last + 1, last + 1);  in xbitmap32_set()
425 		xbitmap32_tree_remove(left, &bitmap->xb_root);  in xbitmap32_set()
426 		xbitmap32_tree_remove(right, &bitmap->xb_root);  in xbitmap32_set()
428 		xbitmap32_tree_insert(left, &bitmap->xb_root);  in xbitmap32_set()
432 		xbitmap32_tree_remove(left, &bitmap->xb_root);  in xbitmap32_set()
434 		xbitmap32_tree_insert(left, &bitmap->xb_root);  in xbitmap32_set()
437 		xbitmap32_tree_remove(right, &bitmap->xb_root);  in xbitmap32_set()
439 		xbitmap32_tree_insert(right, &bitmap->xb_root);  in xbitmap32_set()
447 		xbitmap32_tree_insert(left, &bitmap->xb_root);  in xbitmap32_set()
453 /* Free everything related to this bitmap. */
456 	struct xbitmap32	*bitmap)  in xbitmap32_destroy()  argument
460 	while ((bn = xbitmap32_tree_iter_first(&bitmap->xb_root, 0, -1U))) {  in xbitmap32_destroy()
461 		xbitmap32_tree_remove(bn, &bitmap->xb_root);  in xbitmap32_destroy()
466 /* Set up a per-AG block bitmap. */
469 	struct xbitmap32	*bitmap)  in xbitmap32_init()  argument
471 	bitmap->xb_root = RB_ROOT_CACHED;  in xbitmap32_init()
475  * Remove all the blocks mentioned in @sub from the extents in @bitmap.
478  * for a given owner to generate @bitmap; and iterate all the blocks of the
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
484  * @bitmap can be reaped.
486  * This is the logical equivalent of bitmap &= ~sub.
490 	struct xbitmap32	*bitmap,  in xbitmap32_disunion()  argument
496 	if (xbitmap32_empty(bitmap) || xbitmap32_empty(sub))  in xbitmap32_disunion()
500 		error = xbitmap32_clear(bitmap, bn->bn_start,  in xbitmap32_disunion()
509 /* How many bits are set in this bitmap? */
512 	struct xbitmap32	*bitmap)  in xbitmap32_hweight()  argument
517 	for_each_xbitmap32_extent(bn, bitmap)  in xbitmap32_hweight()
523 /* Call a function for every run of set bits in this bitmap. */
526 	struct xbitmap32	*bitmap,  in xbitmap32_walk()  argument
533 	for_each_xbitmap32_extent(bn, bitmap) {  in xbitmap32_walk()
542 /* Does this bitmap have no bits set at all? */
545 	struct xbitmap32	*bitmap)  in xbitmap32_empty()  argument
547 	return bitmap->xb_root.rb_root.rb_node == NULL;  in xbitmap32_empty()
553 	struct xbitmap32	*bitmap,  in xbitmap32_test()  argument
560 	bn = xbitmap32_tree_iter_first(&bitmap->xb_root, start, last);  in xbitmap32_test()
572 /* Count the number of set regions in this bitmap. */
575 	struct xbitmap32	*bitmap)  in xbitmap32_count_set_regions()  argument
580 	for_each_xbitmap32_extent(bn, bitmap)  in xbitmap32_count_set_regions()