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