[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_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;
	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));

	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);
	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_sblock_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_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 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));
}

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

/*
 * 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,
			mp->m_refc_maxlevels, xfs_refcountbt_cur_cache);
	cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_refcbt_2);

	cur->bc_flags |= XFS_BTREE_CRC_BLOCKS;

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