1 // SPDX-License-Identifier: GPL-2.0+
30 		return -ENOMEM;  in xbitmap_set()
32 	INIT_LIST_HEAD(&bmr->list);  in xbitmap_set()
33 	bmr->start = start;  in xbitmap_set()
34 	bmr->len = len;  in xbitmap_set()
35 	list_add_tail(&bmr->list, &bitmap->list);  in xbitmap_set()
49 		list_del(&bmr->list);  in xbitmap_destroy()
54 /* Set up a per-AG block bitmap. */
59 	INIT_LIST_HEAD(&bitmap->list);  in xbitmap_init()
75 	if (ap->start > bp->start)  in xbitmap_range_cmp()
77 	if (ap->start < bp->start)  in xbitmap_range_cmp()
78 		return -1;  in xbitmap_range_cmp()
83  * Remove all the blocks mentioned in @sub from the extents in @bitmap.
88  * owner to generate @sub.  This routine subtracts all the extents
89  * mentioned in sub from all the extents linked in @bitmap, which leaves
94  * This is the logical equivalent of bitmap &= ~sub.
101 	struct xbitmap		*sub)  in xbitmap_disunion()  argument
112 	if (list_empty(&bitmap->list) || list_empty(&sub->list))  in xbitmap_disunion()
114 	ASSERT(!list_empty(&sub->list));  in xbitmap_disunion()
116 	list_sort(NULL, &bitmap->list, xbitmap_range_cmp);  in xbitmap_disunion()
117 	list_sort(NULL, &sub->list, xbitmap_range_cmp);  in xbitmap_disunion()
121 	 * forward through sub and/or bitmap as necessary until we find an  in xbitmap_disunion()
123 	 * head of bitmap nor do we reset sub_br to the head of sub.  The  in xbitmap_disunion()
127 	sub_br = list_first_entry(&sub->list, struct xbitmap_range,  in xbitmap_disunion()
129 	lp = bitmap->list.next;  in xbitmap_disunion()
130 	while (lp != &bitmap->list) {  in xbitmap_disunion()
137 		while (sub_br->start + sub_br->len <= br->start) {  in xbitmap_disunion()
138 			if (list_is_last(&sub_br->list, &sub->list))  in xbitmap_disunion()
142 		if (sub_br->start >= br->start + br->len) {  in xbitmap_disunion()
143 			lp = lp->next;  in xbitmap_disunion()
148 		sub_start = sub_br->start;  in xbitmap_disunion()
149 		sub_len = sub_br->len;  in xbitmap_disunion()
150 		if (sub_br->start < br->start) {  in xbitmap_disunion()
151 			sub_len -= br->start - sub_br->start;  in xbitmap_disunion()
152 			sub_start = br->start;  in xbitmap_disunion()
154 		if (sub_len > br->len)  in xbitmap_disunion()
155 			sub_len = br->len;  in xbitmap_disunion()
158 		if (sub_start == br->start)  in xbitmap_disunion()
160 		if (sub_start + sub_len == br->start + br->len)  in xbitmap_disunion()
165 			br->start += sub_len;  in xbitmap_disunion()
166 			br->len -= sub_len;  in xbitmap_disunion()
170 			br->len -= sub_len;  in xbitmap_disunion()
171 			lp = lp->next;  in xbitmap_disunion()
175 			lp = lp->next;  in xbitmap_disunion()
176 			list_del(&br->list);  in xbitmap_disunion()
187 				error = -ENOMEM;  in xbitmap_disunion()
190 			INIT_LIST_HEAD(&new_br->list);  in xbitmap_disunion()
191 			new_br->start = sub_start + sub_len;  in xbitmap_disunion()
192 			new_br->len = br->start + br->len - new_br->start;  in xbitmap_disunion()
193 			list_add(&new_br->list, &br->list);  in xbitmap_disunion()
194 			br->len = sub_start - br->start;  in xbitmap_disunion()
195 			lp = lp->next;  in xbitmap_disunion()
215  * to the first record/key in that block, we haven't seen this block before;
216  * and therefore we need to remember that we saw this block in the btree.
224  * Pretend for this example that each leaf block has 100 btree records.  For
226  * that we saw block 1.  Then we observe that bc_ptrs[1] == 1, so we record
227  * block 4.  The list is [1, 4].
232  * For the 101st btree record, we've moved onto leaf block 2.  Now
233  * bc_ptrs[0] == 1 again, so we record that we saw block 2.  We see that
238  * For the 201st record, we've moved on to leaf block 3.  bc_ptrs[0] == 1, so
259 	for (i = 0; i < cur->bc_nlevels && cur->bc_ptrs[i] == 1; i++) {  in xbitmap_set_btcur_path()
263 		fsb = XFS_DADDR_TO_FSB(cur->bc_mp, bp->b_bn);  in xbitmap_set_btcur_path()
272 /* Collect a btree's block in the bitmap. */
287 	fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, bp->b_bn);  in xbitmap_collect_btblock()
291 /* Walk the btree and mark the bitmap wherever a btree block is found. */
311 		ret += bmr->len;  in xbitmap_hweight()