[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, 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.pag = cur->bc_ag.pag;
	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_AGB_TO_FSB(args.mp, args.pag->pag_agno,
					xfs_refc_block(args.mp)));
	if (error)
		goto out_error;
	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));

	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, false);
}

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_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)
{
	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->pag_agno < 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_ag.pag = xfs_perag_hold(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.
 */
int
xfs_refcountbt_maxrecs(
	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->pag_agno))
		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,
a81a0621	33	cur->bc_ag.agbp, cur->bc_ag.pag);
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;
74c36a86	71	args.pag = cur->bc_ag.pag;
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 DC	76	error = xfs_alloc_vextent_near_bno(&args,
	77	XFS_AGB_TO_FSB(args.mp, args.pag->pag_agno,
	78	xfs_refc_block(args.mp)));
bdf28630 DW	79	if (error)
bdf28630 DW	80	goto out_error;
bdf28630	81	if (args.fsbno == NULLFSBLOCK) {
bdf28630 DW	82	*stat = 0;
	83	return 0;
	84	}
50f02fe3	85	ASSERT(args.agno == cur->bc_ag.pag->pag_agno);
bdf28630 DW	86	ASSERT(args.len == 1);
	87
	88	new->s = cpu_to_be32(args.agbno);
	89	be32_add_cpu(&agf->agf_refcount_blocks, 1);
	90	xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_REFCOUNT_BLOCKS);
	91
bdf28630 DW	92	*stat = 1;
	93	return 0;
	94
	95	out_error:
bdf28630 DW	96	return error;
	97	}
	98
	99	STATIC int
	100	xfs_refcountbt_free_block(
	101	struct xfs_btree_cur *cur,
	102	struct xfs_buf *bp)
	103	{
	104	struct xfs_mount *mp = cur->bc_mp;
576af732	105	struct xfs_buf *agbp = cur->bc_ag.agbp;
9798f615	106	struct xfs_agf *agf = agbp->b_addr;
04fcad80	107	xfs_fsblock_t fsbno = XFS_DADDR_TO_FSB(mp, xfs_buf_daddr(bp));
bdf28630	108
bdf28630 DW	109	be32_add_cpu(&agf->agf_refcount_blocks, -1);
bdf28630 DW	110	xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_REFCOUNT_BLOCKS);
b742d7b4	111	return xfs_free_extent_later(cur->bc_tp, fsbno, 1,
4c88fef3	112	&XFS_RMAP_OINFO_REFC, XFS_AG_RESV_METADATA, false);
bdf28630 DW	113	}
	114
	115	STATIC int
	116	xfs_refcountbt_get_minrecs(
	117	struct xfs_btree_cur *cur,
	118	int level)
	119	{
	120	return cur->bc_mp->m_refc_mnr[level != 0];
	121	}
	122
	123	STATIC int
	124	xfs_refcountbt_get_maxrecs(
	125	struct xfs_btree_cur *cur,
	126	int level)
	127	{
	128	return cur->bc_mp->m_refc_mxr[level != 0];
	129	}
	130
	131	STATIC void
	132	xfs_refcountbt_init_key_from_rec(
23825cd1 DW	133	union xfs_btree_key *key,
23825cd1 DW	134	const union xfs_btree_rec *rec)
bdf28630 DW	135	{
	136	key->refc.rc_startblock = rec->refc.rc_startblock;
	137	}
	138
	139	STATIC void
	140	xfs_refcountbt_init_high_key_from_rec(
23825cd1 DW	141	union xfs_btree_key *key,
23825cd1 DW	142	const union xfs_btree_rec *rec)
bdf28630	143	{
23825cd1	144	__u32 x;
bdf28630 DW	145
	146	x = be32_to_cpu(rec->refc.rc_startblock);
	147	x += be32_to_cpu(rec->refc.rc_blockcount) - 1;
	148	key->refc.rc_startblock = cpu_to_be32(x);
	149	}
	150
	151	STATIC void
	152	xfs_refcountbt_init_rec_from_cur(
	153	struct xfs_btree_cur *cur,
	154	union xfs_btree_rec *rec)
	155	{
9a50ee4f DW	156	const struct xfs_refcount_irec *irec = &cur->bc_rec.rc;
	157	uint32_t start;
	158
	159	start = xfs_refcount_encode_startblock(irec->rc_startblock,
	160	irec->rc_domain);
	161	rec->refc.rc_startblock = cpu_to_be32(start);
bdf28630 DW	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	182	{
d29d5577	183	const struct xfs_refcount_key *kp = &key->refc;
9a50ee4f DW	184	const struct xfs_refcount_irec *irec = &cur->bc_rec.rc;
9a50ee4f DW	185	uint32_t start;
bdf28630	186
9a50ee4f DW	187	start = xfs_refcount_encode_startblock(irec->rc_startblock,
	188	irec->rc_domain);
	189	return (int64_t)be32_to_cpu(kp->rc_startblock) - start;
bdf28630 DW	190	}
bdf28630 DW	191
c8ce540d	192	STATIC int64_t
bdf28630	193	xfs_refcountbt_diff_two_keys(
d29d5577 DW	194	struct xfs_btree_cur *cur,
d29d5577 DW	195	const union xfs_btree_key *k1,
4a200a09 DW	196	const union xfs_btree_key *k2,
4a200a09 DW	197	const union xfs_btree_key *mask)
bdf28630	198	{
4a200a09 DW	199	ASSERT(!mask \|\| mask->refc.rc_startblock);
4a200a09 DW	200
c8ce540d	201	return (int64_t)be32_to_cpu(k1->refc.rc_startblock) -
4a200a09	202	be32_to_cpu(k2->refc.rc_startblock);
bdf28630 DW	203	}
bdf28630 DW	204
a6a781a5	205	STATIC xfs_failaddr_t
1946b91c DW	206	xfs_refcountbt_verify(
	207	struct xfs_buf *bp)
	208	{
dbd329f1	209	struct xfs_mount *mp = bp->b_mount;
1946b91c DW	210	struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
1946b91c DW	211	struct xfs_perag *pag = bp->b_pag;
a6a781a5	212	xfs_failaddr_t fa;
1946b91c DW	213	unsigned int level;
1946b91c DW	214
39708c20	215	if (!xfs_verify_magic(bp, block->bb_magic))
a6a781a5	216	return __this_address;
1946b91c	217
38c26bfd	218	if (!xfs_has_reflink(mp))
a6a781a5	219	return __this_address;
5ef819c3	220	fa = xfs_btree_agblock_v5hdr_verify(bp);
a6a781a5 DW	221	if (fa)
a6a781a5 DW	222	return fa;
1946b91c DW	223
1946b91c DW	224	level = be16_to_cpu(block->bb_level);
7ac2ff8b	225	if (pag && xfs_perag_initialised_agf(pag)) {
9099cd38 DW	226	unsigned int maxlevel = pag->pagf_refcount_level;
	227
	228	#ifdef CONFIG_XFS_ONLINE_REPAIR
	229	/*
	230	* Online repair could be rewriting the refcount btree, so
	231	* we'll validate against the larger of either tree while this
	232	* is going on.
	233	*/
	234	maxlevel = max_t(unsigned int, maxlevel,
	235	pag->pagf_repair_refcount_level);
	236	#endif
	237	if (level >= maxlevel)
a6a781a5	238	return __this_address;
1946b91c	239	} else if (level >= mp->m_refc_maxlevels)
a6a781a5	240	return __this_address;
1946b91c	241
5ef819c3	242	return xfs_btree_agblock_verify(bp, mp->m_refc_mxr[level != 0]);
1946b91c DW	243	}
	244
	245	STATIC void
	246	xfs_refcountbt_read_verify(
	247	struct xfs_buf *bp)
	248	{
bc1a09b8 DW	249	xfs_failaddr_t fa;
bc1a09b8 DW	250
5ef819c3	251	if (!xfs_btree_agblock_verify_crc(bp))
bc1a09b8 DW	252	xfs_verifier_error(bp, -EFSBADCRC, __this_address);
	253	else {
	254	fa = xfs_refcountbt_verify(bp);
	255	if (fa)
	256	xfs_verifier_error(bp, -EFSCORRUPTED, fa);
	257	}
1946b91c	258
31ca03c9	259	if (bp->b_error)
1946b91c	260	trace_xfs_btree_corrupt(bp, _RET_IP_);
1946b91c DW	261	}
	262
	263	STATIC void
	264	xfs_refcountbt_write_verify(
	265	struct xfs_buf *bp)
	266	{
bc1a09b8 DW	267	xfs_failaddr_t fa;
	268
	269	fa = xfs_refcountbt_verify(bp);
	270	if (fa) {
1946b91c	271	trace_xfs_btree_corrupt(bp, _RET_IP_);
bc1a09b8	272	xfs_verifier_error(bp, -EFSCORRUPTED, fa);
1946b91c DW	273	return;
1946b91c DW	274	}
5ef819c3	275	xfs_btree_agblock_calc_crc(bp);
1946b91c DW	276
	277	}
	278
	279	const struct xfs_buf_ops xfs_refcountbt_buf_ops = {
	280	.name = "xfs_refcountbt",
39708c20	281	.magic = { 0, cpu_to_be32(XFS_REFC_CRC_MAGIC) },
1946b91c DW	282	.verify_read = xfs_refcountbt_read_verify,
1946b91c DW	283	.verify_write = xfs_refcountbt_write_verify,
b5572597	284	.verify_struct = xfs_refcountbt_verify,
1946b91c DW	285	};
1946b91c DW	286
bdf28630 DW	287	STATIC int
bdf28630 DW	288	xfs_refcountbt_keys_inorder(
8e38dc88 DW	289	struct xfs_btree_cur *cur,
	290	const union xfs_btree_key *k1,
	291	const union xfs_btree_key *k2)
bdf28630 DW	292	{
	293	return be32_to_cpu(k1->refc.rc_startblock) <
	294	be32_to_cpu(k2->refc.rc_startblock);
	295	}
	296
	297	STATIC int
	298	xfs_refcountbt_recs_inorder(
8e38dc88 DW	299	struct xfs_btree_cur *cur,
	300	const union xfs_btree_rec *r1,
	301	const union xfs_btree_rec *r2)
bdf28630 DW	302	{
	303	return be32_to_cpu(r1->refc.rc_startblock) +
	304	be32_to_cpu(r1->refc.rc_blockcount) <=
	305	be32_to_cpu(r2->refc.rc_startblock);
	306	}
bdf28630	307
6abc7aef DW	308	STATIC enum xbtree_key_contig
	309	xfs_refcountbt_keys_contiguous(
	310	struct xfs_btree_cur *cur,
	311	const union xfs_btree_key *key1,
4a200a09 DW	312	const union xfs_btree_key *key2,
4a200a09 DW	313	const union xfs_btree_key *mask)
6abc7aef	314	{
4a200a09 DW	315	ASSERT(!mask \|\| mask->refc.rc_startblock);
4a200a09 DW	316
6abc7aef DW	317	return xbtree_key_contig(be32_to_cpu(key1->refc.rc_startblock),
	318	be32_to_cpu(key2->refc.rc_startblock));
	319	}
	320
d8d6df42	321	const struct xfs_btree_ops xfs_refcountbt_ops = {
77953b97	322	.name = "refcount",
4f0cd5a5 CH	323	.type = XFS_BTREE_TYPE_AG,
4f0cd5a5 CH	324
1946b91c DW	325	.rec_len = sizeof(struct xfs_refcount_rec),
1946b91c DW	326	.key_len = sizeof(struct xfs_refcount_key),
1a9d2629	327	.ptr_len = XFS_BTREE_SHORT_PTR_LEN,
1946b91c	328
90cfae81	329	.lru_refs = XFS_REFC_BTREE_REF,
07b7f2e3	330	.statoff = XFS_STATS_CALC_INDEX(xs_refcbt_2),
7f47734a	331	.sick_mask = XFS_SICK_AG_REFCNTBT,
90cfae81	332
1946b91c	333	.dup_cursor = xfs_refcountbt_dup_cursor,
bdf28630 DW	334	.set_root = xfs_refcountbt_set_root,
	335	.alloc_block = xfs_refcountbt_alloc_block,
	336	.free_block = xfs_refcountbt_free_block,
	337	.get_minrecs = xfs_refcountbt_get_minrecs,
	338	.get_maxrecs = xfs_refcountbt_get_maxrecs,
	339	.init_key_from_rec = xfs_refcountbt_init_key_from_rec,
	340	.init_high_key_from_rec = xfs_refcountbt_init_high_key_from_rec,
	341	.init_rec_from_cur = xfs_refcountbt_init_rec_from_cur,
	342	.init_ptr_from_cur = xfs_refcountbt_init_ptr_from_cur,
	343	.key_diff = xfs_refcountbt_key_diff,
1946b91c	344	.buf_ops = &xfs_refcountbt_buf_ops,
bdf28630	345	.diff_two_keys = xfs_refcountbt_diff_two_keys,
bdf28630 DW	346	.keys_inorder = xfs_refcountbt_keys_inorder,
bdf28630 DW	347	.recs_inorder = xfs_refcountbt_recs_inorder,
6abc7aef	348	.keys_contiguous = xfs_refcountbt_keys_contiguous,
1946b91c DW	349	};
	350
	351	/*
4f2dc69e CH	352	* Create a new refcount btree cursor.
	353	*
	354	* For staging cursors tp and agbp are NULL.
1946b91c	355	*/
4f2dc69e CH	356	struct xfs_btree_cur *
4f2dc69e CH	357	xfs_refcountbt_init_cursor(
1946b91c DW	358	struct xfs_mount *mp,
1946b91c DW	359	struct xfs_trans *tp,
4f2dc69e	360	struct xfs_buf *agbp,
be9fb17d	361	struct xfs_perag *pag)
1946b91c	362	{
1946b91c DW	363	struct xfs_btree_cur *cur;
1946b91c DW	364
a81a0621	365	ASSERT(pag->pag_agno < mp->m_sb.sb_agcount);
1946b91c	366
ec793e69 CH	367	cur = xfs_btree_alloc_cursor(mp, tp, &xfs_refcountbt_ops,
ec793e69 CH	368	mp->m_refc_maxlevels, xfs_refcountbt_cur_cache);
9b2e5a23	369	cur->bc_ag.pag = xfs_perag_hold(pag);
88ee2f48 CH	370	cur->bc_refc.nr_ops = 0;
88ee2f48 CH	371	cur->bc_refc.shape_changes = 0;
56e98164	372	cur->bc_ag.agbp = agbp;
4f2dc69e CH	373	if (agbp) {
	374	struct xfs_agf *agf = agbp->b_addr;
	375
	376	cur->bc_nlevels = be32_to_cpu(agf->agf_refcount_level);
	377	}
56e98164 DW	378	return cur;
	379	}
	380
56e98164 DW	381	/*
	382	* Swap in the new btree root. Once we pass this point the newly rebuilt btree
	383	* is in place and we have to kill off all the old btree blocks.
	384	*/
	385	void
	386	xfs_refcountbt_commit_staged_btree(
	387	struct xfs_btree_cur *cur,
	388	struct xfs_trans *tp,
	389	struct xfs_buf *agbp)
	390	{
	391	struct xfs_agf *agf = agbp->b_addr;
	392	struct xbtree_afakeroot *afake = cur->bc_ag.afake;
	393
	394	ASSERT(cur->bc_flags & XFS_BTREE_STAGING);
	395
	396	agf->agf_refcount_root = cpu_to_be32(afake->af_root);
	397	agf->agf_refcount_level = cpu_to_be32(afake->af_levels);
	398	agf->agf_refcount_blocks = cpu_to_be32(afake->af_blocks);
	399	xfs_alloc_log_agf(tp, agbp, XFS_AGF_REFCOUNT_BLOCKS \|
	400	XFS_AGF_REFCOUNT_ROOT \|
	401	XFS_AGF_REFCOUNT_LEVEL);
2b9e7f26	402	xfs_btree_commit_afakeroot(cur, tp, agbp);
56e98164 DW	403	}
56e98164 DW	404
0ed5f735 DW	405	/* Calculate number of records in a refcount btree block. */
	406	static inline unsigned int
	407	xfs_refcountbt_block_maxrecs(
	408	unsigned int blocklen,
	409	bool leaf)
	410	{
	411	if (leaf)
	412	return blocklen / sizeof(struct xfs_refcount_rec);
	413	return blocklen / (sizeof(struct xfs_refcount_key) +
	414	sizeof(xfs_refcount_ptr_t));
	415	}
	416
1946b91c DW	417	/*
	418	* Calculate the number of records in a refcount btree block.
	419	*/
	420	int
	421	xfs_refcountbt_maxrecs(
1946b91c DW	422	int blocklen,
	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	*/
36029dee	517	if (xfs_ag_contains_log(mp, pag->pag_agno))
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	}