Line data Source code
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 : struct xbitmap_node {
20 : struct rb_node bn_rbnode;
21 :
22 : /* First set bit of this interval and subtree. */
23 : uint64_t bn_start;
24 :
25 : /* Last set bit of this interval. */
26 : uint64_t bn_last;
27 :
28 : /* Last set bit of this subtree. Do not touch this. */
29 : uint64_t __bn_subtree_last;
30 : };
31 :
32 : /* Define our own interval tree type with uint64_t parameters. */
33 :
34 : #define START(node) ((node)->bn_start)
35 : #define LAST(node) ((node)->bn_last)
36 :
37 : /*
38 : * These functions are defined by the INTERVAL_TREE_DEFINE macro, but we'll
39 : * forward-declare them anyway for clarity.
40 : */
41 : static inline void
42 : xbitmap_tree_insert(struct xbitmap_node *node, struct rb_root_cached *root);
43 :
44 : static inline void
45 : xbitmap_tree_remove(struct xbitmap_node *node, struct rb_root_cached *root);
46 :
47 : static inline struct xbitmap_node *
48 : xbitmap_tree_iter_first(struct rb_root_cached *root, uint64_t start,
49 : uint64_t last);
50 :
51 : static inline struct xbitmap_node *
52 : xbitmap_tree_iter_next(struct xbitmap_node *node, uint64_t start,
53 : uint64_t last);
54 :
55 55893434594 : INTERVAL_TREE_DEFINE(struct xbitmap_node, bn_rbnode, uint64_t,
56 : __bn_subtree_last, START, LAST, static inline, xbitmap_tree)
57 :
58 : /* Iterate each interval of a bitmap. Do not change the bitmap. */
59 : #define for_each_xbitmap_extent(bn, bitmap) \
60 : for ((bn) = rb_entry_safe(rb_first(&(bitmap)->xb_root.rb_root), \
61 : struct xbitmap_node, bn_rbnode); \
62 : (bn) != NULL; \
63 : (bn) = rb_entry_safe(rb_next(&(bn)->bn_rbnode), \
64 : struct xbitmap_node, bn_rbnode))
65 :
66 : /* Clear a range of this bitmap. */
67 : int
68 1253978477 : xbitmap_clear(
69 : struct xbitmap *bitmap,
70 : uint64_t start,
71 : uint64_t len)
72 : {
73 1253978477 : struct xbitmap_node *bn;
74 1253978477 : struct xbitmap_node *new_bn;
75 1253978477 : uint64_t last = start + len - 1;
76 :
77 1276774878 : while ((bn = xbitmap_tree_iter_first(&bitmap->xb_root, start, last))) {
78 22810125 : if (bn->bn_start < start && bn->bn_last > last) {
79 135 : uint64_t old_last = bn->bn_last;
80 :
81 : /* overlaps with the entire clearing range */
82 135 : xbitmap_tree_remove(bn, &bitmap->xb_root);
83 135 : bn->bn_last = start - 1;
84 135 : xbitmap_tree_insert(bn, &bitmap->xb_root);
85 :
86 : /* add an extent */
87 135 : new_bn = kmalloc(sizeof(struct xbitmap_node),
88 : XCHK_GFP_FLAGS);
89 135 : if (!new_bn)
90 : return -ENOMEM;
91 135 : new_bn->bn_start = last + 1;
92 135 : new_bn->bn_last = old_last;
93 135 : xbitmap_tree_insert(new_bn, &bitmap->xb_root);
94 22809855 : } else if (bn->bn_start < start) {
95 : /* overlaps with the left side of the clearing range */
96 340797 : xbitmap_tree_remove(bn, &bitmap->xb_root);
97 340797 : bn->bn_last = start - 1;
98 340797 : xbitmap_tree_insert(bn, &bitmap->xb_root);
99 22469058 : } else if (bn->bn_last > last) {
100 : /* overlaps with the right side of the clearing range */
101 13593 : xbitmap_tree_remove(bn, &bitmap->xb_root);
102 13593 : bn->bn_start = last + 1;
103 13593 : xbitmap_tree_insert(bn, &bitmap->xb_root);
104 13593 : break;
105 : } else {
106 : /* in the middle of the clearing range */
107 22455465 : xbitmap_tree_remove(bn, &bitmap->xb_root);
108 22455464 : kfree(bn);
109 : }
110 : }
111 :
112 : return 0;
113 : }
114 :
115 : /* Set a range of this bitmap. */
116 : int
117 1231911042 : xbitmap_set(
118 : struct xbitmap *bitmap,
119 : uint64_t start,
120 : uint64_t len)
121 : {
122 1231911042 : struct xbitmap_node *left;
123 1231911042 : struct xbitmap_node *right;
124 1231911042 : uint64_t last = start + len - 1;
125 1231911042 : int error;
126 :
127 : /* Is this whole range already set? */
128 1231911042 : left = xbitmap_tree_iter_first(&bitmap->xb_root, start, last);
129 1232055574 : if (left && left->bn_start <= start && left->bn_last >= last)
130 : return 0;
131 :
132 : /* Clear out everything in the range we want to set. */
133 1232055574 : error = xbitmap_clear(bitmap, start, len);
134 1231346861 : if (error)
135 : return error;
136 :
137 : /* Do we have a left-adjacent extent? */
138 1231403125 : left = xbitmap_tree_iter_first(&bitmap->xb_root, start - 1, start - 1);
139 1231138668 : ASSERT(!left || left->bn_last + 1 == start);
140 :
141 : /* Do we have a right-adjacent extent? */
142 1231138668 : right = xbitmap_tree_iter_first(&bitmap->xb_root, last + 1, last + 1);
143 1230288902 : ASSERT(!right || right->bn_start == last + 1);
144 :
145 1230288902 : if (left && right) {
146 : /* combine left and right adjacent extent */
147 258896 : xbitmap_tree_remove(left, &bitmap->xb_root);
148 258897 : xbitmap_tree_remove(right, &bitmap->xb_root);
149 258897 : left->bn_last = right->bn_last;
150 258897 : xbitmap_tree_insert(left, &bitmap->xb_root);
151 258896 : kfree(right);
152 1230030006 : } else if (left) {
153 : /* combine with left extent */
154 2978287 : xbitmap_tree_remove(left, &bitmap->xb_root);
155 2978240 : left->bn_last = last;
156 2978240 : xbitmap_tree_insert(left, &bitmap->xb_root);
157 1227051719 : } else if (right) {
158 : /* combine with right extent */
159 4809316 : xbitmap_tree_remove(right, &bitmap->xb_root);
160 4809278 : right->bn_start = start;
161 4809278 : xbitmap_tree_insert(right, &bitmap->xb_root);
162 : } else {
163 : /* add an extent */
164 1222242403 : left = kmalloc(sizeof(struct xbitmap_node), XCHK_GFP_FLAGS);
165 1223083037 : if (!left)
166 : return -ENOMEM;
167 1223083037 : left->bn_start = start;
168 1223083037 : left->bn_last = last;
169 1223083037 : xbitmap_tree_insert(left, &bitmap->xb_root);
170 : }
171 :
172 : return 0;
173 : }
174 :
175 : /* Free everything related to this bitmap. */
176 : void
177 15310290 : xbitmap_destroy(
178 : struct xbitmap *bitmap)
179 : {
180 15310290 : struct xbitmap_node *bn;
181 :
182 1209861787 : while ((bn = xbitmap_tree_iter_first(&bitmap->xb_root, 0, -1ULL))) {
183 1194296485 : xbitmap_tree_remove(bn, &bitmap->xb_root);
184 1193132360 : kfree(bn);
185 : }
186 15309605 : }
187 :
188 : /* Set up a per-AG block bitmap. */
189 : void
190 15293933 : xbitmap_init(
191 : struct xbitmap *bitmap)
192 : {
193 15293933 : bitmap->xb_root = RB_ROOT_CACHED;
194 15293933 : }
195 :
196 : /*
197 : * Remove all the blocks mentioned in @sub from the extents in @bitmap.
198 : *
199 : * The intent is that callers will iterate the rmapbt for all of its records
200 : * for a given owner to generate @bitmap; and iterate all the blocks of the
201 : * metadata structures that are not being rebuilt and have the same rmapbt
202 : * owner to generate @sub. This routine subtracts all the extents
203 : * mentioned in sub from all the extents linked in @bitmap, which leaves
204 : * @bitmap as the list of blocks that are not accounted for, which we assume
205 : * are the dead blocks of the old metadata structure. The blocks mentioned in
206 : * @bitmap can be reaped.
207 : *
208 : * This is the logical equivalent of bitmap &= ~sub.
209 : */
210 : int
211 184447 : xbitmap_disunion(
212 : struct xbitmap *bitmap,
213 : struct xbitmap *sub)
214 : {
215 184447 : struct xbitmap_node *bn;
216 184447 : int error;
217 :
218 368894 : if (xbitmap_empty(bitmap) || xbitmap_empty(sub))
219 : return 0;
220 :
221 15997575 : for_each_xbitmap_extent(bn, sub) {
222 15737578 : error = xbitmap_clear(bitmap, bn->bn_start,
223 15737578 : bn->bn_last - bn->bn_start + 1);
224 15737573 : if (error)
225 0 : return error;
226 : }
227 :
228 : return 0;
229 : }
230 :
231 : /*
232 : * Record all btree blocks seen while iterating all records of a btree.
233 : *
234 : * We know that the btree query_all function starts at the left edge and walks
235 : * towards the right edge of the tree. Therefore, we know that we can walk up
236 : * the btree cursor towards the root; if the pointer for a given level points
237 : * to the first record/key in that block, we haven't seen this block before;
238 : * and therefore we need to remember that we saw this block in the btree.
239 : *
240 : * So if our btree is:
241 : *
242 : * 4
243 : * / | \
244 : * 1 2 3
245 : *
246 : * Pretend for this example that each leaf block has 100 btree records. For
247 : * the first btree record, we'll observe that bc_levels[0].ptr == 1, so we
248 : * record that we saw block 1. Then we observe that bc_levels[1].ptr == 1, so
249 : * we record block 4. The list is [1, 4].
250 : *
251 : * For the second btree record, we see that bc_levels[0].ptr == 2, so we exit
252 : * the loop. The list remains [1, 4].
253 : *
254 : * For the 101st btree record, we've moved onto leaf block 2. Now
255 : * bc_levels[0].ptr == 1 again, so we record that we saw block 2. We see that
256 : * bc_levels[1].ptr == 2, so we exit the loop. The list is now [1, 4, 2].
257 : *
258 : * For the 102nd record, bc_levels[0].ptr == 2, so we continue.
259 : *
260 : * For the 201st record, we've moved on to leaf block 3.
261 : * bc_levels[0].ptr == 1, so we add 3 to the list. Now it is [1, 4, 2, 3].
262 : *
263 : * For the 300th record we just exit, with the list being [1, 4, 2, 3].
264 : */
265 :
266 : /* Mark a btree block to the agblock bitmap. */
267 : STATIC int
268 22837012 : xagb_bitmap_visit_btblock(
269 : struct xfs_btree_cur *cur,
270 : int level,
271 : void *priv)
272 : {
273 22837012 : struct xagb_bitmap *bitmap = priv;
274 22837012 : struct xfs_buf *bp;
275 22837012 : xfs_fsblock_t fsbno;
276 22837012 : xfs_agblock_t agbno;
277 :
278 22837012 : xfs_btree_get_block(cur, level, &bp);
279 22836969 : if (!bp)
280 : return 0;
281 :
282 22836969 : fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, xfs_buf_daddr(bp));
283 22836969 : agbno = XFS_FSB_TO_AGBNO(cur->bc_mp, fsbno);
284 :
285 22836969 : return xagb_bitmap_set(bitmap, agbno, 1);
286 : }
287 :
288 : /* Mark all (per-AG) btree blocks in the agblock bitmap. */
289 : int
290 499739 : xagb_bitmap_set_btblocks(
291 : struct xagb_bitmap *bitmap,
292 : struct xfs_btree_cur *cur)
293 : {
294 499739 : return xfs_btree_visit_blocks(cur, xagb_bitmap_visit_btblock,
295 : XFS_BTREE_VISIT_ALL, bitmap);
296 : }
297 :
298 : /*
299 : * Record all the buffers pointed to by the btree cursor. Callers already
300 : * engaged in a btree walk should call this function to capture the list of
301 : * blocks going from the leaf towards the root.
302 : */
303 : int
304 2188297780 : xagb_bitmap_set_btcur_path(
305 : struct xagb_bitmap *bitmap,
306 : struct xfs_btree_cur *cur)
307 : {
308 2188297780 : int i;
309 2188297780 : int error;
310 :
311 2204422928 : for (i = 0; i < cur->bc_nlevels && cur->bc_levels[i].ptr == 1; i++) {
312 16126259 : error = xagb_bitmap_visit_btblock(cur, i, bitmap);
313 16125148 : if (error)
314 0 : return error;
315 : }
316 :
317 : return 0;
318 : }
319 :
320 : /* How many bits are set in this bitmap? */
321 : uint64_t
322 369704 : xbitmap_hweight(
323 : struct xbitmap *bitmap)
324 : {
325 369704 : struct xbitmap_node *bn;
326 369704 : uint64_t ret = 0;
327 :
328 1589634 : for_each_xbitmap_extent(bn, bitmap)
329 425117 : ret += bn->bn_last - bn->bn_start + 1;
330 :
331 369700 : return ret;
332 : }
333 :
334 : /* Call a function for every run of set bits in this bitmap. */
335 : int
336 1268829 : xbitmap_walk(
337 : struct xbitmap *bitmap,
338 : xbitmap_walk_fn fn,
339 : void *priv)
340 : {
341 1268829 : struct xbitmap_node *bn;
342 1268829 : int error = 0;
343 :
344 4958894 : for_each_xbitmap_extent(bn, bitmap) {
345 1265058 : error = fn(bn->bn_start, bn->bn_last - bn->bn_start + 1, priv);
346 1265069 : if (error)
347 : break;
348 : }
349 :
350 1268832 : return error;
351 : }
352 :
353 : /* Does this bitmap have no bits set at all? */
354 : bool
355 4469 : xbitmap_empty(
356 : struct xbitmap *bitmap)
357 : {
358 184447 : return bitmap->xb_root.rb_root.rb_node == NULL;
359 : }
360 :
361 : /* Is the start of the range set or clear? And for how long? */
362 : bool
363 1192467168 : xbitmap_test(
364 : struct xbitmap *bitmap,
365 : uint64_t start,
366 : uint64_t *len)
367 : {
368 1192467168 : struct xbitmap_node *bn;
369 1192467168 : uint64_t last = start + *len - 1;
370 :
371 1192467168 : bn = xbitmap_tree_iter_first(&bitmap->xb_root, start, last);
372 1191663123 : if (!bn)
373 : return false;
374 5234932 : if (bn->bn_start <= start) {
375 5234932 : if (bn->bn_last < last)
376 0 : *len = bn->bn_last - start + 1;
377 5234932 : return true;
378 : }
379 0 : *len = bn->bn_start - start;
380 0 : return false;
381 : }
382 :
383 : /*
384 : * Find the first set bit in this bitmap, clear it, and return the index of
385 : * that bit in @valp. Returns -ENODATA if no bits were set, or the usual
386 : * negative errno.
387 : */
388 : int
389 4743 : xbitmap_take_first_set(
390 : struct xbitmap *bitmap,
391 : uint64_t start,
392 : uint64_t last,
393 : uint64_t *valp)
394 : {
395 4743 : struct xbitmap_node *bn;
396 4743 : uint64_t val;
397 4743 : int error;
398 :
399 4743 : bn = xbitmap_tree_iter_first(&bitmap->xb_root, start, last);
400 4743 : if (!bn)
401 : return -ENODATA;
402 :
403 1 : val = bn->bn_start;
404 1 : error = xbitmap_clear(bitmap, bn->bn_start, 1);
405 1 : if (error)
406 : return error;
407 1 : *valp = val;
408 1 : return 0;
409 : }
410 :
411 : /* Count the number of set regions in this bitmap. */
412 : uint64_t
413 4553 : xbitmap_count_set_regions(
414 : struct xbitmap *bitmap)
415 : {
416 4553 : struct xbitmap_node *bn;
417 4553 : uint64_t nr = 0;
418 :
419 62180 : for_each_xbitmap_extent(bn, bitmap)
420 26537 : nr++;
421 :
422 4553 : return nr;
423 : }
|
