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 void |
44 | xbitmap64_tree_insert(struct xbitmap64_node *node, struct rb_root_cached *root); |
45 | |
46 | static inline void |
47 | xbitmap64_tree_remove(struct xbitmap64_node *node, struct rb_root_cached *root); |
48 | |
49 | static inline struct xbitmap64_node * |
50 | xbitmap64_tree_iter_first(struct rb_root_cached *root, uint64_t start, |
51 | uint64_t last); |
52 | |
53 | static inline 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, 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. */ |
69 | int |
70 | xbitmap64_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. */ |
118 | int |
119 | xbitmap64_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. */ |
178 | void |
179 | xbitmap64_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. */ |
191 | void |
192 | xbitmap64_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 | */ |
212 | int |
213 | xbitmap64_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? */ |
234 | uint64_t |
235 | xbitmap64_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. */ |
248 | int |
249 | xbitmap64_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? */ |
267 | bool |
268 | xbitmap64_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? */ |
275 | bool |
276 | xbitmap64_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 | |
298 | struct 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 | */ |
317 | static inline void |
318 | xbitmap32_tree_insert(struct xbitmap32_node *node, struct rb_root_cached *root); |
319 | |
320 | static inline void |
321 | xbitmap32_tree_remove(struct xbitmap32_node *node, struct rb_root_cached *root); |
322 | |
323 | static inline struct xbitmap32_node * |
324 | xbitmap32_tree_iter_first(struct rb_root_cached *root, uint32_t start, |
325 | uint32_t last); |
326 | |
327 | static inline struct xbitmap32_node * |
328 | xbitmap32_tree_iter_next(struct xbitmap32_node *node, uint32_t start, |
329 | uint32_t last); |
330 | |
331 | INTERVAL_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. */ |
343 | int |
344 | xbitmap32_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. */ |
392 | int |
393 | xbitmap32_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. */ |
452 | void |
453 | xbitmap32_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. */ |
465 | void |
466 | xbitmap32_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 | */ |
486 | int |
487 | xbitmap32_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? */ |
508 | uint32_t |
509 | xbitmap32_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. */ |
522 | int |
523 | xbitmap32_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? */ |
541 | bool |
542 | xbitmap32_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? */ |
549 | bool |
550 | xbitmap32_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. */ |
571 | uint32_t |
572 | xbitmap32_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 | |