1 // SPDX-License-Identifier: GPL-2.0-or-later
3  * Copyright (C) 2018-2023 Oracle.  All Rights Reserved.
34 #define START(node) ((node)->bn_start)
35 #define LAST(node)  ((node)->bn_last)
39  * forward-declare them anyway for clarity.
60 	for ((bn) = rb_entry_safe(rb_first(&(bitmap)->xb_root.rb_root), \  in INTERVAL_TREE_DEFINE()
63 	     (bn) = rb_entry_safe(rb_next(&(bn)->bn_rbnode), \
75 	uint64_t		last = start + len - 1;
77 	while ((bn = xbitmap_tree_iter_first(&bitmap->xb_root, start, last))) {
78 		if (bn->bn_start < start && bn->bn_last > last) {
79 			uint64_t	old_last = bn->bn_last;
82 			xbitmap_tree_remove(bn, &bitmap->xb_root);
83 			bn->bn_last = start - 1;
84 			xbitmap_tree_insert(bn, &bitmap->xb_root);
90 				return -ENOMEM;
91 			new_bn->bn_start = last + 1;
92 			new_bn->bn_last = old_last;
93 			xbitmap_tree_insert(new_bn, &bitmap->xb_root);
94 		} else if (bn->bn_start < start) {
96 			xbitmap_tree_remove(bn, &bitmap->xb_root);
97 			bn->bn_last = start - 1;
98 			xbitmap_tree_insert(bn, &bitmap->xb_root);
99 		} else if (bn->bn_last > last) {
101 			xbitmap_tree_remove(bn, &bitmap->xb_root);
102 			bn->bn_start = last + 1;
103 			xbitmap_tree_insert(bn, &bitmap->xb_root);
107 			xbitmap_tree_remove(bn, &bitmap->xb_root);
124 	uint64_t		last = start + len - 1;  in xbitmap_set()
128 	left = xbitmap_tree_iter_first(&bitmap->xb_root, start, last);  in xbitmap_set()
129 	if (left && left->bn_start <= start && left->bn_last >= last)  in xbitmap_set()
137 	/* Do we have a left-adjacent extent? */  in xbitmap_set()
138 	left = xbitmap_tree_iter_first(&bitmap->xb_root, start - 1, start - 1);  in xbitmap_set()
139 	ASSERT(!left || left->bn_last + 1 == start);  in xbitmap_set()
141 	/* Do we have a right-adjacent extent? */  in xbitmap_set()
142 	right = xbitmap_tree_iter_first(&bitmap->xb_root, last + 1, last + 1);  in xbitmap_set()
143 	ASSERT(!right || right->bn_start == last + 1);  in xbitmap_set()
147 		xbitmap_tree_remove(left, &bitmap->xb_root);  in xbitmap_set()
148 		xbitmap_tree_remove(right, &bitmap->xb_root);  in xbitmap_set()
149 		left->bn_last = right->bn_last;  in xbitmap_set()
150 		xbitmap_tree_insert(left, &bitmap->xb_root);  in xbitmap_set()
154 		xbitmap_tree_remove(left, &bitmap->xb_root);  in xbitmap_set()
155 		left->bn_last = last;  in xbitmap_set()
156 		xbitmap_tree_insert(left, &bitmap->xb_root);  in xbitmap_set()
159 		xbitmap_tree_remove(right, &bitmap->xb_root);  in xbitmap_set()
160 		right->bn_start = start;  in xbitmap_set()
161 		xbitmap_tree_insert(right, &bitmap->xb_root);  in xbitmap_set()
166 			return -ENOMEM;  in xbitmap_set()
167 		left->bn_start = start;  in xbitmap_set()
168 		left->bn_last = last;  in xbitmap_set()
169 		xbitmap_tree_insert(left, &bitmap->xb_root);  in xbitmap_set()
182 	while ((bn = xbitmap_tree_iter_first(&bitmap->xb_root, 0, -1ULL))) {  in xbitmap_destroy()
183 		xbitmap_tree_remove(bn, &bitmap->xb_root);  in xbitmap_destroy()
188 /* Set up a per-AG block bitmap. */
193 	bitmap->xb_root = RB_ROOT_CACHED;  in xbitmap_init()
197  * Remove all the blocks mentioned in @sub from the extents in @bitmap.
200  * for a given owner to generate @bitmap; and iterate all the blocks of the
202  * owner to generate @sub.  This routine subtracts all the extents
203  * mentioned in sub from all the extents linked in @bitmap, which leaves
204  * @bitmap as the list of blocks that are not accounted for, which we assume
205  * are the dead blocks of the old metadata structure.  The blocks mentioned in
208  * This is the logical equivalent of bitmap &= ~sub.
213 	struct xbitmap		*sub)  in xbitmap_disunion()  argument
218 	if (xbitmap_empty(bitmap) || xbitmap_empty(sub))  in xbitmap_disunion()
221 	for_each_xbitmap_extent(bn, sub) {  in xbitmap_disunion()
222 		error = xbitmap_clear(bitmap, bn->bn_start,  in xbitmap_disunion()
223 				bn->bn_last - bn->bn_start + 1);  in xbitmap_disunion()
232  * Record all btree blocks seen while iterating all records of a btree.
282 	fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, xfs_buf_daddr(bp));  in xagb_bitmap_visit_btblock()
283 	agbno = XFS_FSB_TO_AGBNO(cur->bc_mp, fsbno);  in xagb_bitmap_visit_btblock()
288 /* Mark all (per-AG) btree blocks in the agblock bitmap. */
301  * blocks going from the leaf towards the root.
311 	for (i = 0; i < cur->bc_nlevels && cur->bc_levels[i].ptr == 1; i++) {  in xagb_bitmap_set_btcur_path()
329 		ret += bn->bn_last - bn->bn_start + 1;  in xbitmap_hweight()
345 		error = fn(bn->bn_start, bn->bn_last - bn->bn_start + 1, priv);  in xbitmap_walk()
358 	return bitmap->xb_root.rb_root.rb_node == NULL;  in xbitmap_empty()
369 	uint64_t		last = start + *len - 1;  in xbitmap_test()
371 	bn = xbitmap_tree_iter_first(&bitmap->xb_root, start, last);  in xbitmap_test()
374 	if (bn->bn_start <= start) {  in xbitmap_test()
375 		if (bn->bn_last < last)  in xbitmap_test()
376 			*len = bn->bn_last - start + 1;  in xbitmap_test()
379 	*len = bn->bn_start - start;  in xbitmap_test()