xref: /linux/fs/xfs/scrub/bitmap.c (revision 00f32fdf54983371d39162efef7df693e2842ffb) 
1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /*
3  * Copyright (C) 2018-2023 Oracle.  All Rights Reserved.
4  * Author: Darrick J. Wong <djwong@kernel.org>
5  */
6 #include "xfs_platform.h"
7 #include "xfs_fs.h"
8 #include "xfs_shared.h"
9 #include "xfs_bit.h"
10 #include "xfs_format.h"
11 #include "xfs_trans_resv.h"
12 #include "xfs_mount.h"
13 #include "xfs_btree.h"
14 #include "scrub/scrub.h"
15 #include "scrub/bitmap.h"
16 
17 #include <linux/interval_tree_generic.h>
18 
19 /* u64 bitmap */
20 
21 struct xbitmap64_node {
22 	struct rb_node	bn_rbnode;
23 
24 	/* First set bit of this interval and subtree. */
25 	uint64_t	bn_start;
26 
27 	/* Last set bit of this interval. */
28 	uint64_t	bn_last;
29 
30 	/* Last set bit of this subtree.  Do not touch this. */
31 	uint64_t	__bn_subtree_last;
32 };
33 
34 /* Define our own interval tree type with uint64_t parameters. */
35 
36 #define START(node) ((node)->bn_start)
37 #define LAST(node)  ((node)->bn_last)
38 
39 /*
40  * These functions are defined by the INTERVAL_TREE_DEFINE macro, but we'll
41  * forward-declare them anyway for clarity.
42  */
43 static inline __maybe_unused void
44 xbitmap64_tree_insert(struct xbitmap64_node *node, struct rb_root_cached *root);
45 
46 static inline __maybe_unused void
47 xbitmap64_tree_remove(struct xbitmap64_node *node, struct rb_root_cached *root);
48 
49 static inline __maybe_unused struct xbitmap64_node *
50 xbitmap64_tree_iter_first(struct rb_root_cached *root, uint64_t start,
51 			uint64_t last);
52 
53 static inline __maybe_unused struct xbitmap64_node *
54 xbitmap64_tree_iter_next(struct xbitmap64_node *node, uint64_t start,
55 		       uint64_t last);
56 
57 INTERVAL_TREE_DEFINE(struct xbitmap64_node, bn_rbnode, uint64_t,
58 		__bn_subtree_last, START, LAST, static inline __maybe_unused,
59 		xbitmap64_tree)
60 
61 /* Iterate each interval of a bitmap.  Do not change the bitmap. */
62 #define for_each_xbitmap64_extent(bn, bitmap) \
63 	for ((bn) = rb_entry_safe(rb_first(&(bitmap)->xb_root.rb_root), \
64 				   struct xbitmap64_node, bn_rbnode); \
65 	     (bn) != NULL; \
66 	     (bn) = rb_entry_safe(rb_next(&(bn)->bn_rbnode), \
67 				   struct xbitmap64_node, bn_rbnode))
68 
69 /* Clear a range of this bitmap. */
70 int
71 xbitmap64_clear(
72 	struct xbitmap64	*bitmap,
73 	uint64_t		start,
74 	uint64_t		len)
75 {
76 	struct xbitmap64_node	*bn;
77 	struct xbitmap64_node	*new_bn;
78 	uint64_t		last = start + len - 1;
79 
80 	if (!len)
81 		return 0;
82 
83 	while ((bn = xbitmap64_tree_iter_first(&bitmap->xb_root, start, last))) {
84 		if (bn->bn_start < start && bn->bn_last > last) {
85 			uint64_t	old_last = bn->bn_last;
86 
87 			/* overlaps with the entire clearing range */
88 			xbitmap64_tree_remove(bn, &bitmap->xb_root);
89 			bn->bn_last = start - 1;
90 			xbitmap64_tree_insert(bn, &bitmap->xb_root);
91 
92 			/* add an extent */
93 			new_bn = kmalloc_obj(struct xbitmap64_node,
94 					     XCHK_GFP_FLAGS);
95 			if (!new_bn)
96 				return -ENOMEM;
97 			new_bn->bn_start = last + 1;
98 			new_bn->bn_last = old_last;
99 			xbitmap64_tree_insert(new_bn, &bitmap->xb_root);
100 		} else if (bn->bn_start < start) {
101 			/* overlaps with the left side of the clearing range */
102 			xbitmap64_tree_remove(bn, &bitmap->xb_root);
103 			bn->bn_last = start - 1;
104 			xbitmap64_tree_insert(bn, &bitmap->xb_root);
105 		} else if (bn->bn_last > last) {
106 			/* overlaps with the right side of the clearing range */
107 			xbitmap64_tree_remove(bn, &bitmap->xb_root);
108 			bn->bn_start = last + 1;
109 			xbitmap64_tree_insert(bn, &bitmap->xb_root);
110 			break;
111 		} else {
112 			/* in the middle of the clearing range */
113 			xbitmap64_tree_remove(bn, &bitmap->xb_root);
114 			kfree(bn);
115 		}
116 	}
117 
118 	return 0;
119 }
120 
121 /* Set a range of this bitmap. */
122 int
123 xbitmap64_set(
124 	struct xbitmap64	*bitmap,
125 	uint64_t		start,
126 	uint64_t		len)
127 {
128 	struct xbitmap64_node	*left = NULL;
129 	struct xbitmap64_node	*right = NULL;
130 	uint64_t		last = start + len - 1;
131 	int			error;
132 
133 	if (!len)
134 		return 0;
135 
136 	/* Is this whole range already set? */
137 	left = xbitmap64_tree_iter_first(&bitmap->xb_root, start, last);
138 	if (left && left->bn_start <= start && left->bn_last >= last)
139 		return 0;
140 	left = NULL;
141 
142 	/* Clear out everything in the range we want to set. */
143 	error = xbitmap64_clear(bitmap, start, len);
144 	if (error)
145 		return error;
146 
147 	/* Do we have a left-adjacent extent? */
148 	if (start > 0)
149 		left = xbitmap64_tree_iter_first(&bitmap->xb_root, start - 1,
150 				start - 1);
151 	ASSERT(!left || left->bn_last + 1 == start);
152 
153 	/* Do we have a right-adjacent extent? */
154 	if (last < U64_MAX)
155 		right = xbitmap64_tree_iter_first(&bitmap->xb_root, last + 1,
156 				last + 1);
157 	ASSERT(!right || right->bn_start == last + 1);
158 
159 	if (left && right) {
160 		/* combine left and right adjacent extent */
161 		xbitmap64_tree_remove(left, &bitmap->xb_root);
162 		xbitmap64_tree_remove(right, &bitmap->xb_root);
163 		left->bn_last = right->bn_last;
164 		xbitmap64_tree_insert(left, &bitmap->xb_root);
165 		kfree(right);
166 	} else if (left) {
167 		/* combine with left extent */
168 		xbitmap64_tree_remove(left, &bitmap->xb_root);
169 		left->bn_last = last;
170 		xbitmap64_tree_insert(left, &bitmap->xb_root);
171 	} else if (right) {
172 		/* combine with right extent */
173 		xbitmap64_tree_remove(right, &bitmap->xb_root);
174 		right->bn_start = start;
175 		xbitmap64_tree_insert(right, &bitmap->xb_root);
176 	} else {
177 		/* add an extent */
178 		left = kmalloc_obj(struct xbitmap64_node, XCHK_GFP_FLAGS);
179 		if (!left)
180 			return -ENOMEM;
181 		left->bn_start = start;
182 		left->bn_last = last;
183 		xbitmap64_tree_insert(left, &bitmap->xb_root);
184 	}
185 
186 	return 0;
187 }
188 
189 /* Free everything related to this bitmap. */
190 void
191 xbitmap64_destroy(
192 	struct xbitmap64	*bitmap)
193 {
194 	struct xbitmap64_node	*bn;
195 
196 	while ((bn = xbitmap64_tree_iter_first(&bitmap->xb_root, 0, -1ULL))) {
197 		xbitmap64_tree_remove(bn, &bitmap->xb_root);
198 		kfree(bn);
199 	}
200 }
201 
202 /* Set up a per-AG block bitmap. */
203 void
204 xbitmap64_init(
205 	struct xbitmap64	*bitmap)
206 {
207 	bitmap->xb_root = RB_ROOT_CACHED;
208 }
209 
210 /*
211  * Remove all the blocks mentioned in @sub from the extents in @bitmap.
212  *
213  * The intent is that callers will iterate the rmapbt for all of its records
214  * for a given owner to generate @bitmap; and iterate all the blocks of the
215  * metadata structures that are not being rebuilt and have the same rmapbt
216  * owner to generate @sub.  This routine subtracts all the extents
217  * mentioned in sub from all the extents linked in @bitmap, which leaves
218  * @bitmap as the list of blocks that are not accounted for, which we assume
219  * are the dead blocks of the old metadata structure.  The blocks mentioned in
220  * @bitmap can be reaped.
221  *
222  * This is the logical equivalent of bitmap &= ~sub.
223  */
224 int
225 xbitmap64_disunion(
226 	struct xbitmap64	*bitmap,
227 	struct xbitmap64	*sub)
228 {
229 	struct xbitmap64_node	*bn;
230 	int			error;
231 
232 	ASSERT(bitmap != sub);
233 
234 	if (xbitmap64_empty(bitmap) || xbitmap64_empty(sub))
235 		return 0;
236 
237 	for_each_xbitmap64_extent(bn, sub) {
238 		error = xbitmap64_clear(bitmap, bn->bn_start,
239 				bn->bn_last - bn->bn_start + 1);
240 		if (error)
241 			return error;
242 	}
243 
244 	return 0;
245 }
246 
247 /* How many bits are set in this bitmap? */
248 uint64_t
249 xbitmap64_hweight(
250 	struct xbitmap64	*bitmap)
251 {
252 	struct xbitmap64_node	*bn;
253 	uint64_t		ret = 0;
254 
255 	for_each_xbitmap64_extent(bn, bitmap)
256 		ret += bn->bn_last - bn->bn_start + 1;
257 
258 	return ret;
259 }
260 
261 /* Call a function for every run of set bits in this bitmap. */
262 int
263 xbitmap64_walk(
264 	struct xbitmap64	*bitmap,
265 	xbitmap64_walk_fn		fn,
266 	void			*priv)
267 {
268 	struct xbitmap64_node	*bn;
269 	int			error = 0;
270 
271 	for_each_xbitmap64_extent(bn, bitmap) {
272 		error = fn(bn->bn_start, bn->bn_last - bn->bn_start + 1, priv);
273 		if (error)
274 			break;
275 	}
276 
277 	return error;
278 }
279 
280 /* Does this bitmap have no bits set at all? */
281 bool
282 xbitmap64_empty(
283 	struct xbitmap64	*bitmap)
284 {
285 	return bitmap->xb_root.rb_root.rb_node == NULL;
286 }
287 
288 /* Is the start of the range set or clear?  And for how long? */
289 bool
290 xbitmap64_test(
291 	struct xbitmap64	*bitmap,
292 	uint64_t		start,
293 	uint64_t		*len)
294 {
295 	struct xbitmap64_node	*bn;
296 	uint64_t		last = start + *len - 1;
297 
298 	ASSERT(*len > 0);
299 
300 	bn = xbitmap64_tree_iter_first(&bitmap->xb_root, start, last);
301 	if (!bn)
302 		return false;
303 	if (bn->bn_start <= start) {
304 		if (bn->bn_last < last)
305 			*len = bn->bn_last - start + 1;
306 		return true;
307 	}
308 	*len = bn->bn_start - start;
309 	return false;
310 }
311 
312 /* u32 bitmap */
313 
314 struct xbitmap32_node {
315 	struct rb_node	bn_rbnode;
316 
317 	/* First set bit of this interval and subtree. */
318 	uint32_t	bn_start;
319 
320 	/* Last set bit of this interval. */
321 	uint32_t	bn_last;
322 
323 	/* Last set bit of this subtree.  Do not touch this. */
324 	uint32_t	__bn_subtree_last;
325 };
326 
327 /* Define our own interval tree type with uint32_t parameters. */
328 
329 /*
330  * These functions are defined by the INTERVAL_TREE_DEFINE macro, but we'll
331  * forward-declare them anyway for clarity.
332  */
333 static inline __maybe_unused void
334 xbitmap32_tree_insert(struct xbitmap32_node *node, struct rb_root_cached *root);
335 
336 static inline __maybe_unused void
337 xbitmap32_tree_remove(struct xbitmap32_node *node, struct rb_root_cached *root);
338 
339 static inline __maybe_unused struct xbitmap32_node *
340 xbitmap32_tree_iter_first(struct rb_root_cached *root, uint32_t start,
341 			  uint32_t last);
342 
343 static inline __maybe_unused struct xbitmap32_node *
344 xbitmap32_tree_iter_next(struct xbitmap32_node *node, uint32_t start,
345 			 uint32_t last);
346 
347 INTERVAL_TREE_DEFINE(struct xbitmap32_node, bn_rbnode, uint32_t,
348 		__bn_subtree_last, START, LAST, static inline __maybe_unused,
349 		xbitmap32_tree)
350 
351 /* Iterate each interval of a bitmap.  Do not change the bitmap. */
352 #define for_each_xbitmap32_extent(bn, bitmap) \
353 	for ((bn) = rb_entry_safe(rb_first(&(bitmap)->xb_root.rb_root), \
354 				   struct xbitmap32_node, bn_rbnode); \
355 	     (bn) != NULL; \
356 	     (bn) = rb_entry_safe(rb_next(&(bn)->bn_rbnode), \
357 				   struct xbitmap32_node, bn_rbnode))
358 
359 /* Clear a range of this bitmap. */
360 int
361 xbitmap32_clear(
362 	struct xbitmap32	*bitmap,
363 	uint32_t		start,
364 	uint32_t		len)
365 {
366 	struct xbitmap32_node	*bn;
367 	struct xbitmap32_node	*new_bn;
368 	uint32_t		last = start + len - 1;
369 
370 	if (!len)
371 		return 0;
372 
373 	while ((bn = xbitmap32_tree_iter_first(&bitmap->xb_root, start, last))) {
374 		if (bn->bn_start < start && bn->bn_last > last) {
375 			uint32_t	old_last = bn->bn_last;
376 
377 			/* overlaps with the entire clearing range */
378 			xbitmap32_tree_remove(bn, &bitmap->xb_root);
379 			bn->bn_last = start - 1;
380 			xbitmap32_tree_insert(bn, &bitmap->xb_root);
381 
382 			/* add an extent */
383 			new_bn = kmalloc_obj(struct xbitmap32_node,
384 					     XCHK_GFP_FLAGS);
385 			if (!new_bn)
386 				return -ENOMEM;
387 			new_bn->bn_start = last + 1;
388 			new_bn->bn_last = old_last;
389 			xbitmap32_tree_insert(new_bn, &bitmap->xb_root);
390 		} else if (bn->bn_start < start) {
391 			/* overlaps with the left side of the clearing range */
392 			xbitmap32_tree_remove(bn, &bitmap->xb_root);
393 			bn->bn_last = start - 1;
394 			xbitmap32_tree_insert(bn, &bitmap->xb_root);
395 		} else if (bn->bn_last > last) {
396 			/* overlaps with the right side of the clearing range */
397 			xbitmap32_tree_remove(bn, &bitmap->xb_root);
398 			bn->bn_start = last + 1;
399 			xbitmap32_tree_insert(bn, &bitmap->xb_root);
400 			break;
401 		} else {
402 			/* in the middle of the clearing range */
403 			xbitmap32_tree_remove(bn, &bitmap->xb_root);
404 			kfree(bn);
405 		}
406 	}
407 
408 	return 0;
409 }
410 
411 /* Set a range of this bitmap. */
412 int
413 xbitmap32_set(
414 	struct xbitmap32	*bitmap,
415 	uint32_t		start,
416 	uint32_t		len)
417 {
418 	struct xbitmap32_node	*left = NULL;
419 	struct xbitmap32_node	*right = NULL;
420 	uint32_t		last = start + len - 1;
421 	int			error;
422 
423 	if (!len)
424 		return 0;
425 
426 	/* Is this whole range already set? */
427 	left = xbitmap32_tree_iter_first(&bitmap->xb_root, start, last);
428 	if (left && left->bn_start <= start && left->bn_last >= last)
429 		return 0;
430 	left = NULL;
431 
432 	/* Clear out everything in the range we want to set. */
433 	error = xbitmap32_clear(bitmap, start, len);
434 	if (error)
435 		return error;
436 
437 	/* Do we have a left-adjacent extent? */
438 	if (start > 0)
439 		left = xbitmap32_tree_iter_first(&bitmap->xb_root, start - 1,
440 				start - 1);
441 	ASSERT(!left || left->bn_last + 1 == start);
442 
443 	/* Do we have a right-adjacent extent? */
444 	if (last < U32_MAX)
445 		right = xbitmap32_tree_iter_first(&bitmap->xb_root, last + 1,
446 				last + 1);
447 	ASSERT(!right || right->bn_start == last + 1);
448 
449 	if (left && right) {
450 		/* combine left and right adjacent extent */
451 		xbitmap32_tree_remove(left, &bitmap->xb_root);
452 		xbitmap32_tree_remove(right, &bitmap->xb_root);
453 		left->bn_last = right->bn_last;
454 		xbitmap32_tree_insert(left, &bitmap->xb_root);
455 		kfree(right);
456 	} else if (left) {
457 		/* combine with left extent */
458 		xbitmap32_tree_remove(left, &bitmap->xb_root);
459 		left->bn_last = last;
460 		xbitmap32_tree_insert(left, &bitmap->xb_root);
461 	} else if (right) {
462 		/* combine with right extent */
463 		xbitmap32_tree_remove(right, &bitmap->xb_root);
464 		right->bn_start = start;
465 		xbitmap32_tree_insert(right, &bitmap->xb_root);
466 	} else {
467 		/* add an extent */
468 		left = kmalloc_obj(struct xbitmap32_node, XCHK_GFP_FLAGS);
469 		if (!left)
470 			return -ENOMEM;
471 		left->bn_start = start;
472 		left->bn_last = last;
473 		xbitmap32_tree_insert(left, &bitmap->xb_root);
474 	}
475 
476 	return 0;
477 }
478 
479 /* Free everything related to this bitmap. */
480 void
481 xbitmap32_destroy(
482 	struct xbitmap32	*bitmap)
483 {
484 	struct xbitmap32_node	*bn;
485 
486 	while ((bn = xbitmap32_tree_iter_first(&bitmap->xb_root, 0, -1U))) {
487 		xbitmap32_tree_remove(bn, &bitmap->xb_root);
488 		kfree(bn);
489 	}
490 }
491 
492 /* Set up a per-AG block bitmap. */
493 void
494 xbitmap32_init(
495 	struct xbitmap32	*bitmap)
496 {
497 	bitmap->xb_root = RB_ROOT_CACHED;
498 }
499 
500 /*
501  * Remove all the blocks mentioned in @sub from the extents in @bitmap.
502  *
503  * The intent is that callers will iterate the rmapbt for all of its records
504  * for a given owner to generate @bitmap; and iterate all the blocks of the
505  * metadata structures that are not being rebuilt and have the same rmapbt
506  * owner to generate @sub.  This routine subtracts all the extents
507  * mentioned in sub from all the extents linked in @bitmap, which leaves
508  * @bitmap as the list of blocks that are not accounted for, which we assume
509  * are the dead blocks of the old metadata structure.  The blocks mentioned in
510  * @bitmap can be reaped.
511  *
512  * This is the logical equivalent of bitmap &= ~sub.
513  */
514 int
515 xbitmap32_disunion(
516 	struct xbitmap32	*bitmap,
517 	struct xbitmap32	*sub)
518 {
519 	struct xbitmap32_node	*bn;
520 	int			error;
521 
522 	ASSERT(bitmap != sub);
523 
524 	if (xbitmap32_empty(bitmap) || xbitmap32_empty(sub))
525 		return 0;
526 
527 	for_each_xbitmap32_extent(bn, sub) {
528 		error = xbitmap32_clear(bitmap, bn->bn_start,
529 				bn->bn_last - bn->bn_start + 1);
530 		if (error)
531 			return error;
532 	}
533 
534 	return 0;
535 }
536 
537 /* How many bits are set in this bitmap? */
538 uint32_t
539 xbitmap32_hweight(
540 	struct xbitmap32	*bitmap)
541 {
542 	struct xbitmap32_node	*bn;
543 	uint32_t		ret = 0;
544 
545 	for_each_xbitmap32_extent(bn, bitmap)
546 		ret += bn->bn_last - bn->bn_start + 1;
547 
548 	return ret;
549 }
550 
551 /* Call a function for every run of set bits in this bitmap. */
552 int
553 xbitmap32_walk(
554 	struct xbitmap32	*bitmap,
555 	xbitmap32_walk_fn	fn,
556 	void			*priv)
557 {
558 	struct xbitmap32_node	*bn;
559 	int			error = 0;
560 
561 	for_each_xbitmap32_extent(bn, bitmap) {
562 		error = fn(bn->bn_start, bn->bn_last - bn->bn_start + 1, priv);
563 		if (error)
564 			break;
565 	}
566 
567 	return error;
568 }
569 
570 /* Does this bitmap have no bits set at all? */
571 bool
572 xbitmap32_empty(
573 	struct xbitmap32	*bitmap)
574 {
575 	return bitmap->xb_root.rb_root.rb_node == NULL;
576 }
577 
578 /* Is the start of the range set or clear?  And for how long? */
579 bool
580 xbitmap32_test(
581 	struct xbitmap32	*bitmap,
582 	uint32_t		start,
583 	uint32_t		*len)
584 {
585 	struct xbitmap32_node	*bn;
586 	uint32_t		last = start + *len - 1;
587 
588 	ASSERT(*len > 0);
589 
590 	bn = xbitmap32_tree_iter_first(&bitmap->xb_root, start, last);
591 	if (!bn)
592 		return false;
593 	if (bn->bn_start <= start) {
594 		if (bn->bn_last < last)
595 			*len = bn->bn_last - start + 1;
596 		return true;
597 	}
598 	*len = bn->bn_start - start;
599 	return false;
600 }
601 
602 /* Count the number of set regions in this bitmap. */
603 uint32_t
604 xbitmap32_count_set_regions(
605 	struct xbitmap32	*bitmap)
606 {
607 	struct xbitmap32_node	*bn;
608 	uint32_t		nr = 0;
609 
610 	for_each_xbitmap32_extent(bn, bitmap)
611 		nr++;
612 
613 	return nr;
614 }
615