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_shared.h" |
8 | #include "xfs_bit.h" |
9 | #include "xfs_format.h" |
10 | #include "xfs_trans_resv.h" |
11 | #include "xfs_mount.h" |
12 | #include "xfs_btree.h" |
13 | #include "bitmap.h" |
14 | #include "scrub/agb_bitmap.h" |
15 | |
16 | /* |
17 | * Record all btree blocks seen while iterating all records of a btree. |
18 | * |
19 | * We know that the btree query_all function starts at the left edge and walks |
20 | * towards the right edge of the tree. Therefore, we know that we can walk up |
21 | * the btree cursor towards the root; if the pointer for a given level points |
22 | * to the first record/key in that block, we haven't seen this block before; |
23 | * and therefore we need to remember that we saw this block in the btree. |
24 | * |
25 | * So if our btree is: |
26 | * |
27 | * 4 |
28 | * / | \ |
29 | * 1 2 3 |
30 | * |
31 | * Pretend for this example that each leaf block has 100 btree records. For |
32 | * the first btree record, we'll observe that bc_levels[0].ptr == 1, so we |
33 | * record that we saw block 1. Then we observe that bc_levels[1].ptr == 1, so |
34 | * we record block 4. The list is [1, 4]. |
35 | * |
36 | * For the second btree record, we see that bc_levels[0].ptr == 2, so we exit |
37 | * the loop. The list remains [1, 4]. |
38 | * |
39 | * For the 101st btree record, we've moved onto leaf block 2. Now |
40 | * bc_levels[0].ptr == 1 again, so we record that we saw block 2. We see that |
41 | * bc_levels[1].ptr == 2, so we exit the loop. The list is now [1, 4, 2]. |
42 | * |
43 | * For the 102nd record, bc_levels[0].ptr == 2, so we continue. |
44 | * |
45 | * For the 201st record, we've moved on to leaf block 3. |
46 | * bc_levels[0].ptr == 1, so we add 3 to the list. Now it is [1, 4, 2, 3]. |
47 | * |
48 | * For the 300th record we just exit, with the list being [1, 4, 2, 3]. |
49 | */ |
50 | |
51 | /* Mark a btree block to the agblock bitmap. */ |
52 | STATIC int |
53 | xagb_bitmap_visit_btblock( |
54 | struct xfs_btree_cur *cur, |
55 | int level, |
56 | void *priv) |
57 | { |
58 | struct xagb_bitmap *bitmap = priv; |
59 | struct xfs_buf *bp; |
60 | xfs_fsblock_t fsbno; |
61 | xfs_agblock_t agbno; |
62 | |
63 | xfs_btree_get_block(cur, level, &bp); |
64 | if (!bp) |
65 | return 0; |
66 | |
67 | fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, xfs_buf_daddr(bp)); |
68 | agbno = XFS_FSB_TO_AGBNO(cur->bc_mp, fsbno); |
69 | |
70 | return xagb_bitmap_set(bitmap, agbno, 1); |
71 | } |
72 | |
73 | /* Mark all (per-AG) btree blocks in the agblock bitmap. */ |
74 | int |
75 | xagb_bitmap_set_btblocks( |
76 | struct xagb_bitmap *bitmap, |
77 | struct xfs_btree_cur *cur) |
78 | { |
79 | return xfs_btree_visit_blocks(cur, xagb_bitmap_visit_btblock, |
80 | XFS_BTREE_VISIT_ALL, bitmap); |
81 | } |
82 | |
83 | /* |
84 | * Record all the buffers pointed to by the btree cursor. Callers already |
85 | * engaged in a btree walk should call this function to capture the list of |
86 | * blocks going from the leaf towards the root. |
87 | */ |
88 | int |
89 | xagb_bitmap_set_btcur_path( |
90 | struct xagb_bitmap *bitmap, |
91 | struct xfs_btree_cur *cur) |
92 | { |
93 | int i; |
94 | int error; |
95 | |
96 | for (i = 0; i < cur->bc_nlevels && cur->bc_levels[i].ptr == 1; i++) { |
97 | error = xagb_bitmap_visit_btblock(cur, i, bitmap); |
98 | if (error) |
99 | return error; |
100 | } |
101 | |
102 | return 0; |
103 | } |
104 | |