[linux-block.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_refcount.h"
#include "xfs_alloc.h"
#include "xfs_error.h"
#include "xfs_health.h"
#include "xfs_trace.h"
#include "xfs_trans.h"
#include "xfs_bit.h"
#include "xfs_rmap.h"
#include "xfs_ag.h"

static struct kmem_cache	*xfs_refcountbt_cur_cache;

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, to_perag(cur->bc_group));
}

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.pag = to_perag(cur->bc_group);
	args.oinfo = XFS_RMAP_OINFO_REFC;
	args.minlen = args.maxlen = args.prod = 1;
	args.resv = XFS_AG_RESV_METADATA;

	error = xfs_alloc_vextent_near_bno(&args,
			xfs_agbno_to_fsb(args.pag, xfs_refc_block(args.mp)));
	if (error)
		goto out_error;
	if (args.fsbno == NULLFSBLOCK) {
		*stat = 0;
		return 0;
	}
	ASSERT(args.agno == cur->bc_group->xg_gno);
	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));

	be32_add_cpu(&agf->agf_refcount_blocks, -1);
	xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_REFCOUNT_BLOCKS);
	return xfs_free_extent_later(cur->bc_tp, fsbno, 1,
			&XFS_RMAP_OINFO_REFC, XFS_AG_RESV_METADATA, 0);
}

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)
{
	const struct xfs_refcount_irec *irec = &cur->bc_rec.rc;
	uint32_t		start;

	start = xfs_refcount_encode_startblock(irec->rc_startblock,
			irec->rc_domain);
	rec->refc.rc_startblock = cpu_to_be32(start);
	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_group->xg_gno == 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)
{
	const struct xfs_refcount_key	*kp = &key->refc;
	const struct xfs_refcount_irec	*irec = &cur->bc_rec.rc;
	uint32_t			start;

	start = xfs_refcount_encode_startblock(irec->rc_startblock,
			irec->rc_domain);
	return (int64_t)be32_to_cpu(kp->rc_startblock) - start;
}

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,
	const union xfs_btree_key	*mask)
{
	ASSERT(!mask || mask->refc.rc_startblock);

	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_agblock_v5hdr_verify(bp);
	if (fa)
		return fa;

	level = be16_to_cpu(block->bb_level);
	if (pag && xfs_perag_initialised_agf(pag)) {
		unsigned int	maxlevel = pag->pagf_refcount_level;

#ifdef CONFIG_XFS_ONLINE_REPAIR
		/*
		 * Online repair could be rewriting the refcount btree, so
		 * we'll validate against the larger of either tree while this
		 * is going on.
		 */
		maxlevel = max_t(unsigned int, maxlevel,
				pag->pagf_repair_refcount_level);
#endif
		if (level >= maxlevel)
			return __this_address;
	} else if (level >= mp->m_refc_maxlevels)
		return __this_address;

	return xfs_btree_agblock_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_agblock_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_agblock_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 enum xbtree_key_contig
xfs_refcountbt_keys_contiguous(
	struct xfs_btree_cur		*cur,
	const union xfs_btree_key	*key1,
	const union xfs_btree_key	*key2,
	const union xfs_btree_key	*mask)
{
	ASSERT(!mask || mask->refc.rc_startblock);

	return xbtree_key_contig(be32_to_cpu(key1->refc.rc_startblock),
				 be32_to_cpu(key2->refc.rc_startblock));
}

const struct xfs_btree_ops xfs_refcountbt_ops = {
	.name			= "refcount",
	.type			= XFS_BTREE_TYPE_AG,

	.rec_len		= sizeof(struct xfs_refcount_rec),
	.key_len		= sizeof(struct xfs_refcount_key),
	.ptr_len		= XFS_BTREE_SHORT_PTR_LEN,

	.lru_refs		= XFS_REFC_BTREE_REF,
	.statoff		= XFS_STATS_CALC_INDEX(xs_refcbt_2),
	.sick_mask		= XFS_SICK_AG_REFCNTBT,

	.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,
	.keys_contiguous	= xfs_refcountbt_keys_contiguous,
};

/*
 * Create a new refcount btree cursor.
 *
 * For staging cursors tp and agbp are NULL.
 */
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_btree_cur	*cur;

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

	cur = xfs_btree_alloc_cursor(mp, tp, &xfs_refcountbt_ops,
			mp->m_refc_maxlevels, xfs_refcountbt_cur_cache);
	cur->bc_group = xfs_group_hold(pag_group(pag));
	cur->bc_refc.nr_ops = 0;
	cur->bc_refc.shape_changes = 0;
	cur->bc_ag.agbp = agbp;
	if (agbp) {
		struct xfs_agf		*agf = agbp->b_addr;

		cur->bc_nlevels = be32_to_cpu(agf->agf_refcount_level);
	}
	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);
}

/* Calculate number of records in a refcount btree block. */
static inline unsigned int
xfs_refcountbt_block_maxrecs(
	unsigned int		blocklen,
	bool			leaf)
{
	if (leaf)
		return blocklen / sizeof(struct xfs_refcount_rec);
	return blocklen / (sizeof(struct xfs_refcount_key) +
			   sizeof(xfs_refcount_ptr_t));
}

/*
 * Calculate the number of records in a refcount btree block.
 */
unsigned int
xfs_refcountbt_maxrecs(
	struct xfs_mount	*mp,
	unsigned int		blocklen,
	bool			leaf)
{
	blocklen -= XFS_REFCOUNT_BLOCK_LEN;
	return xfs_refcountbt_block_maxrecs(blocklen, leaf);
}

/* Compute the max possible height of the maximally sized refcount btree. */
unsigned int
xfs_refcountbt_maxlevels_ondisk(void)
{
	unsigned int		minrecs[2];
	unsigned int		blocklen;

	blocklen = XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN;

	minrecs[0] = xfs_refcountbt_block_maxrecs(blocklen, true) / 2;
	minrecs[1] = xfs_refcountbt_block_maxrecs(blocklen, false) / 2;

	return xfs_btree_compute_maxlevels(minrecs, XFS_MAX_CRC_AG_BLOCKS);
}

/* Compute the maximum height of a refcount btree. */
void
xfs_refcountbt_compute_maxlevels(
	struct xfs_mount		*mp)
{
	if (!xfs_has_reflink(mp)) {
		mp->m_refc_maxlevels = 0;
		return;
	}

	mp->m_refc_maxlevels = xfs_btree_compute_maxlevels(
			mp->m_refc_mnr, mp->m_sb.sb_agblocks);
	ASSERT(mp->m_refc_maxlevels <= xfs_refcountbt_maxlevels_ondisk());
}

/* 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(pag, tp, 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 (xfs_ag_contains_log(mp, pag_agno(pag)))
		agblocks -= mp->m_sb.sb_logblocks;

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

	return error;
}

int __init
xfs_refcountbt_init_cur_cache(void)
{
	xfs_refcountbt_cur_cache = kmem_cache_create("xfs_refcbt_cur",
			xfs_btree_cur_sizeof(xfs_refcountbt_maxlevels_ondisk()),
			0, 0, NULL);

	if (!xfs_refcountbt_cur_cache)
		return -ENOMEM;
	return 0;
}

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