1 // SPDX-License-Identifier: GPL-2.0+
35 		return -ENOMEM;  in xfs_bitmap_set()
37 	INIT_LIST_HEAD(&bmr->list);  in xfs_bitmap_set()
38 	bmr->start = start;  in xfs_bitmap_set()
39 	bmr->len = len;  in xfs_bitmap_set()
40 	list_add_tail(&bmr->list, &bitmap->list);  in xfs_bitmap_set()
54 		list_del(&bmr->list);  in xfs_bitmap_destroy()
59 /* Set up a per-AG block bitmap. */
64 	INIT_LIST_HEAD(&bitmap->list);  in xfs_bitmap_init()
80 	if (ap->start > bp->start)  in xfs_bitmap_range_cmp()
82 	if (ap->start < bp->start)  in xfs_bitmap_range_cmp()
83 		return -1;  in xfs_bitmap_range_cmp()
88  * Remove all the blocks mentioned in @sub from the extents in @bitmap.
93  * owner to generate @sub.  This routine subtracts all the extents
94  * mentioned in sub from all the extents linked in @bitmap, which leaves
99  * This is the logical equivalent of bitmap &= ~sub.
106 	struct xfs_bitmap	*sub)  in xfs_bitmap_disunion()  argument
117 	if (list_empty(&bitmap->list) || list_empty(&sub->list))  in xfs_bitmap_disunion()
119 	ASSERT(!list_empty(&sub->list));  in xfs_bitmap_disunion()
121 	list_sort(NULL, &bitmap->list, xfs_bitmap_range_cmp);  in xfs_bitmap_disunion()
122 	list_sort(NULL, &sub->list, xfs_bitmap_range_cmp);  in xfs_bitmap_disunion()
126 	 * forward through sub and/or bitmap as necessary until we find an  in xfs_bitmap_disunion()
128 	 * head of bitmap nor do we reset sub_br to the head of sub.  The  in xfs_bitmap_disunion()
132 	sub_br = list_first_entry(&sub->list, struct xfs_bitmap_range,  in xfs_bitmap_disunion()
134 	lp = bitmap->list.next;  in xfs_bitmap_disunion()
135 	while (lp != &bitmap->list) {  in xfs_bitmap_disunion()
142 		while (sub_br->start + sub_br->len <= br->start) {  in xfs_bitmap_disunion()
143 			if (list_is_last(&sub_br->list, &sub->list))  in xfs_bitmap_disunion()
147 		if (sub_br->start >= br->start + br->len) {  in xfs_bitmap_disunion()
148 			lp = lp->next;  in xfs_bitmap_disunion()
153 		sub_start = sub_br->start;  in xfs_bitmap_disunion()
154 		sub_len = sub_br->len;  in xfs_bitmap_disunion()
155 		if (sub_br->start < br->start) {  in xfs_bitmap_disunion()
156 			sub_len -= br->start - sub_br->start;  in xfs_bitmap_disunion()
157 			sub_start = br->start;  in xfs_bitmap_disunion()
159 		if (sub_len > br->len)  in xfs_bitmap_disunion()
160 			sub_len = br->len;  in xfs_bitmap_disunion()
163 		if (sub_start == br->start)  in xfs_bitmap_disunion()
165 		if (sub_start + sub_len == br->start + br->len)  in xfs_bitmap_disunion()
170 			br->start += sub_len;  in xfs_bitmap_disunion()
171 			br->len -= sub_len;  in xfs_bitmap_disunion()
175 			br->len -= sub_len;  in xfs_bitmap_disunion()
176 			lp = lp->next;  in xfs_bitmap_disunion()
180 			lp = lp->next;  in xfs_bitmap_disunion()
181 			list_del(&br->list);  in xfs_bitmap_disunion()
192 				error = -ENOMEM;  in xfs_bitmap_disunion()
195 			INIT_LIST_HEAD(&new_br->list);  in xfs_bitmap_disunion()
196 			new_br->start = sub_start + sub_len;  in xfs_bitmap_disunion()
197 			new_br->len = br->start + br->len - new_br->start;  in xfs_bitmap_disunion()
198 			list_add(&new_br->list, &br->list);  in xfs_bitmap_disunion()
199 			br->len = sub_start - br->start;  in xfs_bitmap_disunion()
200 			lp = lp->next;  in xfs_bitmap_disunion()
220  * to the first record/key in that block, we haven't seen this block before;
221  * and therefore we need to remember that we saw this block in the btree.
229  * Pretend for this example that each leaf block has 100 btree records.  For
231  * that we saw block 1.  Then we observe that bc_ptrs[1] == 1, so we record
232  * block 4.  The list is [1, 4].
237  * For the 101st btree record, we've moved onto leaf block 2.  Now
238  * bc_ptrs[0] == 1 again, so we record that we saw block 2.  We see that
243  * For the 201st record, we've moved on to leaf block 3.  bc_ptrs[0] == 1, so
264 	for (i = 0; i < cur->bc_nlevels && cur->bc_ptrs[i] == 1; i++) {  in xfs_bitmap_set_btcur_path()
268 		fsb = XFS_DADDR_TO_FSB(cur->bc_mp, bp->b_bn);  in xfs_bitmap_set_btcur_path()
277 /* Collect a btree's block in the bitmap. */
292 	fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, bp->b_bn);  in xfs_bitmap_collect_btblock()
296 /* Walk the btree and mark the bitmap wherever a btree block is found. */