1 // SPDX-License-Identifier: GPL-2.0
31  * Reverse map btree.
33  * This is a per-ag tree used to track the owner(s) of a given extent. With
35  * from classic XFS. Owner records for data extents are inserted when the
51  * reverse lookups will be to find the owner(s) of a particular block, or to
52  * try to recover tree and file data from corrupt primary metadata.
59 	return xfs_rmapbt_init_cursor(cur->bc_mp, cur->bc_tp,  in xfs_rmapbt_dup_cursor()
60 				cur->bc_ag.agbp, to_perag(cur->bc_group));  in xfs_rmapbt_dup_cursor()
69 	struct xfs_buf			*agbp = cur->bc_ag.agbp;  in xfs_rmapbt_set_root()
70 	struct xfs_agf			*agf = agbp->b_addr;  in xfs_rmapbt_set_root()
71 	struct xfs_perag		*pag = to_perag(cur->bc_group);  in xfs_rmapbt_set_root()
73 	ASSERT(ptr->s != 0);  in xfs_rmapbt_set_root()
75 	agf->agf_rmap_root = ptr->s;  in xfs_rmapbt_set_root()
76 	be32_add_cpu(&agf->agf_rmap_level, inc);  in xfs_rmapbt_set_root()
77 	pag->pagf_rmap_level += inc;  in xfs_rmapbt_set_root()
79 	xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS);  in xfs_rmapbt_set_root()
89 	struct xfs_buf		*agbp = cur->bc_ag.agbp;  in xfs_rmapbt_alloc_block()
90 	struct xfs_agf		*agf = agbp->b_addr;  in xfs_rmapbt_alloc_block()
91 	struct xfs_perag	*pag = to_perag(cur->bc_group);  in xfs_rmapbt_alloc_block()
97 	error = xfs_alloc_get_freelist(pag, cur->bc_tp, cur->bc_ag.agbp,  in xfs_rmapbt_alloc_block()
108 	new->s = cpu_to_be32(bno);  in xfs_rmapbt_alloc_block()
109 	be32_add_cpu(&agf->agf_rmap_blocks, 1);  in xfs_rmapbt_alloc_block()
110 	xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_RMAP_BLOCKS);  in xfs_rmapbt_alloc_block()
127 	struct xfs_buf		*agbp = cur->bc_ag.agbp;  in xfs_rmapbt_free_block()
128 	struct xfs_agf		*agf = agbp->b_addr;  in xfs_rmapbt_free_block()
129 	struct xfs_perag	*pag = to_perag(cur->bc_group);  in xfs_rmapbt_free_block()
133 	bno = xfs_daddr_to_agbno(cur->bc_mp, xfs_buf_daddr(bp));  in xfs_rmapbt_free_block()
134 	be32_add_cpu(&agf->agf_rmap_blocks, -1);  in xfs_rmapbt_free_block()
135 	xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_RMAP_BLOCKS);  in xfs_rmapbt_free_block()
136 	error = xfs_alloc_put_freelist(pag, cur->bc_tp, agbp, NULL, bno, 1);  in xfs_rmapbt_free_block()
140 	xfs_extent_busy_insert(cur->bc_tp, pag_group(pag), bno, 1,  in xfs_rmapbt_free_block()
152 	return cur->bc_mp->m_rmap_mnr[level != 0];  in xfs_rmapbt_get_minrecs()
160 	return cur->bc_mp->m_rmap_mxr[level != 0];  in xfs_rmapbt_get_maxrecs()
170 	return rec->rmap.rm_offset & ~cpu_to_be64(XFS_RMAP_OFF_UNWRITTEN);  in ondisk_rec_offset_to_key()
178 	key->rmap.rm_startblock = rec->rmap.rm_startblock;  in xfs_rmapbt_init_key_from_rec()
179 	key->rmap.rm_owner = rec->rmap.rm_owner;  in xfs_rmapbt_init_key_from_rec()
180 	key->rmap.rm_offset = ondisk_rec_offset_to_key(rec);  in xfs_rmapbt_init_key_from_rec()
184  * The high key for a reverse mapping record can be computed by shifting
186  * to that record.  In practice this means that we add blockcount-1 to
187  * the startblock for all records, and if the record is for a data/attr
188  * fork mapping, we add blockcount-1 to the offset too.
198 	adj = be32_to_cpu(rec->rmap.rm_blockcount) - 1;  in xfs_rmapbt_init_high_key_from_rec()
200 	key->rmap.rm_startblock = rec->rmap.rm_startblock;  in xfs_rmapbt_init_high_key_from_rec()
201 	be32_add_cpu(&key->rmap.rm_startblock, adj);  in xfs_rmapbt_init_high_key_from_rec()
202 	key->rmap.rm_owner = rec->rmap.rm_owner;  in xfs_rmapbt_init_high_key_from_rec()
203 	key->rmap.rm_offset = ondisk_rec_offset_to_key(rec);  in xfs_rmapbt_init_high_key_from_rec()
204 	if (XFS_RMAP_NON_INODE_OWNER(be64_to_cpu(rec->rmap.rm_owner)) ||  in xfs_rmapbt_init_high_key_from_rec()
205 	    XFS_RMAP_IS_BMBT_BLOCK(be64_to_cpu(rec->rmap.rm_offset)))  in xfs_rmapbt_init_high_key_from_rec()
207 	off = be64_to_cpu(key->rmap.rm_offset);  in xfs_rmapbt_init_high_key_from_rec()
209 	key->rmap.rm_offset = cpu_to_be64(off);  in xfs_rmapbt_init_high_key_from_rec()
217 	rec->rmap.rm_startblock = cpu_to_be32(cur->bc_rec.r.rm_startblock);  in xfs_rmapbt_init_rec_from_cur()
218 	rec->rmap.rm_blockcount = cpu_to_be32(cur->bc_rec.r.rm_blockcount);  in xfs_rmapbt_init_rec_from_cur()
219 	rec->rmap.rm_owner = cpu_to_be64(cur->bc_rec.r.rm_owner);  in xfs_rmapbt_init_rec_from_cur()
220 	rec->rmap.rm_offset = cpu_to_be64(  in xfs_rmapbt_init_rec_from_cur()
221 			xfs_rmap_irec_offset_pack(&cur->bc_rec.r));  in xfs_rmapbt_init_rec_from_cur()
229 	struct xfs_agf		*agf = cur->bc_ag.agbp->b_addr;  in xfs_rmapbt_init_ptr_from_cur()
231 	ASSERT(cur->bc_group->xg_gno == be32_to_cpu(agf->agf_seqno));  in xfs_rmapbt_init_ptr_from_cur()
233 	ptr->s = agf->agf_rmap_root;  in xfs_rmapbt_init_ptr_from_cur()
251 	struct xfs_rmap_irec		*rec = &cur->bc_rec.r;  in xfs_rmapbt_key_diff()
252 	const struct xfs_rmap_key	*kp = &key->rmap;  in xfs_rmapbt_key_diff()
256 	d = (int64_t)be32_to_cpu(kp->rm_startblock) - rec->rm_startblock;  in xfs_rmapbt_key_diff()
260 	x = be64_to_cpu(kp->rm_owner);  in xfs_rmapbt_key_diff()
261 	y = rec->rm_owner;  in xfs_rmapbt_key_diff()
265 		return -1;  in xfs_rmapbt_key_diff()
267 	x = offset_keymask(be64_to_cpu(kp->rm_offset));  in xfs_rmapbt_key_diff()
272 		return -1;  in xfs_rmapbt_key_diff()
283 	const struct xfs_rmap_key	*kp1 = &k1->rmap;  in xfs_rmapbt_diff_two_keys()
284 	const struct xfs_rmap_key	*kp2 = &k2->rmap;  in xfs_rmapbt_diff_two_keys()
289 	ASSERT(!mask || mask->rmap.rm_startblock);  in xfs_rmapbt_diff_two_keys()
291 	d = (int64_t)be32_to_cpu(kp1->rm_startblock) -  in xfs_rmapbt_diff_two_keys()
292 		     be32_to_cpu(kp2->rm_startblock);  in xfs_rmapbt_diff_two_keys()
296 	if (!mask || mask->rmap.rm_owner) {  in xfs_rmapbt_diff_two_keys()
297 		x = be64_to_cpu(kp1->rm_owner);  in xfs_rmapbt_diff_two_keys()
298 		y = be64_to_cpu(kp2->rm_owner);  in xfs_rmapbt_diff_two_keys()
302 			return -1;  in xfs_rmapbt_diff_two_keys()
305 	if (!mask || mask->rmap.rm_offset) {  in xfs_rmapbt_diff_two_keys()
307 		ASSERT(!mask || mask->rmap.rm_owner);  in xfs_rmapbt_diff_two_keys()
309 		x = offset_keymask(be64_to_cpu(kp1->rm_offset));  in xfs_rmapbt_diff_two_keys()
310 		y = offset_keymask(be64_to_cpu(kp2->rm_offset));  in xfs_rmapbt_diff_two_keys()
314 			return -1;  in xfs_rmapbt_diff_two_keys()
324 	struct xfs_mount	*mp = bp->b_mount;  in xfs_rmapbt_verify()
326 	struct xfs_perag	*pag = bp->b_pag;  in xfs_rmapbt_verify()
342 	if (!xfs_verify_magic(bp, block->bb_magic))  in xfs_rmapbt_verify()
351 	level = be16_to_cpu(block->bb_level);  in xfs_rmapbt_verify()
353 		unsigned int	maxlevel = pag->pagf_rmap_level;  in xfs_rmapbt_verify()
362 				pag->pagf_repair_rmap_level);  in xfs_rmapbt_verify()
366 	} else if (level >= mp->m_rmap_maxlevels)  in xfs_rmapbt_verify()
369 	return xfs_btree_agblock_verify(bp, mp->m_rmap_mxr[level != 0]);  in xfs_rmapbt_verify()
379 		xfs_verifier_error(bp, -EFSBADCRC, __this_address);  in xfs_rmapbt_read_verify()
383 			xfs_verifier_error(bp, -EFSCORRUPTED, fa);  in xfs_rmapbt_read_verify()
386 	if (bp->b_error)  in xfs_rmapbt_read_verify()
399 		xfs_verifier_error(bp, -EFSCORRUPTED, fa);  in xfs_rmapbt_write_verify()
425 	x = be32_to_cpu(k1->rmap.rm_startblock);  in xfs_rmapbt_keys_inorder()
426 	y = be32_to_cpu(k2->rmap.rm_startblock);  in xfs_rmapbt_keys_inorder()
431 	a = be64_to_cpu(k1->rmap.rm_owner);  in xfs_rmapbt_keys_inorder()
432 	b = be64_to_cpu(k2->rmap.rm_owner);  in xfs_rmapbt_keys_inorder()
437 	a = offset_keymask(be64_to_cpu(k1->rmap.rm_offset));  in xfs_rmapbt_keys_inorder()
438 	b = offset_keymask(be64_to_cpu(k2->rmap.rm_offset));  in xfs_rmapbt_keys_inorder()
455 	x = be32_to_cpu(r1->rmap.rm_startblock);  in xfs_rmapbt_recs_inorder()
456 	y = be32_to_cpu(r2->rmap.rm_startblock);  in xfs_rmapbt_recs_inorder()
461 	a = be64_to_cpu(r1->rmap.rm_owner);  in xfs_rmapbt_recs_inorder()
462 	b = be64_to_cpu(r2->rmap.rm_owner);  in xfs_rmapbt_recs_inorder()
467 	a = offset_keymask(be64_to_cpu(r1->rmap.rm_offset));  in xfs_rmapbt_recs_inorder()
468 	b = offset_keymask(be64_to_cpu(r2->rmap.rm_offset));  in xfs_rmapbt_recs_inorder()
481 	ASSERT(!mask || mask->rmap.rm_startblock);  in xfs_rmapbt_keys_contiguous()
488 	ASSERT(!mask || (!mask->rmap.rm_owner && !mask->rmap.rm_offset));  in xfs_rmapbt_keys_contiguous()
490 	return xbtree_key_contig(be32_to_cpu(key1->rmap.rm_startblock),  in xfs_rmapbt_keys_contiguous()
491 				 be32_to_cpu(key2->rmap.rm_startblock));  in xfs_rmapbt_keys_contiguous()
527  * Create a new reverse mapping btree cursor.
541 			mp->m_rmap_maxlevels, xfs_rmapbt_cur_cache);  in xfs_rmapbt_init_cursor()
542 	cur->bc_group = xfs_group_hold(pag_group(pag));  in xfs_rmapbt_init_cursor()
543 	cur->bc_ag.agbp = agbp;  in xfs_rmapbt_init_cursor()
545 		struct xfs_agf		*agf = agbp->b_addr;  in xfs_rmapbt_init_cursor()
547 		cur->bc_nlevels = be32_to_cpu(agf->agf_rmap_level);  in xfs_rmapbt_init_cursor()
565  * Validate an in-memory rmap btree block.  Callers are allowed to generate an
566  * in-memory btree even if the ondisk feature is not enabled.
577 	if (!xfs_verify_magic(bp, block->bb_magic))  in xfs_rmapbt_mem_verify()
584 	level = be16_to_cpu(block->bb_level);  in xfs_rmapbt_mem_verify()
589 			XFBNO_BLOCKSIZE - XFS_BTREE_LBLOCK_CRC_LEN, level == 0);  in xfs_rmapbt_mem_verify()
600 		xfs_verifier_error(bp, -EFSCORRUPTED, fa);  in xfs_rmapbt_mem_rw_verify()
603 /* skip crc checks on in-memory btrees to save time */
643 /* Create a cursor for an in-memory btree. */
654 	cur->bc_mem.xfbtree = xfbt;  in xfs_rmapbt_mem_cursor()
655 	cur->bc_nlevels = xfbt->nlevels;  in xfs_rmapbt_mem_cursor()
657 	cur->bc_group = xfs_group_hold(pag_group(pag));  in xfs_rmapbt_mem_cursor()
661 /* Create an in-memory rmap btree. */
669 	xfbt->owner = agno;  in xfs_rmapbt_mem_init()
673 /* Compute the max possible height for reverse mapping btrees in memory. */
680 	blocklen = XFBNO_BLOCKSIZE - XFS_BTREE_LBLOCK_CRC_LEN;  in xfs_rmapbt_mem_maxlevels()
686 	 * How tall can an in-memory rmap btree become if we filled the entire  in xfs_rmapbt_mem_maxlevels()
697  * Install a new reverse mapping btree root.  Caller is responsible for
706 	struct xfs_agf		*agf = agbp->b_addr;  in xfs_rmapbt_commit_staged_btree()
707 	struct xbtree_afakeroot	*afake = cur->bc_ag.afake;  in xfs_rmapbt_commit_staged_btree()
709 	ASSERT(cur->bc_flags & XFS_BTREE_STAGING);  in xfs_rmapbt_commit_staged_btree()
711 	agf->agf_rmap_root = cpu_to_be32(afake->af_root);  in xfs_rmapbt_commit_staged_btree()
712 	agf->agf_rmap_level = cpu_to_be32(afake->af_levels);  in xfs_rmapbt_commit_staged_btree()
713 	agf->agf_rmap_blocks = cpu_to_be32(afake->af_blocks);  in xfs_rmapbt_commit_staged_btree()
719 /* Calculate number of records in a reverse mapping btree block. */
740 	blocklen -= XFS_RMAP_BLOCK_LEN;  in xfs_rmapbt_maxrecs()
744 /* Compute the max possible height for reverse mapping btrees. */
751 	blocklen = XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN;  in xfs_rmapbt_maxlevels_ondisk()
777 		mp->m_rmap_maxlevels = 0;  in xfs_rmapbt_compute_maxlevels()
795 		mp->m_rmap_maxlevels = xfs_btree_space_to_height(mp->m_rmap_mnr,  in xfs_rmapbt_compute_maxlevels()
796 				mp->m_sb.sb_agblocks);  in xfs_rmapbt_compute_maxlevels()
802 		mp->m_rmap_maxlevels = xfs_btree_compute_maxlevels(  in xfs_rmapbt_compute_maxlevels()
803 				mp->m_rmap_mnr, mp->m_sb.sb_agblocks);  in xfs_rmapbt_compute_maxlevels()
805 	ASSERT(mp->m_rmap_maxlevels <= xfs_rmapbt_maxlevels_ondisk());  in xfs_rmapbt_compute_maxlevels()
814 	return xfs_btree_calc_size(mp->m_rmap_mnr, len);  in xfs_rmapbt_calc_size()
826 	if (mp->m_rmap_mxr[0] == 0)  in xfs_rmapbt_max_size()
856 	agf = agbp->b_addr;  in xfs_rmapbt_calc_reserves()
857 	agblocks = be32_to_cpu(agf->agf_length);  in xfs_rmapbt_calc_reserves()
858 	tree_len = be32_to_cpu(agf->agf_rmap_blocks);  in xfs_rmapbt_calc_reserves()
867 		agblocks -= mp->m_sb.sb_logblocks;  in xfs_rmapbt_calc_reserves()
884 		return -ENOMEM;  in xfs_rmapbt_init_cur_cache()