[thirdparty/xfsprogs-dev.git] / libxfs / xfs_refcount_btree.c

// SPDX-License-Identifier: GPL-2.0+
/*
 * Copyright (C) 2016 Oracle.  All Rights Reserved.
 * Author: Darrick J. Wong <darrick.wong@oracle.com>
 */
#include "libxfs_priv.h"
#include "xfs_fs.h"
#include "xfs_shared.h"
#include "xfs_format.h"
#include "xfs_log_format.h"
#include "xfs_trans_resv.h"
#include "xfs_mount.h"
#include "xfs_btree.h"
#include "xfs_btree_staging.h"
#include "xfs_refcount_btree.h"
#include "xfs_alloc.h"
#include "xfs_trace.h"
#include "xfs_trans.h"
#include "xfs_bit.h"
#include "xfs_rmap.h"
#include "xfs_ag.h"

static struct xfs_btree_cur *
xfs_refcountbt_dup_cursor(
	struct xfs_btree_cur	*cur)
{
	return xfs_refcountbt_init_cursor(cur->bc_mp, cur->bc_tp,
			cur->bc_ag.agbp, cur->bc_ag.pag);
}

STATIC void
xfs_refcountbt_set_root(
	struct xfs_btree_cur		*cur,
	const union xfs_btree_ptr	*ptr,
	int				inc)
{
	struct xfs_buf		*agbp = cur->bc_ag.agbp;
	struct xfs_agf		*agf = agbp->b_addr;
	struct xfs_perag	*pag = agbp->b_pag;

	ASSERT(ptr->s != 0);

	agf->agf_refcount_root = ptr->s;
	be32_add_cpu(&agf->agf_refcount_level, inc);
	pag->pagf_refcount_level += inc;

	xfs_alloc_log_agf(cur->bc_tp, agbp,
			XFS_AGF_REFCOUNT_ROOT | XFS_AGF_REFCOUNT_LEVEL);
}

STATIC int
xfs_refcountbt_alloc_block(
	struct xfs_btree_cur		*cur,
	const union xfs_btree_ptr	*start,
	union xfs_btree_ptr		*new,
	int				*stat)
{
	struct xfs_buf		*agbp = cur->bc_ag.agbp;
	struct xfs_agf		*agf = agbp->b_addr;
	struct xfs_alloc_arg	args;		/* block allocation args */
	int			error;		/* error return value */

	memset(&args, 0, sizeof(args));
	args.tp = cur->bc_tp;
	args.mp = cur->bc_mp;
	args.type = XFS_ALLOCTYPE_NEAR_BNO;
	args.fsbno = XFS_AGB_TO_FSB(cur->bc_mp, cur->bc_ag.pag->pag_agno,
			xfs_refc_block(args.mp));
	args.oinfo = XFS_RMAP_OINFO_REFC;
	args.minlen = args.maxlen = args.prod = 1;
	args.resv = XFS_AG_RESV_METADATA;

	error = xfs_alloc_vextent(&args);
	if (error)
		goto out_error;
	trace_xfs_refcountbt_alloc_block(cur->bc_mp, cur->bc_ag.pag->pag_agno,
			args.agbno, 1);
	if (args.fsbno == NULLFSBLOCK) {
		*stat = 0;
		return 0;
	}
	ASSERT(args.agno == cur->bc_ag.pag->pag_agno);
	ASSERT(args.len == 1);

	new->s = cpu_to_be32(args.agbno);
	be32_add_cpu(&agf->agf_refcount_blocks, 1);
	xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_REFCOUNT_BLOCKS);

	*stat = 1;
	return 0;

out_error:
	return error;
}

STATIC int
xfs_refcountbt_free_block(
	struct xfs_btree_cur	*cur,
	struct xfs_buf		*bp)
{
	struct xfs_mount	*mp = cur->bc_mp;
	struct xfs_buf		*agbp = cur->bc_ag.agbp;
	struct xfs_agf		*agf = agbp->b_addr;
	xfs_fsblock_t		fsbno = XFS_DADDR_TO_FSB(mp, xfs_buf_daddr(bp));
	int			error;

	trace_xfs_refcountbt_free_block(cur->bc_mp, cur->bc_ag.pag->pag_agno,
			XFS_FSB_TO_AGBNO(cur->bc_mp, fsbno), 1);
	be32_add_cpu(&agf->agf_refcount_blocks, -1);
	xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_REFCOUNT_BLOCKS);
	error = xfs_free_extent(cur->bc_tp, fsbno, 1, &XFS_RMAP_OINFO_REFC,
			XFS_AG_RESV_METADATA);
	if (error)
		return error;

	return error;
}

STATIC int
xfs_refcountbt_get_minrecs(
	struct xfs_btree_cur	*cur,
	int			level)
{
	return cur->bc_mp->m_refc_mnr[level != 0];
}

STATIC int
xfs_refcountbt_get_maxrecs(
	struct xfs_btree_cur	*cur,
	int			level)
{
	return cur->bc_mp->m_refc_mxr[level != 0];
}

STATIC void
xfs_refcountbt_init_key_from_rec(
	union xfs_btree_key		*key,
	const union xfs_btree_rec	*rec)
{
	key->refc.rc_startblock = rec->refc.rc_startblock;
}

STATIC void
xfs_refcountbt_init_high_key_from_rec(
	union xfs_btree_key		*key,
	const union xfs_btree_rec	*rec)
{
	__u32				x;

	x = be32_to_cpu(rec->refc.rc_startblock);
	x += be32_to_cpu(rec->refc.rc_blockcount) - 1;
	key->refc.rc_startblock = cpu_to_be32(x);
}

STATIC void
xfs_refcountbt_init_rec_from_cur(
	struct xfs_btree_cur	*cur,
	union xfs_btree_rec	*rec)
{
	rec->refc.rc_startblock = cpu_to_be32(cur->bc_rec.rc.rc_startblock);
	rec->refc.rc_blockcount = cpu_to_be32(cur->bc_rec.rc.rc_blockcount);
	rec->refc.rc_refcount = cpu_to_be32(cur->bc_rec.rc.rc_refcount);
}

STATIC void
xfs_refcountbt_init_ptr_from_cur(
	struct xfs_btree_cur	*cur,
	union xfs_btree_ptr	*ptr)
{
	struct xfs_agf		*agf = cur->bc_ag.agbp->b_addr;

	ASSERT(cur->bc_ag.pag->pag_agno == be32_to_cpu(agf->agf_seqno));

	ptr->s = agf->agf_refcount_root;
}

STATIC int64_t
xfs_refcountbt_key_diff(
	struct xfs_btree_cur		*cur,
	const union xfs_btree_key	*key)
{
	struct xfs_refcount_irec	*rec = &cur->bc_rec.rc;
	const struct xfs_refcount_key	*kp = &key->refc;

	return (int64_t)be32_to_cpu(kp->rc_startblock) - rec->rc_startblock;
}

STATIC int64_t
xfs_refcountbt_diff_two_keys(
	struct xfs_btree_cur		*cur,
	const union xfs_btree_key	*k1,
	const union xfs_btree_key	*k2)
{
	return (int64_t)be32_to_cpu(k1->refc.rc_startblock) -
			  be32_to_cpu(k2->refc.rc_startblock);
}

STATIC xfs_failaddr_t
xfs_refcountbt_verify(
	struct xfs_buf		*bp)
{
	struct xfs_mount	*mp = bp->b_mount;
	struct xfs_btree_block	*block = XFS_BUF_TO_BLOCK(bp);
	struct xfs_perag	*pag = bp->b_pag;
	xfs_failaddr_t		fa;
	unsigned int		level;

	if (!xfs_verify_magic(bp, block->bb_magic))
		return __this_address;

	if (!xfs_has_reflink(mp))
		return __this_address;
	fa = xfs_btree_sblock_v5hdr_verify(bp);
	if (fa)
		return fa;

	level = be16_to_cpu(block->bb_level);
	if (pag && pag->pagf_init) {
		if (level >= pag->pagf_refcount_level)
			return __this_address;
	} else if (level >= mp->m_refc_maxlevels)
		return __this_address;

	return xfs_btree_sblock_verify(bp, mp->m_refc_mxr[level != 0]);
}

STATIC void
xfs_refcountbt_read_verify(
	struct xfs_buf	*bp)
{
	xfs_failaddr_t	fa;

	if (!xfs_btree_sblock_verify_crc(bp))
		xfs_verifier_error(bp, -EFSBADCRC, __this_address);
	else {
		fa = xfs_refcountbt_verify(bp);
		if (fa)
			xfs_verifier_error(bp, -EFSCORRUPTED, fa);
	}

	if (bp->b_error)
		trace_xfs_btree_corrupt(bp, _RET_IP_);
}

STATIC void
xfs_refcountbt_write_verify(
	struct xfs_buf	*bp)
{
	xfs_failaddr_t	fa;

	fa = xfs_refcountbt_verify(bp);
	if (fa) {
		trace_xfs_btree_corrupt(bp, _RET_IP_);
		xfs_verifier_error(bp, -EFSCORRUPTED, fa);
		return;
	}
	xfs_btree_sblock_calc_crc(bp);

}

const struct xfs_buf_ops xfs_refcountbt_buf_ops = {
	.name			= "xfs_refcountbt",
	.magic			= { 0, cpu_to_be32(XFS_REFC_CRC_MAGIC) },
	.verify_read		= xfs_refcountbt_read_verify,
	.verify_write		= xfs_refcountbt_write_verify,
	.verify_struct		= xfs_refcountbt_verify,
};

STATIC int
xfs_refcountbt_keys_inorder(
	struct xfs_btree_cur		*cur,
	const union xfs_btree_key	*k1,
	const union xfs_btree_key	*k2)
{
	return be32_to_cpu(k1->refc.rc_startblock) <
	       be32_to_cpu(k2->refc.rc_startblock);
}

STATIC int
xfs_refcountbt_recs_inorder(
	struct xfs_btree_cur		*cur,
	const union xfs_btree_rec	*r1,
	const union xfs_btree_rec	*r2)
{
	return  be32_to_cpu(r1->refc.rc_startblock) +
		be32_to_cpu(r1->refc.rc_blockcount) <=
		be32_to_cpu(r2->refc.rc_startblock);
}

static const struct xfs_btree_ops xfs_refcountbt_ops = {
	.rec_len		= sizeof(struct xfs_refcount_rec),
	.key_len		= sizeof(struct xfs_refcount_key),

	.dup_cursor		= xfs_refcountbt_dup_cursor,
	.set_root		= xfs_refcountbt_set_root,
	.alloc_block		= xfs_refcountbt_alloc_block,
	.free_block		= xfs_refcountbt_free_block,
	.get_minrecs		= xfs_refcountbt_get_minrecs,
	.get_maxrecs		= xfs_refcountbt_get_maxrecs,
	.init_key_from_rec	= xfs_refcountbt_init_key_from_rec,
	.init_high_key_from_rec	= xfs_refcountbt_init_high_key_from_rec,
	.init_rec_from_cur	= xfs_refcountbt_init_rec_from_cur,
	.init_ptr_from_cur	= xfs_refcountbt_init_ptr_from_cur,
	.key_diff		= xfs_refcountbt_key_diff,
	.buf_ops		= &xfs_refcountbt_buf_ops,
	.diff_two_keys		= xfs_refcountbt_diff_two_keys,
	.keys_inorder		= xfs_refcountbt_keys_inorder,
	.recs_inorder		= xfs_refcountbt_recs_inorder,
};

/*
 * Initialize a new refcount btree cursor.
 */
static struct xfs_btree_cur *
xfs_refcountbt_init_common(
	struct xfs_mount	*mp,
	struct xfs_trans	*tp,
	struct xfs_perag	*pag)
{
	struct xfs_btree_cur	*cur;

	ASSERT(pag->pag_agno < mp->m_sb.sb_agcount);

	cur = xfs_btree_alloc_cursor(mp, tp, XFS_BTNUM_REFC);
	cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_refcbt_2);

	cur->bc_flags |= XFS_BTREE_CRC_BLOCKS;

	/* take a reference for the cursor */
	atomic_inc(&pag->pag_ref);
	cur->bc_ag.pag = pag;

	cur->bc_ag.refc.nr_ops = 0;
	cur->bc_ag.refc.shape_changes = 0;
	cur->bc_ops = &xfs_refcountbt_ops;
	return cur;
}

/* Create a btree cursor. */
struct xfs_btree_cur *
xfs_refcountbt_init_cursor(
	struct xfs_mount	*mp,
	struct xfs_trans	*tp,
	struct xfs_buf		*agbp,
	struct xfs_perag	*pag)
{
	struct xfs_agf		*agf = agbp->b_addr;
	struct xfs_btree_cur	*cur;

	cur = xfs_refcountbt_init_common(mp, tp, pag);
	cur->bc_nlevels = be32_to_cpu(agf->agf_refcount_level);
	cur->bc_ag.agbp = agbp;
	return cur;
}

/* Create a btree cursor with a fake root for staging. */
struct xfs_btree_cur *
xfs_refcountbt_stage_cursor(
	struct xfs_mount	*mp,
	struct xbtree_afakeroot	*afake,
	struct xfs_perag	*pag)
{
	struct xfs_btree_cur	*cur;

	cur = xfs_refcountbt_init_common(mp, NULL, pag);
	xfs_btree_stage_afakeroot(cur, afake);
	return cur;
}

/*
 * Swap in the new btree root.  Once we pass this point the newly rebuilt btree
 * is in place and we have to kill off all the old btree blocks.
 */
void
xfs_refcountbt_commit_staged_btree(
	struct xfs_btree_cur	*cur,
	struct xfs_trans	*tp,
	struct xfs_buf		*agbp)
{
	struct xfs_agf		*agf = agbp->b_addr;
	struct xbtree_afakeroot	*afake = cur->bc_ag.afake;

	ASSERT(cur->bc_flags & XFS_BTREE_STAGING);

	agf->agf_refcount_root = cpu_to_be32(afake->af_root);
	agf->agf_refcount_level = cpu_to_be32(afake->af_levels);
	agf->agf_refcount_blocks = cpu_to_be32(afake->af_blocks);
	xfs_alloc_log_agf(tp, agbp, XFS_AGF_REFCOUNT_BLOCKS |
				    XFS_AGF_REFCOUNT_ROOT |
				    XFS_AGF_REFCOUNT_LEVEL);
	xfs_btree_commit_afakeroot(cur, tp, agbp, &xfs_refcountbt_ops);
}

/*
 * Calculate the number of records in a refcount btree block.
 */
int
xfs_refcountbt_maxrecs(
	int			blocklen,
	bool			leaf)
{
	blocklen -= XFS_REFCOUNT_BLOCK_LEN;

	if (leaf)
		return blocklen / sizeof(struct xfs_refcount_rec);
	return blocklen / (sizeof(struct xfs_refcount_key) +
			   sizeof(xfs_refcount_ptr_t));
}

/* Compute the maximum height of a refcount btree. */
void
xfs_refcountbt_compute_maxlevels(
	struct xfs_mount		*mp)
{
	mp->m_refc_maxlevels = xfs_btree_compute_maxlevels(
			mp->m_refc_mnr, mp->m_sb.sb_agblocks);
}

/* Calculate the refcount btree size for some records. */
xfs_extlen_t
xfs_refcountbt_calc_size(
	struct xfs_mount	*mp,
	unsigned long long	len)
{
	return xfs_btree_calc_size(mp->m_refc_mnr, len);
}

/*
 * Calculate the maximum refcount btree size.
 */
xfs_extlen_t
xfs_refcountbt_max_size(
	struct xfs_mount	*mp,
	xfs_agblock_t		agblocks)
{
	/* Bail out if we're uninitialized, which can happen in mkfs. */
	if (mp->m_refc_mxr[0] == 0)
		return 0;

	return xfs_refcountbt_calc_size(mp, agblocks);
}

/*
 * Figure out how many blocks to reserve and how many are used by this btree.
 */
int
xfs_refcountbt_calc_reserves(
	struct xfs_mount	*mp,
	struct xfs_trans	*tp,
	struct xfs_perag	*pag,
	xfs_extlen_t		*ask,
	xfs_extlen_t		*used)
{
	struct xfs_buf		*agbp;
	struct xfs_agf		*agf;
	xfs_agblock_t		agblocks;
	xfs_extlen_t		tree_len;
	int			error;

	if (!xfs_has_reflink(mp))
		return 0;

	error = xfs_alloc_read_agf(mp, tp, pag->pag_agno, 0, &agbp);
	if (error)
		return error;

	agf = agbp->b_addr;
	agblocks = be32_to_cpu(agf->agf_length);
	tree_len = be32_to_cpu(agf->agf_refcount_blocks);
	xfs_trans_brelse(tp, agbp);

	/*
	 * The log is permanently allocated, so the space it occupies will
	 * never be available for the kinds of things that would require btree
	 * expansion.  We therefore can pretend the space isn't there.
	 */
	if (mp->m_sb.sb_logstart &&
	    XFS_FSB_TO_AGNO(mp, mp->m_sb.sb_logstart) == pag->pag_agno)
		agblocks -= mp->m_sb.sb_logblocks;

	*ask += xfs_refcountbt_max_size(mp, agblocks);
	*used += tree_len;

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