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