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