1 // SPDX-License-Identifier: GPL-2.0
3  * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
49 	__be32				magic = ops->buf_ops->magic[idx];  in xfs_btree_magic()
51 	/* Ensure we asked for crc for crc-only magics. */  in xfs_btree_magic()
63  * on x86-64. Yes, gcc-11 fails to inline them, and explicit inlining of these
127 	struct xfs_btree_block	*block,  in __xfs_btree_check_lblock_hdr()  argument
131 	struct xfs_mount	*mp = cur->bc_mp;  in __xfs_btree_check_lblock_hdr()
134 		if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid))  in __xfs_btree_check_lblock_hdr()
136 		if (block->bb_u.l.bb_blkno !=  in __xfs_btree_check_lblock_hdr()
139 		if (block->bb_u.l.bb_pad != cpu_to_be32(0))  in __xfs_btree_check_lblock_hdr()
143 	if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(mp, cur->bc_ops))  in __xfs_btree_check_lblock_hdr()
145 	if (be16_to_cpu(block->bb_level) != level)  in __xfs_btree_check_lblock_hdr()
147 	if (be16_to_cpu(block->bb_numrecs) >  in __xfs_btree_check_lblock_hdr()
148 	    cur->bc_ops->get_maxrecs(cur, level))  in __xfs_btree_check_lblock_hdr()
155  * Check a long btree block header.  Return the address of the failing check,
161 	struct xfs_btree_block	*block,  in __xfs_btree_check_fsblock()  argument
165 	struct xfs_mount	*mp = cur->bc_mp;  in __xfs_btree_check_fsblock()
169 	fa = __xfs_btree_check_lblock_hdr(cur, block, level, bp);  in __xfs_btree_check_fsblock()
174 	 * For inode-rooted btrees, the root block sits in the inode fork.  In  in __xfs_btree_check_fsblock()
175 	 * that case bp is NULL, and the block must not have any siblings.  in __xfs_btree_check_fsblock()
178 		if (block->bb_u.l.bb_leftsib != cpu_to_be64(NULLFSBLOCK))  in __xfs_btree_check_fsblock()
180 		if (block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK))  in __xfs_btree_check_fsblock()
187 			block->bb_u.l.bb_leftsib);  in __xfs_btree_check_fsblock()
190 				block->bb_u.l.bb_rightsib);  in __xfs_btree_check_fsblock()
195  * Check an in-memory btree block header.  Return the address of the failing
201 	struct xfs_btree_block	*block,  in __xfs_btree_check_memblock()  argument
205 	struct xfs_buftarg	*btp = cur->bc_mem.xfbtree->target;  in __xfs_btree_check_memblock()
209 	fa = __xfs_btree_check_lblock_hdr(cur, block, level, bp);  in __xfs_btree_check_memblock()
215 			block->bb_u.l.bb_leftsib);  in __xfs_btree_check_memblock()
218 				block->bb_u.l.bb_rightsib);  in __xfs_btree_check_memblock()
223  * Check a short btree block header.  Return the address of the failing check,
229 	struct xfs_btree_block	*block,  in __xfs_btree_check_agblock()  argument
233 	struct xfs_mount	*mp = cur->bc_mp;  in __xfs_btree_check_agblock()
234 	struct xfs_perag	*pag = to_perag(cur->bc_group);  in __xfs_btree_check_agblock()
239 		if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid))  in __xfs_btree_check_agblock()
241 		if (block->bb_u.s.bb_blkno != cpu_to_be64(xfs_buf_daddr(bp)))  in __xfs_btree_check_agblock()
245 	if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(mp, cur->bc_ops))  in __xfs_btree_check_agblock()
247 	if (be16_to_cpu(block->bb_level) != level)  in __xfs_btree_check_agblock()
249 	if (be16_to_cpu(block->bb_numrecs) >  in __xfs_btree_check_agblock()
250 	    cur->bc_ops->get_maxrecs(cur, level))  in __xfs_btree_check_agblock()
255 			block->bb_u.s.bb_leftsib);  in __xfs_btree_check_agblock()
258 				block->bb_u.s.bb_rightsib);  in __xfs_btree_check_agblock()
263  * Internal btree block check.
265  * Return NULL if the block is ok or the address of the failed check otherwise.
270 	struct xfs_btree_block	*block,  in __xfs_btree_check_block()  argument
274 	switch (cur->bc_ops->type) {  in __xfs_btree_check_block()
276 		return __xfs_btree_check_memblock(cur, block, level, bp);  in __xfs_btree_check_block()
278 		return __xfs_btree_check_agblock(cur, block, level, bp);  in __xfs_btree_check_block()
280 		return __xfs_btree_check_fsblock(cur, block, level, bp);  in __xfs_btree_check_block()
289 	if (cur->bc_ops->ptr_len == XFS_BTREE_SHORT_PTR_LEN)  in xfs_btree_block_errtag()
295  * Debug routine: check that block header is ok.
300 	struct xfs_btree_block	*block,	/* generic btree block pointer */  in xfs_btree_check_block()  argument
301 	int			level,	/* level of the btree block */  in xfs_btree_check_block()
302 	struct xfs_buf		*bp)	/* buffer containing block, if any */  in xfs_btree_check_block()
304 	struct xfs_mount	*mp = cur->bc_mp;  in xfs_btree_check_block()
307 	fa = __xfs_btree_check_block(cur, block, level, bp);  in xfs_btree_check_block()
313 		return -EFSCORRUPTED;  in xfs_btree_check_block()
326 		return -EFSCORRUPTED;  in __xfs_btree_check_ptr()
328 	switch (cur->bc_ops->type) {  in __xfs_btree_check_ptr()
330 		if (!xfbtree_verify_bno(cur->bc_mem.xfbtree,  in __xfs_btree_check_ptr()
331 				be64_to_cpu((&ptr->l)[index])))  in __xfs_btree_check_ptr()
332 			return -EFSCORRUPTED;  in __xfs_btree_check_ptr()
335 		if (!xfs_verify_fsbno(cur->bc_mp,  in __xfs_btree_check_ptr()
336 				be64_to_cpu((&ptr->l)[index])))  in __xfs_btree_check_ptr()
337 			return -EFSCORRUPTED;  in __xfs_btree_check_ptr()
340 		if (!xfs_verify_agbno(to_perag(cur->bc_group),  in __xfs_btree_check_ptr()
341 				be32_to_cpu((&ptr->s)[index])))  in __xfs_btree_check_ptr()
342 			return -EFSCORRUPTED;  in __xfs_btree_check_ptr()
364 		switch (cur->bc_ops->type) {  in xfs_btree_check_ptr()
366 			xfs_err(cur->bc_mp,  in xfs_btree_check_ptr()
367 "In-memory: Corrupt %sbt flags 0x%x pointer at level %d index %d fa %pS.",  in xfs_btree_check_ptr()
368 				cur->bc_ops->name, cur->bc_flags, level, index,  in xfs_btree_check_ptr()
372 			xfs_err(cur->bc_mp,  in xfs_btree_check_ptr()
374 				cur->bc_ino.ip->i_ino,  in xfs_btree_check_ptr()
375 				cur->bc_ino.whichfork, cur->bc_ops->name,  in xfs_btree_check_ptr()
379 			xfs_err(cur->bc_mp,  in xfs_btree_check_ptr()
381 				cur->bc_group->xg_gno, cur->bc_ops->name,  in xfs_btree_check_ptr()
398  * Calculate CRC on the whole btree block and stuff it into the
399  * long-form btree header.
409 	struct xfs_btree_block	*block = XFS_BUF_TO_BLOCK(bp);  in xfs_btree_fsblock_calc_crc()  local
410 	struct xfs_buf_log_item	*bip = bp->b_log_item;  in xfs_btree_fsblock_calc_crc()
412 	if (!xfs_has_crc(bp->b_mount))  in xfs_btree_fsblock_calc_crc()
415 		block->bb_u.l.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn);  in xfs_btree_fsblock_calc_crc()
423 	struct xfs_btree_block	*block = XFS_BUF_TO_BLOCK(bp);  in xfs_btree_fsblock_verify_crc()  local
424 	struct xfs_mount	*mp = bp->b_mount;  in xfs_btree_fsblock_verify_crc()
427 		if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.l.bb_lsn)))  in xfs_btree_fsblock_verify_crc()
436  * Calculate CRC on the whole btree block and stuff it into the
437  * short-form btree header.
447 	struct xfs_btree_block	*block = XFS_BUF_TO_BLOCK(bp);  in xfs_btree_agblock_calc_crc()  local
448 	struct xfs_buf_log_item	*bip = bp->b_log_item;  in xfs_btree_agblock_calc_crc()
450 	if (!xfs_has_crc(bp->b_mount))  in xfs_btree_agblock_calc_crc()
453 		block->bb_u.s.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn);  in xfs_btree_agblock_calc_crc()
461 	struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);  in xfs_btree_agblock_verify_crc()  local
462 	struct xfs_mount	*mp = bp->b_mount;  in xfs_btree_agblock_verify_crc()
465 		if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.s.bb_lsn)))  in xfs_btree_agblock_verify_crc()
483 	 * Don't allow block freeing for a staging cursor, because staging  in xfs_btree_free_block()
486 	if (unlikely(cur->bc_flags & XFS_BTREE_STAGING)) {  in xfs_btree_free_block()
488 		return -EFSCORRUPTED;  in xfs_btree_free_block()
491 	error = cur->bc_ops->free_block(cur, bp);  in xfs_btree_free_block()
493 		xfs_trans_binval(cur->bc_tp, bp);  in xfs_btree_free_block()
516 	for (i = 0; i < cur->bc_nlevels; i++) {  in xfs_btree_del_cursor()
517 		if (cur->bc_levels[i].bp)  in xfs_btree_del_cursor()
518 			xfs_trans_brelse(cur->bc_tp, cur->bc_levels[i].bp);  in xfs_btree_del_cursor()
529 	ASSERT(!xfs_btree_is_bmap(cur->bc_ops) || cur->bc_bmap.allocated == 0 ||  in xfs_btree_del_cursor()
530 	       xfs_is_shutdown(cur->bc_mp) || error != 0);  in xfs_btree_del_cursor()
532 	if (cur->bc_group)  in xfs_btree_del_cursor()
533 		xfs_group_put(cur->bc_group);  in xfs_btree_del_cursor()
534 	kmem_cache_free(cur->bc_cache, cur);  in xfs_btree_del_cursor()
542 	if (cur->bc_ops->type == XFS_BTREE_TYPE_MEM)  in xfs_btree_buftarg()
543 		return cur->bc_mem.xfbtree->target;  in xfs_btree_buftarg()
544 	return cur->bc_mp->m_ddev_targp;  in xfs_btree_buftarg()
547 /* Return the block size (in units of 512b sectors) for this btree. */
552 	if (cur->bc_ops->type == XFS_BTREE_TYPE_MEM)  in xfs_btree_bbsize()
554 	return cur->bc_mp->m_bsize;  in xfs_btree_bbsize()
559  * Allocate a new one, copy the record, re-get the buffers.
566 	struct xfs_mount	*mp = cur->bc_mp;  in xfs_btree_dup_cursor()
567 	struct xfs_trans	*tp = cur->bc_tp;  in xfs_btree_dup_cursor()
577 	if (unlikely(cur->bc_flags & XFS_BTREE_STAGING)) {  in xfs_btree_dup_cursor()
579 		return -EFSCORRUPTED;  in xfs_btree_dup_cursor()
585 	new = cur->bc_ops->dup_cursor(cur);  in xfs_btree_dup_cursor()
588 	 * Copy the record currently in the cursor.  in xfs_btree_dup_cursor()
590 	new->bc_rec = cur->bc_rec;  in xfs_btree_dup_cursor()
593 	 * For each level current, re-get the buffer and copy the ptr value.  in xfs_btree_dup_cursor()
595 	for (i = 0; i < new->bc_nlevels; i++) {  in xfs_btree_dup_cursor()
596 		new->bc_levels[i].ptr = cur->bc_levels[i].ptr;  in xfs_btree_dup_cursor()
597 		new->bc_levels[i].ra = cur->bc_levels[i].ra;  in xfs_btree_dup_cursor()
598 		bp = cur->bc_levels[i].bp;  in xfs_btree_dup_cursor()
604 					cur->bc_ops->buf_ops);  in xfs_btree_dup_cursor()
613 		new->bc_levels[i].bp = bp;  in xfs_btree_dup_cursor()
620  * XFS btree block layout and addressing:
622  * There are two types of blocks in the btree: leaf and non-leaf blocks.
625  * the values.  A non-leaf block also starts with the same header, and
629  *		+--------+-------+-------+-------+-------+-------+-------+
631  *		+--------+-------+-------+-------+-------+-------+-------+
633  *		+--------+-------+-------+-------+-------+-------+-------+
634  * Non-Leaf:	| header | key 1 | key 2 | key N | ptr 1 | ptr 2 | ptr N |
635  *		+--------+-------+-------+-------+-------+-------+-------+
638  * and comes in different versions for short (32bit) and long (64bit) block
640  * and opaque to the btree core.  The block pointers are simple disk endian
644  * into a btree block (xfs_btree_*_offset) or return a pointer to the given
646  * inside the btree block is done using indices starting at one, not zero!
651  * However, nodes are different: each pointer has two associated keys -- one
652  * indexing the lowest key available in the block(s) below (the same behavior
654  * available in the block(s) below.  Because records are /not/ sorted by the
655  * highest key, all leaf block updates require us to compute the highest key
660  *		+--------+-----+-----+-----+-----+-----+-------+-------+-----+
661  * Non-Leaf:	| header | lo1 | hi1 | lo2 | hi2 | ... | ptr 1 | ptr 2 | ... |
662  *		+--------+-----+-----+-----+-----+-----+-------+-------+-----+
665  * depth-first search and use the low and high keys to decide if we can skip
668  * entries.  For a non-overlapped tree, simply search for the record associated
669  * with the lowest key and iterate forward until a non-matching record is
677  * 1: +- file A startblock B offset C length D -----------+
678  * 2:      +- file E startblock F offset G length H --------------+
679  * 3:      +- file I startblock F offset J length K --+
680  * 4:                                                        +- file L... --+
682  * Now say we want to map block (B+D) into file A at offset (C+D).  Ideally,
684  * that ends at (B+D-1) (i.e. record 1)?  A LE lookup of (B+D-1) would return
686  * query would return records 1 and 2 because they both overlap (B+D-1), and
689  * In the non-overlapped case you can do a LE lookup and decrement the cursor
694  * Return size of the btree block header for this btree instance.
698 	if (cur->bc_ops->ptr_len == XFS_BTREE_LONG_PTR_LEN) {  in xfs_btree_block_len()
699 		if (xfs_has_crc(cur->bc_mp))  in xfs_btree_block_len()
703 	if (xfs_has_crc(cur->bc_mp))  in xfs_btree_block_len()
709  * Calculate offset of the n-th record in a btree block.
717 		(n - 1) * cur->bc_ops->rec_len;  in xfs_btree_rec_offset()
721  * Calculate offset of the n-th key in a btree block.
729 		(n - 1) * cur->bc_ops->key_len;  in xfs_btree_key_offset()
733  * Calculate offset of the n-th high key in a btree block.
741 		(n - 1) * cur->bc_ops->key_len + (cur->bc_ops->key_len / 2);  in xfs_btree_high_key_offset()
745  * Calculate offset of the n-th block pointer in a btree block.
754 		cur->bc_ops->get_maxrecs(cur, level) * cur->bc_ops->key_len +  in xfs_btree_ptr_offset()
755 		(n - 1) * cur->bc_ops->ptr_len;  in xfs_btree_ptr_offset()
759  * Return a pointer to the n-th record in the btree block.
765 	struct xfs_btree_block	*block)  in xfs_btree_rec_addr()  argument
768 		((char *)block + xfs_btree_rec_offset(cur, n));  in xfs_btree_rec_addr()
772  * Return a pointer to the n-th key in the btree block.
778 	struct xfs_btree_block	*block)  in xfs_btree_key_addr()  argument
781 		((char *)block + xfs_btree_key_offset(cur, n));  in xfs_btree_key_addr()
785  * Return a pointer to the n-th high key in the btree block.
791 	struct xfs_btree_block	*block)  in xfs_btree_high_key_addr()  argument
794 		((char *)block + xfs_btree_high_key_offset(cur, n));  in xfs_btree_high_key_addr()
798  * Return a pointer to the n-th block pointer in the btree block.
804 	struct xfs_btree_block	*block)  in xfs_btree_ptr_addr()  argument
806 	int			level = xfs_btree_get_level(block);  in xfs_btree_ptr_addr()
808 	ASSERT(block->bb_level != 0);  in xfs_btree_ptr_addr()
811 		((char *)block + xfs_btree_ptr_offset(cur, n, level));  in xfs_btree_ptr_addr()
818 	ASSERT(cur->bc_ops->type == XFS_BTREE_TYPE_INODE);  in xfs_btree_ifork_ptr()
820 	if (cur->bc_flags & XFS_BTREE_STAGING)  in xfs_btree_ifork_ptr()
821 		return cur->bc_ino.ifake->if_fork;  in xfs_btree_ifork_ptr()
822 	return xfs_ifork_ptr(cur->bc_ino.ip, cur->bc_ino.whichfork);  in xfs_btree_ifork_ptr()
826  * Get the root block which is stored in the inode.
837 	return (struct xfs_btree_block *)ifp->if_broot;  in xfs_btree_get_iroot()
841  * Retrieve the block pointer from the cursor at the given level.
844 struct xfs_btree_block *		/* generic btree block pointer */
848 	struct xfs_buf		**bpp)	/* buffer containing the block */  in xfs_btree_get_block()
855 	*bpp = cur->bc_levels[level].bp;  in xfs_btree_get_block()
868 	struct xfs_btree_block	*block;	/* generic btree block pointer */  in xfs_btree_firstrec()  local
869 	struct xfs_buf		*bp;	/* buffer containing block */  in xfs_btree_firstrec()
872 	 * Get the block pointer for this level.  in xfs_btree_firstrec()
874 	block = xfs_btree_get_block(cur, level, &bp);  in xfs_btree_firstrec()
875 	if (xfs_btree_check_block(cur, block, level, bp))  in xfs_btree_firstrec()
880 	if (!block->bb_numrecs)  in xfs_btree_firstrec()
885 	cur->bc_levels[level].ptr = 1;  in xfs_btree_firstrec()
890  * Change the cursor to point to the last record in the current block
898 	struct xfs_btree_block	*block;	/* generic btree block pointer */  in xfs_btree_lastrec()  local
899 	struct xfs_buf		*bp;	/* buffer containing block */  in xfs_btree_lastrec()
902 	 * Get the block pointer for this level.  in xfs_btree_lastrec()
904 	block = xfs_btree_get_block(cur, level, &bp);  in xfs_btree_lastrec()
905 	if (xfs_btree_check_block(cur, block, level, bp))  in xfs_btree_lastrec()
910 	if (!block->bb_numrecs)  in xfs_btree_lastrec()
915 	cur->bc_levels[level].ptr = be16_to_cpu(block->bb_numrecs);  in xfs_btree_lastrec()
947 	for (i = nbits - 1, imask = 1u << i; ; i--, imask >>= 1) {  in xfs_btree_offsets()
949 			*last = offsets[i + 1] - 1;  in xfs_btree_offsets()
959 	struct xfs_btree_block	*block)  in xfs_btree_readahead_fsblock()  argument
961 	struct xfs_mount	*mp = cur->bc_mp;  in xfs_btree_readahead_fsblock()
962 	xfs_fsblock_t		left = be64_to_cpu(block->bb_u.l.bb_leftsib);  in xfs_btree_readahead_fsblock()
963 	xfs_fsblock_t		right = be64_to_cpu(block->bb_u.l.bb_rightsib);  in xfs_btree_readahead_fsblock()
967 		xfs_buf_readahead(mp->m_ddev_targp, XFS_FSB_TO_DADDR(mp, left),  in xfs_btree_readahead_fsblock()
968 				mp->m_bsize, cur->bc_ops->buf_ops);  in xfs_btree_readahead_fsblock()
973 		xfs_buf_readahead(mp->m_ddev_targp, XFS_FSB_TO_DADDR(mp, right),  in xfs_btree_readahead_fsblock()
974 				mp->m_bsize, cur->bc_ops->buf_ops);  in xfs_btree_readahead_fsblock()
985 	struct xfs_btree_block	*block)  in xfs_btree_readahead_memblock()  argument
987 	struct xfs_buftarg	*btp = cur->bc_mem.xfbtree->target;  in xfs_btree_readahead_memblock()
988 	xfbno_t			left = be64_to_cpu(block->bb_u.l.bb_leftsib);  in xfs_btree_readahead_memblock()
989 	xfbno_t			right = be64_to_cpu(block->bb_u.l.bb_rightsib);  in xfs_btree_readahead_memblock()
994 				cur->bc_ops->buf_ops);  in xfs_btree_readahead_memblock()
1000 				cur->bc_ops->buf_ops);  in xfs_btree_readahead_memblock()
1011 	struct xfs_btree_block	*block)  in xfs_btree_readahead_agblock()  argument
1013 	struct xfs_mount	*mp = cur->bc_mp;  in xfs_btree_readahead_agblock()
1014 	struct xfs_perag	*pag = to_perag(cur->bc_group);  in xfs_btree_readahead_agblock()
1015 	xfs_agblock_t		left = be32_to_cpu(block->bb_u.s.bb_leftsib);  in xfs_btree_readahead_agblock()
1016 	xfs_agblock_t		right = be32_to_cpu(block->bb_u.s.bb_rightsib);  in xfs_btree_readahead_agblock()
1020 		xfs_buf_readahead(mp->m_ddev_targp,  in xfs_btree_readahead_agblock()
1021 				xfs_agbno_to_daddr(pag, left), mp->m_bsize,  in xfs_btree_readahead_agblock()
1022 				cur->bc_ops->buf_ops);  in xfs_btree_readahead_agblock()
1027 		xfs_buf_readahead(mp->m_ddev_targp,  in xfs_btree_readahead_agblock()
1028 				xfs_agbno_to_daddr(pag, right), mp->m_bsize,  in xfs_btree_readahead_agblock()
1029 				cur->bc_ops->buf_ops);  in xfs_btree_readahead_agblock()
1037  * Read-ahead btree blocks, at the given level.
1046 	struct xfs_btree_block	*block;  in xfs_btree_readahead()  local
1055 	if ((cur->bc_levels[lev].ra | lr) == cur->bc_levels[lev].ra)  in xfs_btree_readahead()
1058 	cur->bc_levels[lev].ra |= lr;  in xfs_btree_readahead()
1059 	block = XFS_BUF_TO_BLOCK(cur->bc_levels[lev].bp);  in xfs_btree_readahead()
1061 	switch (cur->bc_ops->type) {  in xfs_btree_readahead()
1063 		return xfs_btree_readahead_agblock(cur, lr, block);  in xfs_btree_readahead()
1065 		return xfs_btree_readahead_fsblock(cur, lr, block);  in xfs_btree_readahead()
1067 		return xfs_btree_readahead_memblock(cur, lr, block);  in xfs_btree_readahead()
1086 	switch (cur->bc_ops->type) {  in xfs_btree_ptr_to_daddr()
1088 		*daddr = xfs_agbno_to_daddr(to_perag(cur->bc_group),  in xfs_btree_ptr_to_daddr()
1089 				be32_to_cpu(ptr->s));  in xfs_btree_ptr_to_daddr()
1092 		*daddr = XFS_FSB_TO_DADDR(cur->bc_mp, be64_to_cpu(ptr->l));  in xfs_btree_ptr_to_daddr()
1095 		*daddr = xfbno_to_daddr(be64_to_cpu(ptr->l));  in xfs_btree_ptr_to_daddr()
1119 			cur->bc_ops->buf_ops);  in xfs_btree_readahead_ptr()
1132 	struct xfs_btree_block	*b;	/* btree block */  in xfs_btree_setbuf()
1134 	if (cur->bc_levels[lev].bp)  in xfs_btree_setbuf()
1135 		xfs_trans_brelse(cur->bc_tp, cur->bc_levels[lev].bp);  in xfs_btree_setbuf()
1136 	cur->bc_levels[lev].bp = bp;  in xfs_btree_setbuf()
1137 	cur->bc_levels[lev].ra = 0;  in xfs_btree_setbuf()
1140 	if (cur->bc_ops->ptr_len == XFS_BTREE_LONG_PTR_LEN) {  in xfs_btree_setbuf()
1141 		if (b->bb_u.l.bb_leftsib == cpu_to_be64(NULLFSBLOCK))  in xfs_btree_setbuf()
1142 			cur->bc_levels[lev].ra |= XFS_BTCUR_LEFTRA;  in xfs_btree_setbuf()
1143 		if (b->bb_u.l.bb_rightsib == cpu_to_be64(NULLFSBLOCK))  in xfs_btree_setbuf()
1144 			cur->bc_levels[lev].ra |= XFS_BTCUR_RIGHTRA;  in xfs_btree_setbuf()
1146 		if (b->bb_u.s.bb_leftsib == cpu_to_be32(NULLAGBLOCK))  in xfs_btree_setbuf()
1147 			cur->bc_levels[lev].ra |= XFS_BTCUR_LEFTRA;  in xfs_btree_setbuf()
1148 		if (b->bb_u.s.bb_rightsib == cpu_to_be32(NULLAGBLOCK))  in xfs_btree_setbuf()
1149 			cur->bc_levels[lev].ra |= XFS_BTCUR_RIGHTRA;  in xfs_btree_setbuf()
1158 	if (cur->bc_ops->ptr_len == XFS_BTREE_LONG_PTR_LEN)  in xfs_btree_ptr_is_null()
1159 		return ptr->l == cpu_to_be64(NULLFSBLOCK);  in xfs_btree_ptr_is_null()
1161 		return ptr->s == cpu_to_be32(NULLAGBLOCK);  in xfs_btree_ptr_is_null()
1169 	if (cur->bc_ops->ptr_len == XFS_BTREE_LONG_PTR_LEN)  in xfs_btree_set_ptr_null()
1170 		ptr->l = cpu_to_be64(NULLFSBLOCK);  in xfs_btree_set_ptr_null()
1172 		ptr->s = cpu_to_be32(NULLAGBLOCK);  in xfs_btree_set_ptr_null()
1181 	if (cur->bc_ops->ptr_len == XFS_BTREE_LONG_PTR_LEN)  in xfs_btree_ptrs_equal()
1182 		return ptr1->l == ptr2->l;  in xfs_btree_ptrs_equal()
1183 	return ptr1->s == ptr2->s;  in xfs_btree_ptrs_equal()
1192 	struct xfs_btree_block	*block,  in xfs_btree_get_sibling()  argument
1198 	if (cur->bc_ops->ptr_len == XFS_BTREE_LONG_PTR_LEN) {  in xfs_btree_get_sibling()
1200 			ptr->l = block->bb_u.l.bb_rightsib;  in xfs_btree_get_sibling()
1202 			ptr->l = block->bb_u.l.bb_leftsib;  in xfs_btree_get_sibling()
1205 			ptr->s = block->bb_u.s.bb_rightsib;  in xfs_btree_get_sibling()
1207 			ptr->s = block->bb_u.s.bb_leftsib;  in xfs_btree_get_sibling()
1214 	struct xfs_btree_block		*block,  in xfs_btree_set_sibling()  argument
1220 	if (cur->bc_ops->ptr_len == XFS_BTREE_LONG_PTR_LEN) {  in xfs_btree_set_sibling()
1222 			block->bb_u.l.bb_rightsib = ptr->l;  in xfs_btree_set_sibling()
1224 			block->bb_u.l.bb_leftsib = ptr->l;  in xfs_btree_set_sibling()
1227 			block->bb_u.s.bb_rightsib = ptr->s;  in xfs_btree_set_sibling()
1229 			block->bb_u.s.bb_leftsib = ptr->s;  in xfs_btree_set_sibling()
1246 	buf->bb_magic = cpu_to_be32(magic);  in __xfs_btree_init_block()
1247 	buf->bb_level = cpu_to_be16(level);  in __xfs_btree_init_block()
1248 	buf->bb_numrecs = cpu_to_be16(numrecs);  in __xfs_btree_init_block()
1250 	if (ops->ptr_len == XFS_BTREE_LONG_PTR_LEN) {  in __xfs_btree_init_block()
1251 		buf->bb_u.l.bb_leftsib = cpu_to_be64(NULLFSBLOCK);  in __xfs_btree_init_block()
1252 		buf->bb_u.l.bb_rightsib = cpu_to_be64(NULLFSBLOCK);  in __xfs_btree_init_block()
1254 			buf->bb_u.l.bb_blkno = cpu_to_be64(blkno);  in __xfs_btree_init_block()
1255 			buf->bb_u.l.bb_owner = cpu_to_be64(owner);  in __xfs_btree_init_block()
1256 			uuid_copy(&buf->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid);  in __xfs_btree_init_block()
1257 			buf->bb_u.l.bb_pad = 0;  in __xfs_btree_init_block()
1258 			buf->bb_u.l.bb_lsn = 0;  in __xfs_btree_init_block()
1261 		buf->bb_u.s.bb_leftsib = cpu_to_be32(NULLAGBLOCK);  in __xfs_btree_init_block()
1262 		buf->bb_u.s.bb_rightsib = cpu_to_be32(NULLAGBLOCK);  in __xfs_btree_init_block()
1264 			buf->bb_u.s.bb_blkno = cpu_to_be64(blkno);  in __xfs_btree_init_block()
1266 			buf->bb_u.s.bb_owner = cpu_to_be32((__u32)owner);  in __xfs_btree_init_block()
1267 			uuid_copy(&buf->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid);  in __xfs_btree_init_block()
1268 			buf->bb_u.s.bb_lsn = 0;  in __xfs_btree_init_block()
1276 	struct xfs_btree_block	*block,  in xfs_btree_init_block()  argument
1282 	__xfs_btree_init_block(mp, block, ops, XFS_BUF_DADDR_NULL, level,  in xfs_btree_init_block()
1297 	bp->b_ops = ops->buf_ops;  in xfs_btree_init_buf()
1304 	switch (cur->bc_ops->type) {  in xfs_btree_owner()
1306 		return cur->bc_mem.xfbtree->owner;  in xfs_btree_owner()
1308 		return cur->bc_ino.ip->i_ino;  in xfs_btree_owner()
1310 		return cur->bc_group->xg_gno;  in xfs_btree_owner()
1324 	xfs_btree_init_buf(cur->bc_mp, bp, cur->bc_ops, level, numrecs,  in xfs_btree_init_block_cur()
1334 	switch (cur->bc_ops->type) {  in xfs_btree_buf_to_ptr()
1336 		ptr->s = cpu_to_be32(xfs_daddr_to_agbno(cur->bc_mp,  in xfs_btree_buf_to_ptr()
1340 		ptr->l = cpu_to_be64(XFS_DADDR_TO_FSB(cur->bc_mp,  in xfs_btree_buf_to_ptr()
1344 		ptr->l = cpu_to_be64(xfs_daddr_to_xfbno(xfs_buf_daddr(bp)));  in xfs_btree_buf_to_ptr()
1354 	xfs_buf_set_ref(bp, cur->bc_ops->lru_refs);  in xfs_btree_set_refs()
1361 	struct xfs_btree_block		**block,  in xfs_btree_get_buf_block()  argument
1370 	error = xfs_trans_get_buf(cur->bc_tp, xfs_btree_buftarg(cur), d,  in xfs_btree_get_buf_block()
1375 	(*bpp)->b_ops = cur->bc_ops->buf_ops;  in xfs_btree_get_buf_block()
1376 	*block = XFS_BUF_TO_BLOCK(*bpp);  in xfs_btree_get_buf_block()
1382  * the block pointer within the buffer.
1389 	struct xfs_btree_block		**block,  in xfs_btree_read_buf_block()  argument
1392 	struct xfs_mount	*mp = cur->bc_mp;  in xfs_btree_read_buf_block()
1402 	error = xfs_trans_read_buf(mp, cur->bc_tp, xfs_btree_buftarg(cur), d,  in xfs_btree_read_buf_block()
1404 			cur->bc_ops->buf_ops);  in xfs_btree_read_buf_block()
1411 	*block = XFS_BUF_TO_BLOCK(*bpp);  in xfs_btree_read_buf_block()
1416  * Copy keys from one btree block to another.
1426 	memcpy(dst_key, src_key, numkeys * cur->bc_ops->key_len);  in xfs_btree_copy_keys()
1430  * Copy records from one btree block to another.
1440 	memcpy(dst_rec, src_rec, numrecs * cur->bc_ops->rec_len);  in xfs_btree_copy_recs()
1444  * Copy block pointers from one btree block to another.
1454 	memcpy(dst_ptr, src_ptr, numptrs * cur->bc_ops->ptr_len);  in xfs_btree_copy_ptrs()
1458  * Shift keys one index left/right inside a single btree block.
1470 	ASSERT(dir == 1 || dir == -1);  in xfs_btree_shift_keys()
1472 	dst_key = (char *)key + (dir * cur->bc_ops->key_len);  in xfs_btree_shift_keys()
1473 	memmove(dst_key, key, numkeys * cur->bc_ops->key_len);  in xfs_btree_shift_keys()
1477  * Shift records one index left/right inside a single btree block.
1489 	ASSERT(dir == 1 || dir == -1);  in xfs_btree_shift_recs()
1491 	dst_rec = (char *)rec + (dir * cur->bc_ops->rec_len);  in xfs_btree_shift_recs()
1492 	memmove(dst_rec, rec, numrecs * cur->bc_ops->rec_len);  in xfs_btree_shift_recs()
1496  * Shift block pointers one index left/right inside a single btree block.
1508 	ASSERT(dir == 1 || dir == -1);  in xfs_btree_shift_ptrs()
1510 	dst_ptr = (char *)ptr + (dir * cur->bc_ops->ptr_len);  in xfs_btree_shift_ptrs()
1511 	memmove(dst_ptr, ptr, numptrs * cur->bc_ops->ptr_len);  in xfs_btree_shift_ptrs()
1515  * Log key values from the btree block.
1526 		xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);  in xfs_btree_log_keys()
1527 		xfs_trans_log_buf(cur->bc_tp, bp,  in xfs_btree_log_keys()
1529 				  xfs_btree_key_offset(cur, last + 1) - 1);  in xfs_btree_log_keys()
1531 		xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip,  in xfs_btree_log_keys()
1532 				xfs_ilog_fbroot(cur->bc_ino.whichfork));  in xfs_btree_log_keys()
1537  * Log record values from the btree block.
1547 		xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip,  in xfs_btree_log_recs()
1548 				xfs_ilog_fbroot(cur->bc_ino.whichfork));  in xfs_btree_log_recs()
1552 	xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);  in xfs_btree_log_recs()
1553 	xfs_trans_log_buf(cur->bc_tp, bp,  in xfs_btree_log_recs()
1555 			  xfs_btree_rec_offset(cur, last + 1) - 1);  in xfs_btree_log_recs()
1559  * Log block pointer fields from a btree block (nonleaf).
1564 	struct xfs_buf		*bp,	/* buffer containing btree block */  in xfs_btree_log_ptrs()
1570 		struct xfs_btree_block	*block = XFS_BUF_TO_BLOCK(bp);  in xfs_btree_log_ptrs()  local
1571 		int			level = xfs_btree_get_level(block);  in xfs_btree_log_ptrs()
1573 		xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);  in xfs_btree_log_ptrs()
1574 		xfs_trans_log_buf(cur->bc_tp, bp,  in xfs_btree_log_ptrs()
1576 				xfs_btree_ptr_offset(cur, last + 1, level) - 1);  in xfs_btree_log_ptrs()
1578 		xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip,  in xfs_btree_log_ptrs()
1579 			xfs_ilog_fbroot(cur->bc_ino.whichfork));  in xfs_btree_log_ptrs()
1585  * Log fields from a btree block header.
1590 	struct xfs_buf		*bp,	/* buffer containing btree block */  in xfs_btree_log_block()
1626 		if (xfs_has_crc(cur->bc_mp)) {  in xfs_btree_log_block()
1629 			 * block but instead recreate it during log  in xfs_btree_log_block()
1641 				  (cur->bc_ops->ptr_len == XFS_BTREE_LONG_PTR_LEN) ?  in xfs_btree_log_block()
1644 		xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);  in xfs_btree_log_block()
1645 		xfs_trans_log_buf(cur->bc_tp, bp, first, last);  in xfs_btree_log_block()
1647 		xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip,  in xfs_btree_log_block()
1648 			xfs_ilog_fbroot(cur->bc_ino.whichfork));  in xfs_btree_log_block()
1654  * For nonzero levels the leaf-ward information is untouched.
1662 	struct xfs_btree_block	*block;  in xfs_btree_increment()  local
1668 	ASSERT(level < cur->bc_nlevels);  in xfs_btree_increment()
1670 	/* Read-ahead to the right at this level. */  in xfs_btree_increment()
1673 	/* Get a pointer to the btree block. */  in xfs_btree_increment()
1674 	block = xfs_btree_get_block(cur, level, &bp);  in xfs_btree_increment()
1677 	error = xfs_btree_check_block(cur, block, level, bp);  in xfs_btree_increment()
1682 	/* We're done if we remain in the block after the increment. */  in xfs_btree_increment()
1683 	if (++cur->bc_levels[level].ptr <= xfs_btree_get_numrecs(block))  in xfs_btree_increment()
1687 	xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);  in xfs_btree_increment()
1695 	 * Stop when we don't go off the right edge of a block.  in xfs_btree_increment()
1697 	for (lev = level + 1; lev < cur->bc_nlevels; lev++) {  in xfs_btree_increment()
1698 		block = xfs_btree_get_block(cur, lev, &bp);  in xfs_btree_increment()
1701 		error = xfs_btree_check_block(cur, block, lev, bp);  in xfs_btree_increment()
1706 		if (++cur->bc_levels[lev].ptr <= xfs_btree_get_numrecs(block))  in xfs_btree_increment()
1709 		/* Read-ahead the right block for the next loop. */  in xfs_btree_increment()
1717 	if (lev == cur->bc_nlevels) {  in xfs_btree_increment()
1718 		if (cur->bc_ops->type == XFS_BTREE_TYPE_INODE)  in xfs_btree_increment()
1722 		error = -EFSCORRUPTED;  in xfs_btree_increment()
1725 	ASSERT(lev < cur->bc_nlevels);  in xfs_btree_increment()
1731 	for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) {  in xfs_btree_increment()
1734 		ptrp = xfs_btree_ptr_addr(cur, cur->bc_levels[lev].ptr, block);  in xfs_btree_increment()
1735 		--lev;  in xfs_btree_increment()
1736 		error = xfs_btree_read_buf_block(cur, ptrp, 0, &block, &bp);  in xfs_btree_increment()
1741 		cur->bc_levels[lev].ptr = 1;  in xfs_btree_increment()
1757  * For nonzero levels the leaf-ward information is untouched.
1765 	struct xfs_btree_block	*block;  in xfs_btree_decrement()  local
1771 	ASSERT(level < cur->bc_nlevels);  in xfs_btree_decrement()
1773 	/* Read-ahead to the left at this level. */  in xfs_btree_decrement()
1776 	/* We're done if we remain in the block after the decrement. */  in xfs_btree_decrement()
1777 	if (--cur->bc_levels[level].ptr > 0)  in xfs_btree_decrement()
1780 	/* Get a pointer to the btree block. */  in xfs_btree_decrement()
1781 	block = xfs_btree_get_block(cur, level, &bp);  in xfs_btree_decrement()
1784 	error = xfs_btree_check_block(cur, block, level, bp);  in xfs_btree_decrement()
1790 	xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB);  in xfs_btree_decrement()
1798 	 * Stop when we don't go off the left edge of a block.  in xfs_btree_decrement()
1800 	for (lev = level + 1; lev < cur->bc_nlevels; lev++) {  in xfs_btree_decrement()
1801 		if (--cur->bc_levels[lev].ptr > 0)  in xfs_btree_decrement()
1803 		/* Read-ahead the left block for the next loop. */  in xfs_btree_decrement()
1811 	if (lev == cur->bc_nlevels) {  in xfs_btree_decrement()
1812 		if (cur->bc_ops->type == XFS_BTREE_TYPE_INODE)  in xfs_btree_decrement()
1816 		error = -EFSCORRUPTED;  in xfs_btree_decrement()
1819 	ASSERT(lev < cur->bc_nlevels);  in xfs_btree_decrement()
1825 	for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) {  in xfs_btree_decrement()
1828 		ptrp = xfs_btree_ptr_addr(cur, cur->bc_levels[lev].ptr, block);  in xfs_btree_decrement()
1829 		--lev;  in xfs_btree_decrement()
1830 		error = xfs_btree_read_buf_block(cur, ptrp, 0, &block, &bp);  in xfs_btree_decrement()
1834 		cur->bc_levels[lev].ptr = xfs_btree_get_numrecs(block);  in xfs_btree_decrement()
1849  * Check the btree block owner now that we have the context to know who the
1855 	struct xfs_btree_block	*block)  in xfs_btree_check_block_owner()  argument
1859 	if (!xfs_has_crc(cur->bc_mp) ||  in xfs_btree_check_block_owner()
1860 	    (cur->bc_flags & XFS_BTREE_BMBT_INVALID_OWNER))  in xfs_btree_check_block_owner()
1864 	if (cur->bc_ops->ptr_len == XFS_BTREE_LONG_PTR_LEN) {  in xfs_btree_check_block_owner()
1865 		if (be64_to_cpu(block->bb_u.l.bb_owner) != owner)  in xfs_btree_check_block_owner()
1868 		if (be32_to_cpu(block->bb_u.s.bb_owner) != owner)  in xfs_btree_check_block_owner()
1879 	const union xfs_btree_ptr	*pp,	/* ptr to btree block */  in xfs_btree_lookup_get_block()
1880 	struct xfs_btree_block		**blkp) /* return btree block */  in xfs_btree_lookup_get_block()
1882 	struct xfs_buf		*bp;	/* buffer pointer for btree block */  in xfs_btree_lookup_get_block()
1886 	/* special case the root block if in an inode */  in xfs_btree_lookup_get_block()
1894 	 * looking for re-use it.  in xfs_btree_lookup_get_block()
1898 	bp = cur->bc_levels[level].bp;  in xfs_btree_lookup_get_block()
1916 	if (be16_to_cpu((*blkp)->bb_level) != level)  in xfs_btree_lookup_get_block()
1920 	if (level != 0 && be16_to_cpu((*blkp)->bb_numrecs) == 0)  in xfs_btree_lookup_get_block()
1929 	xfs_trans_brelse(cur->bc_tp, bp);  in xfs_btree_lookup_get_block()
1931 	return -EFSCORRUPTED;  in xfs_btree_lookup_get_block()
1944 	struct xfs_btree_block	*block,  in xfs_lookup_get_search_key()  argument
1948 		cur->bc_ops->init_key_from_rec(kp,  in xfs_lookup_get_search_key()
1949 				xfs_btree_rec_addr(cur, keyno, block));  in xfs_lookup_get_search_key()
1953 	return xfs_btree_key_addr(cur, keyno, block);  in xfs_lookup_get_search_key()
1957  * Initialize a pointer to the root block.
1964 	if (cur->bc_ops->type == XFS_BTREE_TYPE_INODE) {  in xfs_btree_init_ptr_from_cur()
1966 		 * Inode-rooted btrees call xfs_btree_get_iroot to find the root  in xfs_btree_init_ptr_from_cur()
1969 		ptr->l = 0;  in xfs_btree_init_ptr_from_cur()
1970 	} else if (cur->bc_flags & XFS_BTREE_STAGING) {  in xfs_btree_init_ptr_from_cur()
1971 		ptr->s = cpu_to_be32(cur->bc_ag.afake->af_root);  in xfs_btree_init_ptr_from_cur()
1973 		cur->bc_ops->init_ptr_from_cur(cur, ptr);  in xfs_btree_init_ptr_from_cur()
1987 	struct xfs_btree_block	*block;	/* current btree block */  in xfs_btree_lookup()  local
1992 	union xfs_btree_ptr	*pp;	/* ptr to btree block */  in xfs_btree_lookup()
1993 	union xfs_btree_ptr	ptr;	/* ptr to btree block */  in xfs_btree_lookup()
1997 	/* No such thing as a zero-level tree. */  in xfs_btree_lookup()
1998 	if (XFS_IS_CORRUPT(cur->bc_mp, cur->bc_nlevels == 0)) {  in xfs_btree_lookup()
2000 		return -EFSCORRUPTED;  in xfs_btree_lookup()
2003 	block = NULL;  in xfs_btree_lookup()
2013 	 * on the lookup record, then follow the corresponding block  in xfs_btree_lookup()
2016 	for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {  in xfs_btree_lookup()
2017 		/* Get the block we need to do the lookup on. */  in xfs_btree_lookup()
2018 		error = xfs_btree_lookup_get_block(cur, level, pp, &block);  in xfs_btree_lookup()
2025 			 * know we need to use the first entry in this block.  in xfs_btree_lookup()
2029 			/* Otherwise search this block. Do a binary search. */  in xfs_btree_lookup()
2034 			/* Set low and high entry numbers, 1-based. */  in xfs_btree_lookup()
2036 			high = xfs_btree_get_numrecs(block);  in xfs_btree_lookup()
2038 				/* Block is empty, must be an empty leaf. */  in xfs_btree_lookup()
2039 				if (level != 0 || cur->bc_nlevels != 1) {  in xfs_btree_lookup()
2042 							cur->bc_mp, block,  in xfs_btree_lookup()
2043 							sizeof(*block));  in xfs_btree_lookup()
2045 					return -EFSCORRUPTED;  in xfs_btree_lookup()
2048 				cur->bc_levels[0].ptr = dir != XFS_LOOKUP_LE;  in xfs_btree_lookup()
2053 			/* Binary search the block. */  in xfs_btree_lookup()
2065 						keyno, block, &key);  in xfs_btree_lookup()
2069 				 *  - less than, move right  in xfs_btree_lookup()
2070 				 *  - greater than, move left  in xfs_btree_lookup()
2071 				 *  - equal, we're done  in xfs_btree_lookup()
2073 				diff = cur->bc_ops->key_diff(cur, kp);  in xfs_btree_lookup()
2077 					high = keyno - 1;  in xfs_btree_lookup()
2085 		 * by getting the block number and filling in the cursor.  in xfs_btree_lookup()
2092 			if (diff > 0 && --keyno < 1)  in xfs_btree_lookup()
2094 			pp = xfs_btree_ptr_addr(cur, keyno, block);  in xfs_btree_lookup()
2100 			cur->bc_levels[level].ptr = keyno;  in xfs_btree_lookup()
2108 		 * If ge search and we went off the end of the block, but it's  in xfs_btree_lookup()
2109 		 * not the last block, we're in the wrong block.  in xfs_btree_lookup()
2111 		xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);  in xfs_btree_lookup()
2113 		    keyno > xfs_btree_get_numrecs(block) &&  in xfs_btree_lookup()
2117 			cur->bc_levels[0].ptr = keyno;  in xfs_btree_lookup()
2121 			if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {  in xfs_btree_lookup()
2123 				return -EFSCORRUPTED;  in xfs_btree_lookup()
2129 		keyno--;  in xfs_btree_lookup()
2130 	cur->bc_levels[0].ptr = keyno;  in xfs_btree_lookup()
2133 	if (keyno == 0 || keyno > xfs_btree_get_numrecs(block))  in xfs_btree_lookup()
2151 	ASSERT(cur->bc_ops->geom_flags & XFS_BTGEO_OVERLAPPING);  in xfs_btree_high_key_from_key()
2153 			(cur->bc_ops->key_len / 2));  in xfs_btree_high_key_from_key()
2156 /* Determine the low (and high if overlapped) keys of a leaf block */
2160 	struct xfs_btree_block	*block,  in xfs_btree_get_leaf_keys()  argument
2169 	rec = xfs_btree_rec_addr(cur, 1, block);  in xfs_btree_get_leaf_keys()
2170 	cur->bc_ops->init_key_from_rec(key, rec);  in xfs_btree_get_leaf_keys()
2172 	if (cur->bc_ops->geom_flags & XFS_BTGEO_OVERLAPPING) {  in xfs_btree_get_leaf_keys()
2174 		cur->bc_ops->init_high_key_from_rec(&max_hkey, rec);  in xfs_btree_get_leaf_keys()
2175 		for (n = 2; n <= xfs_btree_get_numrecs(block); n++) {  in xfs_btree_get_leaf_keys()
2176 			rec = xfs_btree_rec_addr(cur, n, block);  in xfs_btree_get_leaf_keys()
2177 			cur->bc_ops->init_high_key_from_rec(&hkey, rec);  in xfs_btree_get_leaf_keys()
2183 		memcpy(high, &max_hkey, cur->bc_ops->key_len / 2);  in xfs_btree_get_leaf_keys()
2187 /* Determine the low (and high if overlapped) keys of a node block */
2191 	struct xfs_btree_block	*block,  in xfs_btree_get_node_keys()  argument
2199 	if (cur->bc_ops->geom_flags & XFS_BTGEO_OVERLAPPING) {  in xfs_btree_get_node_keys()
2200 		memcpy(key, xfs_btree_key_addr(cur, 1, block),  in xfs_btree_get_node_keys()
2201 				cur->bc_ops->key_len / 2);  in xfs_btree_get_node_keys()
2203 		max_hkey = xfs_btree_high_key_addr(cur, 1, block);  in xfs_btree_get_node_keys()
2204 		for (n = 2; n <= xfs_btree_get_numrecs(block); n++) {  in xfs_btree_get_node_keys()
2205 			hkey = xfs_btree_high_key_addr(cur, n, block);  in xfs_btree_get_node_keys()
2211 		memcpy(high, max_hkey, cur->bc_ops->key_len / 2);  in xfs_btree_get_node_keys()
2213 		memcpy(key, xfs_btree_key_addr(cur, 1, block),  in xfs_btree_get_node_keys()
2214 				cur->bc_ops->key_len);  in xfs_btree_get_node_keys()
2218 /* Derive the keys for any btree block. */
2222 	struct xfs_btree_block	*block,  in xfs_btree_get_keys()  argument
2225 	if (be16_to_cpu(block->bb_level) == 0)  in xfs_btree_get_keys()
2226 		xfs_btree_get_leaf_keys(cur, block, key);  in xfs_btree_get_keys()
2228 		xfs_btree_get_node_keys(cur, block, key);  in xfs_btree_get_keys()
2232  * Decide if we need to update the parent keys of a btree block.  For
2236  * in the block.
2243 	return (cur->bc_ops->geom_flags & XFS_BTGEO_OVERLAPPING) || ptr == 1;  in xfs_btree_needs_key_update()
2255 	struct xfs_btree_block	*block,  in __xfs_btree_updkeys()  argument
2267 	ASSERT(cur->bc_ops->geom_flags & XFS_BTGEO_OVERLAPPING);  in __xfs_btree_updkeys()
2270 	if (level + 1 >= cur->bc_nlevels)  in __xfs_btree_updkeys()
2277 	xfs_btree_get_keys(cur, block, lkey);  in __xfs_btree_updkeys()
2278 	for (level++; level < cur->bc_nlevels; level++) {  in __xfs_btree_updkeys()
2282 		block = xfs_btree_get_block(cur, level, &bp);  in __xfs_btree_updkeys()
2285 		error = xfs_btree_check_block(cur, block, level, bp);  in __xfs_btree_updkeys()
2289 		ptr = cur->bc_levels[level].ptr;  in __xfs_btree_updkeys()
2290 		nlkey = xfs_btree_key_addr(cur, ptr, block);  in __xfs_btree_updkeys()
2291 		nhkey = xfs_btree_high_key_addr(cur, ptr, block);  in __xfs_btree_updkeys()
2298 		if (level + 1 >= cur->bc_nlevels)  in __xfs_btree_updkeys()
2300 		xfs_btree_get_node_keys(cur, block, lkey);  in __xfs_btree_updkeys()
2313 	struct xfs_btree_block	*block;  in xfs_btree_updkeys_force()  local
2315 	block = xfs_btree_get_block(cur, level, &bp);  in xfs_btree_updkeys_force()
2316 	return __xfs_btree_updkeys(cur, level, block, bp, true);  in xfs_btree_updkeys_force()
2327 	struct xfs_btree_block	*block;  in xfs_btree_update_keys()  local
2335 	block = xfs_btree_get_block(cur, level, &bp);  in xfs_btree_update_keys()
2336 	if (cur->bc_ops->geom_flags & XFS_BTGEO_OVERLAPPING)  in xfs_btree_update_keys()
2337 		return __xfs_btree_updkeys(cur, level, block, bp, false);  in xfs_btree_update_keys()
2343 	 * at the first entry in the block.  in xfs_btree_update_keys()
2345 	xfs_btree_get_keys(cur, block, &key);  in xfs_btree_update_keys()
2346 	for (level++, ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) {  in xfs_btree_update_keys()
2350 		block = xfs_btree_get_block(cur, level, &bp);  in xfs_btree_update_keys()
2352 		error = xfs_btree_check_block(cur, block, level, bp);  in xfs_btree_update_keys()
2356 		ptr = cur->bc_levels[level].ptr;  in xfs_btree_update_keys()
2357 		kp = xfs_btree_key_addr(cur, ptr, block);  in xfs_btree_update_keys()
2375 	struct xfs_btree_block	*block;  in xfs_btree_update()  local
2381 	/* Pick up the current block. */  in xfs_btree_update()
2382 	block = xfs_btree_get_block(cur, 0, &bp);  in xfs_btree_update()
2385 	error = xfs_btree_check_block(cur, block, 0, bp);  in xfs_btree_update()
2390 	ptr = cur->bc_levels[0].ptr;  in xfs_btree_update()
2391 	rp = xfs_btree_rec_addr(cur, ptr, block);  in xfs_btree_update()
2421 	struct xfs_btree_block	*left;		/* left btree block */  in xfs_btree_lshift()
2424 	struct xfs_btree_block	*right;		/* right btree block */  in xfs_btree_lshift()
2437 	/* Set up variables for this block as "right". */  in xfs_btree_lshift()
2455 	if (cur->bc_levels[level].ptr <= 1)  in xfs_btree_lshift()
2465 	if (lrecs == cur->bc_ops->get_maxrecs(cur, level))  in xfs_btree_lshift()
2476 	rrecs--;  in xfs_btree_lshift()
2482 	 * If non-leaf, copy a key and a ptr to the left block.  in xfs_btree_lshift()
2483 	 * Log the changes to the left block.  in xfs_btree_lshift()
2486 		/* It's a non-leaf.  Move keys and pointers. */  in xfs_btree_lshift()
2506 		ASSERT(cur->bc_ops->keys_inorder(cur,  in xfs_btree_lshift()
2507 			xfs_btree_key_addr(cur, lrecs - 1, left), lkp));  in xfs_btree_lshift()
2518 		ASSERT(cur->bc_ops->recs_inorder(cur,  in xfs_btree_lshift()
2519 			xfs_btree_rec_addr(cur, lrecs - 1, left), lrp));  in xfs_btree_lshift()
2531 	XFS_BTREE_STATS_ADD(cur, moves, rrecs - 1);  in xfs_btree_lshift()
2542 				-1, rrecs);  in xfs_btree_lshift()
2545 				-1, rrecs);  in xfs_btree_lshift()
2553 			-1, rrecs);  in xfs_btree_lshift()
2559 	 * block on the left.  in xfs_btree_lshift()
2561 	if (cur->bc_ops->geom_flags & XFS_BTGEO_OVERLAPPING) {  in xfs_btree_lshift()
2566 		if (XFS_IS_CORRUPT(tcur->bc_mp, i != 1)) {  in xfs_btree_lshift()
2568 			error = -EFSCORRUPTED;  in xfs_btree_lshift()
2576 		/* Update the parent high keys of the left block, if needed. */  in xfs_btree_lshift()
2584 	/* Update the parent keys of the right block. */  in xfs_btree_lshift()
2590 	cur->bc_levels[level].ptr--;  in xfs_btree_lshift()
2618 	struct xfs_btree_block	*left;		/* left btree block */  in xfs_btree_rshift()
2620 	struct xfs_btree_block	*right;		/* right btree block */  in xfs_btree_rshift()
2622 	union xfs_btree_ptr	rptr;		/* right block pointer */  in xfs_btree_rshift()
2632 	/* Set up variables for this block as "left". */  in xfs_btree_rshift()
2651 	if (cur->bc_levels[level].ptr >= lrecs)  in xfs_btree_rshift()
2661 	if (rrecs == cur->bc_ops->get_maxrecs(cur, level))  in xfs_btree_rshift()
2668 	 * Make a hole at the start of the right neighbor block, then  in xfs_btree_rshift()
2669 	 * copy the last left block entry to the hole.  in xfs_btree_rshift()
2682 		for (i = rrecs - 1; i >= 0; i--) {  in xfs_btree_rshift()
2702 		ASSERT(cur->bc_ops->keys_inorder(cur, rkp,  in xfs_btree_rshift()
2722 	xfs_btree_set_numrecs(left, --lrecs);  in xfs_btree_rshift()
2730 	 * block on the right.  in xfs_btree_rshift()
2736 	if (XFS_IS_CORRUPT(tcur->bc_mp, i != 1)) {  in xfs_btree_rshift()
2738 		error = -EFSCORRUPTED;  in xfs_btree_rshift()
2746 	/* Update the parent high keys of the left block, if needed. */  in xfs_btree_rshift()
2747 	if (cur->bc_ops->geom_flags & XFS_BTGEO_OVERLAPPING) {  in xfs_btree_rshift()
2753 	/* Update the parent keys of the right block. */  in xfs_btree_rshift()
2785 	 * Don't allow block allocation for a staging cursor, because staging  in xfs_btree_alloc_block()
2791 	if (unlikely(cur->bc_flags & XFS_BTREE_STAGING)) {  in xfs_btree_alloc_block()
2793 		return -EFSCORRUPTED;  in xfs_btree_alloc_block()
2796 	error = cur->bc_ops->alloc_block(cur, hint_block, new_block, stat);  in xfs_btree_alloc_block()
2802  * Split cur/level block in half.
2803  * Return new block number and the key to its first
2815 	union xfs_btree_ptr	lptr;		/* left sibling block ptr */  in __xfs_btree_split()
2817 	struct xfs_btree_block	*left;		/* left btree block */  in __xfs_btree_split()
2818 	union xfs_btree_ptr	rptr;		/* right sibling block ptr */  in __xfs_btree_split()
2820 	struct xfs_btree_block	*right;		/* right btree block */  in __xfs_btree_split()
2821 	union xfs_btree_ptr	rrptr;		/* right-right sibling ptr */  in __xfs_btree_split()
2822 	struct xfs_buf		*rrbp;		/* right-right buffer pointer */  in __xfs_btree_split()
2823 	struct xfs_btree_block	*rrblock;	/* right-right btree block */  in __xfs_btree_split()
2832 	/* Set up left block (current one). */  in __xfs_btree_split()
2843 	/* Allocate the new block. If we can't do it, we're toast. Give up. */  in __xfs_btree_split()
2851 	/* Set up the new block as "right". */  in __xfs_btree_split()
2856 	/* Fill in the btree header for the new right block. */  in __xfs_btree_split()
2860 	 * Split the entries between the old and the new block evenly.  in __xfs_btree_split()
2862 	 * each new block will have the same number of entries.  in __xfs_btree_split()
2866 	if ((lrecs & 1) && cur->bc_levels[level].ptr <= rrecs + 1)  in __xfs_btree_split()
2868 	src_index = (lrecs - rrecs + 1);  in __xfs_btree_split()
2873 	lrecs -= rrecs;  in __xfs_btree_split()
2878 	 * Copy btree block entries from the left block over to the  in __xfs_btree_split()
2879 	 * new block, the right. Update the right block and log the  in __xfs_btree_split()
2883 		/* It's a non-leaf.  Move keys and pointers. */  in __xfs_btree_split()
2900 		/* Copy the keys & pointers to the new block. */  in __xfs_btree_split()
2907 		/* Stash the keys of the new block for later insertion. */  in __xfs_btree_split()
2917 		/* Copy records to the new block. */  in __xfs_btree_split()
2921 		/* Stash the keys of the new block for later insertion. */  in __xfs_btree_split()
2926 	 * Find the left block number by looking in the buffer.  in __xfs_btree_split()
2938 	 * If there's a block to the new block's right, make that block  in __xfs_btree_split()
2950 	/* Update the parent high keys of the left block, if needed. */  in __xfs_btree_split()
2951 	if (cur->bc_ops->geom_flags & XFS_BTGEO_OVERLAPPING) {  in __xfs_btree_split()
2958 	 * If the cursor is really in the right block, move it there.  in __xfs_btree_split()
2962 	if (cur->bc_levels[level].ptr > lrecs + 1) {  in __xfs_btree_split()
2964 		cur->bc_levels[level].ptr -= lrecs;  in __xfs_btree_split()
2968 	 * the right block, no matter where this cursor was.  in __xfs_btree_split()
2970 	if (level + 1 < cur->bc_nlevels) {  in __xfs_btree_split()
2974 		(*curp)->bc_levels[level + 1].ptr++;  in __xfs_btree_split()
3016 	 * temporarily to ensure that we don't block waiting for memory reclaim  in xfs_btree_split_worker()
3019 	if (args->kswapd)  in xfs_btree_split_worker()
3023 	xfs_trans_set_context(args->cur->bc_tp);  in xfs_btree_split_worker()
3025 	args->result = __xfs_btree_split(args->cur, args->level, args->ptrp,  in xfs_btree_split_worker()
3026 					 args->key, args->curp, args->stat);  in xfs_btree_split_worker()
3028 	xfs_trans_clear_context(args->cur->bc_tp);  in xfs_btree_split_worker()
3035 	complete(args->done);  in xfs_btree_split_worker()
3044  * Care must be taken here - the work queue rescuer thread introduces potential
3045  * AGF <> worker queue deadlocks if the BMBT block allocation has to lock new
3069 	if (!xfs_btree_is_bmap(cur->bc_ops) ||  in xfs_btree_split()
3070 	    cur->bc_tp->t_highest_agno == NULLAGNUMBER)  in xfs_btree_split()
3091 /* Move the records from a root leaf block to a separate block. */
3095 	struct xfs_btree_block	*block,  in xfs_btree_promote_leaf_iroot()  argument
3105 	int			numrecs = xfs_btree_get_numrecs(block);  in xfs_btree_promote_leaf_iroot()
3107 	/* Copy the records from the leaf broot into the new child block. */  in xfs_btree_promote_leaf_iroot()
3108 	rp = xfs_btree_rec_addr(cur, 1, block);  in xfs_btree_promote_leaf_iroot()
3116 	 * ifork's btree root block may change when we convert the broot from a  in xfs_btree_promote_leaf_iroot()
3117 	 * leaf to a node block.  Free the existing leaf broot so that nobody  in xfs_btree_promote_leaf_iroot()
3121 	cur->bc_ops->broot_realloc(cur, 0);  in xfs_btree_promote_leaf_iroot()
3122 	cur->bc_nlevels++;  in xfs_btree_promote_leaf_iroot()
3123 	cur->bc_levels[1].ptr = 1;  in xfs_btree_promote_leaf_iroot()
3127 	 * child block.  in xfs_btree_promote_leaf_iroot()
3129 	broot = cur->bc_ops->broot_realloc(cur, 1);  in xfs_btree_promote_leaf_iroot()
3130 	xfs_btree_init_block(cur->bc_mp, broot, cur->bc_ops,  in xfs_btree_promote_leaf_iroot()
3131 			cur->bc_nlevels - 1, 1, cur->bc_ino.ip->i_ino);  in xfs_btree_promote_leaf_iroot()
3138 	/* Attach the new block to the cursor and log it. */  in xfs_btree_promote_leaf_iroot()
3145  * Move the keys and pointers from a root block to a separate block.
3148  * tree height, copy the keyptrs to the new internal node (cblock), shrink
3149  * the root, and copy the pointers there.
3154 	struct xfs_btree_block	*block,  in xfs_btree_promote_node_iroot()  argument
3166 	int			numrecs = xfs_btree_get_numrecs(block);  in xfs_btree_promote_node_iroot()
3169 	 * Increase tree height, adjusting the root block level to match.  in xfs_btree_promote_node_iroot()
3171 	 * block contents to the new child block.  in xfs_btree_promote_node_iroot()
3173 	be16_add_cpu(&block->bb_level, 1);  in xfs_btree_promote_node_iroot()
3174 	cur->bc_nlevels++;  in xfs_btree_promote_node_iroot()
3175 	cur->bc_levels[level + 1].ptr = 1;  in xfs_btree_promote_node_iroot()
3178 	 * Adjust the root btree record count, then copy the keys from the old  in xfs_btree_promote_node_iroot()
3179 	 * root to the new child block.  in xfs_btree_promote_node_iroot()
3181 	xfs_btree_set_numrecs(block, 1);  in xfs_btree_promote_node_iroot()
3182 	kp = xfs_btree_key_addr(cur, 1, block);  in xfs_btree_promote_node_iroot()
3186 	/* Check the pointers and copy them to the new child block. */  in xfs_btree_promote_node_iroot()
3187 	pp = xfs_btree_ptr_addr(cur, 1, block);  in xfs_btree_promote_node_iroot()
3197 	 * Set the first keyptr to point to the new child block, then shrink  in xfs_btree_promote_node_iroot()
3198 	 * the memory buffer for the root block.  in xfs_btree_promote_node_iroot()
3206 	cur->bc_ops->broot_realloc(cur, 1);  in xfs_btree_promote_node_iroot()
3208 	/* Attach the new block to the cursor and log it. */  in xfs_btree_promote_node_iroot()
3217  * Copy the old inode root contents into a real block and make the
3224 	int			*stat)		/* return status - 0 fail */  in xfs_btree_new_iroot()
3227 	struct xfs_btree_block	*block;		/* btree block */  in xfs_btree_new_iroot()  local
3228 	struct xfs_btree_block	*cblock;	/* child btree block */  in xfs_btree_new_iroot()
3230 	union xfs_btree_ptr	nptr;		/* new block addr */  in xfs_btree_new_iroot()
3236 	ASSERT(cur->bc_ops->type == XFS_BTREE_TYPE_INODE);  in xfs_btree_new_iroot()
3238 	level = cur->bc_nlevels - 1;  in xfs_btree_new_iroot()
3240 	block = xfs_btree_get_iroot(cur);  in xfs_btree_new_iroot()
3241 	ASSERT(level > 0 || (cur->bc_ops->geom_flags & XFS_BTGEO_IROOT_RECORDS));  in xfs_btree_new_iroot()
3243 		aptr = *xfs_btree_ptr_addr(cur, 1, block);  in xfs_btree_new_iroot()
3245 		aptr.l = cpu_to_be64(XFS_INO_TO_FSB(cur->bc_mp,  in xfs_btree_new_iroot()
3246 				cur->bc_ino.ip->i_ino));  in xfs_btree_new_iroot()
3248 	/* Allocate the new block. If we can't do it, we're toast. Give up. */  in xfs_btree_new_iroot()
3257 	/* Copy the root into a real block. */  in xfs_btree_new_iroot()
3266 	memcpy(cblock, block, xfs_btree_block_len(cur));  in xfs_btree_new_iroot()
3267 	if (xfs_has_crc(cur->bc_mp)) {  in xfs_btree_new_iroot()
3269 		if (cur->bc_ops->ptr_len == XFS_BTREE_LONG_PTR_LEN)  in xfs_btree_new_iroot()
3270 			cblock->bb_u.l.bb_blkno = bno;  in xfs_btree_new_iroot()
3272 			cblock->bb_u.s.bb_blkno = bno;  in xfs_btree_new_iroot()
3276 		error = xfs_btree_promote_node_iroot(cur, block, level, cbp,  in xfs_btree_new_iroot()
3281 		xfs_btree_promote_leaf_iroot(cur, block, cbp, &nptr, cblock);  in xfs_btree_new_iroot()
3284 	*logflags |= XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_ino.whichfork);  in xfs_btree_new_iroot()
3297 	if (cur->bc_flags & XFS_BTREE_STAGING) {  in xfs_btree_set_root()
3298 		/* Update the btree root information for a per-AG fake root. */  in xfs_btree_set_root()
3299 		cur->bc_ag.afake->af_root = be32_to_cpu(ptr->s);  in xfs_btree_set_root()
3300 		cur->bc_ag.afake->af_levels += inc;  in xfs_btree_set_root()
3302 		cur->bc_ops->set_root(cur, ptr, inc);  in xfs_btree_set_root()
3307  * Allocate a new root block, fill it in.
3314 	struct xfs_btree_block	*block;	/* one half of the old root block */  in xfs_btree_new_root()  local
3315 	struct xfs_buf		*bp;	/* buffer containing block */  in xfs_btree_new_root()
3318 	struct xfs_btree_block	*left;	/* left btree block */  in xfs_btree_new_root()
3320 	struct xfs_btree_block	*new;	/* new (root) btree block */  in xfs_btree_new_root()
3323 	struct xfs_btree_block	*right;	/* right btree block */  in xfs_btree_new_root()
3332 	/* Allocate the new block. If we can't do it, we're toast. Give up. */  in xfs_btree_new_root()
3340 	/* Set up the new block. */  in xfs_btree_new_root()
3350 	 * and the new block generated when it was split.  We don't know which  in xfs_btree_new_root()
3354 	block = xfs_btree_get_block(cur, cur->bc_nlevels - 1, &bp);  in xfs_btree_new_root()
3357 	error = xfs_btree_check_block(cur, block, cur->bc_nlevels - 1, bp);  in xfs_btree_new_root()
3362 	xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB);  in xfs_btree_new_root()
3364 		/* Our block is left, pick up the right block. */  in xfs_btree_new_root()
3367 		left = block;  in xfs_btree_new_root()
3374 		/* Our block is right, pick up the left block. */  in xfs_btree_new_root()
3377 		right = block;  in xfs_btree_new_root()
3386 	/* Fill in the new block's btree header and log it. */  in xfs_btree_new_root()
3387 	xfs_btree_init_block_cur(cur, nbp, cur->bc_nlevels, 2);  in xfs_btree_new_root()
3395 		 * Get the keys for the left block's keys and put them directly  in xfs_btree_new_root()
3396 		 * in the parent block.  Do the same for the right block.  in xfs_btree_new_root()
3404 		 * Get the keys for the left block's records and put them  in xfs_btree_new_root()
3405 		 * directly in the parent block.  Do the same for the right  in xfs_btree_new_root()
3406 		 * block.  in xfs_btree_new_root()
3423 	xfs_btree_setbuf(cur, cur->bc_nlevels, nbp);  in xfs_btree_new_root()
3424 	cur->bc_levels[cur->bc_nlevels].ptr = nptr;  in xfs_btree_new_root()
3425 	cur->bc_nlevels++;  in xfs_btree_new_root()
3426 	ASSERT(cur->bc_nlevels <= cur->bc_maxlevels);  in xfs_btree_new_root()
3440 	int			numrecs,/* # of recs in block */  in xfs_btree_make_block_unfull()
3445 	union xfs_btree_key	*key,	/* key of new block */  in xfs_btree_make_block_unfull()
3451 		struct xfs_inode *ip = cur->bc_ino.ip;  in xfs_btree_make_block_unfull()
3453 		if (numrecs < cur->bc_ops->get_dmaxrecs(cur, level)) {  in xfs_btree_make_block_unfull()
3454 			/* A root block that can be made bigger. */  in xfs_btree_make_block_unfull()
3455 			cur->bc_ops->broot_realloc(cur, numrecs + 1);  in xfs_btree_make_block_unfull()
3458 			/* A root block that needs replacing */  in xfs_btree_make_block_unfull()
3465 			xfs_trans_log_inode(cur->bc_tp, ip, logflags);  in xfs_btree_make_block_unfull()
3482 		*oindex = *index = cur->bc_levels[level].ptr;  in xfs_btree_make_block_unfull()
3487 	 * Next, try splitting the current block in half.  in xfs_btree_make_block_unfull()
3489 	 * If this works we have to re-set our variables because we  in xfs_btree_make_block_unfull()
3490 	 * could be in a different block now.  in xfs_btree_make_block_unfull()
3497 	*index = cur->bc_levels[level].ptr;  in xfs_btree_make_block_unfull()
3509 	union xfs_btree_ptr	*ptrp,	/* i/o: block number inserted */  in xfs_btree_insrec()
3511 	union xfs_btree_key	*key,	/* i/o: block key for ptrp */  in xfs_btree_insrec()
3515 	struct xfs_btree_block	*block;	/* btree block */  in xfs_btree_insrec()  local
3516 	struct xfs_buf		*bp;	/* buffer for block */  in xfs_btree_insrec()
3517 	union xfs_btree_ptr	nptr;	/* new block ptr */  in xfs_btree_insrec()
3519 	union xfs_btree_key	nkey;	/* new block key */  in xfs_btree_insrec()
3533 	 * root level, allocate a new root block and we're done.  in xfs_btree_insrec()
3535 	if (cur->bc_ops->type != XFS_BTREE_TYPE_INODE &&  in xfs_btree_insrec()
3536 	    level >= cur->bc_nlevels) {  in xfs_btree_insrec()
3544 	ptr = cur->bc_levels[level].ptr;  in xfs_btree_insrec()
3554 	/* Get pointers to the btree buffer and block. */  in xfs_btree_insrec()
3555 	block = xfs_btree_get_block(cur, level, &bp);  in xfs_btree_insrec()
3557 	numrecs = xfs_btree_get_numrecs(block);  in xfs_btree_insrec()
3560 	error = xfs_btree_check_block(cur, block, level, bp);  in xfs_btree_insrec()
3567 			ASSERT(cur->bc_ops->recs_inorder(cur, rec,  in xfs_btree_insrec()
3568 				xfs_btree_rec_addr(cur, ptr, block)));  in xfs_btree_insrec()
3570 			ASSERT(cur->bc_ops->keys_inorder(cur, key,  in xfs_btree_insrec()
3571 				xfs_btree_key_addr(cur, ptr, block)));  in xfs_btree_insrec()
3577 	 * If the block is full, we can't insert the new entry until we  in xfs_btree_insrec()
3578 	 * make the block un-full.  in xfs_btree_insrec()
3581 	if (numrecs == cur->bc_ops->get_maxrecs(cur, level)) {  in xfs_btree_insrec()
3589 	 * The current block may have changed if the block was  in xfs_btree_insrec()
3592 	block = xfs_btree_get_block(cur, level, &bp);  in xfs_btree_insrec()
3593 	numrecs = xfs_btree_get_numrecs(block);  in xfs_btree_insrec()
3596 	error = xfs_btree_check_block(cur, block, level, bp);  in xfs_btree_insrec()
3602 	 * At this point we know there's room for our new entry in the block  in xfs_btree_insrec()
3605 	XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr + 1);  in xfs_btree_insrec()
3612 		kp = xfs_btree_key_addr(cur, ptr, block);  in xfs_btree_insrec()
3613 		pp = xfs_btree_ptr_addr(cur, ptr, block);  in xfs_btree_insrec()
3615 		for (i = numrecs - ptr; i >= 0; i--) {  in xfs_btree_insrec()
3621 		xfs_btree_shift_keys(cur, kp, 1, numrecs - ptr + 1);  in xfs_btree_insrec()
3622 		xfs_btree_shift_ptrs(cur, pp, 1, numrecs - ptr + 1);  in xfs_btree_insrec()
3632 		xfs_btree_set_numrecs(block, numrecs);  in xfs_btree_insrec()
3637 			ASSERT(cur->bc_ops->keys_inorder(cur, kp,  in xfs_btree_insrec()
3638 				xfs_btree_key_addr(cur, ptr + 1, block)));  in xfs_btree_insrec()
3645 		rp = xfs_btree_rec_addr(cur, ptr, block);  in xfs_btree_insrec()
3647 		xfs_btree_shift_recs(cur, rp, 1, numrecs - ptr + 1);  in xfs_btree_insrec()
3651 		xfs_btree_set_numrecs(block, ++numrecs);  in xfs_btree_insrec()
3655 			ASSERT(cur->bc_ops->recs_inorder(cur, rp,  in xfs_btree_insrec()
3656 				xfs_btree_rec_addr(cur, ptr + 1, block)));  in xfs_btree_insrec()
3669 	 * If the caller had us target a full block for the insertion, we dealt  in xfs_btree_insrec()
3671 	 * "make unfull" function splits the block, it'll hand us back the key  in xfs_btree_insrec()
3672 	 * and pointer of the new block.  We haven't yet added the new block to  in xfs_btree_insrec()
3674 	 * block (bp->b_bn != old_bn), we have to update the caller's pointer  in xfs_btree_insrec()
3675 	 * so that the caller adds the new block with the correct key.  in xfs_btree_insrec()
3677 	 * However, there is a third possibility-- if the selected block is the  in xfs_btree_insrec()
3678 	 * root block of an inode-rooted btree and cannot be expanded further,  in xfs_btree_insrec()
3679 	 * the "make unfull" function moves the root block contents to a new  in xfs_btree_insrec()
3680 	 * block and updates the root block to point to the new block.  In this  in xfs_btree_insrec()
3681 	 * case, no block pointer is passed back because the block has already  in xfs_btree_insrec()
3690 		xfs_btree_get_keys(cur, block, lkey);  in xfs_btree_insrec()
3698 	 * Return the new block number, if any.  in xfs_btree_insrec()
3719  * A multi-level split of the tree on insert will invalidate the original
3731 	union xfs_btree_ptr	nptr;	/* new block number (split result) */  in xfs_btree_insert()
3734 	union xfs_btree_key	bkey;	/* key of block to insert */  in xfs_btree_insert()
3746 	cur->bc_ops->init_rec_from_cur(cur, &rec);  in xfs_btree_insert()
3747 	cur->bc_ops->init_key_from_rec(key, &rec);  in xfs_btree_insert()
3751 	 * Stop when we don't get a split block, that must mean that  in xfs_btree_insert()
3767 		if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {  in xfs_btree_insert()
3769 			error = -EFSCORRUPTED;  in xfs_btree_insert()
3782 			if (cur->bc_ops->update_cursor &&  in xfs_btree_insert()
3783 			    !(cur->bc_flags & XFS_BTREE_STAGING))  in xfs_btree_insert()
3784 				cur->bc_ops->update_cursor(pcur, cur);  in xfs_btree_insert()
3785 			cur->bc_nlevels = pcur->bc_nlevels;  in xfs_btree_insert()
3801 /* Move the records from a child leaf block to the root block. */
3816 	 * ifork's btree root block may change when we convert the broot from a  in xfs_btree_demote_leaf_child()
3820 	cur->bc_ops->broot_realloc(cur, 0);  in xfs_btree_demote_leaf_child()
3821 	cur->bc_nlevels--;  in xfs_btree_demote_leaf_child()
3824 	 * Allocate a new leaf broot and copy the records from the old child.  in xfs_btree_demote_leaf_child()
3827 	broot = cur->bc_ops->broot_realloc(cur, numrecs);  in xfs_btree_demote_leaf_child()
3828 	xfs_btree_init_block(cur->bc_mp, broot, cur->bc_ops, 0, numrecs,  in xfs_btree_demote_leaf_child()
3829 			cur->bc_ino.ip->i_ino);  in xfs_btree_demote_leaf_child()
3835 	cur->bc_levels[0].bp = NULL;  in xfs_btree_demote_leaf_child()
3839  * Move the keyptrs from a child node block to the root block.
3842  * tree height, copy the keyptrs to the new internal node (cblock), shrink
3843  * the root, and copy the pointers there.
3852 	struct xfs_btree_block	*block;  in xfs_btree_demote_node_child()  local
3862 	 * doomed child so that we can copy the keyptrs ahead of changing the  in xfs_btree_demote_node_child()
3865 	block = cur->bc_ops->broot_realloc(cur, numrecs);  in xfs_btree_demote_node_child()
3867 	xfs_btree_set_numrecs(block, numrecs);  in xfs_btree_demote_node_child()
3868 	ASSERT(block->bb_numrecs == cblock->bb_numrecs);  in xfs_btree_demote_node_child()
3870 	/* Copy keys from the doomed block. */  in xfs_btree_demote_node_child()
3871 	kp = xfs_btree_key_addr(cur, 1, block);  in xfs_btree_demote_node_child()
3875 	/* Copy pointers from the doomed block. */  in xfs_btree_demote_node_child()
3876 	pp = xfs_btree_ptr_addr(cur, 1, block);  in xfs_btree_demote_node_child()
3879 		error = xfs_btree_debug_check_ptr(cur, cpp, i, level - 1);  in xfs_btree_demote_node_child()
3885 	/* Decrease tree height, adjusting the root block level to match. */  in xfs_btree_demote_node_child()
3886 	cur->bc_levels[level - 1].bp = NULL;  in xfs_btree_demote_node_child()
3887 	be16_add_cpu(&block->bb_level, -1);  in xfs_btree_demote_node_child()
3888 	cur->bc_nlevels--;  in xfs_btree_demote_node_child()
3893  * Try to merge a non-leaf block back into the inode root.
3896  * killing the old root block.  But because we can't just delete the
3897  * inode we have to copy the single block it was pointing to into the
3904 	struct xfs_inode	*ip = cur->bc_ino.ip;  in xfs_btree_kill_iroot()
3905 	struct xfs_btree_block	*block;  in xfs_btree_kill_iroot()  local
3915 	ASSERT(cur->bc_ops->type == XFS_BTREE_TYPE_INODE);  in xfs_btree_kill_iroot()
3916 	ASSERT((cur->bc_ops->geom_flags & XFS_BTGEO_IROOT_RECORDS) ||  in xfs_btree_kill_iroot()
3917 	       cur->bc_nlevels > 1);  in xfs_btree_kill_iroot()
3920 	 * Don't deal with the root block needs to be a leaf case.  in xfs_btree_kill_iroot()
3923 	level = cur->bc_nlevels - 1;  in xfs_btree_kill_iroot()
3924 	if (level == 1 && !(cur->bc_ops->geom_flags & XFS_BTGEO_IROOT_RECORDS))  in xfs_btree_kill_iroot()
3934 	block = xfs_btree_get_iroot(cur);  in xfs_btree_kill_iroot()
3935 	if (xfs_btree_get_numrecs(block) != 1)  in xfs_btree_kill_iroot()
3938 	cblock = xfs_btree_get_block(cur, level - 1, &cbp);  in xfs_btree_kill_iroot()
3946 	if (numrecs > cur->bc_ops->get_dmaxrecs(cur, level))  in xfs_btree_kill_iroot()
3952 	xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB);  in xfs_btree_kill_iroot()
3954 	xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);  in xfs_btree_kill_iroot()
3970 	xfs_trans_log_inode(cur->bc_tp, ip,  in xfs_btree_kill_iroot()
3971 		XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_ino.whichfork));  in xfs_btree_kill_iroot()
3994 	xfs_btree_set_root(cur, newroot, -1);  in xfs_btree_kill_root()
4000 	cur->bc_levels[level].bp = NULL;  in xfs_btree_kill_root()
4001 	cur->bc_levels[level].ra = 0;  in xfs_btree_kill_root()
4002 	cur->bc_nlevels--;  in xfs_btree_kill_root()
4029  * Remove the record from its block then rebalance the tree.
4036 	int			*stat)		/* fail/done/go-on */  in xfs_btree_delrec()
4038 	struct xfs_btree_block	*block;		/* btree block */  in xfs_btree_delrec()  local
4039 	union xfs_btree_ptr	cptr;		/* current block ptr */  in xfs_btree_delrec()
4040 	struct xfs_buf		*bp;		/* buffer for block */  in xfs_btree_delrec()
4043 	union xfs_btree_ptr	lptr;		/* left sibling block ptr */  in xfs_btree_delrec()
4045 	struct xfs_btree_block	*left;		/* left btree block */  in xfs_btree_delrec()
4048 	union xfs_btree_ptr	rptr;		/* right sibling block ptr */  in xfs_btree_delrec()
4050 	struct xfs_btree_block	*right;		/* right btree block */  in xfs_btree_delrec()
4051 	struct xfs_btree_block	*rrblock;	/* right-right btree block */  in xfs_btree_delrec()
4052 	struct xfs_buf		*rrbp;		/* right-right buffer pointer */  in xfs_btree_delrec()
4060 	ptr = cur->bc_levels[level].ptr;  in xfs_btree_delrec()
4066 	/* Get the buffer & block containing the record or key/ptr. */  in xfs_btree_delrec()
4067 	block = xfs_btree_get_block(cur, level, &bp);  in xfs_btree_delrec()
4068 	numrecs = xfs_btree_get_numrecs(block);  in xfs_btree_delrec()
4071 	error = xfs_btree_check_block(cur, block, level, bp);  in xfs_btree_delrec()
4076 	/* Fail if we're off the end of the block. */  in xfs_btree_delrec()
4083 	XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr);  in xfs_btree_delrec()
4091 		lkp = xfs_btree_key_addr(cur, ptr + 1, block);  in xfs_btree_delrec()
4092 		lpp = xfs_btree_ptr_addr(cur, ptr + 1, block);  in xfs_btree_delrec()
4094 		for (i = 0; i < numrecs - ptr; i++) {  in xfs_btree_delrec()
4101 			xfs_btree_shift_keys(cur, lkp, -1, numrecs - ptr);  in xfs_btree_delrec()
4102 			xfs_btree_shift_ptrs(cur, lpp, -1, numrecs - ptr);  in xfs_btree_delrec()
4103 			xfs_btree_log_keys(cur, bp, ptr, numrecs - 1);  in xfs_btree_delrec()
4104 			xfs_btree_log_ptrs(cur, bp, ptr, numrecs - 1);  in xfs_btree_delrec()
4110 				xfs_btree_rec_addr(cur, ptr + 1, block),  in xfs_btree_delrec()
4111 				-1, numrecs - ptr);  in xfs_btree_delrec()
4112 			xfs_btree_log_recs(cur, bp, ptr, numrecs - 1);  in xfs_btree_delrec()
4117 	 * Decrement and log the number of entries in the block.  in xfs_btree_delrec()
4119 	xfs_btree_set_numrecs(block, --numrecs);  in xfs_btree_delrec()
4123 	 * We're at the root level.  First, shrink the root block in-memory.  in xfs_btree_delrec()
4128 		cur->bc_ops->broot_realloc(cur, numrecs);  in xfs_btree_delrec()
4145 	if (level == cur->bc_nlevels - 1) {  in xfs_btree_delrec()
4149 			 * pp is still set to the first pointer in the block.  in xfs_btree_delrec()
4152 			pp = xfs_btree_ptr_addr(cur, 1, block);  in xfs_btree_delrec()
4166 	 * If we deleted the leftmost entry in the block, update the  in xfs_btree_delrec()
4176 	 * If the number of records remaining in the block is at least  in xfs_btree_delrec()
4179 	if (numrecs >= cur->bc_ops->get_minrecs(cur, level)) {  in xfs_btree_delrec()
4189 	 * see if we can re-balance by moving only one record.  in xfs_btree_delrec()
4191 	xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB);  in xfs_btree_delrec()
4192 	xfs_btree_get_sibling(cur, block, &lptr, XFS_BB_LEFTSIB);  in xfs_btree_delrec()
4194 	if (cur->bc_ops->type == XFS_BTREE_TYPE_INODE) {  in xfs_btree_delrec()
4196 		 * One child of root, need to get a chance to copy its contents  in xfs_btree_delrec()
4202 		    level == cur->bc_nlevels - 2) {  in xfs_btree_delrec()
4229 		 * Move the temp cursor to the last entry in the next block.  in xfs_btree_delrec()
4233 		if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {  in xfs_btree_delrec()
4235 			error = -EFSCORRUPTED;  in xfs_btree_delrec()
4242 		if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {  in xfs_btree_delrec()
4244 			error = -EFSCORRUPTED;  in xfs_btree_delrec()
4249 		if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {  in xfs_btree_delrec()
4251 			error = -EFSCORRUPTED;  in xfs_btree_delrec()
4255 		/* Grab a pointer to the block. */  in xfs_btree_delrec()
4262 		/* Grab the current block number, for future use. */  in xfs_btree_delrec()
4266 		 * If right block is full enough so that removing one entry  in xfs_btree_delrec()
4267 		 * won't make it too empty, and left-shifting an entry out  in xfs_btree_delrec()
4270 		if (xfs_btree_get_numrecs(right) - 1 >=  in xfs_btree_delrec()
4271 		    cur->bc_ops->get_minrecs(tcur, level)) {  in xfs_btree_delrec()
4276 				ASSERT(xfs_btree_get_numrecs(block) >=  in xfs_btree_delrec()
4277 				       cur->bc_ops->get_minrecs(tcur, level));  in xfs_btree_delrec()
4292 		 * to our block again (last record).  in xfs_btree_delrec()
4297 			if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {  in xfs_btree_delrec()
4299 				error = -EFSCORRUPTED;  in xfs_btree_delrec()
4306 			if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {  in xfs_btree_delrec()
4308 				error = -EFSCORRUPTED;  in xfs_btree_delrec()
4321 		 * previous block.  in xfs_btree_delrec()
4324 		if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {  in xfs_btree_delrec()
4326 			error = -EFSCORRUPTED;  in xfs_btree_delrec()
4334 		if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {  in xfs_btree_delrec()
4336 			error = -EFSCORRUPTED;  in xfs_btree_delrec()
4340 		/* Grab a pointer to the block. */  in xfs_btree_delrec()
4347 		/* Grab the current block number, for future use. */  in xfs_btree_delrec()
4351 		 * If left block is full enough so that removing one entry  in xfs_btree_delrec()
4352 		 * won't make it too empty, and right-shifting an entry out  in xfs_btree_delrec()
4355 		if (xfs_btree_get_numrecs(left) - 1 >=  in xfs_btree_delrec()
4356 		    cur->bc_ops->get_minrecs(tcur, level)) {  in xfs_btree_delrec()
4361 				ASSERT(xfs_btree_get_numrecs(block) >=  in xfs_btree_delrec()
4362 				       cur->bc_ops->get_minrecs(tcur, level));  in xfs_btree_delrec()
4366 					cur->bc_levels[0].ptr++;  in xfs_btree_delrec()
4388 	    lrecs + xfs_btree_get_numrecs(block) <=  in xfs_btree_delrec()
4389 			cur->bc_ops->get_maxrecs(cur, level)) {  in xfs_btree_delrec()
4391 		 * Set "right" to be the starting block,  in xfs_btree_delrec()
4395 		right = block;  in xfs_btree_delrec()
4402 	 * If that won't work, see if we can join with the right neighbor block.  in xfs_btree_delrec()
4405 		   rrecs + xfs_btree_get_numrecs(block) <=  in xfs_btree_delrec()
4406 			cur->bc_ops->get_maxrecs(cur, level)) {  in xfs_btree_delrec()
4408 		 * Set "left" to be the starting block,  in xfs_btree_delrec()
4412 		left = block;  in xfs_btree_delrec()
4438 		/* It's a non-leaf.  Move keys and pointers. */  in xfs_btree_delrec()
4475 	 * Fix up the number of records and right block pointer in the  in xfs_btree_delrec()
4476 	 * surviving block, and log it.  in xfs_btree_delrec()
4483 	/* If there is a right sibling, point it to the remaining block. */  in xfs_btree_delrec()
4493 	/* Free the deleted block. */  in xfs_btree_delrec()
4500 	 * cursor to the left block, and fix up the index.  in xfs_btree_delrec()
4503 		cur->bc_levels[level].bp = lbp;  in xfs_btree_delrec()
4504 		cur->bc_levels[level].ptr += lrecs;  in xfs_btree_delrec()
4505 		cur->bc_levels[level].ra = 0;  in xfs_btree_delrec()
4511 	else if (cur->bc_ops->type == XFS_BTREE_TYPE_INODE ||  in xfs_btree_delrec()
4512 		 level + 1 < cur->bc_nlevels) {  in xfs_btree_delrec()
4525 		cur->bc_levels[level].ptr--;  in xfs_btree_delrec()
4530 	 * bc_levels[level + 1].ptr points to the old block so that the caller  in xfs_btree_delrec()
4580 	if (joined && (cur->bc_ops->geom_flags & XFS_BTGEO_OVERLAPPING)) {  in xfs_btree_delete()
4587 		for (level = 1; level < cur->bc_nlevels; level++) {  in xfs_btree_delete()
4588 			if (cur->bc_levels[level].ptr == 0) {  in xfs_btree_delete()
4604  * Get the data from the pointed-to record.
4612 	struct xfs_btree_block	*block;	/* btree block */  in xfs_btree_get_rec()  local
4619 	ptr = cur->bc_levels[0].ptr;  in xfs_btree_get_rec()
4620 	block = xfs_btree_get_block(cur, 0, &bp);  in xfs_btree_get_rec()
4623 	error = xfs_btree_check_block(cur, block, 0, bp);  in xfs_btree_get_rec()
4631 	if (ptr > xfs_btree_get_numrecs(block) || ptr <= 0) {  in xfs_btree_get_rec()
4639 	*recp = xfs_btree_rec_addr(cur, ptr, block);  in xfs_btree_get_rec()
4644 /* Visit a block in a btree. */
4652 	struct xfs_btree_block		*block;  in xfs_btree_visit_block()  local
4659 	block = xfs_btree_get_block(cur, level, &bp);  in xfs_btree_visit_block()
4661 	/* process the block */  in xfs_btree_visit_block()
4666 	/* now read rh sibling block for next iteration */  in xfs_btree_visit_block()
4667 	xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB);  in xfs_btree_visit_block()
4669 		return -ENOENT;  in xfs_btree_visit_block()
4674 	 * return the same block without checking if the right sibling points  in xfs_btree_visit_block()
4680 		return -EFSCORRUPTED;  in xfs_btree_visit_block()
4683 	return xfs_btree_lookup_get_block(cur, level, &rptr, &block);  in xfs_btree_visit_block()
4687 /* Visit every block in a btree. */
4697 	struct xfs_btree_block		*block = NULL;  in xfs_btree_visit_blocks()  local
4703 	for (level = cur->bc_nlevels - 1; level >= 0; level--) {  in xfs_btree_visit_blocks()
4704 		/* grab the left hand block */  in xfs_btree_visit_blocks()
4705 		error = xfs_btree_lookup_get_block(cur, level, &lptr, &block);  in xfs_btree_visit_blocks()
4709 		/* readahead the left most block for the next level down */  in xfs_btree_visit_blocks()
4713 			ptr = xfs_btree_ptr_addr(cur, 1, block);  in xfs_btree_visit_blocks()
4730 		if (error != -ENOENT)  in xfs_btree_visit_blocks()
4745  * We do the btree walk in the most optimal manner possible - we have sibling
4750  * as the amount of CPU work we have to do before moving to the next block is
4753  * For each btree block that we load, modify the owner appropriately, set the
4773 	struct xfs_btree_block	*block;  in xfs_btree_block_change_owner()  local
4777 	block = xfs_btree_get_block(cur, level, &bp);  in xfs_btree_block_change_owner()
4778 	if (cur->bc_ops->ptr_len == XFS_BTREE_LONG_PTR_LEN) {  in xfs_btree_block_change_owner()
4779 		if (block->bb_u.l.bb_owner == cpu_to_be64(bbcoi->new_owner))  in xfs_btree_block_change_owner()
4781 		block->bb_u.l.bb_owner = cpu_to_be64(bbcoi->new_owner);  in xfs_btree_block_change_owner()
4783 		if (block->bb_u.s.bb_owner == cpu_to_be32(bbcoi->new_owner))  in xfs_btree_block_change_owner()
4785 		block->bb_u.s.bb_owner = cpu_to_be32(bbcoi->new_owner);  in xfs_btree_block_change_owner()
4789 	 * If the block is a root block hosted in an inode, we might not have a  in xfs_btree_block_change_owner()
4792 	 * block is formatted into the on-disk inode fork. We still change it,  in xfs_btree_block_change_owner()
4796 		ASSERT(cur->bc_ops->type == XFS_BTREE_TYPE_INODE);  in xfs_btree_block_change_owner()
4797 		ASSERT(level == cur->bc_nlevels - 1);  in xfs_btree_block_change_owner()
4801 	if (cur->bc_tp) {  in xfs_btree_block_change_owner()
4802 		if (!xfs_trans_ordered_buf(cur->bc_tp, bp)) {  in xfs_btree_block_change_owner()
4804 			return -EAGAIN;  in xfs_btree_block_change_owner()
4807 		xfs_buf_delwri_queue(bp, bbcoi->buffer_list);  in xfs_btree_block_change_owner()
4828 /* Verify the v5 fields of a long-format btree block. */
4834 	struct xfs_mount	*mp = bp->b_mount;  in xfs_btree_fsblock_v5hdr_verify()
4835 	struct xfs_btree_block	*block = XFS_BUF_TO_BLOCK(bp);  in xfs_btree_fsblock_v5hdr_verify()  local
4839 	if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid))  in xfs_btree_fsblock_v5hdr_verify()
4841 	if (block->bb_u.l.bb_blkno != cpu_to_be64(xfs_buf_daddr(bp)))  in xfs_btree_fsblock_v5hdr_verify()
4844 	    be64_to_cpu(block->bb_u.l.bb_owner) != owner)  in xfs_btree_fsblock_v5hdr_verify()
4849 /* Verify a long-format btree block. */
4855 	struct xfs_mount	*mp = bp->b_mount;  in xfs_btree_fsblock_verify()
4856 	struct xfs_btree_block	*block = XFS_BUF_TO_BLOCK(bp);  in xfs_btree_fsblock_verify()  local
4860 	ASSERT(!xfs_buftarg_is_mem(bp->b_target));  in xfs_btree_fsblock_verify()
4863 	if (be16_to_cpu(block->bb_numrecs) > max_recs)  in xfs_btree_fsblock_verify()
4869 			block->bb_u.l.bb_leftsib);  in xfs_btree_fsblock_verify()
4872 				block->bb_u.l.bb_rightsib);  in xfs_btree_fsblock_verify()
4876 /* Verify an in-memory btree block. */
4882 	struct xfs_btree_block	*block = XFS_BUF_TO_BLOCK(bp);  in xfs_btree_memblock_verify()  local
4883 	struct xfs_buftarg	*btp = bp->b_target;  in xfs_btree_memblock_verify()
4887 	ASSERT(xfs_buftarg_is_mem(bp->b_target));  in xfs_btree_memblock_verify()
4890 	if (be16_to_cpu(block->bb_numrecs) > max_recs)  in xfs_btree_memblock_verify()
4896 			block->bb_u.l.bb_leftsib);  in xfs_btree_memblock_verify()
4900 			block->bb_u.l.bb_rightsib);  in xfs_btree_memblock_verify()
4907  * xfs_btree_agblock_v5hdr_verify() -- verify the v5 fields of a short-format
4908  *				      btree block
4910  * @bp: buffer containing the btree block
4916 	struct xfs_mount	*mp = bp->b_mount;  in xfs_btree_agblock_v5hdr_verify()
4917 	struct xfs_btree_block	*block = XFS_BUF_TO_BLOCK(bp);  in xfs_btree_agblock_v5hdr_verify()  local
4918 	struct xfs_perag	*pag = bp->b_pag;  in xfs_btree_agblock_v5hdr_verify()
4922 	if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid))  in xfs_btree_agblock_v5hdr_verify()
4924 	if (block->bb_u.s.bb_blkno != cpu_to_be64(xfs_buf_daddr(bp)))  in xfs_btree_agblock_v5hdr_verify()
4926 	if (pag && be32_to_cpu(block->bb_u.s.bb_owner) != pag_agno(pag))  in xfs_btree_agblock_v5hdr_verify()
4932  * xfs_btree_agblock_verify() -- verify a short-format btree block
4934  * @bp: buffer containing the btree block
4942 	struct xfs_mount	*mp = bp->b_mount;  in xfs_btree_agblock_verify()
4943 	struct xfs_btree_block	*block = XFS_BUF_TO_BLOCK(bp);  in xfs_btree_agblock_verify()  local
4947 	ASSERT(!xfs_buftarg_is_mem(bp->b_target));  in xfs_btree_agblock_verify()
4950 	if (be16_to_cpu(block->bb_numrecs) > max_recs)  in xfs_btree_agblock_verify()
4955 	fa = xfs_btree_check_agblock_siblings(bp->b_pag, agbno,  in xfs_btree_agblock_verify()
4956 			block->bb_u.s.bb_leftsib);  in xfs_btree_agblock_verify()
4958 		fa = xfs_btree_check_agblock_siblings(bp->b_pag, agbno,  in xfs_btree_agblock_verify()
4959 				block->bb_u.s.bb_rightsib);  in xfs_btree_agblock_verify()
4964  * For the given limits on leaf and keyptr records per block, calculate the
4984  * For the given limits on leaf and keyptr records per block, calculate the
5009  * We start by assuming a single level tree consumes a single block, then track
5021 	 * The root btree block can have fewer than minrecs pointers in it  in xfs_btree_space_to_height()
5026 	unsigned long long	blocks_left = leaf_blocks - 1;  in xfs_btree_space_to_height()
5033 		blocks_left -= node_blocks;  in xfs_btree_space_to_height()
5060 	ASSERT(cur->bc_ops->init_high_key_from_rec);  in xfs_btree_simple_query_range()
5061 	ASSERT(cur->bc_ops->diff_two_keys);  in xfs_btree_simple_query_range()
5087 			cur->bc_ops->init_high_key_from_rec(&rec_key, recp);  in xfs_btree_simple_query_range()
5094 		cur->bc_ops->init_key_from_rec(&rec_key, recp);  in xfs_btree_simple_query_range()
5130  * As an optimization, we stop scanning a block when we find a low key
5148 	struct xfs_btree_block		*block;  in xfs_btree_overlapped_query_range()  local
5155 	level = cur->bc_nlevels - 1;  in xfs_btree_overlapped_query_range()
5157 	error = xfs_btree_lookup_get_block(cur, level, &ptr, &block);  in xfs_btree_overlapped_query_range()
5163 	error = xfs_btree_check_block(cur, block, level, bp);  in xfs_btree_overlapped_query_range()
5167 	cur->bc_levels[level].ptr = 1;  in xfs_btree_overlapped_query_range()
5169 	while (level < cur->bc_nlevels) {  in xfs_btree_overlapped_query_range()
5170 		block = xfs_btree_get_block(cur, level, &bp);  in xfs_btree_overlapped_query_range()
5173 		if (cur->bc_levels[level].ptr >  in xfs_btree_overlapped_query_range()
5174 					be16_to_cpu(block->bb_numrecs)) {  in xfs_btree_overlapped_query_range()
5176 			if (level < cur->bc_nlevels - 1)  in xfs_btree_overlapped_query_range()
5177 				cur->bc_levels[level + 1].ptr++;  in xfs_btree_overlapped_query_range()
5184 			recp = xfs_btree_rec_addr(cur, cur->bc_levels[0].ptr,  in xfs_btree_overlapped_query_range()
5185 					block);  in xfs_btree_overlapped_query_range()
5187 			cur->bc_ops->init_high_key_from_rec(&rec_hkey, recp);  in xfs_btree_overlapped_query_range()
5188 			cur->bc_ops->init_key_from_rec(&rec_key, recp);  in xfs_btree_overlapped_query_range()
5192 			 * are no more interesting records in this block.  Pop  in xfs_btree_overlapped_query_range()
5206 			cur->bc_levels[level].ptr++;  in xfs_btree_overlapped_query_range()
5211 		lkp = xfs_btree_key_addr(cur, cur->bc_levels[level].ptr, block);  in xfs_btree_overlapped_query_range()
5212 		hkp = xfs_btree_high_key_addr(cur, cur->bc_levels[level].ptr,  in xfs_btree_overlapped_query_range()
5213 				block);  in xfs_btree_overlapped_query_range()
5214 		pp = xfs_btree_ptr_addr(cur, cur->bc_levels[level].ptr, block);  in xfs_btree_overlapped_query_range()
5218 		 * more interesting keys in this block.  Pop up one leaf level  in xfs_btree_overlapped_query_range()
5228 			level--;  in xfs_btree_overlapped_query_range()
5230 					&block);  in xfs_btree_overlapped_query_range()
5236 			error = xfs_btree_check_block(cur, block, level, bp);  in xfs_btree_overlapped_query_range()
5240 			cur->bc_levels[level].ptr = 1;  in xfs_btree_overlapped_query_range()
5243 		cur->bc_levels[level].ptr++;  in xfs_btree_overlapped_query_range()
5249 	 * block, a subsequent non-error cursor deletion will not release  in xfs_btree_overlapped_query_range()
5250 	 * node-level buffers, causing a buffer leak.  This is quite possible  in xfs_btree_overlapped_query_range()
5251 	 * with a zero-results range query, so release the buffers if we  in xfs_btree_overlapped_query_range()
5254 	if (cur->bc_levels[0].bp == NULL) {  in xfs_btree_overlapped_query_range()
5255 		for (i = 0; i < cur->bc_nlevels; i++) {  in xfs_btree_overlapped_query_range()
5256 			if (cur->bc_levels[i].bp) {  in xfs_btree_overlapped_query_range()
5257 				xfs_trans_brelse(cur->bc_tp,  in xfs_btree_overlapped_query_range()
5258 						cur->bc_levels[i].bp);  in xfs_btree_overlapped_query_range()
5259 				cur->bc_levels[i].bp = NULL;  in xfs_btree_overlapped_query_range()
5260 				cur->bc_levels[i].ptr = 0;  in xfs_btree_overlapped_query_range()
5261 				cur->bc_levels[i].ra = 0;  in xfs_btree_overlapped_query_range()
5277 	cur->bc_rec = *irec;  in xfs_btree_key_from_irec()
5278 	cur->bc_ops->init_rec_from_cur(cur, &rec);  in xfs_btree_key_from_irec()
5279 	cur->bc_ops->init_key_from_rec(key, &rec);  in xfs_btree_key_from_irec()
5286  * code.  This function returns -ECANCELED, zero, or a negative error code.
5305 		return -EINVAL;  in xfs_btree_query_range()
5307 	if (!(cur->bc_ops->geom_flags & XFS_BTGEO_OVERLAPPING))  in xfs_btree_query_range()
5324 	memset(&cur->bc_rec, 0, sizeof(cur->bc_rec));  in xfs_btree_query_all()
5361 	if (cur->bc_ops->ptr_len == XFS_BTREE_LONG_PTR_LEN)  in xfs_btree_diff_two_ptrs()
5362 		return (int64_t)be64_to_cpu(a->l) - be64_to_cpu(b->l);  in xfs_btree_diff_two_ptrs()
5363 	return (int64_t)be32_to_cpu(a->s) - be32_to_cpu(b->s);  in xfs_btree_diff_two_ptrs()
5391 	cur->bc_ops->init_key_from_rec(&rec_key, rec);  in xfs_btree_has_records_helper()
5393 	if (info->outcome == XBTREE_RECPACKING_EMPTY) {  in xfs_btree_has_records_helper()
5394 		info->outcome = XBTREE_RECPACKING_SPARSE;  in xfs_btree_has_records_helper()
5401 		if (xfs_btree_masked_keycmp_lt(cur, &info->start_key, &rec_key,  in xfs_btree_has_records_helper()
5402 					info->key_mask))  in xfs_btree_has_records_helper()
5403 			return -ECANCELED;  in xfs_btree_has_records_helper()
5412 		key_contig = cur->bc_ops->keys_contiguous(cur, &info->high_key,  in xfs_btree_has_records_helper()
5413 					&rec_key, info->key_mask);  in xfs_btree_has_records_helper()
5415 				!(cur->bc_ops->geom_flags & XFS_BTGEO_OVERLAPPING))  in xfs_btree_has_records_helper()
5416 			return -EFSCORRUPTED;  in xfs_btree_has_records_helper()
5418 			return -ECANCELED;  in xfs_btree_has_records_helper()
5425 	cur->bc_ops->init_high_key_from_rec(&rec_high_key, rec);  in xfs_btree_has_records_helper()
5426 	if (xfs_btree_masked_keycmp_gt(cur, &rec_high_key, &info->high_key,  in xfs_btree_has_records_helper()
5427 				info->key_mask))  in xfs_btree_has_records_helper()
5428 		info->high_key = rec_high_key; /* struct copy */  in xfs_btree_has_records_helper()
5462 	if (!cur->bc_ops->keys_contiguous) {  in xfs_btree_has_records()
5464 		return -EOPNOTSUPP;  in xfs_btree_has_records()
5472 	if (error == -ECANCELED)  in xfs_btree_has_records()
5499 	struct xfs_btree_block	*block;  in xfs_btree_has_more_records()  local
5502 	block = xfs_btree_get_block(cur, 0, &bp);  in xfs_btree_has_more_records()
5504 	/* There are still records in this block. */  in xfs_btree_has_more_records()
5505 	if (cur->bc_levels[0].ptr < xfs_btree_get_numrecs(block))  in xfs_btree_has_more_records()
5509 	if (cur->bc_ops->ptr_len == XFS_BTREE_LONG_PTR_LEN)  in xfs_btree_has_more_records()
5510 		return block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK);  in xfs_btree_has_more_records()
5512 		return block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK);  in xfs_btree_has_more_records()
5570 	memset(&cur->bc_rec, 0, sizeof(cur->bc_rec));  in xfs_btree_goto_left_edge()
5583 		return -EFSCORRUPTED;  in xfs_btree_goto_left_edge()
5589 /* Allocate a block for an inode-rooted metadata btree. */
5598 		.mp			= cur->bc_mp,  in xfs_btree_alloc_metafile_block()
5599 		.tp			= cur->bc_tp,  in xfs_btree_alloc_metafile_block()
5605 	struct xfs_inode		*ip = cur->bc_ino.ip;  in xfs_btree_alloc_metafile_block()
5610 	xfs_rmap_ino_bmbt_owner(&args.oinfo, ip->i_ino, cur->bc_ino.whichfork);  in xfs_btree_alloc_metafile_block()
5612 			XFS_INO_TO_FSB(cur->bc_mp, ip->i_ino));  in xfs_btree_alloc_metafile_block()
5623 	new->l = cpu_to_be64(args.fsbno);  in xfs_btree_alloc_metafile_block()
5628 /* Free a block from an inode-rooted metadata btree. */
5635 	struct xfs_mount	*mp = cur->bc_mp;  in xfs_btree_free_metafile_block()
5636 	struct xfs_inode	*ip = cur->bc_ino.ip;  in xfs_btree_free_metafile_block()
5637 	struct xfs_trans	*tp = cur->bc_tp;  in xfs_btree_free_metafile_block()
5643 	xfs_rmap_ino_bmbt_owner(&oinfo, ip->i_ino, cur->bc_ino.whichfork);  in xfs_btree_free_metafile_block()