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 1410327423 : rcbagbt_init_key_from_rec(
25 : union xfs_btree_key *key,
26 : const union xfs_btree_rec *rec)
27 : {
28 1410327423 : struct rcbag_key *bag_key = (struct rcbag_key *)key;
29 1410327423 : const struct rcbag_rec *bag_rec = (const struct rcbag_rec *)rec;
30 :
31 1410327423 : BUILD_BUG_ON(sizeof(struct rcbag_key) > sizeof(union xfs_btree_key));
32 1410327423 : BUILD_BUG_ON(sizeof(struct rcbag_rec) > sizeof(union xfs_btree_rec));
33 :
34 1410327423 : bag_key->rbg_startblock = bag_rec->rbg_startblock;
35 1410327423 : bag_key->rbg_blockcount = bag_rec->rbg_blockcount;
36 1410327423 : }
37 :
38 : STATIC void
39 332248948 : rcbagbt_init_rec_from_cur(
40 : struct xfs_btree_cur *cur,
41 : union xfs_btree_rec *rec)
42 : {
43 332248948 : struct rcbag_rec *bag_rec = (struct rcbag_rec *)rec;
44 332248948 : struct rcbag_rec *bag_irec = (struct rcbag_rec *)&cur->bc_rec;
45 :
46 332248948 : bag_rec->rbg_startblock = bag_irec->rbg_startblock;
47 332248948 : bag_rec->rbg_blockcount = bag_irec->rbg_blockcount;
48 332248948 : bag_rec->rbg_refcount = bag_irec->rbg_refcount;
49 332248948 : }
50 :
51 : STATIC int64_t
52 738661048 : rcbagbt_key_diff(
53 : struct xfs_btree_cur *cur,
54 : const union xfs_btree_key *key)
55 : {
56 738661048 : struct rcbag_rec *rec = (struct rcbag_rec *)&cur->bc_rec;
57 738661048 : const struct rcbag_key *kp = (const struct rcbag_key *)key;
58 :
59 738661048 : if (kp->rbg_startblock > rec->rbg_startblock)
60 : return 1;
61 404307574 : if (kp->rbg_startblock < rec->rbg_startblock)
62 : return -1;
63 :
64 48730019 : if (kp->rbg_blockcount > rec->rbg_blockcount)
65 : return 1;
66 44876489 : if (kp->rbg_blockcount < rec->rbg_blockcount)
67 15513330 : 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 0 : 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 0 : const struct rcbag_key *kp1 = (const struct rcbag_key *)k1;
104 0 : const struct rcbag_key *kp2 = (const struct rcbag_key *)k2;
105 :
106 0 : if (kp1->rbg_startblock > kp2->rbg_startblock)
107 : return 0;
108 0 : if (kp1->rbg_startblock < kp2->rbg_startblock)
109 : return 1;
110 :
111 0 : if (kp1->rbg_blockcount > kp2->rbg_blockcount)
112 : return 0;
113 0 : if (kp1->rbg_blockcount < kp2->rbg_blockcount)
114 0 : return 1;
115 :
116 : return 0;
117 : }
118 :
119 : STATIC int
120 3756448 : 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 3756448 : const struct rcbag_rec *rp1 = (const struct rcbag_rec *)r1;
126 3756448 : const struct rcbag_rec *rp2 = (const struct rcbag_rec *)r2;
127 :
128 3756448 : if (rp1->rbg_startblock > rp2->rbg_startblock)
129 : return 0;
130 3756448 : if (rp1->rbg_startblock < rp2->rbg_startblock)
131 : return 1;
132 :
133 3756448 : if (rp1->rbg_blockcount > rp2->rbg_blockcount)
134 : return 0;
135 3756448 : if (rp1->rbg_blockcount < rp2->rbg_blockcount)
136 3756448 : return 1;
137 :
138 : return 0;
139 : }
140 :
141 : static xfs_failaddr_t
142 691670358 : rcbagbt_verify(
143 : struct xfs_buf *bp)
144 : {
145 691670358 : struct xfs_mount *mp = bp->b_mount;
146 691670358 : struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
147 691670358 : xfs_failaddr_t fa;
148 691670358 : unsigned int level;
149 :
150 691670358 : if (!xfs_verify_magic(bp, block->bb_magic))
151 0 : return __this_address;
152 :
153 691670353 : fa = xfs_btree_lblock_v5hdr_verify(bp, XFS_RMAP_OWN_UNKNOWN);
154 691670356 : if (fa)
155 : return fa;
156 :
157 691670351 : level = be16_to_cpu(block->bb_level);
158 691670351 : if (level >= rcbagbt_maxlevels_possible())
159 0 : return __this_address;
160 :
161 691670355 : return xfbtree_lblock_verify(bp,
162 : rcbagbt_maxrecs(mp, xfo_to_b(1), level == 0));
163 : }
164 :
165 : static void
166 65966 : rcbagbt_rw_verify(
167 : struct xfs_buf *bp)
168 : {
169 65966 : xfs_failaddr_t fa = rcbagbt_verify(bp);
170 :
171 65969 : if (fa)
172 0 : xfs_verifier_error(bp, -EFSCORRUPTED, fa);
173 65969 : }
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 1025285946 : 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 1025285946 : struct xfs_btree_cur *cur;
216 :
217 1025285944 : cur = xfs_btree_alloc_cursor(mp, tp, XFS_BTNUM_RCBAG, &rcbagbt_mem_ops,
218 1025285946 : rcbagbt_maxlevels_possible(), rcbagbt_cur_cache);
219 :
220 1025285951 : cur->bc_mem.xfbtree = xfbtree;
221 1025285951 : cur->bc_mem.head_bp = head_bp;
222 1025285951 : cur->bc_nlevels = xfs_btree_mem_head_nlevels(head_bp);
223 1025285943 : return cur;
224 : }
225 :
226 : /* Create an in-memory refcount bag btree. */
227 : int
228 65969 : rcbagbt_mem_create(
229 : struct xfs_mount *mp,
230 : struct xfs_buftarg *target,
231 : struct xfbtree **xfbtreep)
232 : {
233 65969 : struct xfbtree_config cfg = {
234 : .btree_ops = &rcbagbt_mem_ops,
235 : .target = target,
236 : .flags = XFBTREE_DIRECT_MAP,
237 : };
238 :
239 65969 : 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 1716955640 : rcbagbt_maxlevels_possible(void)
280 : {
281 1716955640 : unsigned int minrecs[2];
282 :
283 1716955640 : RCBAGBT_INIT_MINRECS(minrecs);
284 1716955640 : 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 12 : rcbagbt_init_cur_cache(void)
300 : {
301 12 : rcbagbt_cur_cache = kmem_cache_create("xfs_rcbagbt_cur",
302 12 : xfs_btree_cur_sizeof(rcbagbt_maxlevels_possible()),
303 : 0, 0, NULL);
304 :
305 12 : if (!rcbagbt_cur_cache)
306 0 : return -ENOMEM;
307 : return 0;
308 : }
309 :
310 : void
311 12 : rcbagbt_destroy_cur_cache(void)
312 : {
313 12 : kmem_cache_destroy(rcbagbt_cur_cache);
314 12 : rcbagbt_cur_cache = NULL;
315 12 : }
316 :
317 : /* Look up the refcount bag record corresponding to this reverse mapping. */
318 : int
319 361612106 : rcbagbt_lookup_eq(
320 : struct xfs_btree_cur *cur,
321 : const struct xfs_rmap_irec *rmap,
322 : int *success)
323 : {
324 361612106 : struct rcbag_rec *rec = (struct rcbag_rec *)&cur->bc_rec;
325 :
326 361612106 : rec->rbg_startblock = rmap->rm_startblock;
327 361612106 : rec->rbg_blockcount = rmap->rm_blockcount;
328 :
329 361612106 : return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, success);
330 : }
331 :
332 : /* Get the data from the pointed-to record. */
333 : int
334 717921960 : rcbagbt_get_rec(
335 : struct xfs_btree_cur *cur,
336 : struct rcbag_rec *rec,
337 : int *has)
338 : {
339 717921960 : union xfs_btree_rec *btrec;
340 717921960 : int error;
341 :
342 717921960 : error = xfs_btree_get_rec(cur, &btrec, has);
343 717922013 : if (error || !(*has))
344 : return error;
345 :
346 1435844026 : memcpy(rec, btrec, sizeof(struct rcbag_rec));
347 717922013 : return 0;
348 : }
349 :
350 : /* Update the record referred to by cur to the value given. */
351 : int
352 29363159 : rcbagbt_update(
353 : struct xfs_btree_cur *cur,
354 : const struct rcbag_rec *rec)
355 : {
356 29363159 : union xfs_btree_rec btrec;
357 :
358 29363159 : memcpy(&btrec, rec, sizeof(struct rcbag_rec));
359 29363159 : return xfs_btree_update(cur, &btrec);
360 : }
361 :
362 : /* Update the record referred to by cur to the value given. */
363 : int
364 332248948 : rcbagbt_insert(
365 : struct xfs_btree_cur *cur,
366 : const struct rcbag_rec *rec,
367 : int *success)
368 : {
369 332248948 : struct rcbag_rec *btrec = (struct rcbag_rec *)&cur->bc_rec;
370 :
371 664497896 : memcpy(btrec, rec, sizeof(struct rcbag_rec));
372 332248948 : return xfs_btree_insert(cur, success);
373 : }
|
