Line data Source code
1 : // SPDX-License-Identifier: GPL-2.0-or-later
2 : /*
3 : * Copyright (C) 2022-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_format.h"
10 : #include "xfs_trans_resv.h"
11 : #include "xfs_mount.h"
12 : #include "xfs_defer.h"
13 : #include "xfs_btree.h"
14 : #include "xfs_btree_mem.h"
15 : #include "xfs_error.h"
16 : #include "scrub/xfile.h"
17 : #include "scrub/xfbtree.h"
18 : #include "scrub/rcbag_btree.h"
19 : #include "scrub/trace.h"
20 :
21 : static struct kmem_cache *rcbagbt_cur_cache;
22 :
23 : STATIC void
24 1331886088 : rcbagbt_init_key_from_rec(
25 : union xfs_btree_key *key,
26 : const union xfs_btree_rec *rec)
27 : {
28 1331886088 : struct rcbag_key *bag_key = (struct rcbag_key *)key;
29 1331886088 : const struct rcbag_rec *bag_rec = (const struct rcbag_rec *)rec;
30 :
31 1331886088 : BUILD_BUG_ON(sizeof(struct rcbag_key) > sizeof(union xfs_btree_key));
32 1331886088 : BUILD_BUG_ON(sizeof(struct rcbag_rec) > sizeof(union xfs_btree_rec));
33 :
34 1331886088 : bag_key->rbg_startblock = bag_rec->rbg_startblock;
35 1331886088 : bag_key->rbg_blockcount = bag_rec->rbg_blockcount;
36 1331886088 : }
37 :
38 : STATIC void
39 285109992 : rcbagbt_init_rec_from_cur(
40 : struct xfs_btree_cur *cur,
41 : union xfs_btree_rec *rec)
42 : {
43 285109992 : struct rcbag_rec *bag_rec = (struct rcbag_rec *)rec;
44 285109992 : struct rcbag_rec *bag_irec = (struct rcbag_rec *)&cur->bc_rec;
45 :
46 285109992 : bag_rec->rbg_startblock = bag_irec->rbg_startblock;
47 285109992 : bag_rec->rbg_blockcount = bag_irec->rbg_blockcount;
48 285109992 : bag_rec->rbg_refcount = bag_irec->rbg_refcount;
49 285109992 : }
50 :
51 : STATIC int64_t
52 740018423 : rcbagbt_key_diff(
53 : struct xfs_btree_cur *cur,
54 : const union xfs_btree_key *key)
55 : {
56 740018423 : struct rcbag_rec *rec = (struct rcbag_rec *)&cur->bc_rec;
57 740018423 : const struct rcbag_key *kp = (const struct rcbag_key *)key;
58 :
59 740018423 : if (kp->rbg_startblock > rec->rbg_startblock)
60 : return 1;
61 451023921 : if (kp->rbg_startblock < rec->rbg_startblock)
62 : return -1;
63 :
64 115143369 : if (kp->rbg_blockcount > rec->rbg_blockcount)
65 : return 1;
66 103806507 : if (kp->rbg_blockcount < rec->rbg_blockcount)
67 36102862 : return -1;
68 :
69 : return 0;
70 : }
71 :
72 : STATIC int64_t
73 0 : rcbagbt_diff_two_keys(
74 : struct xfs_btree_cur *cur,
75 : const union xfs_btree_key *k1,
76 : const union xfs_btree_key *k2,
77 : const union xfs_btree_key *mask)
78 : {
79 0 : const struct rcbag_key *kp1 = (const struct rcbag_key *)k1;
80 0 : const struct rcbag_key *kp2 = (const struct rcbag_key *)k2;
81 :
82 0 : ASSERT(mask == NULL);
83 :
84 0 : if (kp1->rbg_startblock > kp2->rbg_startblock)
85 : return 1;
86 0 : if (kp1->rbg_startblock < kp2->rbg_startblock)
87 : return -1;
88 :
89 0 : if (kp1->rbg_blockcount > kp2->rbg_blockcount)
90 : return 1;
91 0 : if (kp1->rbg_blockcount < kp2->rbg_blockcount)
92 0 : return -1;
93 :
94 : return 0;
95 : }
96 :
97 : STATIC int
98 14 : rcbagbt_keys_inorder(
99 : struct xfs_btree_cur *cur,
100 : const union xfs_btree_key *k1,
101 : const union xfs_btree_key *k2)
102 : {
103 14 : const struct rcbag_key *kp1 = (const struct rcbag_key *)k1;
104 14 : const struct rcbag_key *kp2 = (const struct rcbag_key *)k2;
105 :
106 14 : if (kp1->rbg_startblock > kp2->rbg_startblock)
107 : return 0;
108 14 : if (kp1->rbg_startblock < kp2->rbg_startblock)
109 : return 1;
110 :
111 14 : if (kp1->rbg_blockcount > kp2->rbg_blockcount)
112 : return 0;
113 14 : if (kp1->rbg_blockcount < kp2->rbg_blockcount)
114 14 : return 1;
115 :
116 : return 0;
117 : }
118 :
119 : STATIC int
120 7143132 : rcbagbt_recs_inorder(
121 : struct xfs_btree_cur *cur,
122 : const union xfs_btree_rec *r1,
123 : const union xfs_btree_rec *r2)
124 : {
125 7143132 : const struct rcbag_rec *rp1 = (const struct rcbag_rec *)r1;
126 7143132 : const struct rcbag_rec *rp2 = (const struct rcbag_rec *)r2;
127 :
128 7143132 : if (rp1->rbg_startblock > rp2->rbg_startblock)
129 : return 0;
130 7143132 : if (rp1->rbg_startblock < rp2->rbg_startblock)
131 : return 1;
132 :
133 7143132 : if (rp1->rbg_blockcount > rp2->rbg_blockcount)
134 : return 0;
135 7143132 : if (rp1->rbg_blockcount < rp2->rbg_blockcount)
136 7143132 : return 1;
137 :
138 : return 0;
139 : }
140 :
141 : static xfs_failaddr_t
142 633465309 : rcbagbt_verify(
143 : struct xfs_buf *bp)
144 : {
145 633465309 : struct xfs_mount *mp = bp->b_mount;
146 633465309 : struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
147 633465309 : xfs_failaddr_t fa;
148 633465309 : unsigned int level;
149 :
150 633465309 : if (!xfs_verify_magic(bp, block->bb_magic))
151 0 : return __this_address;
152 :
153 633459680 : fa = xfs_btree_lblock_v5hdr_verify(bp, XFS_RMAP_OWN_UNKNOWN);
154 633454025 : if (fa)
155 : return fa;
156 :
157 633453979 : level = be16_to_cpu(block->bb_level);
158 633453979 : if (level >= rcbagbt_maxlevels_possible())
159 0 : return __this_address;
160 :
161 633451840 : return xfbtree_lblock_verify(bp,
162 : rcbagbt_maxrecs(mp, xfo_to_b(1), level == 0));
163 : }
164 :
165 : static void
166 120258 : rcbagbt_rw_verify(
167 : struct xfs_buf *bp)
168 : {
169 120258 : xfs_failaddr_t fa = rcbagbt_verify(bp);
170 :
171 120113 : if (fa)
172 0 : xfs_verifier_error(bp, -EFSCORRUPTED, fa);
173 120113 : }
174 :
175 : /* skip crc checks on in-memory btrees to save time */
176 : static const struct xfs_buf_ops rcbagbt_mem_buf_ops = {
177 : .name = "rcbagbt_mem",
178 : .magic = { 0, cpu_to_be32(RCBAG_MAGIC) },
179 : .verify_read = rcbagbt_rw_verify,
180 : .verify_write = rcbagbt_rw_verify,
181 : .verify_struct = rcbagbt_verify,
182 : };
183 :
184 : static const struct xfs_btree_ops rcbagbt_mem_ops = {
185 : .rec_len = sizeof(struct rcbag_rec),
186 : .key_len = sizeof(struct rcbag_key),
187 : .lru_refs = 1,
188 : .geom_flags = XFS_BTREE_CRC_BLOCKS | XFS_BTREE_LONG_PTRS |
189 : XFS_BTREE_IN_XFILE,
190 :
191 : .dup_cursor = xfbtree_dup_cursor,
192 : .set_root = xfbtree_set_root,
193 : .alloc_block = xfbtree_alloc_block,
194 : .free_block = xfbtree_free_block,
195 : .get_minrecs = xfbtree_get_minrecs,
196 : .get_maxrecs = xfbtree_get_maxrecs,
197 : .init_key_from_rec = rcbagbt_init_key_from_rec,
198 : .init_rec_from_cur = rcbagbt_init_rec_from_cur,
199 : .init_ptr_from_cur = xfbtree_init_ptr_from_cur,
200 : .key_diff = rcbagbt_key_diff,
201 : .buf_ops = &rcbagbt_mem_buf_ops,
202 : .diff_two_keys = rcbagbt_diff_two_keys,
203 : .keys_inorder = rcbagbt_keys_inorder,
204 : .recs_inorder = rcbagbt_recs_inorder,
205 : };
206 :
207 : /* Create a cursor for an in-memory btree. */
208 : struct xfs_btree_cur *
209 919678747 : rcbagbt_mem_cursor(
210 : struct xfs_mount *mp,
211 : struct xfs_trans *tp,
212 : struct xfs_buf *head_bp,
213 : struct xfbtree *xfbtree)
214 : {
215 919678747 : struct xfs_btree_cur *cur;
216 :
217 919674163 : cur = xfs_btree_alloc_cursor(mp, tp, XFS_BTNUM_RCBAG, &rcbagbt_mem_ops,
218 919678747 : rcbagbt_maxlevels_possible(), rcbagbt_cur_cache);
219 :
220 919700101 : cur->bc_mem.xfbtree = xfbtree;
221 919700101 : cur->bc_mem.head_bp = head_bp;
222 919700101 : cur->bc_nlevels = xfs_btree_mem_head_nlevels(head_bp);
223 919695610 : return cur;
224 : }
225 :
226 : /* Create an in-memory refcount bag btree. */
227 : int
228 120448 : rcbagbt_mem_create(
229 : struct xfs_mount *mp,
230 : struct xfs_buftarg *target,
231 : struct xfbtree **xfbtreep)
232 : {
233 120448 : struct xfbtree_config cfg = {
234 : .btree_ops = &rcbagbt_mem_ops,
235 : .target = target,
236 : .flags = XFBTREE_DIRECT_MAP,
237 : };
238 :
239 120448 : return xfbtree_create(mp, &cfg, xfbtreep);
240 : }
241 :
242 : /* Calculate number of records in a refcount bag btree block. */
243 : static inline unsigned int
244 : rcbagbt_block_maxrecs(
245 : unsigned int blocklen,
246 : bool leaf)
247 : {
248 0 : if (leaf)
249 0 : return blocklen / sizeof(struct rcbag_rec);
250 0 : return blocklen /
251 : (sizeof(struct rcbag_key) + sizeof(rcbag_ptr_t));
252 : }
253 :
254 : /*
255 : * Calculate number of records in an refcount bag btree block.
256 : */
257 : unsigned int
258 0 : rcbagbt_maxrecs(
259 : struct xfs_mount *mp,
260 : unsigned int blocklen,
261 : bool leaf)
262 : {
263 0 : blocklen -= RCBAG_BLOCK_LEN;
264 0 : return rcbagbt_block_maxrecs(blocklen, leaf);
265 : }
266 :
267 : #define RCBAGBT_INIT_MINRECS(minrecs) \
268 : do { \
269 : unsigned int blocklen; \
270 : \
271 : blocklen = PAGE_SIZE - XFS_BTREE_LBLOCK_CRC_LEN; \
272 : \
273 : minrecs[0] = rcbagbt_block_maxrecs(blocklen, true) / 2; \
274 : minrecs[1] = rcbagbt_block_maxrecs(blocklen, false) / 2; \
275 : } while (0)
276 :
277 : /* Compute the max possible height for refcount bag btrees. */
278 : unsigned int
279 1553132976 : rcbagbt_maxlevels_possible(void)
280 : {
281 1553132976 : unsigned int minrecs[2];
282 :
283 1553132976 : RCBAGBT_INIT_MINRECS(minrecs);
284 1553132976 : return xfs_btree_space_to_height(minrecs, ULLONG_MAX);
285 : }
286 :
287 : /* Calculate the refcount bag btree size for some records. */
288 : unsigned long long
289 0 : rcbagbt_calc_size(
290 : unsigned long long nr_records)
291 : {
292 0 : unsigned int minrecs[2];
293 :
294 0 : RCBAGBT_INIT_MINRECS(minrecs);
295 0 : return xfs_btree_calc_size(minrecs, nr_records);
296 : }
297 :
298 : int __init
299 59 : rcbagbt_init_cur_cache(void)
300 : {
301 59 : rcbagbt_cur_cache = kmem_cache_create("xfs_rcbagbt_cur",
302 59 : xfs_btree_cur_sizeof(rcbagbt_maxlevels_possible()),
303 : 0, 0, NULL);
304 :
305 59 : if (!rcbagbt_cur_cache)
306 0 : return -ENOMEM;
307 : return 0;
308 : }
309 :
310 : void
311 58 : rcbagbt_destroy_cur_cache(void)
312 : {
313 58 : kmem_cache_destroy(rcbagbt_cur_cache);
314 58 : rcbagbt_cur_cache = NULL;
315 58 : }
316 :
317 : /* Look up the refcount bag record corresponding to this reverse mapping. */
318 : int
319 352820551 : rcbagbt_lookup_eq(
320 : struct xfs_btree_cur *cur,
321 : const struct xfs_rmap_irec *rmap,
322 : int *success)
323 : {
324 352820551 : struct rcbag_rec *rec = (struct rcbag_rec *)&cur->bc_rec;
325 :
326 352820551 : rec->rbg_startblock = rmap->rm_startblock;
327 352820551 : rec->rbg_blockcount = rmap->rm_blockcount;
328 :
329 352820551 : return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, success);
330 : }
331 :
332 : /* Get the data from the pointed-to record. */
333 : int
334 694206390 : rcbagbt_get_rec(
335 : struct xfs_btree_cur *cur,
336 : struct rcbag_rec *rec,
337 : int *has)
338 : {
339 694206390 : union xfs_btree_rec *btrec;
340 694206390 : int error;
341 :
342 694206390 : error = xfs_btree_get_rec(cur, &btrec, has);
343 694202205 : if (error || !(*has))
344 : return error;
345 :
346 1388404410 : memcpy(rec, btrec, sizeof(struct rcbag_rec));
347 694202205 : return 0;
348 : }
349 :
350 : /* Update the record referred to by cur to the value given. */
351 : int
352 67703902 : rcbagbt_update(
353 : struct xfs_btree_cur *cur,
354 : const struct rcbag_rec *rec)
355 : {
356 67703902 : union xfs_btree_rec btrec;
357 :
358 67703902 : memcpy(&btrec, rec, sizeof(struct rcbag_rec));
359 67703902 : return xfs_btree_update(cur, &btrec);
360 : }
361 :
362 : /* Update the record referred to by cur to the value given. */
363 : int
364 285110769 : rcbagbt_insert(
365 : struct xfs_btree_cur *cur,
366 : const struct rcbag_rec *rec,
367 : int *success)
368 : {
369 285110769 : struct rcbag_rec *btrec = (struct rcbag_rec *)&cur->bc_rec;
370 :
371 570221538 : memcpy(btrec, rec, sizeof(struct rcbag_rec));
372 285110769 : return xfs_btree_insert(cur, success);
373 : }
|
