xref: /openbmc/linux/fs/xfs/libxfs/xfs_rmap_btree.c (revision 36029dee)
10b61f8a4SDave Chinner // SPDX-License-Identifier: GPL-2.0
2035e00acSDarrick J. Wong /*
3035e00acSDarrick J. Wong  * Copyright (c) 2014 Red Hat, Inc.
4035e00acSDarrick J. Wong  * All Rights Reserved.
5035e00acSDarrick J. Wong  */
6035e00acSDarrick J. Wong #include "xfs.h"
7035e00acSDarrick J. Wong #include "xfs_fs.h"
8035e00acSDarrick J. Wong #include "xfs_shared.h"
9035e00acSDarrick J. Wong #include "xfs_format.h"
10035e00acSDarrick J. Wong #include "xfs_log_format.h"
11035e00acSDarrick J. Wong #include "xfs_trans_resv.h"
12035e00acSDarrick J. Wong #include "xfs_mount.h"
13035e00acSDarrick J. Wong #include "xfs_trans.h"
14035e00acSDarrick J. Wong #include "xfs_alloc.h"
15035e00acSDarrick J. Wong #include "xfs_btree.h"
1659d67712SDarrick J. Wong #include "xfs_btree_staging.h"
174b8ed677SDarrick J. Wong #include "xfs_rmap.h"
18035e00acSDarrick J. Wong #include "xfs_rmap_btree.h"
19035e00acSDarrick J. Wong #include "xfs_trace.h"
20035e00acSDarrick J. Wong #include "xfs_error.h"
21035e00acSDarrick J. Wong #include "xfs_extent_busy.h"
229bbafc71SDave Chinner #include "xfs_ag.h"
2384d69619SDarrick J. Wong #include "xfs_ag_resv.h"
24035e00acSDarrick J. Wong 
25e7720afaSDarrick J. Wong static struct kmem_cache	*xfs_rmapbt_cur_cache;
269fa47bdcSDarrick J. Wong 
274b8ed677SDarrick J. Wong /*
284b8ed677SDarrick J. Wong  * Reverse map btree.
294b8ed677SDarrick J. Wong  *
304b8ed677SDarrick J. Wong  * This is a per-ag tree used to track the owner(s) of a given extent. With
314b8ed677SDarrick J. Wong  * reflink it is possible for there to be multiple owners, which is a departure
324b8ed677SDarrick J. Wong  * from classic XFS. Owner records for data extents are inserted when the
334b8ed677SDarrick J. Wong  * extent is mapped and removed when an extent is unmapped.  Owner records for
344b8ed677SDarrick J. Wong  * all other block types (i.e. metadata) are inserted when an extent is
354b8ed677SDarrick J. Wong  * allocated and removed when an extent is freed. There can only be one owner
364b8ed677SDarrick J. Wong  * of a metadata extent, usually an inode or some other metadata structure like
374b8ed677SDarrick J. Wong  * an AG btree.
384b8ed677SDarrick J. Wong  *
394b8ed677SDarrick J. Wong  * The rmap btree is part of the free space management, so blocks for the tree
404b8ed677SDarrick J. Wong  * are sourced from the agfl. Hence we need transaction reservation support for
414b8ed677SDarrick J. Wong  * this tree so that the freelist is always large enough. This also impacts on
424b8ed677SDarrick J. Wong  * the minimum space we need to leave free in the AG.
434b8ed677SDarrick J. Wong  *
444b8ed677SDarrick J. Wong  * The tree is ordered by [ag block, owner, offset]. This is a large key size,
454b8ed677SDarrick J. Wong  * but it is the only way to enforce unique keys when a block can be owned by
464b8ed677SDarrick J. Wong  * multiple files at any offset. There's no need to order/search by extent
474b8ed677SDarrick J. Wong  * size for online updating/management of the tree. It is intended that most
484b8ed677SDarrick J. Wong  * reverse lookups will be to find the owner(s) of a particular block, or to
494b8ed677SDarrick J. Wong  * try to recover tree and file data from corrupt primary metadata.
504b8ed677SDarrick J. Wong  */
514b8ed677SDarrick J. Wong 
52035e00acSDarrick J. Wong static struct xfs_btree_cur *
53035e00acSDarrick J. Wong xfs_rmapbt_dup_cursor(
54035e00acSDarrick J. Wong 	struct xfs_btree_cur	*cur)
55035e00acSDarrick J. Wong {
56035e00acSDarrick J. Wong 	return xfs_rmapbt_init_cursor(cur->bc_mp, cur->bc_tp,
57fa9c3c19SDave Chinner 				cur->bc_ag.agbp, cur->bc_ag.pag);
58035e00acSDarrick J. Wong }
59035e00acSDarrick J. Wong 
604b8ed677SDarrick J. Wong STATIC void
614b8ed677SDarrick J. Wong xfs_rmapbt_set_root(
624b8ed677SDarrick J. Wong 	struct xfs_btree_cur		*cur,
63b5a6e5feSDarrick J. Wong 	const union xfs_btree_ptr	*ptr,
644b8ed677SDarrick J. Wong 	int				inc)
654b8ed677SDarrick J. Wong {
66576af732SDave Chinner 	struct xfs_buf		*agbp = cur->bc_ag.agbp;
679798f615SChristoph Hellwig 	struct xfs_agf		*agf = agbp->b_addr;
684b8ed677SDarrick J. Wong 	int			btnum = cur->bc_btnum;
694b8ed677SDarrick J. Wong 
704b8ed677SDarrick J. Wong 	ASSERT(ptr->s != 0);
714b8ed677SDarrick J. Wong 
724b8ed677SDarrick J. Wong 	agf->agf_roots[btnum] = ptr->s;
734b8ed677SDarrick J. Wong 	be32_add_cpu(&agf->agf_levels[btnum], inc);
74fa9c3c19SDave Chinner 	cur->bc_ag.pag->pagf_levels[btnum] += inc;
754b8ed677SDarrick J. Wong 
764b8ed677SDarrick J. Wong 	xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS);
774b8ed677SDarrick J. Wong }
784b8ed677SDarrick J. Wong 
794b8ed677SDarrick J. Wong STATIC int
804b8ed677SDarrick J. Wong xfs_rmapbt_alloc_block(
814b8ed677SDarrick J. Wong 	struct xfs_btree_cur		*cur,
82deb06b9aSDarrick J. Wong 	const union xfs_btree_ptr	*start,
834b8ed677SDarrick J. Wong 	union xfs_btree_ptr		*new,
844b8ed677SDarrick J. Wong 	int				*stat)
854b8ed677SDarrick J. Wong {
86576af732SDave Chinner 	struct xfs_buf		*agbp = cur->bc_ag.agbp;
879798f615SChristoph Hellwig 	struct xfs_agf		*agf = agbp->b_addr;
88fa9c3c19SDave Chinner 	struct xfs_perag	*pag = cur->bc_ag.pag;
894b8ed677SDarrick J. Wong 	int			error;
904b8ed677SDarrick J. Wong 	xfs_agblock_t		bno;
914b8ed677SDarrick J. Wong 
924b8ed677SDarrick J. Wong 	/* Allocate the new block from the freelist. If we can't, give up.  */
9349f0d84eSDave Chinner 	error = xfs_alloc_get_freelist(pag, cur->bc_tp, cur->bc_ag.agbp,
944b8ed677SDarrick J. Wong 				       &bno, 1);
95e157ebdcSCarlos Maiolino 	if (error)
964b8ed677SDarrick J. Wong 		return error;
974b8ed677SDarrick J. Wong 
98fa9c3c19SDave Chinner 	trace_xfs_rmapbt_alloc_block(cur->bc_mp, pag->pag_agno, bno, 1);
994b8ed677SDarrick J. Wong 	if (bno == NULLAGBLOCK) {
1004b8ed677SDarrick J. Wong 		*stat = 0;
1014b8ed677SDarrick J. Wong 		return 0;
1024b8ed677SDarrick J. Wong 	}
1034b8ed677SDarrick J. Wong 
104fa9c3c19SDave Chinner 	xfs_extent_busy_reuse(cur->bc_mp, pag, bno, 1, false);
1054b8ed677SDarrick J. Wong 
1064b8ed677SDarrick J. Wong 	new->s = cpu_to_be32(bno);
107f32866fdSDarrick J. Wong 	be32_add_cpu(&agf->agf_rmap_blocks, 1);
108f32866fdSDarrick J. Wong 	xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_RMAP_BLOCKS);
1094b8ed677SDarrick J. Wong 
110fa9c3c19SDave Chinner 	xfs_ag_resv_rmapbt_alloc(cur->bc_mp, pag->pag_agno);
1110ab32086SBrian Foster 
1124b8ed677SDarrick J. Wong 	*stat = 1;
1134b8ed677SDarrick J. Wong 	return 0;
1144b8ed677SDarrick J. Wong }
1154b8ed677SDarrick J. Wong 
1164b8ed677SDarrick J. Wong STATIC int
1174b8ed677SDarrick J. Wong xfs_rmapbt_free_block(
1184b8ed677SDarrick J. Wong 	struct xfs_btree_cur	*cur,
1194b8ed677SDarrick J. Wong 	struct xfs_buf		*bp)
1204b8ed677SDarrick J. Wong {
121576af732SDave Chinner 	struct xfs_buf		*agbp = cur->bc_ag.agbp;
1229798f615SChristoph Hellwig 	struct xfs_agf		*agf = agbp->b_addr;
123fa9c3c19SDave Chinner 	struct xfs_perag	*pag = cur->bc_ag.pag;
1244b8ed677SDarrick J. Wong 	xfs_agblock_t		bno;
1254b8ed677SDarrick J. Wong 	int			error;
1264b8ed677SDarrick J. Wong 
12704fcad80SDave Chinner 	bno = xfs_daddr_to_agbno(cur->bc_mp, xfs_buf_daddr(bp));
128fa9c3c19SDave Chinner 	trace_xfs_rmapbt_free_block(cur->bc_mp, pag->pag_agno,
1294b8ed677SDarrick J. Wong 			bno, 1);
130f32866fdSDarrick J. Wong 	be32_add_cpu(&agf->agf_rmap_blocks, -1);
131f32866fdSDarrick J. Wong 	xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_RMAP_BLOCKS);
1328c392eb2SDave Chinner 	error = xfs_alloc_put_freelist(pag, cur->bc_tp, agbp, NULL, bno, 1);
1334b8ed677SDarrick J. Wong 	if (error)
1344b8ed677SDarrick J. Wong 		return error;
1354b8ed677SDarrick J. Wong 
13645d06621SDave Chinner 	xfs_extent_busy_insert(cur->bc_tp, pag, bno, 1,
1374b8ed677SDarrick J. Wong 			      XFS_EXTENT_BUSY_SKIP_DISCARD);
1384b8ed677SDarrick J. Wong 
13992a00544SGao Xiang 	xfs_ag_resv_free_extent(pag, XFS_AG_RESV_RMAPBT, NULL, 1);
1404b8ed677SDarrick J. Wong 	return 0;
1414b8ed677SDarrick J. Wong }
1424b8ed677SDarrick J. Wong 
1434b8ed677SDarrick J. Wong STATIC int
1444b8ed677SDarrick J. Wong xfs_rmapbt_get_minrecs(
1454b8ed677SDarrick J. Wong 	struct xfs_btree_cur	*cur,
1464b8ed677SDarrick J. Wong 	int			level)
1474b8ed677SDarrick J. Wong {
1484b8ed677SDarrick J. Wong 	return cur->bc_mp->m_rmap_mnr[level != 0];
1494b8ed677SDarrick J. Wong }
1504b8ed677SDarrick J. Wong 
1514b8ed677SDarrick J. Wong STATIC int
1524b8ed677SDarrick J. Wong xfs_rmapbt_get_maxrecs(
1534b8ed677SDarrick J. Wong 	struct xfs_btree_cur	*cur,
1544b8ed677SDarrick J. Wong 	int			level)
1554b8ed677SDarrick J. Wong {
1564b8ed677SDarrick J. Wong 	return cur->bc_mp->m_rmap_mxr[level != 0];
1574b8ed677SDarrick J. Wong }
1584b8ed677SDarrick J. Wong 
1594b8ed677SDarrick J. Wong STATIC void
1604b8ed677SDarrick J. Wong xfs_rmapbt_init_key_from_rec(
1614b8ed677SDarrick J. Wong 	union xfs_btree_key		*key,
16223825cd1SDarrick J. Wong 	const union xfs_btree_rec	*rec)
1634b8ed677SDarrick J. Wong {
1644b8ed677SDarrick J. Wong 	key->rmap.rm_startblock = rec->rmap.rm_startblock;
1654b8ed677SDarrick J. Wong 	key->rmap.rm_owner = rec->rmap.rm_owner;
1664b8ed677SDarrick J. Wong 	key->rmap.rm_offset = rec->rmap.rm_offset;
1674b8ed677SDarrick J. Wong }
1684b8ed677SDarrick J. Wong 
169cfed56aeSDarrick J. Wong /*
170cfed56aeSDarrick J. Wong  * The high key for a reverse mapping record can be computed by shifting
171cfed56aeSDarrick J. Wong  * the startblock and offset to the highest value that would still map
172cfed56aeSDarrick J. Wong  * to that record.  In practice this means that we add blockcount-1 to
173cfed56aeSDarrick J. Wong  * the startblock for all records, and if the record is for a data/attr
174cfed56aeSDarrick J. Wong  * fork mapping, we add blockcount-1 to the offset too.
175cfed56aeSDarrick J. Wong  */
176cfed56aeSDarrick J. Wong STATIC void
177cfed56aeSDarrick J. Wong xfs_rmapbt_init_high_key_from_rec(
178cfed56aeSDarrick J. Wong 	union xfs_btree_key		*key,
17923825cd1SDarrick J. Wong 	const union xfs_btree_rec	*rec)
180cfed56aeSDarrick J. Wong {
181c8ce540dSDarrick J. Wong 	uint64_t			off;
182cfed56aeSDarrick J. Wong 	int				adj;
183cfed56aeSDarrick J. Wong 
184cfed56aeSDarrick J. Wong 	adj = be32_to_cpu(rec->rmap.rm_blockcount) - 1;
185cfed56aeSDarrick J. Wong 
186cfed56aeSDarrick J. Wong 	key->rmap.rm_startblock = rec->rmap.rm_startblock;
187cfed56aeSDarrick J. Wong 	be32_add_cpu(&key->rmap.rm_startblock, adj);
188cfed56aeSDarrick J. Wong 	key->rmap.rm_owner = rec->rmap.rm_owner;
189cfed56aeSDarrick J. Wong 	key->rmap.rm_offset = rec->rmap.rm_offset;
190cfed56aeSDarrick J. Wong 	if (XFS_RMAP_NON_INODE_OWNER(be64_to_cpu(rec->rmap.rm_owner)) ||
191cfed56aeSDarrick J. Wong 	    XFS_RMAP_IS_BMBT_BLOCK(be64_to_cpu(rec->rmap.rm_offset)))
192cfed56aeSDarrick J. Wong 		return;
193cfed56aeSDarrick J. Wong 	off = be64_to_cpu(key->rmap.rm_offset);
194cfed56aeSDarrick J. Wong 	off = (XFS_RMAP_OFF(off) + adj) | (off & ~XFS_RMAP_OFF_MASK);
195cfed56aeSDarrick J. Wong 	key->rmap.rm_offset = cpu_to_be64(off);
196cfed56aeSDarrick J. Wong }
197cfed56aeSDarrick J. Wong 
1984b8ed677SDarrick J. Wong STATIC void
1994b8ed677SDarrick J. Wong xfs_rmapbt_init_rec_from_cur(
2004b8ed677SDarrick J. Wong 	struct xfs_btree_cur	*cur,
2014b8ed677SDarrick J. Wong 	union xfs_btree_rec	*rec)
2024b8ed677SDarrick J. Wong {
2034b8ed677SDarrick J. Wong 	rec->rmap.rm_startblock = cpu_to_be32(cur->bc_rec.r.rm_startblock);
2044b8ed677SDarrick J. Wong 	rec->rmap.rm_blockcount = cpu_to_be32(cur->bc_rec.r.rm_blockcount);
2054b8ed677SDarrick J. Wong 	rec->rmap.rm_owner = cpu_to_be64(cur->bc_rec.r.rm_owner);
2064b8ed677SDarrick J. Wong 	rec->rmap.rm_offset = cpu_to_be64(
2074b8ed677SDarrick J. Wong 			xfs_rmap_irec_offset_pack(&cur->bc_rec.r));
2084b8ed677SDarrick J. Wong }
2094b8ed677SDarrick J. Wong 
2104b8ed677SDarrick J. Wong STATIC void
2114b8ed677SDarrick J. Wong xfs_rmapbt_init_ptr_from_cur(
2124b8ed677SDarrick J. Wong 	struct xfs_btree_cur	*cur,
2134b8ed677SDarrick J. Wong 	union xfs_btree_ptr	*ptr)
2144b8ed677SDarrick J. Wong {
215576af732SDave Chinner 	struct xfs_agf		*agf = cur->bc_ag.agbp->b_addr;
2164b8ed677SDarrick J. Wong 
217fa9c3c19SDave Chinner 	ASSERT(cur->bc_ag.pag->pag_agno == be32_to_cpu(agf->agf_seqno));
2184b8ed677SDarrick J. Wong 
2194b8ed677SDarrick J. Wong 	ptr->s = agf->agf_roots[cur->bc_btnum];
2204b8ed677SDarrick J. Wong }
2214b8ed677SDarrick J. Wong 
222c8ce540dSDarrick J. Wong STATIC int64_t
2234b8ed677SDarrick J. Wong xfs_rmapbt_key_diff(
2244b8ed677SDarrick J. Wong 	struct xfs_btree_cur		*cur,
225d29d5577SDarrick J. Wong 	const union xfs_btree_key	*key)
2264b8ed677SDarrick J. Wong {
2274b8ed677SDarrick J. Wong 	struct xfs_rmap_irec		*rec = &cur->bc_rec.r;
228d29d5577SDarrick J. Wong 	const struct xfs_rmap_key	*kp = &key->rmap;
2294b8ed677SDarrick J. Wong 	__u64				x, y;
230c8ce540dSDarrick J. Wong 	int64_t				d;
2314b8ed677SDarrick J. Wong 
232c8ce540dSDarrick J. Wong 	d = (int64_t)be32_to_cpu(kp->rm_startblock) - rec->rm_startblock;
2334b8ed677SDarrick J. Wong 	if (d)
2344b8ed677SDarrick J. Wong 		return d;
2354b8ed677SDarrick J. Wong 
2364b8ed677SDarrick J. Wong 	x = be64_to_cpu(kp->rm_owner);
2374b8ed677SDarrick J. Wong 	y = rec->rm_owner;
2384b8ed677SDarrick J. Wong 	if (x > y)
2394b8ed677SDarrick J. Wong 		return 1;
2404b8ed677SDarrick J. Wong 	else if (y > x)
2414b8ed677SDarrick J. Wong 		return -1;
2424b8ed677SDarrick J. Wong 
243eb840907SDarrick J. Wong 	x = XFS_RMAP_OFF(be64_to_cpu(kp->rm_offset));
244eb840907SDarrick J. Wong 	y = rec->rm_offset;
2454b8ed677SDarrick J. Wong 	if (x > y)
2464b8ed677SDarrick J. Wong 		return 1;
2474b8ed677SDarrick J. Wong 	else if (y > x)
2484b8ed677SDarrick J. Wong 		return -1;
2494b8ed677SDarrick J. Wong 	return 0;
2504b8ed677SDarrick J. Wong }
2514b8ed677SDarrick J. Wong 
252c8ce540dSDarrick J. Wong STATIC int64_t
253cfed56aeSDarrick J. Wong xfs_rmapbt_diff_two_keys(
254cfed56aeSDarrick J. Wong 	struct xfs_btree_cur		*cur,
255d29d5577SDarrick J. Wong 	const union xfs_btree_key	*k1,
256d29d5577SDarrick J. Wong 	const union xfs_btree_key	*k2)
257cfed56aeSDarrick J. Wong {
258d29d5577SDarrick J. Wong 	const struct xfs_rmap_key	*kp1 = &k1->rmap;
259d29d5577SDarrick J. Wong 	const struct xfs_rmap_key	*kp2 = &k2->rmap;
260c8ce540dSDarrick J. Wong 	int64_t				d;
261cfed56aeSDarrick J. Wong 	__u64				x, y;
262cfed56aeSDarrick J. Wong 
263c8ce540dSDarrick J. Wong 	d = (int64_t)be32_to_cpu(kp1->rm_startblock) -
264cfed56aeSDarrick J. Wong 		       be32_to_cpu(kp2->rm_startblock);
265cfed56aeSDarrick J. Wong 	if (d)
266cfed56aeSDarrick J. Wong 		return d;
267cfed56aeSDarrick J. Wong 
268cfed56aeSDarrick J. Wong 	x = be64_to_cpu(kp1->rm_owner);
269cfed56aeSDarrick J. Wong 	y = be64_to_cpu(kp2->rm_owner);
270cfed56aeSDarrick J. Wong 	if (x > y)
271cfed56aeSDarrick J. Wong 		return 1;
272cfed56aeSDarrick J. Wong 	else if (y > x)
273cfed56aeSDarrick J. Wong 		return -1;
274cfed56aeSDarrick J. Wong 
275eb840907SDarrick J. Wong 	x = XFS_RMAP_OFF(be64_to_cpu(kp1->rm_offset));
276eb840907SDarrick J. Wong 	y = XFS_RMAP_OFF(be64_to_cpu(kp2->rm_offset));
277cfed56aeSDarrick J. Wong 	if (x > y)
278cfed56aeSDarrick J. Wong 		return 1;
279cfed56aeSDarrick J. Wong 	else if (y > x)
280cfed56aeSDarrick J. Wong 		return -1;
281cfed56aeSDarrick J. Wong 	return 0;
282cfed56aeSDarrick J. Wong }
283cfed56aeSDarrick J. Wong 
284a6a781a5SDarrick J. Wong static xfs_failaddr_t
285035e00acSDarrick J. Wong xfs_rmapbt_verify(
286035e00acSDarrick J. Wong 	struct xfs_buf		*bp)
287035e00acSDarrick J. Wong {
288dbd329f1SChristoph Hellwig 	struct xfs_mount	*mp = bp->b_mount;
289035e00acSDarrick J. Wong 	struct xfs_btree_block	*block = XFS_BUF_TO_BLOCK(bp);
290035e00acSDarrick J. Wong 	struct xfs_perag	*pag = bp->b_pag;
291a6a781a5SDarrick J. Wong 	xfs_failaddr_t		fa;
292035e00acSDarrick J. Wong 	unsigned int		level;
293035e00acSDarrick J. Wong 
294035e00acSDarrick J. Wong 	/*
295035e00acSDarrick J. Wong 	 * magic number and level verification
296035e00acSDarrick J. Wong 	 *
297035e00acSDarrick J. Wong 	 * During growfs operations, we can't verify the exact level or owner as
298035e00acSDarrick J. Wong 	 * the perag is not fully initialised and hence not attached to the
299035e00acSDarrick J. Wong 	 * buffer.  In this case, check against the maximum tree depth.
300035e00acSDarrick J. Wong 	 *
301035e00acSDarrick J. Wong 	 * Similarly, during log recovery we will have a perag structure
302035e00acSDarrick J. Wong 	 * attached, but the agf information will not yet have been initialised
303035e00acSDarrick J. Wong 	 * from the on disk AGF. Again, we can only check against maximum limits
304035e00acSDarrick J. Wong 	 * in this case.
305035e00acSDarrick J. Wong 	 */
30639708c20SBrian Foster 	if (!xfs_verify_magic(bp, block->bb_magic))
307a6a781a5SDarrick J. Wong 		return __this_address;
308035e00acSDarrick J. Wong 
30938c26bfdSDave Chinner 	if (!xfs_has_rmapbt(mp))
310a6a781a5SDarrick J. Wong 		return __this_address;
311a6a781a5SDarrick J. Wong 	fa = xfs_btree_sblock_v5hdr_verify(bp);
312a6a781a5SDarrick J. Wong 	if (fa)
313a6a781a5SDarrick J. Wong 		return fa;
314035e00acSDarrick J. Wong 
315035e00acSDarrick J. Wong 	level = be16_to_cpu(block->bb_level);
316035e00acSDarrick J. Wong 	if (pag && pag->pagf_init) {
317035e00acSDarrick J. Wong 		if (level >= pag->pagf_levels[XFS_BTNUM_RMAPi])
318a6a781a5SDarrick J. Wong 			return __this_address;
319035e00acSDarrick J. Wong 	} else if (level >= mp->m_rmap_maxlevels)
320a6a781a5SDarrick J. Wong 		return __this_address;
321035e00acSDarrick J. Wong 
322035e00acSDarrick J. Wong 	return xfs_btree_sblock_verify(bp, mp->m_rmap_mxr[level != 0]);
323035e00acSDarrick J. Wong }
324035e00acSDarrick J. Wong 
325035e00acSDarrick J. Wong static void
326035e00acSDarrick J. Wong xfs_rmapbt_read_verify(
327035e00acSDarrick J. Wong 	struct xfs_buf	*bp)
328035e00acSDarrick J. Wong {
329bc1a09b8SDarrick J. Wong 	xfs_failaddr_t	fa;
330bc1a09b8SDarrick J. Wong 
331035e00acSDarrick J. Wong 	if (!xfs_btree_sblock_verify_crc(bp))
332bc1a09b8SDarrick J. Wong 		xfs_verifier_error(bp, -EFSBADCRC, __this_address);
333bc1a09b8SDarrick J. Wong 	else {
334bc1a09b8SDarrick J. Wong 		fa = xfs_rmapbt_verify(bp);
335bc1a09b8SDarrick J. Wong 		if (fa)
336bc1a09b8SDarrick J. Wong 			xfs_verifier_error(bp, -EFSCORRUPTED, fa);
337bc1a09b8SDarrick J. Wong 	}
338035e00acSDarrick J. Wong 
33931ca03c9SDarrick J. Wong 	if (bp->b_error)
340035e00acSDarrick J. Wong 		trace_xfs_btree_corrupt(bp, _RET_IP_);
341035e00acSDarrick J. Wong }
342035e00acSDarrick J. Wong 
343035e00acSDarrick J. Wong static void
344035e00acSDarrick J. Wong xfs_rmapbt_write_verify(
345035e00acSDarrick J. Wong 	struct xfs_buf	*bp)
346035e00acSDarrick J. Wong {
347bc1a09b8SDarrick J. Wong 	xfs_failaddr_t	fa;
348bc1a09b8SDarrick J. Wong 
349bc1a09b8SDarrick J. Wong 	fa = xfs_rmapbt_verify(bp);
350bc1a09b8SDarrick J. Wong 	if (fa) {
351035e00acSDarrick J. Wong 		trace_xfs_btree_corrupt(bp, _RET_IP_);
352bc1a09b8SDarrick J. Wong 		xfs_verifier_error(bp, -EFSCORRUPTED, fa);
353035e00acSDarrick J. Wong 		return;
354035e00acSDarrick J. Wong 	}
355035e00acSDarrick J. Wong 	xfs_btree_sblock_calc_crc(bp);
356035e00acSDarrick J. Wong 
357035e00acSDarrick J. Wong }
358035e00acSDarrick J. Wong 
359035e00acSDarrick J. Wong const struct xfs_buf_ops xfs_rmapbt_buf_ops = {
360035e00acSDarrick J. Wong 	.name			= "xfs_rmapbt",
36139708c20SBrian Foster 	.magic			= { 0, cpu_to_be32(XFS_RMAP_CRC_MAGIC) },
362035e00acSDarrick J. Wong 	.verify_read		= xfs_rmapbt_read_verify,
363035e00acSDarrick J. Wong 	.verify_write		= xfs_rmapbt_write_verify,
364b5572597SDarrick J. Wong 	.verify_struct		= xfs_rmapbt_verify,
365035e00acSDarrick J. Wong };
366035e00acSDarrick J. Wong 
3674b8ed677SDarrick J. Wong STATIC int
3684b8ed677SDarrick J. Wong xfs_rmapbt_keys_inorder(
3694b8ed677SDarrick J. Wong 	struct xfs_btree_cur		*cur,
3708e38dc88SDarrick J. Wong 	const union xfs_btree_key	*k1,
3718e38dc88SDarrick J. Wong 	const union xfs_btree_key	*k2)
3724b8ed677SDarrick J. Wong {
373c8ce540dSDarrick J. Wong 	uint32_t		x;
374c8ce540dSDarrick J. Wong 	uint32_t		y;
375c8ce540dSDarrick J. Wong 	uint64_t		a;
376c8ce540dSDarrick J. Wong 	uint64_t		b;
3774b8ed677SDarrick J. Wong 
3784b8ed677SDarrick J. Wong 	x = be32_to_cpu(k1->rmap.rm_startblock);
3794b8ed677SDarrick J. Wong 	y = be32_to_cpu(k2->rmap.rm_startblock);
3804b8ed677SDarrick J. Wong 	if (x < y)
3814b8ed677SDarrick J. Wong 		return 1;
3824b8ed677SDarrick J. Wong 	else if (x > y)
3834b8ed677SDarrick J. Wong 		return 0;
3844b8ed677SDarrick J. Wong 	a = be64_to_cpu(k1->rmap.rm_owner);
3854b8ed677SDarrick J. Wong 	b = be64_to_cpu(k2->rmap.rm_owner);
3864b8ed677SDarrick J. Wong 	if (a < b)
3874b8ed677SDarrick J. Wong 		return 1;
3884b8ed677SDarrick J. Wong 	else if (a > b)
3894b8ed677SDarrick J. Wong 		return 0;
390eb840907SDarrick J. Wong 	a = XFS_RMAP_OFF(be64_to_cpu(k1->rmap.rm_offset));
391eb840907SDarrick J. Wong 	b = XFS_RMAP_OFF(be64_to_cpu(k2->rmap.rm_offset));
3924b8ed677SDarrick J. Wong 	if (a <= b)
3934b8ed677SDarrick J. Wong 		return 1;
3944b8ed677SDarrick J. Wong 	return 0;
3954b8ed677SDarrick J. Wong }
3964b8ed677SDarrick J. Wong 
3974b8ed677SDarrick J. Wong STATIC int
3984b8ed677SDarrick J. Wong xfs_rmapbt_recs_inorder(
3994b8ed677SDarrick J. Wong 	struct xfs_btree_cur		*cur,
4008e38dc88SDarrick J. Wong 	const union xfs_btree_rec	*r1,
4018e38dc88SDarrick J. Wong 	const union xfs_btree_rec	*r2)
4024b8ed677SDarrick J. Wong {
403c8ce540dSDarrick J. Wong 	uint32_t		x;
404c8ce540dSDarrick J. Wong 	uint32_t		y;
405c8ce540dSDarrick J. Wong 	uint64_t		a;
406c8ce540dSDarrick J. Wong 	uint64_t		b;
4074b8ed677SDarrick J. Wong 
4084b8ed677SDarrick J. Wong 	x = be32_to_cpu(r1->rmap.rm_startblock);
4094b8ed677SDarrick J. Wong 	y = be32_to_cpu(r2->rmap.rm_startblock);
4104b8ed677SDarrick J. Wong 	if (x < y)
4114b8ed677SDarrick J. Wong 		return 1;
4124b8ed677SDarrick J. Wong 	else if (x > y)
4134b8ed677SDarrick J. Wong 		return 0;
4144b8ed677SDarrick J. Wong 	a = be64_to_cpu(r1->rmap.rm_owner);
4154b8ed677SDarrick J. Wong 	b = be64_to_cpu(r2->rmap.rm_owner);
4164b8ed677SDarrick J. Wong 	if (a < b)
4174b8ed677SDarrick J. Wong 		return 1;
4184b8ed677SDarrick J. Wong 	else if (a > b)
4194b8ed677SDarrick J. Wong 		return 0;
420eb840907SDarrick J. Wong 	a = XFS_RMAP_OFF(be64_to_cpu(r1->rmap.rm_offset));
421eb840907SDarrick J. Wong 	b = XFS_RMAP_OFF(be64_to_cpu(r2->rmap.rm_offset));
4224b8ed677SDarrick J. Wong 	if (a <= b)
4234b8ed677SDarrick J. Wong 		return 1;
4244b8ed677SDarrick J. Wong 	return 0;
4254b8ed677SDarrick J. Wong }
4264b8ed677SDarrick J. Wong 
427035e00acSDarrick J. Wong static const struct xfs_btree_ops xfs_rmapbt_ops = {
428035e00acSDarrick J. Wong 	.rec_len		= sizeof(struct xfs_rmap_rec),
429035e00acSDarrick J. Wong 	.key_len		= 2 * sizeof(struct xfs_rmap_key),
430035e00acSDarrick J. Wong 
431035e00acSDarrick J. Wong 	.dup_cursor		= xfs_rmapbt_dup_cursor,
4324b8ed677SDarrick J. Wong 	.set_root		= xfs_rmapbt_set_root,
4334b8ed677SDarrick J. Wong 	.alloc_block		= xfs_rmapbt_alloc_block,
4344b8ed677SDarrick J. Wong 	.free_block		= xfs_rmapbt_free_block,
4354b8ed677SDarrick J. Wong 	.get_minrecs		= xfs_rmapbt_get_minrecs,
4364b8ed677SDarrick J. Wong 	.get_maxrecs		= xfs_rmapbt_get_maxrecs,
4374b8ed677SDarrick J. Wong 	.init_key_from_rec	= xfs_rmapbt_init_key_from_rec,
438cfed56aeSDarrick J. Wong 	.init_high_key_from_rec	= xfs_rmapbt_init_high_key_from_rec,
4394b8ed677SDarrick J. Wong 	.init_rec_from_cur	= xfs_rmapbt_init_rec_from_cur,
4404b8ed677SDarrick J. Wong 	.init_ptr_from_cur	= xfs_rmapbt_init_ptr_from_cur,
4414b8ed677SDarrick J. Wong 	.key_diff		= xfs_rmapbt_key_diff,
442035e00acSDarrick J. Wong 	.buf_ops		= &xfs_rmapbt_buf_ops,
443cfed56aeSDarrick J. Wong 	.diff_two_keys		= xfs_rmapbt_diff_two_keys,
4444b8ed677SDarrick J. Wong 	.keys_inorder		= xfs_rmapbt_keys_inorder,
4454b8ed677SDarrick J. Wong 	.recs_inorder		= xfs_rmapbt_recs_inorder,
446035e00acSDarrick J. Wong };
447035e00acSDarrick J. Wong 
44859d67712SDarrick J. Wong static struct xfs_btree_cur *
44959d67712SDarrick J. Wong xfs_rmapbt_init_common(
45059d67712SDarrick J. Wong 	struct xfs_mount	*mp,
45159d67712SDarrick J. Wong 	struct xfs_trans	*tp,
452be9fb17dSDave Chinner 	struct xfs_perag	*pag)
45359d67712SDarrick J. Wong {
45459d67712SDarrick J. Wong 	struct xfs_btree_cur	*cur;
45559d67712SDarrick J. Wong 
45659d67712SDarrick J. Wong 	/* Overlapping btree; 2 keys per pointer. */
457c940a0c5SDarrick J. Wong 	cur = xfs_btree_alloc_cursor(mp, tp, XFS_BTNUM_RMAP,
4589fa47bdcSDarrick J. Wong 			mp->m_rmap_maxlevels, xfs_rmapbt_cur_cache);
45959d67712SDarrick J. Wong 	cur->bc_flags = XFS_BTREE_CRC_BLOCKS | XFS_BTREE_OVERLAPPING;
46059d67712SDarrick J. Wong 	cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_rmap_2);
46159d67712SDarrick J. Wong 	cur->bc_ops = &xfs_rmapbt_ops;
462fa9c3c19SDave Chinner 
463be9fb17dSDave Chinner 	/* take a reference for the cursor */
464be9fb17dSDave Chinner 	atomic_inc(&pag->pag_ref);
465be9fb17dSDave Chinner 	cur->bc_ag.pag = pag;
46659d67712SDarrick J. Wong 
46759d67712SDarrick J. Wong 	return cur;
46859d67712SDarrick J. Wong }
46959d67712SDarrick J. Wong 
47059d67712SDarrick J. Wong /* Create a new reverse mapping btree cursor. */
471035e00acSDarrick J. Wong struct xfs_btree_cur *
472035e00acSDarrick J. Wong xfs_rmapbt_init_cursor(
473035e00acSDarrick J. Wong 	struct xfs_mount	*mp,
474035e00acSDarrick J. Wong 	struct xfs_trans	*tp,
475035e00acSDarrick J. Wong 	struct xfs_buf		*agbp,
476be9fb17dSDave Chinner 	struct xfs_perag	*pag)
477035e00acSDarrick J. Wong {
4789798f615SChristoph Hellwig 	struct xfs_agf		*agf = agbp->b_addr;
479035e00acSDarrick J. Wong 	struct xfs_btree_cur	*cur;
480035e00acSDarrick J. Wong 
481fa9c3c19SDave Chinner 	cur = xfs_rmapbt_init_common(mp, tp, pag);
482035e00acSDarrick J. Wong 	cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_RMAP]);
483576af732SDave Chinner 	cur->bc_ag.agbp = agbp;
484035e00acSDarrick J. Wong 	return cur;
485035e00acSDarrick J. Wong }
486035e00acSDarrick J. Wong 
48759d67712SDarrick J. Wong /* Create a new reverse mapping btree cursor with a fake root for staging. */
48859d67712SDarrick J. Wong struct xfs_btree_cur *
48959d67712SDarrick J. Wong xfs_rmapbt_stage_cursor(
49059d67712SDarrick J. Wong 	struct xfs_mount	*mp,
49159d67712SDarrick J. Wong 	struct xbtree_afakeroot	*afake,
492fa9c3c19SDave Chinner 	struct xfs_perag	*pag)
49359d67712SDarrick J. Wong {
49459d67712SDarrick J. Wong 	struct xfs_btree_cur	*cur;
49559d67712SDarrick J. Wong 
496fa9c3c19SDave Chinner 	cur = xfs_rmapbt_init_common(mp, NULL, pag);
49759d67712SDarrick J. Wong 	xfs_btree_stage_afakeroot(cur, afake);
49859d67712SDarrick J. Wong 	return cur;
49959d67712SDarrick J. Wong }
50059d67712SDarrick J. Wong 
50159d67712SDarrick J. Wong /*
50259d67712SDarrick J. Wong  * Install a new reverse mapping btree root.  Caller is responsible for
50359d67712SDarrick J. Wong  * invalidating and freeing the old btree blocks.
50459d67712SDarrick J. Wong  */
50559d67712SDarrick J. Wong void
50659d67712SDarrick J. Wong xfs_rmapbt_commit_staged_btree(
50759d67712SDarrick J. Wong 	struct xfs_btree_cur	*cur,
50859d67712SDarrick J. Wong 	struct xfs_trans	*tp,
50959d67712SDarrick J. Wong 	struct xfs_buf		*agbp)
51059d67712SDarrick J. Wong {
51159d67712SDarrick J. Wong 	struct xfs_agf		*agf = agbp->b_addr;
51259d67712SDarrick J. Wong 	struct xbtree_afakeroot	*afake = cur->bc_ag.afake;
51359d67712SDarrick J. Wong 
51459d67712SDarrick J. Wong 	ASSERT(cur->bc_flags & XFS_BTREE_STAGING);
51559d67712SDarrick J. Wong 
51659d67712SDarrick J. Wong 	agf->agf_roots[cur->bc_btnum] = cpu_to_be32(afake->af_root);
51759d67712SDarrick J. Wong 	agf->agf_levels[cur->bc_btnum] = cpu_to_be32(afake->af_levels);
51859d67712SDarrick J. Wong 	agf->agf_rmap_blocks = cpu_to_be32(afake->af_blocks);
51959d67712SDarrick J. Wong 	xfs_alloc_log_agf(tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS |
52059d67712SDarrick J. Wong 				    XFS_AGF_RMAP_BLOCKS);
52159d67712SDarrick J. Wong 	xfs_btree_commit_afakeroot(cur, tp, agbp, &xfs_rmapbt_ops);
52259d67712SDarrick J. Wong }
52359d67712SDarrick J. Wong 
5240ed5f735SDarrick J. Wong /* Calculate number of records in a reverse mapping btree block. */
5250ed5f735SDarrick J. Wong static inline unsigned int
5260ed5f735SDarrick J. Wong xfs_rmapbt_block_maxrecs(
5270ed5f735SDarrick J. Wong 	unsigned int		blocklen,
5280ed5f735SDarrick J. Wong 	bool			leaf)
5290ed5f735SDarrick J. Wong {
5300ed5f735SDarrick J. Wong 	if (leaf)
5310ed5f735SDarrick J. Wong 		return blocklen / sizeof(struct xfs_rmap_rec);
5320ed5f735SDarrick J. Wong 	return blocklen /
5330ed5f735SDarrick J. Wong 		(2 * sizeof(struct xfs_rmap_key) + sizeof(xfs_rmap_ptr_t));
5340ed5f735SDarrick J. Wong }
5350ed5f735SDarrick J. Wong 
536035e00acSDarrick J. Wong /*
537035e00acSDarrick J. Wong  * Calculate number of records in an rmap btree block.
538035e00acSDarrick J. Wong  */
539035e00acSDarrick J. Wong int
540035e00acSDarrick J. Wong xfs_rmapbt_maxrecs(
541035e00acSDarrick J. Wong 	int			blocklen,
542035e00acSDarrick J. Wong 	int			leaf)
543035e00acSDarrick J. Wong {
544035e00acSDarrick J. Wong 	blocklen -= XFS_RMAP_BLOCK_LEN;
5450ed5f735SDarrick J. Wong 	return xfs_rmapbt_block_maxrecs(blocklen, leaf);
5460ed5f735SDarrick J. Wong }
547035e00acSDarrick J. Wong 
5480ed5f735SDarrick J. Wong /* Compute the max possible height for reverse mapping btrees. */
5490ed5f735SDarrick J. Wong unsigned int
5500ed5f735SDarrick J. Wong xfs_rmapbt_maxlevels_ondisk(void)
5510ed5f735SDarrick J. Wong {
5520ed5f735SDarrick J. Wong 	unsigned int		minrecs[2];
5530ed5f735SDarrick J. Wong 	unsigned int		blocklen;
5540ed5f735SDarrick J. Wong 
5550ed5f735SDarrick J. Wong 	blocklen = XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN;
5560ed5f735SDarrick J. Wong 
5570ed5f735SDarrick J. Wong 	minrecs[0] = xfs_rmapbt_block_maxrecs(blocklen, true) / 2;
5580ed5f735SDarrick J. Wong 	minrecs[1] = xfs_rmapbt_block_maxrecs(blocklen, false) / 2;
5590ed5f735SDarrick J. Wong 
5600ed5f735SDarrick J. Wong 	/*
5610ed5f735SDarrick J. Wong 	 * Compute the asymptotic maxlevels for an rmapbt on any reflink fs.
5620ed5f735SDarrick J. Wong 	 *
5630ed5f735SDarrick J. Wong 	 * On a reflink filesystem, each AG block can have up to 2^32 (per the
5640ed5f735SDarrick J. Wong 	 * refcount record format) owners, which means that theoretically we
5650ed5f735SDarrick J. Wong 	 * could face up to 2^64 rmap records.  However, we're likely to run
5660ed5f735SDarrick J. Wong 	 * out of blocks in the AG long before that happens, which means that
5670ed5f735SDarrick J. Wong 	 * we must compute the max height based on what the btree will look
5680ed5f735SDarrick J. Wong 	 * like if it consumes almost all the blocks in the AG due to maximal
5690ed5f735SDarrick J. Wong 	 * sharing factor.
5700ed5f735SDarrick J. Wong 	 */
5710ed5f735SDarrick J. Wong 	return xfs_btree_space_to_height(minrecs, XFS_MAX_CRC_AG_BLOCKS);
572035e00acSDarrick J. Wong }
573035e00acSDarrick J. Wong 
574035e00acSDarrick J. Wong /* Compute the maximum height of an rmap btree. */
575035e00acSDarrick J. Wong void
576035e00acSDarrick J. Wong xfs_rmapbt_compute_maxlevels(
577035e00acSDarrick J. Wong 	struct xfs_mount		*mp)
578035e00acSDarrick J. Wong {
5799ec69120SDarrick J. Wong 	if (!xfs_has_rmapbt(mp)) {
5809ec69120SDarrick J. Wong 		mp->m_rmap_maxlevels = 0;
5819ec69120SDarrick J. Wong 		return;
5829ec69120SDarrick J. Wong 	}
5839ec69120SDarrick J. Wong 
5849ec69120SDarrick J. Wong 	if (xfs_has_reflink(mp)) {
58546eeb521SDarrick J. Wong 		/*
5869ec69120SDarrick J. Wong 		 * Compute the asymptotic maxlevels for an rmap btree on a
5879ec69120SDarrick J. Wong 		 * filesystem that supports reflink.
58846eeb521SDarrick J. Wong 		 *
5899ec69120SDarrick J. Wong 		 * On a reflink filesystem, each AG block can have up to 2^32
5909ec69120SDarrick J. Wong 		 * (per the refcount record format) owners, which means that
5919ec69120SDarrick J. Wong 		 * theoretically we could face up to 2^64 rmap records.
5929ec69120SDarrick J. Wong 		 * However, we're likely to run out of blocks in the AG long
5939ec69120SDarrick J. Wong 		 * before that happens, which means that we must compute the
5949ec69120SDarrick J. Wong 		 * max height based on what the btree will look like if it
5959ec69120SDarrick J. Wong 		 * consumes almost all the blocks in the AG due to maximal
5969ec69120SDarrick J. Wong 		 * sharing factor.
59746eeb521SDarrick J. Wong 		 */
5989ec69120SDarrick J. Wong 		mp->m_rmap_maxlevels = xfs_btree_space_to_height(mp->m_rmap_mnr,
5999ec69120SDarrick J. Wong 				mp->m_sb.sb_agblocks);
6009ec69120SDarrick J. Wong 	} else {
6019ec69120SDarrick J. Wong 		/*
6029ec69120SDarrick J. Wong 		 * If there's no block sharing, compute the maximum rmapbt
6039ec69120SDarrick J. Wong 		 * height assuming one rmap record per AG block.
6049ec69120SDarrick J. Wong 		 */
605a1f69417SEric Sandeen 		mp->m_rmap_maxlevels = xfs_btree_compute_maxlevels(
606035e00acSDarrick J. Wong 				mp->m_rmap_mnr, mp->m_sb.sb_agblocks);
607035e00acSDarrick J. Wong 	}
6080ed5f735SDarrick J. Wong 	ASSERT(mp->m_rmap_maxlevels <= xfs_rmapbt_maxlevels_ondisk());
6099ec69120SDarrick J. Wong }
61084d69619SDarrick J. Wong 
61184d69619SDarrick J. Wong /* Calculate the refcount btree size for some records. */
61284d69619SDarrick J. Wong xfs_extlen_t
61384d69619SDarrick J. Wong xfs_rmapbt_calc_size(
61484d69619SDarrick J. Wong 	struct xfs_mount	*mp,
61584d69619SDarrick J. Wong 	unsigned long long	len)
61684d69619SDarrick J. Wong {
617a1f69417SEric Sandeen 	return xfs_btree_calc_size(mp->m_rmap_mnr, len);
61884d69619SDarrick J. Wong }
61984d69619SDarrick J. Wong 
62084d69619SDarrick J. Wong /*
62184d69619SDarrick J. Wong  * Calculate the maximum refcount btree size.
62284d69619SDarrick J. Wong  */
62384d69619SDarrick J. Wong xfs_extlen_t
62484d69619SDarrick J. Wong xfs_rmapbt_max_size(
62520e73b00SDarrick J. Wong 	struct xfs_mount	*mp,
62620e73b00SDarrick J. Wong 	xfs_agblock_t		agblocks)
62784d69619SDarrick J. Wong {
62884d69619SDarrick J. Wong 	/* Bail out if we're uninitialized, which can happen in mkfs. */
62984d69619SDarrick J. Wong 	if (mp->m_rmap_mxr[0] == 0)
63084d69619SDarrick J. Wong 		return 0;
63184d69619SDarrick J. Wong 
63220e73b00SDarrick J. Wong 	return xfs_rmapbt_calc_size(mp, agblocks);
63384d69619SDarrick J. Wong }
63484d69619SDarrick J. Wong 
63584d69619SDarrick J. Wong /*
63684d69619SDarrick J. Wong  * Figure out how many blocks to reserve and how many are used by this btree.
63784d69619SDarrick J. Wong  */
63884d69619SDarrick J. Wong int
63984d69619SDarrick J. Wong xfs_rmapbt_calc_reserves(
64084d69619SDarrick J. Wong 	struct xfs_mount	*mp,
641ebcbef3aSDarrick J. Wong 	struct xfs_trans	*tp,
64230933120SDave Chinner 	struct xfs_perag	*pag,
64384d69619SDarrick J. Wong 	xfs_extlen_t		*ask,
64484d69619SDarrick J. Wong 	xfs_extlen_t		*used)
64584d69619SDarrick J. Wong {
64684d69619SDarrick J. Wong 	struct xfs_buf		*agbp;
64784d69619SDarrick J. Wong 	struct xfs_agf		*agf;
64820e73b00SDarrick J. Wong 	xfs_agblock_t		agblocks;
64984d69619SDarrick J. Wong 	xfs_extlen_t		tree_len;
65084d69619SDarrick J. Wong 	int			error;
65184d69619SDarrick J. Wong 
65238c26bfdSDave Chinner 	if (!xfs_has_rmapbt(mp))
65384d69619SDarrick J. Wong 		return 0;
65484d69619SDarrick J. Wong 
65508d3e84fSDave Chinner 	error = xfs_alloc_read_agf(pag, tp, 0, &agbp);
65684d69619SDarrick J. Wong 	if (error)
65784d69619SDarrick J. Wong 		return error;
65884d69619SDarrick J. Wong 
6599798f615SChristoph Hellwig 	agf = agbp->b_addr;
66020e73b00SDarrick J. Wong 	agblocks = be32_to_cpu(agf->agf_length);
66184d69619SDarrick J. Wong 	tree_len = be32_to_cpu(agf->agf_rmap_blocks);
662ebcbef3aSDarrick J. Wong 	xfs_trans_brelse(tp, agbp);
66384d69619SDarrick J. Wong 
6645cd213b0SDarrick J. Wong 	/*
6655cd213b0SDarrick J. Wong 	 * The log is permanently allocated, so the space it occupies will
6665cd213b0SDarrick J. Wong 	 * never be available for the kinds of things that would require btree
6675cd213b0SDarrick J. Wong 	 * expansion.  We therefore can pretend the space isn't there.
6685cd213b0SDarrick J. Wong 	 */
669*36029deeSDave Chinner 	if (xfs_ag_contains_log(mp, pag->pag_agno))
6705cd213b0SDarrick J. Wong 		agblocks -= mp->m_sb.sb_logblocks;
6715cd213b0SDarrick J. Wong 
67220e73b00SDarrick J. Wong 	/* Reserve 1% of the AG or enough for 1 block per record. */
67320e73b00SDarrick J. Wong 	*ask += max(agblocks / 100, xfs_rmapbt_max_size(mp, agblocks));
67484d69619SDarrick J. Wong 	*used += tree_len;
67584d69619SDarrick J. Wong 
67684d69619SDarrick J. Wong 	return error;
67784d69619SDarrick J. Wong }
6789fa47bdcSDarrick J. Wong 
6799fa47bdcSDarrick J. Wong int __init
6809fa47bdcSDarrick J. Wong xfs_rmapbt_init_cur_cache(void)
6819fa47bdcSDarrick J. Wong {
6829fa47bdcSDarrick J. Wong 	xfs_rmapbt_cur_cache = kmem_cache_create("xfs_rmapbt_cur",
6839fa47bdcSDarrick J. Wong 			xfs_btree_cur_sizeof(xfs_rmapbt_maxlevels_ondisk()),
6849fa47bdcSDarrick J. Wong 			0, 0, NULL);
6859fa47bdcSDarrick J. Wong 
6869fa47bdcSDarrick J. Wong 	if (!xfs_rmapbt_cur_cache)
6879fa47bdcSDarrick J. Wong 		return -ENOMEM;
6889fa47bdcSDarrick J. Wong 	return 0;
6899fa47bdcSDarrick J. Wong }
6909fa47bdcSDarrick J. Wong 
6919fa47bdcSDarrick J. Wong void
6929fa47bdcSDarrick J. Wong xfs_rmapbt_destroy_cur_cache(void)
6939fa47bdcSDarrick J. Wong {
6949fa47bdcSDarrick J. Wong 	kmem_cache_destroy(xfs_rmapbt_cur_cache);
6959fa47bdcSDarrick J. Wong 	xfs_rmapbt_cur_cache = NULL;
6969fa47bdcSDarrick J. Wong }
697