1 // SPDX-License-Identifier: GPL-2.0-or-later
3  * Copyright (C) 2018-2023 Oracle.  All Rights Reserved.
25 	/* Last set bit of this interval. */
28 	/* Last set bit of this subtree.  Do not touch this. */
34 #define START(node) ((node)->bn_start)
35 #define LAST(node)  ((node)->bn_last)  macro
39  * forward-declare them anyway for clarity.
49 			uint64_t last);
53 		       uint64_t last);
56 		__bn_subtree_last, START, LAST, static inline, xbitmap_tree)  in INTERVAL_TREE_DEFINE()  argument
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;  local
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()  local
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()
222 		error = xbitmap_clear(bitmap, bn->bn_start,  in xbitmap_disunion()
223 				bn->bn_last - bn->bn_start + 1);  in xbitmap_disunion()
236  * the btree cursor towards the root; if the pointer for a given level points
270 	int			level,  in xagb_bitmap_visit_btblock()  argument
278 	xfs_btree_get_block(cur, level, &bp);  in xagb_bitmap_visit_btblock()
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. */
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()  local
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()