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