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