1 // SPDX-License-Identifier: GPL-2.0+
2 /*
3  * Copyright (C) 2016 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_log_format.h"
11 #include "xfs_trans_resv.h"
12 #include "xfs_mount.h"
13 #include "xfs_btree.h"
14 #include "xfs_btree_staging.h"
15 #include "xfs_refcount_btree.h"
16 #include "xfs_alloc.h"
17 #include "xfs_error.h"
18 #include "xfs_trace.h"
19 #include "xfs_trans.h"
20 #include "xfs_bit.h"
21 #include "xfs_rmap.h"
22 #include "xfs_ag.h"
23 
24 static struct kmem_cache	*xfs_refcountbt_cur_cache;
25 
26 static struct xfs_btree_cur *
27 xfs_refcountbt_dup_cursor(
28 	struct xfs_btree_cur	*cur)
29 {
30 	return xfs_refcountbt_init_cursor(cur->bc_mp, cur->bc_tp,
31 			cur->bc_ag.agbp, cur->bc_ag.pag);
32 }
33 
34 STATIC void
35 xfs_refcountbt_set_root(
36 	struct xfs_btree_cur		*cur,
37 	const union xfs_btree_ptr	*ptr,
38 	int				inc)
39 {
40 	struct xfs_buf		*agbp = cur->bc_ag.agbp;
41 	struct xfs_agf		*agf = agbp->b_addr;
42 	struct xfs_perag	*pag = agbp->b_pag;
43 
44 	ASSERT(ptr->s != 0);
45 
46 	agf->agf_refcount_root = ptr->s;
47 	be32_add_cpu(&agf->agf_refcount_level, inc);
48 	pag->pagf_refcount_level += inc;
49 
50 	xfs_alloc_log_agf(cur->bc_tp, agbp,
51 			XFS_AGF_REFCOUNT_ROOT | XFS_AGF_REFCOUNT_LEVEL);
52 }
53 
54 STATIC int
55 xfs_refcountbt_alloc_block(
56 	struct xfs_btree_cur		*cur,
57 	const union xfs_btree_ptr	*start,
58 	union xfs_btree_ptr		*new,
59 	int				*stat)
60 {
61 	struct xfs_buf		*agbp = cur->bc_ag.agbp;
62 	struct xfs_agf		*agf = agbp->b_addr;
63 	struct xfs_alloc_arg	args;		/* block allocation args */
64 	int			error;		/* error return value */
65 
66 	memset(&args, 0, sizeof(args));
67 	args.tp = cur->bc_tp;
68 	args.mp = cur->bc_mp;
69 	args.type = XFS_ALLOCTYPE_NEAR_BNO;
70 	args.fsbno = XFS_AGB_TO_FSB(cur->bc_mp, cur->bc_ag.pag->pag_agno,
71 			xfs_refc_block(args.mp));
72 	args.oinfo = XFS_RMAP_OINFO_REFC;
73 	args.minlen = args.maxlen = args.prod = 1;
74 	args.resv = XFS_AG_RESV_METADATA;
75 
76 	error = xfs_alloc_vextent(&args);
77 	if (error)
78 		goto out_error;
79 	trace_xfs_refcountbt_alloc_block(cur->bc_mp, cur->bc_ag.pag->pag_agno,
80 			args.agbno, 1);
81 	if (args.fsbno == NULLFSBLOCK) {
82 		*stat = 0;
83 		return 0;
84 	}
85 	ASSERT(args.agno == cur->bc_ag.pag->pag_agno);
86 	ASSERT(args.len == 1);
87 
88 	new->s = cpu_to_be32(args.agbno);
89 	be32_add_cpu(&agf->agf_refcount_blocks, 1);
90 	xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_REFCOUNT_BLOCKS);
91 
92 	*stat = 1;
93 	return 0;
94 
95 out_error:
96 	return error;
97 }
98 
99 STATIC int
100 xfs_refcountbt_free_block(
101 	struct xfs_btree_cur	*cur,
102 	struct xfs_buf		*bp)
103 {
104 	struct xfs_mount	*mp = cur->bc_mp;
105 	struct xfs_buf		*agbp = cur->bc_ag.agbp;
106 	struct xfs_agf		*agf = agbp->b_addr;
107 	xfs_fsblock_t		fsbno = XFS_DADDR_TO_FSB(mp, xfs_buf_daddr(bp));
108 	int			error;
109 
110 	trace_xfs_refcountbt_free_block(cur->bc_mp, cur->bc_ag.pag->pag_agno,
111 			XFS_FSB_TO_AGBNO(cur->bc_mp, fsbno), 1);
112 	be32_add_cpu(&agf->agf_refcount_blocks, -1);
113 	xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_REFCOUNT_BLOCKS);
114 	error = xfs_free_extent(cur->bc_tp, fsbno, 1, &XFS_RMAP_OINFO_REFC,
115 			XFS_AG_RESV_METADATA);
116 	if (error)
117 		return error;
118 
119 	return error;
120 }
121 
122 STATIC int
123 xfs_refcountbt_get_minrecs(
124 	struct xfs_btree_cur	*cur,
125 	int			level)
126 {
127 	return cur->bc_mp->m_refc_mnr[level != 0];
128 }
129 
130 STATIC int
131 xfs_refcountbt_get_maxrecs(
132 	struct xfs_btree_cur	*cur,
133 	int			level)
134 {
135 	return cur->bc_mp->m_refc_mxr[level != 0];
136 }
137 
138 STATIC void
139 xfs_refcountbt_init_key_from_rec(
140 	union xfs_btree_key		*key,
141 	const union xfs_btree_rec	*rec)
142 {
143 	key->refc.rc_startblock = rec->refc.rc_startblock;
144 }
145 
146 STATIC void
147 xfs_refcountbt_init_high_key_from_rec(
148 	union xfs_btree_key		*key,
149 	const union xfs_btree_rec	*rec)
150 {
151 	__u32				x;
152 
153 	x = be32_to_cpu(rec->refc.rc_startblock);
154 	x += be32_to_cpu(rec->refc.rc_blockcount) - 1;
155 	key->refc.rc_startblock = cpu_to_be32(x);
156 }
157 
158 STATIC void
159 xfs_refcountbt_init_rec_from_cur(
160 	struct xfs_btree_cur	*cur,
161 	union xfs_btree_rec	*rec)
162 {
163 	rec->refc.rc_startblock = cpu_to_be32(cur->bc_rec.rc.rc_startblock);
164 	rec->refc.rc_blockcount = cpu_to_be32(cur->bc_rec.rc.rc_blockcount);
165 	rec->refc.rc_refcount = cpu_to_be32(cur->bc_rec.rc.rc_refcount);
166 }
167 
168 STATIC void
169 xfs_refcountbt_init_ptr_from_cur(
170 	struct xfs_btree_cur	*cur,
171 	union xfs_btree_ptr	*ptr)
172 {
173 	struct xfs_agf		*agf = cur->bc_ag.agbp->b_addr;
174 
175 	ASSERT(cur->bc_ag.pag->pag_agno == be32_to_cpu(agf->agf_seqno));
176 
177 	ptr->s = agf->agf_refcount_root;
178 }
179 
180 STATIC int64_t
181 xfs_refcountbt_key_diff(
182 	struct xfs_btree_cur		*cur,
183 	const union xfs_btree_key	*key)
184 {
185 	struct xfs_refcount_irec	*rec = &cur->bc_rec.rc;
186 	const struct xfs_refcount_key	*kp = &key->refc;
187 
188 	return (int64_t)be32_to_cpu(kp->rc_startblock) - rec->rc_startblock;
189 }
190 
191 STATIC int64_t
192 xfs_refcountbt_diff_two_keys(
193 	struct xfs_btree_cur		*cur,
194 	const union xfs_btree_key	*k1,
195 	const union xfs_btree_key	*k2)
196 {
197 	return (int64_t)be32_to_cpu(k1->refc.rc_startblock) -
198 			  be32_to_cpu(k2->refc.rc_startblock);
199 }
200 
201 STATIC xfs_failaddr_t
202 xfs_refcountbt_verify(
203 	struct xfs_buf		*bp)
204 {
205 	struct xfs_mount	*mp = bp->b_mount;
206 	struct xfs_btree_block	*block = XFS_BUF_TO_BLOCK(bp);
207 	struct xfs_perag	*pag = bp->b_pag;
208 	xfs_failaddr_t		fa;
209 	unsigned int		level;
210 
211 	if (!xfs_verify_magic(bp, block->bb_magic))
212 		return __this_address;
213 
214 	if (!xfs_has_reflink(mp))
215 		return __this_address;
216 	fa = xfs_btree_sblock_v5hdr_verify(bp);
217 	if (fa)
218 		return fa;
219 
220 	level = be16_to_cpu(block->bb_level);
221 	if (pag && pag->pagf_init) {
222 		if (level >= pag->pagf_refcount_level)
223 			return __this_address;
224 	} else if (level >= mp->m_refc_maxlevels)
225 		return __this_address;
226 
227 	return xfs_btree_sblock_verify(bp, mp->m_refc_mxr[level != 0]);
228 }
229 
230 STATIC void
231 xfs_refcountbt_read_verify(
232 	struct xfs_buf	*bp)
233 {
234 	xfs_failaddr_t	fa;
235 
236 	if (!xfs_btree_sblock_verify_crc(bp))
237 		xfs_verifier_error(bp, -EFSBADCRC, __this_address);
238 	else {
239 		fa = xfs_refcountbt_verify(bp);
240 		if (fa)
241 			xfs_verifier_error(bp, -EFSCORRUPTED, fa);
242 	}
243 
244 	if (bp->b_error)
245 		trace_xfs_btree_corrupt(bp, _RET_IP_);
246 }
247 
248 STATIC void
249 xfs_refcountbt_write_verify(
250 	struct xfs_buf	*bp)
251 {
252 	xfs_failaddr_t	fa;
253 
254 	fa = xfs_refcountbt_verify(bp);
255 	if (fa) {
256 		trace_xfs_btree_corrupt(bp, _RET_IP_);
257 		xfs_verifier_error(bp, -EFSCORRUPTED, fa);
258 		return;
259 	}
260 	xfs_btree_sblock_calc_crc(bp);
261 
262 }
263 
264 const struct xfs_buf_ops xfs_refcountbt_buf_ops = {
265 	.name			= "xfs_refcountbt",
266 	.magic			= { 0, cpu_to_be32(XFS_REFC_CRC_MAGIC) },
267 	.verify_read		= xfs_refcountbt_read_verify,
268 	.verify_write		= xfs_refcountbt_write_verify,
269 	.verify_struct		= xfs_refcountbt_verify,
270 };
271 
272 STATIC int
273 xfs_refcountbt_keys_inorder(
274 	struct xfs_btree_cur		*cur,
275 	const union xfs_btree_key	*k1,
276 	const union xfs_btree_key	*k2)
277 {
278 	return be32_to_cpu(k1->refc.rc_startblock) <
279 	       be32_to_cpu(k2->refc.rc_startblock);
280 }
281 
282 STATIC int
283 xfs_refcountbt_recs_inorder(
284 	struct xfs_btree_cur		*cur,
285 	const union xfs_btree_rec	*r1,
286 	const union xfs_btree_rec	*r2)
287 {
288 	return  be32_to_cpu(r1->refc.rc_startblock) +
289 		be32_to_cpu(r1->refc.rc_blockcount) <=
290 		be32_to_cpu(r2->refc.rc_startblock);
291 }
292 
293 static const struct xfs_btree_ops xfs_refcountbt_ops = {
294 	.rec_len		= sizeof(struct xfs_refcount_rec),
295 	.key_len		= sizeof(struct xfs_refcount_key),
296 
297 	.dup_cursor		= xfs_refcountbt_dup_cursor,
298 	.set_root		= xfs_refcountbt_set_root,
299 	.alloc_block		= xfs_refcountbt_alloc_block,
300 	.free_block		= xfs_refcountbt_free_block,
301 	.get_minrecs		= xfs_refcountbt_get_minrecs,
302 	.get_maxrecs		= xfs_refcountbt_get_maxrecs,
303 	.init_key_from_rec	= xfs_refcountbt_init_key_from_rec,
304 	.init_high_key_from_rec	= xfs_refcountbt_init_high_key_from_rec,
305 	.init_rec_from_cur	= xfs_refcountbt_init_rec_from_cur,
306 	.init_ptr_from_cur	= xfs_refcountbt_init_ptr_from_cur,
307 	.key_diff		= xfs_refcountbt_key_diff,
308 	.buf_ops		= &xfs_refcountbt_buf_ops,
309 	.diff_two_keys		= xfs_refcountbt_diff_two_keys,
310 	.keys_inorder		= xfs_refcountbt_keys_inorder,
311 	.recs_inorder		= xfs_refcountbt_recs_inorder,
312 };
313 
314 /*
315  * Initialize a new refcount btree cursor.
316  */
317 static struct xfs_btree_cur *
318 xfs_refcountbt_init_common(
319 	struct xfs_mount	*mp,
320 	struct xfs_trans	*tp,
321 	struct xfs_perag	*pag)
322 {
323 	struct xfs_btree_cur	*cur;
324 
325 	ASSERT(pag->pag_agno < mp->m_sb.sb_agcount);
326 
327 	cur = xfs_btree_alloc_cursor(mp, tp, XFS_BTNUM_REFC,
328 			mp->m_refc_maxlevels, xfs_refcountbt_cur_cache);
329 	cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_refcbt_2);
330 
331 	cur->bc_flags |= XFS_BTREE_CRC_BLOCKS;
332 
333 	/* take a reference for the cursor */
334 	atomic_inc(&pag->pag_ref);
335 	cur->bc_ag.pag = pag;
336 
337 	cur->bc_ag.refc.nr_ops = 0;
338 	cur->bc_ag.refc.shape_changes = 0;
339 	cur->bc_ops = &xfs_refcountbt_ops;
340 	return cur;
341 }
342 
343 /* Create a btree cursor. */
344 struct xfs_btree_cur *
345 xfs_refcountbt_init_cursor(
346 	struct xfs_mount	*mp,
347 	struct xfs_trans	*tp,
348 	struct xfs_buf		*agbp,
349 	struct xfs_perag	*pag)
350 {
351 	struct xfs_agf		*agf = agbp->b_addr;
352 	struct xfs_btree_cur	*cur;
353 
354 	cur = xfs_refcountbt_init_common(mp, tp, pag);
355 	cur->bc_nlevels = be32_to_cpu(agf->agf_refcount_level);
356 	cur->bc_ag.agbp = agbp;
357 	return cur;
358 }
359 
360 /* Create a btree cursor with a fake root for staging. */
361 struct xfs_btree_cur *
362 xfs_refcountbt_stage_cursor(
363 	struct xfs_mount	*mp,
364 	struct xbtree_afakeroot	*afake,
365 	struct xfs_perag	*pag)
366 {
367 	struct xfs_btree_cur	*cur;
368 
369 	cur = xfs_refcountbt_init_common(mp, NULL, pag);
370 	xfs_btree_stage_afakeroot(cur, afake);
371 	return cur;
372 }
373 
374 /*
375  * Swap in the new btree root.  Once we pass this point the newly rebuilt btree
376  * is in place and we have to kill off all the old btree blocks.
377  */
378 void
379 xfs_refcountbt_commit_staged_btree(
380 	struct xfs_btree_cur	*cur,
381 	struct xfs_trans	*tp,
382 	struct xfs_buf		*agbp)
383 {
384 	struct xfs_agf		*agf = agbp->b_addr;
385 	struct xbtree_afakeroot	*afake = cur->bc_ag.afake;
386 
387 	ASSERT(cur->bc_flags & XFS_BTREE_STAGING);
388 
389 	agf->agf_refcount_root = cpu_to_be32(afake->af_root);
390 	agf->agf_refcount_level = cpu_to_be32(afake->af_levels);
391 	agf->agf_refcount_blocks = cpu_to_be32(afake->af_blocks);
392 	xfs_alloc_log_agf(tp, agbp, XFS_AGF_REFCOUNT_BLOCKS |
393 				    XFS_AGF_REFCOUNT_ROOT |
394 				    XFS_AGF_REFCOUNT_LEVEL);
395 	xfs_btree_commit_afakeroot(cur, tp, agbp, &xfs_refcountbt_ops);
396 }
397 
398 /* Calculate number of records in a refcount btree block. */
399 static inline unsigned int
400 xfs_refcountbt_block_maxrecs(
401 	unsigned int		blocklen,
402 	bool			leaf)
403 {
404 	if (leaf)
405 		return blocklen / sizeof(struct xfs_refcount_rec);
406 	return blocklen / (sizeof(struct xfs_refcount_key) +
407 			   sizeof(xfs_refcount_ptr_t));
408 }
409 
410 /*
411  * Calculate the number of records in a refcount btree block.
412  */
413 int
414 xfs_refcountbt_maxrecs(
415 	int			blocklen,
416 	bool			leaf)
417 {
418 	blocklen -= XFS_REFCOUNT_BLOCK_LEN;
419 	return xfs_refcountbt_block_maxrecs(blocklen, leaf);
420 }
421 
422 /* Compute the max possible height of the maximally sized refcount btree. */
423 unsigned int
424 xfs_refcountbt_maxlevels_ondisk(void)
425 {
426 	unsigned int		minrecs[2];
427 	unsigned int		blocklen;
428 
429 	blocklen = XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN;
430 
431 	minrecs[0] = xfs_refcountbt_block_maxrecs(blocklen, true) / 2;
432 	minrecs[1] = xfs_refcountbt_block_maxrecs(blocklen, false) / 2;
433 
434 	return xfs_btree_compute_maxlevels(minrecs, XFS_MAX_CRC_AG_BLOCKS);
435 }
436 
437 /* Compute the maximum height of a refcount btree. */
438 void
439 xfs_refcountbt_compute_maxlevels(
440 	struct xfs_mount		*mp)
441 {
442 	if (!xfs_has_reflink(mp)) {
443 		mp->m_refc_maxlevels = 0;
444 		return;
445 	}
446 
447 	mp->m_refc_maxlevels = xfs_btree_compute_maxlevels(
448 			mp->m_refc_mnr, mp->m_sb.sb_agblocks);
449 	ASSERT(mp->m_refc_maxlevels <= xfs_refcountbt_maxlevels_ondisk());
450 }
451 
452 /* Calculate the refcount btree size for some records. */
453 xfs_extlen_t
454 xfs_refcountbt_calc_size(
455 	struct xfs_mount	*mp,
456 	unsigned long long	len)
457 {
458 	return xfs_btree_calc_size(mp->m_refc_mnr, len);
459 }
460 
461 /*
462  * Calculate the maximum refcount btree size.
463  */
464 xfs_extlen_t
465 xfs_refcountbt_max_size(
466 	struct xfs_mount	*mp,
467 	xfs_agblock_t		agblocks)
468 {
469 	/* Bail out if we're uninitialized, which can happen in mkfs. */
470 	if (mp->m_refc_mxr[0] == 0)
471 		return 0;
472 
473 	return xfs_refcountbt_calc_size(mp, agblocks);
474 }
475 
476 /*
477  * Figure out how many blocks to reserve and how many are used by this btree.
478  */
479 int
480 xfs_refcountbt_calc_reserves(
481 	struct xfs_mount	*mp,
482 	struct xfs_trans	*tp,
483 	struct xfs_perag	*pag,
484 	xfs_extlen_t		*ask,
485 	xfs_extlen_t		*used)
486 {
487 	struct xfs_buf		*agbp;
488 	struct xfs_agf		*agf;
489 	xfs_agblock_t		agblocks;
490 	xfs_extlen_t		tree_len;
491 	int			error;
492 
493 	if (!xfs_has_reflink(mp))
494 		return 0;
495 
496 	error = xfs_alloc_read_agf(pag, tp, 0, &agbp);
497 	if (error)
498 		return error;
499 
500 	agf = agbp->b_addr;
501 	agblocks = be32_to_cpu(agf->agf_length);
502 	tree_len = be32_to_cpu(agf->agf_refcount_blocks);
503 	xfs_trans_brelse(tp, agbp);
504 
505 	/*
506 	 * The log is permanently allocated, so the space it occupies will
507 	 * never be available for the kinds of things that would require btree
508 	 * expansion.  We therefore can pretend the space isn't there.
509 	 */
510 	if (xfs_ag_contains_log(mp, pag->pag_agno))
511 		agblocks -= mp->m_sb.sb_logblocks;
512 
513 	*ask += xfs_refcountbt_max_size(mp, agblocks);
514 	*used += tree_len;
515 
516 	return error;
517 }
518 
519 int __init
520 xfs_refcountbt_init_cur_cache(void)
521 {
522 	xfs_refcountbt_cur_cache = kmem_cache_create("xfs_refcbt_cur",
523 			xfs_btree_cur_sizeof(xfs_refcountbt_maxlevels_ondisk()),
524 			0, 0, NULL);
525 
526 	if (!xfs_refcountbt_cur_cache)
527 		return -ENOMEM;
528 	return 0;
529 }
530 
531 void
532 xfs_refcountbt_destroy_cur_cache(void)
533 {
534 	kmem_cache_destroy(xfs_refcountbt_cur_cache);
535 	xfs_refcountbt_cur_cache = NULL;
536 }
537