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