1 // SPDX-License-Identifier: GPL-2.0+
3 * Copyright (C) 2018 Oracle. All Rights Reserved.
4 * Author: Darrick J. Wong <darrick.wong@oracle.com>
8 #include "xfs_shared.h"
9 #include "xfs_format.h"
10 #include "xfs_trans_resv.h"
11 #include "xfs_mount.h"
12 #include "xfs_btree.h"
13 #include "scrub/xfs_scrub.h"
14 #include "scrub/scrub.h"
15 #include "scrub/common.h"
16 #include "scrub/trace.h"
17 #include "scrub/repair.h"
18 #include "scrub/bitmap.h"
21 * Set a range of this bitmap. Caller must ensure the range is not set.
23 * This is the logical equivalent of bitmap |= mask(start, len).
27 struct xfs_bitmap *bitmap,
31 struct xfs_bitmap_range *bmr;
33 bmr = kmem_alloc(sizeof(struct xfs_bitmap_range), KM_MAYFAIL);
37 INIT_LIST_HEAD(&bmr->list);
40 list_add_tail(&bmr->list, &bitmap->list);
45 /* Free everything related to this bitmap. */
48 struct xfs_bitmap *bitmap)
50 struct xfs_bitmap_range *bmr;
51 struct xfs_bitmap_range *n;
53 for_each_xfs_bitmap_extent(bmr, n, bitmap) {
59 /* Set up a per-AG block bitmap. */
62 struct xfs_bitmap *bitmap)
64 INIT_LIST_HEAD(&bitmap->list);
67 /* Compare two btree extents. */
74 struct xfs_bitmap_range *ap;
75 struct xfs_bitmap_range *bp;
77 ap = container_of(a, struct xfs_bitmap_range, list);
78 bp = container_of(b, struct xfs_bitmap_range, list);
80 if (ap->start > bp->start)
82 if (ap->start < bp->start)
88 * Remove all the blocks mentioned in @sub from the extents in @bitmap.
90 * The intent is that callers will iterate the rmapbt for all of its records
91 * for a given owner to generate @bitmap; and iterate all the blocks of the
92 * metadata structures that are not being rebuilt and have the same rmapbt
93 * owner to generate @sub. This routine subtracts all the extents
94 * mentioned in sub from all the extents linked in @bitmap, which leaves
95 * @bitmap as the list of blocks that are not accounted for, which we assume
96 * are the dead blocks of the old metadata structure. The blocks mentioned in
97 * @bitmap can be reaped.
99 * This is the logical equivalent of bitmap &= ~sub.
101 #define LEFT_ALIGNED (1 << 0)
102 #define RIGHT_ALIGNED (1 << 1)
105 struct xfs_bitmap *bitmap,
106 struct xfs_bitmap *sub)
108 struct list_head *lp;
109 struct xfs_bitmap_range *br;
110 struct xfs_bitmap_range *new_br;
111 struct xfs_bitmap_range *sub_br;
117 if (list_empty(&bitmap->list) || list_empty(&sub->list))
119 ASSERT(!list_empty(&sub->list));
121 list_sort(NULL, &bitmap->list, xfs_bitmap_range_cmp);
122 list_sort(NULL, &sub->list, xfs_bitmap_range_cmp);
125 * Now that we've sorted both lists, we iterate bitmap once, rolling
126 * forward through sub and/or bitmap as necessary until we find an
127 * overlap or reach the end of either list. We do not reset lp to the
128 * head of bitmap nor do we reset sub_br to the head of sub. The
129 * list traversal is similar to merge sort, but we're deleting
130 * instead. In this manner we avoid O(n^2) operations.
132 sub_br = list_first_entry(&sub->list, struct xfs_bitmap_range,
134 lp = bitmap->list.next;
135 while (lp != &bitmap->list) {
136 br = list_entry(lp, struct xfs_bitmap_range, list);
139 * Advance sub_br and/or br until we find a pair that
140 * intersect or we run out of extents.
142 while (sub_br->start + sub_br->len <= br->start) {
143 if (list_is_last(&sub_br->list, &sub->list))
145 sub_br = list_next_entry(sub_br, list);
147 if (sub_br->start >= br->start + br->len) {
152 /* trim sub_br to fit the extent we have */
153 sub_start = sub_br->start;
154 sub_len = sub_br->len;
155 if (sub_br->start < br->start) {
156 sub_len -= br->start - sub_br->start;
157 sub_start = br->start;
159 if (sub_len > br->len)
163 if (sub_start == br->start)
164 state |= LEFT_ALIGNED;
165 if (sub_start + sub_len == br->start + br->len)
166 state |= RIGHT_ALIGNED;
169 /* Coincides with only the left. */
170 br->start += sub_len;
174 /* Coincides with only the right. */
178 case LEFT_ALIGNED | RIGHT_ALIGNED:
179 /* Total overlap, just delete ex. */
186 * Deleting from the middle: add the new right extent
187 * and then shrink the left extent.
189 new_br = kmem_alloc(sizeof(struct xfs_bitmap_range),
195 INIT_LIST_HEAD(&new_br->list);
196 new_br->start = sub_start + sub_len;
197 new_br->len = br->start + br->len - new_br->start;
198 list_add(&new_br->list, &br->list);
199 br->len = sub_start - br->start;
215 * Record all btree blocks seen while iterating all records of a btree.
217 * We know that the btree query_all function starts at the left edge and walks
218 * towards the right edge of the tree. Therefore, we know that we can walk up
219 * the btree cursor towards the root; if the pointer for a given level points
220 * to the first record/key in that block, we haven't seen this block before;
221 * and therefore we need to remember that we saw this block in the btree.
223 * So if our btree is:
229 * Pretend for this example that each leaf block has 100 btree records. For
230 * the first btree record, we'll observe that bc_ptrs[0] == 1, so we record
231 * that we saw block 1. Then we observe that bc_ptrs[1] == 1, so we record
232 * block 4. The list is [1, 4].
234 * For the second btree record, we see that bc_ptrs[0] == 2, so we exit the
235 * loop. The list remains [1, 4].
237 * For the 101st btree record, we've moved onto leaf block 2. Now
238 * bc_ptrs[0] == 1 again, so we record that we saw block 2. We see that
239 * bc_ptrs[1] == 2, so we exit the loop. The list is now [1, 4, 2].
241 * For the 102nd record, bc_ptrs[0] == 2, so we continue.
243 * For the 201st record, we've moved on to leaf block 3. bc_ptrs[0] == 1, so
244 * we add 3 to the list. Now it is [1, 4, 2, 3].
246 * For the 300th record we just exit, with the list being [1, 4, 2, 3].
250 * Record all the buffers pointed to by the btree cursor. Callers already
251 * engaged in a btree walk should call this function to capture the list of
252 * blocks going from the leaf towards the root.
255 xfs_bitmap_set_btcur_path(
256 struct xfs_bitmap *bitmap,
257 struct xfs_btree_cur *cur)
264 for (i = 0; i < cur->bc_nlevels && cur->bc_ptrs[i] == 1; i++) {
265 xfs_btree_get_block(cur, i, &bp);
268 fsb = XFS_DADDR_TO_FSB(cur->bc_mp, bp->b_bn);
269 error = xfs_bitmap_set(bitmap, fsb, 1);
277 /* Collect a btree's block in the bitmap. */
279 xfs_bitmap_collect_btblock(
280 struct xfs_btree_cur *cur,
284 struct xfs_bitmap *bitmap = priv;
288 xfs_btree_get_block(cur, level, &bp);
292 fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, bp->b_bn);
293 return xfs_bitmap_set(bitmap, fsbno, 1);
296 /* Walk the btree and mark the bitmap wherever a btree block is found. */
298 xfs_bitmap_set_btblocks(
299 struct xfs_bitmap *bitmap,
300 struct xfs_btree_cur *cur)
302 return xfs_btree_visit_blocks(cur, xfs_bitmap_collect_btblock, bitmap);