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