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(root: &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(node: bn, root: &bitmap->xb_root);
85 bn->bn_last = start - 1;
86 xbitmap64_tree_insert(node: bn, root: &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(node: new_bn, root: &bitmap->xb_root);
96 } else if (bn->bn_start < start) {
97 /* overlaps with the left side of the clearing range */
98 xbitmap64_tree_remove(node: bn, root: &bitmap->xb_root);
99 bn->bn_last = start - 1;
100 xbitmap64_tree_insert(node: bn, root: &bitmap->xb_root);
101 } else if (bn->bn_last > last) {
102 /* overlaps with the right side of the clearing range */
103 xbitmap64_tree_remove(node: bn, root: &bitmap->xb_root);
104 bn->bn_start = last + 1;
105 xbitmap64_tree_insert(node: bn, root: &bitmap->xb_root);
106 break;
107 } else {
108 /* in the middle of the clearing range */
109 xbitmap64_tree_remove(node: bn, root: &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(root: &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(root: &bitmap->xb_root, start: start - 1, last: 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(root: &bitmap->xb_root, start: last + 1, last: 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(node: left, root: &bitmap->xb_root);
150 xbitmap64_tree_remove(node: right, root: &bitmap->xb_root);
151 left->bn_last = right->bn_last;
152 xbitmap64_tree_insert(node: left, root: &bitmap->xb_root);
153 kfree(right);
154 } else if (left) {
155 /* combine with left extent */
156 xbitmap64_tree_remove(node: left, root: &bitmap->xb_root);
157 left->bn_last = last;
158 xbitmap64_tree_insert(node: left, root: &bitmap->xb_root);
159 } else if (right) {
160 /* combine with right extent */
161 xbitmap64_tree_remove(node: right, root: &bitmap->xb_root);
162 right->bn_start = start;
163 xbitmap64_tree_insert(node: right, root: &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(node: left, root: &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(root: &bitmap->xb_root, start: 0, last: -1ULL))) {
185 xbitmap64_tree_remove(node: bn, root: &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, start: bn->bn_start,
225 len: 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(root: &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(root: &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(node: bn, root: &bitmap->xb_root);
359 bn->bn_last = start - 1;
360 xbitmap32_tree_insert(node: bn, root: &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(node: new_bn, root: &bitmap->xb_root);
370 } else if (bn->bn_start < start) {
371 /* overlaps with the left side of the clearing range */
372 xbitmap32_tree_remove(node: bn, root: &bitmap->xb_root);
373 bn->bn_last = start - 1;
374 xbitmap32_tree_insert(node: bn, root: &bitmap->xb_root);
375 } else if (bn->bn_last > last) {
376 /* overlaps with the right side of the clearing range */
377 xbitmap32_tree_remove(node: bn, root: &bitmap->xb_root);
378 bn->bn_start = last + 1;
379 xbitmap32_tree_insert(node: bn, root: &bitmap->xb_root);
380 break;
381 } else {
382 /* in the middle of the clearing range */
383 xbitmap32_tree_remove(node: bn, root: &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(root: &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(root: &bitmap->xb_root, start: start - 1, last: 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(root: &bitmap->xb_root, start: last + 1, last: 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(node: left, root: &bitmap->xb_root);
424 xbitmap32_tree_remove(node: right, root: &bitmap->xb_root);
425 left->bn_last = right->bn_last;
426 xbitmap32_tree_insert(node: left, root: &bitmap->xb_root);
427 kfree(right);
428 } else if (left) {
429 /* combine with left extent */
430 xbitmap32_tree_remove(node: left, root: &bitmap->xb_root);
431 left->bn_last = last;
432 xbitmap32_tree_insert(node: left, root: &bitmap->xb_root);
433 } else if (right) {
434 /* combine with right extent */
435 xbitmap32_tree_remove(node: right, root: &bitmap->xb_root);
436 right->bn_start = start;
437 xbitmap32_tree_insert(node: right, root: &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(node: left, root: &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(root: &bitmap->xb_root, start: 0, last: -1U))) {
459 xbitmap32_tree_remove(node: bn, root: &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, start: bn->bn_start,
499 len: 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(root: &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

source code of linux/fs/xfs/scrub/bitmap.c