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