1 // SPDX-License-Identifier: GPL-2.0+
2 /*
3 * Copyright (C) 2018 Oracle. All Rights Reserved.
4 * Author: Darrick J. Wong <darrick.wong@oracle.com>
5 */
6 #include "xfs.h"
7 #include "xfs_fs.h"
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/scrub.h"
14 #include "scrub/bitmap.h"
15
16 /*
17 * Set a range of this bitmap. Caller must ensure the range is not set.
18 *
19 * This is the logical equivalent of bitmap |= mask(start, len).
20 */
21 int
xbitmap_set(struct xbitmap * bitmap,uint64_t start,uint64_t len)22 xbitmap_set(
23 struct xbitmap *bitmap,
24 uint64_t start,
25 uint64_t len)
26 {
27 struct xbitmap_range *bmr;
28
29 bmr = kmalloc(sizeof(struct xbitmap_range), XCHK_GFP_FLAGS);
30 if (!bmr)
31 return -ENOMEM;
32
33 INIT_LIST_HEAD(&bmr->list);
34 bmr->start = start;
35 bmr->len = len;
36 list_add_tail(&bmr->list, &bitmap->list);
37
38 return 0;
39 }
40
41 /* Free everything related to this bitmap. */
42 void
xbitmap_destroy(struct xbitmap * bitmap)43 xbitmap_destroy(
44 struct xbitmap *bitmap)
45 {
46 struct xbitmap_range *bmr;
47 struct xbitmap_range *n;
48
49 for_each_xbitmap_extent(bmr, n, bitmap) {
50 list_del(&bmr->list);
51 kfree(bmr);
52 }
53 }
54
55 /* Set up a per-AG block bitmap. */
56 void
xbitmap_init(struct xbitmap * bitmap)57 xbitmap_init(
58 struct xbitmap *bitmap)
59 {
60 INIT_LIST_HEAD(&bitmap->list);
61 }
62
63 /* Compare two btree extents. */
64 static int
xbitmap_range_cmp(void * priv,const struct list_head * a,const struct list_head * b)65 xbitmap_range_cmp(
66 void *priv,
67 const struct list_head *a,
68 const struct list_head *b)
69 {
70 struct xbitmap_range *ap;
71 struct xbitmap_range *bp;
72
73 ap = container_of(a, struct xbitmap_range, list);
74 bp = container_of(b, struct xbitmap_range, list);
75
76 if (ap->start > bp->start)
77 return 1;
78 if (ap->start < bp->start)
79 return -1;
80 return 0;
81 }
82
83 /*
84 * Remove all the blocks mentioned in @sub from the extents in @bitmap.
85 *
86 * The intent is that callers will iterate the rmapbt for all of its records
87 * for a given owner to generate @bitmap; and iterate all the blocks of the
88 * metadata structures that are not being rebuilt and have the same rmapbt
89 * owner to generate @sub. This routine subtracts all the extents
90 * mentioned in sub from all the extents linked in @bitmap, which leaves
91 * @bitmap as the list of blocks that are not accounted for, which we assume
92 * are the dead blocks of the old metadata structure. The blocks mentioned in
93 * @bitmap can be reaped.
94 *
95 * This is the logical equivalent of bitmap &= ~sub.
96 */
97 #define LEFT_ALIGNED (1 << 0)
98 #define RIGHT_ALIGNED (1 << 1)
99 int
xbitmap_disunion(struct xbitmap * bitmap,struct xbitmap * sub)100 xbitmap_disunion(
101 struct xbitmap *bitmap,
102 struct xbitmap *sub)
103 {
104 struct list_head *lp;
105 struct xbitmap_range *br;
106 struct xbitmap_range *new_br;
107 struct xbitmap_range *sub_br;
108 uint64_t sub_start;
109 uint64_t sub_len;
110 int state;
111 int error = 0;
112
113 if (list_empty(&bitmap->list) || list_empty(&sub->list))
114 return 0;
115 ASSERT(!list_empty(&sub->list));
116
117 list_sort(NULL, &bitmap->list, xbitmap_range_cmp);
118 list_sort(NULL, &sub->list, xbitmap_range_cmp);
119
120 /*
121 * Now that we've sorted both lists, we iterate bitmap once, rolling
122 * forward through sub and/or bitmap as necessary until we find an
123 * overlap or reach the end of either list. We do not reset lp to the
124 * head of bitmap nor do we reset sub_br to the head of sub. The
125 * list traversal is similar to merge sort, but we're deleting
126 * instead. In this manner we avoid O(n^2) operations.
127 */
128 sub_br = list_first_entry(&sub->list, struct xbitmap_range,
129 list);
130 lp = bitmap->list.next;
131 while (lp != &bitmap->list) {
132 br = list_entry(lp, struct xbitmap_range, list);
133
134 /*
135 * Advance sub_br and/or br until we find a pair that
136 * intersect or we run out of extents.
137 */
138 while (sub_br->start + sub_br->len <= br->start) {
139 if (list_is_last(&sub_br->list, &sub->list))
140 goto out;
141 sub_br = list_next_entry(sub_br, list);
142 }
143 if (sub_br->start >= br->start + br->len) {
144 lp = lp->next;
145 continue;
146 }
147
148 /* trim sub_br to fit the extent we have */
149 sub_start = sub_br->start;
150 sub_len = sub_br->len;
151 if (sub_br->start < br->start) {
152 sub_len -= br->start - sub_br->start;
153 sub_start = br->start;
154 }
155 if (sub_len > br->len)
156 sub_len = br->len;
157
158 state = 0;
159 if (sub_start == br->start)
160 state |= LEFT_ALIGNED;
161 if (sub_start + sub_len == br->start + br->len)
162 state |= RIGHT_ALIGNED;
163 switch (state) {
164 case LEFT_ALIGNED:
165 /* Coincides with only the left. */
166 br->start += sub_len;
167 br->len -= sub_len;
168 break;
169 case RIGHT_ALIGNED:
170 /* Coincides with only the right. */
171 br->len -= sub_len;
172 lp = lp->next;
173 break;
174 case LEFT_ALIGNED | RIGHT_ALIGNED:
175 /* Total overlap, just delete ex. */
176 lp = lp->next;
177 list_del(&br->list);
178 kfree(br);
179 break;
180 case 0:
181 /*
182 * Deleting from the middle: add the new right extent
183 * and then shrink the left extent.
184 */
185 new_br = kmalloc(sizeof(struct xbitmap_range),
186 XCHK_GFP_FLAGS);
187 if (!new_br) {
188 error = -ENOMEM;
189 goto out;
190 }
191 INIT_LIST_HEAD(&new_br->list);
192 new_br->start = sub_start + sub_len;
193 new_br->len = br->start + br->len - new_br->start;
194 list_add(&new_br->list, &br->list);
195 br->len = sub_start - br->start;
196 lp = lp->next;
197 break;
198 default:
199 ASSERT(0);
200 break;
201 }
202 }
203
204 out:
205 return error;
206 }
207 #undef LEFT_ALIGNED
208 #undef RIGHT_ALIGNED
209
210 /*
211 * Record all btree blocks seen while iterating all records of a btree.
212 *
213 * We know that the btree query_all function starts at the left edge and walks
214 * towards the right edge of the tree. Therefore, we know that we can walk up
215 * the btree cursor towards the root; if the pointer for a given level points
216 * to the first record/key in that block, we haven't seen this block before;
217 * and therefore we need to remember that we saw this block in the btree.
218 *
219 * So if our btree is:
220 *
221 * 4
222 * / | \
223 * 1 2 3
224 *
225 * Pretend for this example that each leaf block has 100 btree records. For
226 * the first btree record, we'll observe that bc_levels[0].ptr == 1, so we
227 * record that we saw block 1. Then we observe that bc_levels[1].ptr == 1, so
228 * we record block 4. The list is [1, 4].
229 *
230 * For the second btree record, we see that bc_levels[0].ptr == 2, so we exit
231 * the loop. The list remains [1, 4].
232 *
233 * For the 101st btree record, we've moved onto leaf block 2. Now
234 * bc_levels[0].ptr == 1 again, so we record that we saw block 2. We see that
235 * bc_levels[1].ptr == 2, so we exit the loop. The list is now [1, 4, 2].
236 *
237 * For the 102nd record, bc_levels[0].ptr == 2, so we continue.
238 *
239 * For the 201st record, we've moved on to leaf block 3.
240 * bc_levels[0].ptr == 1, so we add 3 to the list. Now it is [1, 4, 2, 3].
241 *
242 * For the 300th record we just exit, with the list being [1, 4, 2, 3].
243 */
244
245 /*
246 * Record all the buffers pointed to by the btree cursor. Callers already
247 * engaged in a btree walk should call this function to capture the list of
248 * blocks going from the leaf towards the root.
249 */
250 int
xbitmap_set_btcur_path(struct xbitmap * bitmap,struct xfs_btree_cur * cur)251 xbitmap_set_btcur_path(
252 struct xbitmap *bitmap,
253 struct xfs_btree_cur *cur)
254 {
255 struct xfs_buf *bp;
256 xfs_fsblock_t fsb;
257 int i;
258 int error;
259
260 for (i = 0; i < cur->bc_nlevels && cur->bc_levels[i].ptr == 1; i++) {
261 xfs_btree_get_block(cur, i, &bp);
262 if (!bp)
263 continue;
264 fsb = XFS_DADDR_TO_FSB(cur->bc_mp, xfs_buf_daddr(bp));
265 error = xbitmap_set(bitmap, fsb, 1);
266 if (error)
267 return error;
268 }
269
270 return 0;
271 }
272
273 /* Collect a btree's block in the bitmap. */
274 STATIC int
xbitmap_collect_btblock(struct xfs_btree_cur * cur,int level,void * priv)275 xbitmap_collect_btblock(
276 struct xfs_btree_cur *cur,
277 int level,
278 void *priv)
279 {
280 struct xbitmap *bitmap = priv;
281 struct xfs_buf *bp;
282 xfs_fsblock_t fsbno;
283
284 xfs_btree_get_block(cur, level, &bp);
285 if (!bp)
286 return 0;
287
288 fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, xfs_buf_daddr(bp));
289 return xbitmap_set(bitmap, fsbno, 1);
290 }
291
292 /* Walk the btree and mark the bitmap wherever a btree block is found. */
293 int
xbitmap_set_btblocks(struct xbitmap * bitmap,struct xfs_btree_cur * cur)294 xbitmap_set_btblocks(
295 struct xbitmap *bitmap,
296 struct xfs_btree_cur *cur)
297 {
298 return xfs_btree_visit_blocks(cur, xbitmap_collect_btblock,
299 XFS_BTREE_VISIT_ALL, bitmap);
300 }
301
302 /* How many bits are set in this bitmap? */
303 uint64_t
xbitmap_hweight(struct xbitmap * bitmap)304 xbitmap_hweight(
305 struct xbitmap *bitmap)
306 {
307 struct xbitmap_range *bmr;
308 struct xbitmap_range *n;
309 uint64_t ret = 0;
310
311 for_each_xbitmap_extent(bmr, n, bitmap)
312 ret += bmr->len;
313
314 return ret;
315 }
316