127 	struct xfs_btree_block	*block,  in __xfs_btree_check_lblock_hdr()  argument
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()
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
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
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
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()
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
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()
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()
307 	fa = __xfs_btree_check_block(cur, block, level, bp);  in xfs_btree_check_block()
398  * Calculate CRC on the whole btree block and stuff it into the
409 	struct xfs_btree_block	*block = XFS_BUF_TO_BLOCK(bp);  in xfs_btree_fsblock_calc_crc()  local
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
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
447 	struct xfs_btree_block	*block = XFS_BUF_TO_BLOCK(bp);  in xfs_btree_agblock_calc_crc()  local
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
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()
547 /* Return the block size (in units of 512b sectors) for this btree. */
620  * XFS btree block layout and addressing:
625  * the values.  A non-leaf block also starts with the same header, and
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!
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
682  * Now say we want to map block (B+D) into file A at offset (C+D).  Ideally,
694  * Return size of the btree block header for this btree instance.
709  * Calculate offset of the n-th record in a btree block.
721  * Calculate offset of the n-th key in a btree block.
733  * Calculate offset of the n-th high key in a btree block.
745  * Calculate offset of the n-th block pointer in a btree block.
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()
826  * Get the root block which is stored in the inode.
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()
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()
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()
959 	struct xfs_btree_block	*block)  in xfs_btree_readahead_fsblock()  argument
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()
985 	struct xfs_btree_block	*block)  in xfs_btree_readahead_memblock()  argument
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()
1011 	struct xfs_btree_block	*block)  in xfs_btree_readahead_agblock()  argument
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()
1046 	struct xfs_btree_block	*block;  in xfs_btree_readahead()  local
1059 	block = XFS_BUF_TO_BLOCK(cur->bc_levels[lev].bp);  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()
1132 	struct xfs_btree_block	*b;	/* btree block */  in xfs_btree_setbuf()
1192 	struct xfs_btree_block	*block,  in xfs_btree_get_sibling()  argument
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
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()
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()
1361 	struct xfs_btree_block		**block,  in xfs_btree_get_buf_block()  argument
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
1411 	*block = XFS_BUF_TO_BLOCK(*bpp);  in xfs_btree_read_buf_block()
1416  * Copy keys from one btree block to another.
1430  * Copy records from one btree block to another.
1444  * Copy block pointers from one btree block to another.
1458  * Shift keys one index left/right inside a single btree block.
1477  * Shift records one index left/right inside a single btree block.
1496  * Shift block pointers one index left/right inside a single btree block.
1515  * Log key values from the btree block.
1537  * Log record values from the btree block.
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()
1585  * Log fields from a btree block header.
1590 	struct xfs_buf		*bp,	/* buffer containing btree block */  in xfs_btree_log_block()
1629 			 * block but instead recreate it during log  in xfs_btree_log_block()
1662 	struct xfs_btree_block	*block;  in xfs_btree_increment()  local
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()
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()
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()
1736 		error = xfs_btree_read_buf_block(cur, ptrp, 0, &block, &bp);  in xfs_btree_increment()
1765 	struct xfs_btree_block	*block;  in xfs_btree_decrement()  local
1776 	/* We're done if we remain in the block after the decrement. */  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()
1803 		/* Read-ahead the left block for the next loop. */  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()
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
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()
1944 	struct xfs_btree_block	*block,  in xfs_lookup_get_search_key()  argument
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.
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()
2003 	block = NULL;  in xfs_btree_lookup()
2013 	 * on the lookup record, then follow the corresponding block  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()
2036 			high = xfs_btree_get_numrecs(block);  in xfs_btree_lookup()
2038 				/* Block is empty, must be an empty leaf. */  in xfs_btree_lookup()
2042 							cur->bc_mp, block,  in xfs_btree_lookup()
2043 							sizeof(*block));  in xfs_btree_lookup()
2053 			/* Binary search the block. */  in xfs_btree_lookup()
2065 						keyno, block, &key);  in xfs_btree_lookup()
2085 		 * by getting the block number and filling in the cursor.  in xfs_btree_lookup()
2094 			pp = xfs_btree_ptr_addr(cur, keyno, block);  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()
2133 	if (keyno == 0 || keyno > xfs_btree_get_numrecs(block))  in xfs_btree_lookup()
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()
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()
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
2200 		memcpy(key, xfs_btree_key_addr(cur, 1, block),  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()
2213 		memcpy(key, xfs_btree_key_addr(cur, 1, block),  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.
2255 	struct xfs_btree_block	*block,  in __xfs_btree_updkeys()  argument
2277 	xfs_btree_get_keys(cur, block, lkey);  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()
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()
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()
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()
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()
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()
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()
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()
2559 	 * block on the left.  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()
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()
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()
2730 	 * block on the right.  in xfs_btree_rshift()
2746 	/* Update the parent high keys of the left block, if needed. */  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()
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()
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()
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()
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()
2958 	 * If the cursor is really in the right block, move it there.  in __xfs_btree_split()
2968 	 * the right block, no matter where this cursor was.  in __xfs_btree_split()
3016 	 * temporarily to ensure that we don't block waiting for memory reclaim  in xfs_btree_split_worker()
3045  * AGF <> worker queue deadlocks if the BMBT block allocation has to lock new
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()
3127 	 * child block.  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.
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()
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()
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
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()
3240 	block = xfs_btree_get_iroot(cur);  in xfs_btree_new_iroot()
3243 		aptr = *xfs_btree_ptr_addr(cur, 1, block);  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()
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()
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()
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()
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()
3454 			/* A root block that can be made bigger. */  in xfs_btree_make_block_unfull()
3458 			/* A root block that needs replacing */  in xfs_btree_make_block_unfull()
3487 	 * Next, try splitting the current block in half.  in xfs_btree_make_block_unfull()
3490 	 * could be in a different block now.  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()
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()
3568 				xfs_btree_rec_addr(cur, ptr, block)));  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()
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()
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()
3632 		xfs_btree_set_numrecs(block, numrecs);  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()
3651 		xfs_btree_set_numrecs(block, ++numrecs);  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()
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()
3751 	 * Stop when we don't get a split block, that must mean that  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()
3839  * Move the keyptrs from a child node block to the root block.
3852 	struct xfs_btree_block	*block;  in xfs_btree_demote_node_child()  local
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()
3885 	/* Decrease tree height, adjusting the root block level to match. */  in xfs_btree_demote_node_child()
3887 	be16_add_cpu(&block->bb_level, -1);  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
3905 	struct xfs_btree_block	*block;  in xfs_btree_kill_iroot()  local
3920 	 * Don't deal with the root block needs to be a leaf case.  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()
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()
4029  * Remove the record from its block then rebalance the tree.
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()
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()
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()
4110 				xfs_btree_rec_addr(cur, ptr + 1, block),  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()
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()
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()
4229 		 * Move the temp cursor to the last entry in the next block.  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()
4276 				ASSERT(xfs_btree_get_numrecs(block) >=  in xfs_btree_delrec()
4292 		 * to our block again (last record).  in xfs_btree_delrec()
4321 		 * previous block.  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()
4361 				ASSERT(xfs_btree_get_numrecs(block) >=  in xfs_btree_delrec()
4388 	    lrecs + xfs_btree_get_numrecs(block) <=  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()
4408 		 * Set "left" to be the starting block,  in xfs_btree_delrec()
4412 		left = block;  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()
4530 	 * bc_levels[level + 1].ptr points to the old block so that the caller  in xfs_btree_delrec()
4612 	struct xfs_btree_block	*block;	/* btree block */  in xfs_btree_get_rec()  local
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()
4674 	 * return the same block without checking if the right sibling points  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
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()
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()
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()
4828 /* Verify the v5 fields of a long-format btree block. */
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. */
4856 	struct xfs_btree_block	*block = XFS_BUF_TO_BLOCK(bp);  in xfs_btree_fsblock_verify()  local
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
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()
4908  *				      btree block
4910  * @bp: buffer containing the btree block
4917 	struct xfs_btree_block	*block = XFS_BUF_TO_BLOCK(bp);  in xfs_btree_agblock_v5hdr_verify()  local
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
4943 	struct xfs_btree_block	*block = XFS_BUF_TO_BLOCK(bp);  in xfs_btree_agblock_verify()  local
4950 	if (be16_to_cpu(block->bb_numrecs) > max_recs)  in xfs_btree_agblock_verify()
4956 			block->bb_u.s.bb_leftsib);  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()
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
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()
5170 		block = xfs_btree_get_block(cur, level, &bp);  in xfs_btree_overlapped_query_range()
5174 					be16_to_cpu(block->bb_numrecs)) {  in xfs_btree_overlapped_query_range()
5185 					block);  in xfs_btree_overlapped_query_range()
5192 			 * are no more interesting records in this block.  Pop  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()
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()
5230 					&block);  in xfs_btree_overlapped_query_range()
5236 			error = xfs_btree_check_block(cur, block, level, bp);  in xfs_btree_overlapped_query_range()
5249 	 * block, a subsequent non-error cursor deletion will not release  in xfs_btree_overlapped_query_range()
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()
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()
5589 /* Allocate a block for an inode-rooted metadata btree. */
5628 /* Free a block from an inode-rooted metadata btree. */