Lines Matching full:block
53 * Check a long btree block header. Return the address of the failing check,
59 struct xfs_btree_block *block, in __xfs_btree_check_lblock() argument
68 if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid)) in __xfs_btree_check_lblock()
70 if (block->bb_u.l.bb_blkno != in __xfs_btree_check_lblock()
73 if (block->bb_u.l.bb_pad != cpu_to_be32(0)) in __xfs_btree_check_lblock()
77 if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(crc, btnum)) in __xfs_btree_check_lblock()
79 if (be16_to_cpu(block->bb_level) != level) in __xfs_btree_check_lblock()
81 if (be16_to_cpu(block->bb_numrecs) > in __xfs_btree_check_lblock()
84 if (block->bb_u.l.bb_leftsib != cpu_to_be64(NULLFSBLOCK) && in __xfs_btree_check_lblock()
85 !xfs_btree_check_lptr(cur, be64_to_cpu(block->bb_u.l.bb_leftsib), in __xfs_btree_check_lblock()
88 if (block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK) && in __xfs_btree_check_lblock()
89 !xfs_btree_check_lptr(cur, be64_to_cpu(block->bb_u.l.bb_rightsib), in __xfs_btree_check_lblock()
96 /* Check a long btree block header. */
100 struct xfs_btree_block *block, in xfs_btree_check_lblock() argument
107 fa = __xfs_btree_check_lblock(cur, block, level, bp); in xfs_btree_check_lblock()
119 * Check a short btree block header. Return the address of the failing check,
125 struct xfs_btree_block *block, in __xfs_btree_check_sblock() argument
134 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid)) in __xfs_btree_check_sblock()
136 if (block->bb_u.s.bb_blkno != in __xfs_btree_check_sblock()
141 if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(crc, btnum)) in __xfs_btree_check_sblock()
143 if (be16_to_cpu(block->bb_level) != level) in __xfs_btree_check_sblock()
145 if (be16_to_cpu(block->bb_numrecs) > in __xfs_btree_check_sblock()
148 if (block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK) && in __xfs_btree_check_sblock()
149 !xfs_btree_check_sptr(cur, be32_to_cpu(block->bb_u.s.bb_leftsib), in __xfs_btree_check_sblock()
152 if (block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK) && in __xfs_btree_check_sblock()
153 !xfs_btree_check_sptr(cur, be32_to_cpu(block->bb_u.s.bb_rightsib), in __xfs_btree_check_sblock()
160 /* Check a short btree block header. */
164 struct xfs_btree_block *block, in xfs_btree_check_sblock() argument
171 fa = __xfs_btree_check_sblock(cur, block, level, bp); in xfs_btree_check_sblock()
183 * Debug routine: check that block header is ok.
188 struct xfs_btree_block *block, /* generic btree block pointer */ in xfs_btree_check_block() argument
189 int level, /* level of the btree block */ in xfs_btree_check_block()
190 struct xfs_buf *bp) /* buffer containing block, if any */ in xfs_btree_check_block()
193 return xfs_btree_check_lblock(cur, block, level, bp); in xfs_btree_check_block()
195 return xfs_btree_check_sblock(cur, block, level, bp); in xfs_btree_check_block()
262 * Calculate CRC on the whole btree block and stuff it into the
273 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_lblock_calc_crc() local
279 block->bb_u.l.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn); in xfs_btree_lblock_calc_crc()
287 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_lblock_verify_crc() local
291 if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.l.bb_lsn))) in xfs_btree_lblock_verify_crc()
300 * Calculate CRC on the whole btree block and stuff it into the
311 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_sblock_calc_crc() local
317 block->bb_u.s.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn); in xfs_btree_sblock_calc_crc()
325 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_sblock_verify_crc() local
329 if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.s.bb_lsn))) in xfs_btree_sblock_verify_crc()
399 xfs_buf_t *bp; /* btree block's buffer pointer */ in xfs_btree_dup_cursor()
401 int i; /* level number of btree block */ in xfs_btree_dup_cursor()
444 * XFS btree block layout and addressing:
449 * the values. A non-leaf block also starts with the same header, and
462 * and comes in different versions for short (32bit) and long (64bit) block
464 * and opaque to the btree core. The block pointers are simple disk endian
468 * into a btree block (xfs_btree_*_offset) or return a pointer to the given
470 * inside the btree block is done using indices starting at one, not zero!
476 * indexing the lowest key available in the block(s) below (the same behavior
478 * available in the block(s) below. Because records are /not/ sorted by the
479 * highest key, all leaf block updates require us to compute the highest key
506 * Now say we want to map block (B+D) into file A at offset (C+D). Ideally,
518 * Return size of the btree block header for this btree instance.
533 * Return size of btree block pointers for this btree instance.
542 * Calculate offset of the n-th record in a btree block.
554 * Calculate offset of the n-th key in a btree block.
566 * Calculate offset of the n-th high key in a btree block.
578 * Calculate offset of the n-th block pointer in a btree block.
592 * Return a pointer to the n-th record in the btree block.
598 struct xfs_btree_block *block) in xfs_btree_rec_addr() argument
601 ((char *)block + xfs_btree_rec_offset(cur, n)); in xfs_btree_rec_addr()
605 * Return a pointer to the n-th key in the btree block.
611 struct xfs_btree_block *block) in xfs_btree_key_addr() argument
614 ((char *)block + xfs_btree_key_offset(cur, n)); in xfs_btree_key_addr()
618 * Return a pointer to the n-th high key in the btree block.
624 struct xfs_btree_block *block) in xfs_btree_high_key_addr() argument
627 ((char *)block + xfs_btree_high_key_offset(cur, n)); in xfs_btree_high_key_addr()
631 * Return a pointer to the n-th block pointer in the btree block.
637 struct xfs_btree_block *block) in xfs_btree_ptr_addr() argument
639 int level = xfs_btree_get_level(block); in xfs_btree_ptr_addr()
641 ASSERT(block->bb_level != 0); in xfs_btree_ptr_addr()
644 ((char *)block + xfs_btree_ptr_offset(cur, n, level)); in xfs_btree_ptr_addr()
648 * Get the root block which is stored in the inode.
664 * Retrieve the block pointer from the cursor at the given level.
667 struct xfs_btree_block * /* generic btree block pointer */
671 struct xfs_buf **bpp) /* buffer containing the block */ in xfs_btree_get_block()
684 * Get a buffer for the block, return it with no data read.
691 xfs_fsblock_t fsbno) /* file system block number */ in xfs_btree_get_bufl()
693 xfs_daddr_t d; /* real disk block address */ in xfs_btree_get_bufl()
701 * Get a buffer for the block, return it with no data read.
709 xfs_agblock_t agbno) /* allocation group block number */ in xfs_btree_get_bufs()
711 xfs_daddr_t d; /* real disk block address */ in xfs_btree_get_bufs()
720 * Check for the cursor referring to the last block at the given level.
722 int /* 1=is last block, 0=not last block */
727 struct xfs_btree_block *block; /* generic btree block pointer */ in xfs_btree_islastblock() local
728 xfs_buf_t *bp; /* buffer containing block */ in xfs_btree_islastblock()
730 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_islastblock()
731 xfs_btree_check_block(cur, block, level, bp); in xfs_btree_islastblock()
733 return block->bb_u.l.bb_rightsib == cpu_to_be64(NULLFSBLOCK); in xfs_btree_islastblock()
735 return block->bb_u.s.bb_rightsib == cpu_to_be32(NULLAGBLOCK); in xfs_btree_islastblock()
747 struct xfs_btree_block *block; /* generic btree block pointer */ in xfs_btree_firstrec() local
748 xfs_buf_t *bp; /* buffer containing block */ in xfs_btree_firstrec()
751 * Get the block pointer for this level. in xfs_btree_firstrec()
753 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_firstrec()
754 if (xfs_btree_check_block(cur, block, level, bp)) in xfs_btree_firstrec()
759 if (!block->bb_numrecs) in xfs_btree_firstrec()
769 * Change the cursor to point to the last record in the current block
777 struct xfs_btree_block *block; /* generic btree block pointer */ in xfs_btree_lastrec() local
778 xfs_buf_t *bp; /* buffer containing block */ in xfs_btree_lastrec()
781 * Get the block pointer for this level. in xfs_btree_lastrec()
783 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_lastrec()
784 if (xfs_btree_check_block(cur, block, level, bp)) in xfs_btree_lastrec()
789 if (!block->bb_numrecs) in xfs_btree_lastrec()
794 cur->bc_ptrs[level] = be16_to_cpu(block->bb_numrecs); in xfs_btree_lastrec()
835 * Get a buffer for the block, return it read in.
842 xfs_fsblock_t fsbno, /* file system block number */ in xfs_btree_read_bufl()
848 xfs_daddr_t d; /* real disk block address */ in xfs_btree_read_bufl()
865 * Read-ahead the block, don't wait for it, don't return a buffer.
872 xfs_fsblock_t fsbno, /* file system block number */ in xfs_btree_reada_bufl()
884 * Read-ahead the block, don't wait for it, don't return a buffer.
892 xfs_agblock_t agbno, /* allocation group block number */ in xfs_btree_reada_bufs()
908 struct xfs_btree_block *block) in xfs_btree_readahead_lblock() argument
911 xfs_fsblock_t left = be64_to_cpu(block->bb_u.l.bb_leftsib); in xfs_btree_readahead_lblock()
912 xfs_fsblock_t right = be64_to_cpu(block->bb_u.l.bb_rightsib); in xfs_btree_readahead_lblock()
933 struct xfs_btree_block *block) in xfs_btree_readahead_sblock() argument
936 xfs_agblock_t left = be32_to_cpu(block->bb_u.s.bb_leftsib); in xfs_btree_readahead_sblock()
937 xfs_agblock_t right = be32_to_cpu(block->bb_u.s.bb_rightsib); in xfs_btree_readahead_sblock()
965 struct xfs_btree_block *block; in xfs_btree_readahead() local
979 block = XFS_BUF_TO_BLOCK(cur->bc_bufs[lev]); in xfs_btree_readahead()
982 return xfs_btree_readahead_lblock(cur, lr, block); in xfs_btree_readahead()
983 return xfs_btree_readahead_sblock(cur, lr, block); in xfs_btree_readahead()
1042 struct xfs_btree_block *b; /* btree block */ in xfs_btree_setbuf()
1091 struct xfs_btree_block *block, in xfs_btree_get_sibling() argument
1099 ptr->l = block->bb_u.l.bb_rightsib; in xfs_btree_get_sibling()
1101 ptr->l = block->bb_u.l.bb_leftsib; in xfs_btree_get_sibling()
1104 ptr->s = block->bb_u.s.bb_rightsib; in xfs_btree_get_sibling()
1106 ptr->s = block->bb_u.s.bb_leftsib; in xfs_btree_get_sibling()
1113 struct xfs_btree_block *block, in xfs_btree_set_sibling() argument
1121 block->bb_u.l.bb_rightsib = ptr->l; in xfs_btree_set_sibling()
1123 block->bb_u.l.bb_leftsib = ptr->l; in xfs_btree_set_sibling()
1126 block->bb_u.s.bb_rightsib = ptr->s; in xfs_btree_set_sibling()
1128 block->bb_u.s.bb_leftsib = ptr->s; in xfs_btree_set_sibling()
1221 struct xfs_btree_block *block, in xfs_btree_is_lastrec() argument
1231 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); in xfs_btree_is_lastrec()
1284 struct xfs_btree_block **block, in xfs_btree_get_buf_block() argument
1301 *block = XFS_BUF_TO_BLOCK(*bpp); in xfs_btree_get_buf_block()
1307 * the block pointer within the buffer.
1314 struct xfs_btree_block **block, in xfs_btree_read_buf_block() argument
1334 *block = XFS_BUF_TO_BLOCK(*bpp); in xfs_btree_read_buf_block()
1339 * Copy keys from one btree block to another.
1353 * Copy records from one btree block to another.
1367 * Copy block pointers from one btree block to another.
1381 * Shift keys one index left/right inside a single btree block.
1400 * Shift records one index left/right inside a single btree block.
1419 * Shift block pointers one index left/right inside a single btree block.
1438 * Log key values from the btree block.
1460 * Log record values from the btree block.
1478 * Log block pointer fields from a btree block (nonleaf).
1483 struct xfs_buf *bp, /* buffer containing btree block */ in xfs_btree_log_ptrs()
1489 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_log_ptrs() local
1490 int level = xfs_btree_get_level(block); in xfs_btree_log_ptrs()
1504 * Log fields from a btree block header.
1509 struct xfs_buf *bp, /* buffer containing btree block */ in xfs_btree_log_block()
1548 * block but instead recreate it during log in xfs_btree_log_block()
1581 struct xfs_btree_block *block; in xfs_btree_increment() local
1592 /* Get a pointer to the btree block. */ in xfs_btree_increment()
1593 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_increment()
1596 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_increment()
1601 /* We're done if we remain in the block after the increment. */ in xfs_btree_increment()
1602 if (++cur->bc_ptrs[level] <= xfs_btree_get_numrecs(block)) in xfs_btree_increment()
1606 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); in xfs_btree_increment()
1614 * Stop when we don't go off the right edge of a block. in xfs_btree_increment()
1617 block = xfs_btree_get_block(cur, lev, &bp); in xfs_btree_increment()
1620 error = xfs_btree_check_block(cur, block, lev, bp); in xfs_btree_increment()
1625 if (++cur->bc_ptrs[lev] <= xfs_btree_get_numrecs(block)) in xfs_btree_increment()
1628 /* Read-ahead the right block for the next loop. */ in xfs_btree_increment()
1649 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) { in xfs_btree_increment()
1652 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block); in xfs_btree_increment()
1654 error = xfs_btree_read_buf_block(cur, ptrp, 0, &block, &bp); in xfs_btree_increment()
1683 struct xfs_btree_block *block; in xfs_btree_decrement() local
1694 /* We're done if we remain in the block after the decrement. */ in xfs_btree_decrement()
1698 /* Get a pointer to the btree block. */ in xfs_btree_decrement()
1699 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_decrement()
1702 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_decrement()
1708 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB); in xfs_btree_decrement()
1716 * Stop when we don't go off the left edge of a block. in xfs_btree_decrement()
1721 /* Read-ahead the left block for the next loop. */ in xfs_btree_decrement()
1742 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) { in xfs_btree_decrement()
1745 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block); in xfs_btree_decrement()
1747 error = xfs_btree_read_buf_block(cur, ptrp, 0, &block, &bp); in xfs_btree_decrement()
1751 cur->bc_ptrs[lev] = xfs_btree_get_numrecs(block); in xfs_btree_decrement()
1769 union xfs_btree_ptr *pp, /* ptr to btree block */ in xfs_btree_lookup_get_block()
1770 struct xfs_btree_block **blkp) /* return btree block */ in xfs_btree_lookup_get_block()
1772 struct xfs_buf *bp; /* buffer pointer for btree block */ in xfs_btree_lookup_get_block()
1776 /* special case the root block if in an inode */ in xfs_btree_lookup_get_block()
1837 struct xfs_btree_block *block, in xfs_lookup_get_search_key() argument
1842 xfs_btree_rec_addr(cur, keyno, block)); in xfs_lookup_get_search_key()
1846 return xfs_btree_key_addr(cur, keyno, block); in xfs_lookup_get_search_key()
1859 struct xfs_btree_block *block; /* current btree block */ in xfs_btree_lookup() local
1864 union xfs_btree_ptr *pp; /* ptr to btree block */ in xfs_btree_lookup()
1865 union xfs_btree_ptr ptr; /* ptr to btree block */ in xfs_btree_lookup()
1873 block = NULL; in xfs_btree_lookup()
1883 * on the lookup record, then follow the corresponding block in xfs_btree_lookup()
1887 /* Get the block we need to do the lookup on. */ in xfs_btree_lookup()
1888 error = xfs_btree_lookup_get_block(cur, level, pp, &block); in xfs_btree_lookup()
1895 * know we need to use the first entry in this block. in xfs_btree_lookup()
1899 /* Otherwise search this block. Do a binary search. */ in xfs_btree_lookup()
1906 high = xfs_btree_get_numrecs(block); in xfs_btree_lookup()
1908 /* Block is empty, must be an empty leaf. */ in xfs_btree_lookup()
1912 cur->bc_mp, block, in xfs_btree_lookup()
1913 sizeof(*block)); in xfs_btree_lookup()
1922 /* Binary search the block. */ in xfs_btree_lookup()
1934 keyno, block, &key); in xfs_btree_lookup()
1954 * by getting the block number and filling in the cursor. in xfs_btree_lookup()
1963 pp = xfs_btree_ptr_addr(cur, keyno, block); in xfs_btree_lookup()
1977 * If ge search and we went off the end of the block, but it's in xfs_btree_lookup()
1978 * not the last block, we're in the wrong block. in xfs_btree_lookup()
1980 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); in xfs_btree_lookup()
1982 keyno > xfs_btree_get_numrecs(block) && in xfs_btree_lookup()
1999 if (keyno == 0 || keyno > xfs_btree_get_numrecs(block)) in xfs_btree_lookup()
2022 /* Determine the low (and high if overlapped) keys of a leaf block */
2026 struct xfs_btree_block *block, in xfs_btree_get_leaf_keys() argument
2035 rec = xfs_btree_rec_addr(cur, 1, block); in xfs_btree_get_leaf_keys()
2041 for (n = 2; n <= xfs_btree_get_numrecs(block); n++) { in xfs_btree_get_leaf_keys()
2042 rec = xfs_btree_rec_addr(cur, n, block); in xfs_btree_get_leaf_keys()
2054 /* Determine the low (and high if overlapped) keys of a node block */
2058 struct xfs_btree_block *block, in xfs_btree_get_node_keys() argument
2067 memcpy(key, xfs_btree_key_addr(cur, 1, block), in xfs_btree_get_node_keys()
2070 max_hkey = xfs_btree_high_key_addr(cur, 1, block); in xfs_btree_get_node_keys()
2071 for (n = 2; n <= xfs_btree_get_numrecs(block); n++) { in xfs_btree_get_node_keys()
2072 hkey = xfs_btree_high_key_addr(cur, n, block); in xfs_btree_get_node_keys()
2080 memcpy(key, xfs_btree_key_addr(cur, 1, block), in xfs_btree_get_node_keys()
2085 /* Derive the keys for any btree block. */
2089 struct xfs_btree_block *block, in xfs_btree_get_keys() argument
2092 if (be16_to_cpu(block->bb_level) == 0) in xfs_btree_get_keys()
2093 xfs_btree_get_leaf_keys(cur, block, key); in xfs_btree_get_keys()
2095 xfs_btree_get_node_keys(cur, block, key); in xfs_btree_get_keys()
2099 * Decide if we need to update the parent keys of a btree block. For
2103 * in the block.
2122 struct xfs_btree_block *block, in __xfs_btree_updkeys() argument
2144 xfs_btree_get_keys(cur, block, lkey); in __xfs_btree_updkeys()
2149 block = xfs_btree_get_block(cur, level, &bp); in __xfs_btree_updkeys()
2152 error = xfs_btree_check_block(cur, block, level, bp); in __xfs_btree_updkeys()
2157 nlkey = xfs_btree_key_addr(cur, ptr, block); in __xfs_btree_updkeys()
2158 nhkey = xfs_btree_high_key_addr(cur, ptr, block); in __xfs_btree_updkeys()
2167 xfs_btree_get_node_keys(cur, block, lkey); in __xfs_btree_updkeys()
2180 struct xfs_btree_block *block; in xfs_btree_updkeys_force() local
2182 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_updkeys_force()
2183 return __xfs_btree_updkeys(cur, level, block, bp, true); in xfs_btree_updkeys_force()
2194 struct xfs_btree_block *block; in xfs_btree_update_keys() local
2202 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_update_keys()
2204 return __xfs_btree_updkeys(cur, level, block, bp, false); in xfs_btree_update_keys()
2210 * at the first entry in the block. in xfs_btree_update_keys()
2212 xfs_btree_get_keys(cur, block, &key); in xfs_btree_update_keys()
2217 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_update_keys()
2219 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_update_keys()
2224 kp = xfs_btree_key_addr(cur, ptr, block); in xfs_btree_update_keys()
2242 struct xfs_btree_block *block; in xfs_btree_update() local
2248 /* Pick up the current block. */ in xfs_btree_update()
2249 block = xfs_btree_get_block(cur, 0, &bp); in xfs_btree_update()
2252 error = xfs_btree_check_block(cur, block, 0, bp); in xfs_btree_update()
2258 rp = xfs_btree_rec_addr(cur, ptr, block); in xfs_btree_update()
2268 if (xfs_btree_is_lastrec(cur, block, 0)) { in xfs_btree_update()
2269 cur->bc_ops->update_lastrec(cur, block, rec, in xfs_btree_update()
2297 struct xfs_btree_block *left; /* left btree block */ in xfs_btree_lshift()
2300 struct xfs_btree_block *right; /* right btree block */ in xfs_btree_lshift()
2314 /* Set up variables for this block as "right". */ in xfs_btree_lshift()
2359 * If non-leaf, copy a key and a ptr to the left block. in xfs_btree_lshift()
2360 * Log the changes to the left block. in xfs_btree_lshift()
2438 * block on the left. in xfs_btree_lshift()
2451 /* Update the parent high keys of the left block, if needed. */ in xfs_btree_lshift()
2459 /* Update the parent keys of the right block. */ in xfs_btree_lshift()
2493 struct xfs_btree_block *left; /* left btree block */ in xfs_btree_rshift()
2495 struct xfs_btree_block *right; /* right btree block */ in xfs_btree_rshift()
2497 union xfs_btree_ptr rptr; /* right block pointer */ in xfs_btree_rshift()
2508 /* Set up variables for this block as "left". */ in xfs_btree_rshift()
2544 * Make a hole at the start of the right neighbor block, then in xfs_btree_rshift()
2545 * copy the last left block entry to the hole. in xfs_btree_rshift()
2606 * block on the right. in xfs_btree_rshift()
2618 /* Update the parent high keys of the left block, if needed. */ in xfs_btree_rshift()
2625 /* Update the parent keys of the right block. */ in xfs_btree_rshift()
2648 * Split cur/level block in half.
2649 * Return new block number and the key to its first
2661 union xfs_btree_ptr lptr; /* left sibling block ptr */ in __xfs_btree_split()
2663 struct xfs_btree_block *left; /* left btree block */ in __xfs_btree_split()
2664 union xfs_btree_ptr rptr; /* right sibling block ptr */ in __xfs_btree_split()
2666 struct xfs_btree_block *right; /* right btree block */ in __xfs_btree_split()
2669 struct xfs_btree_block *rrblock; /* right-right btree block */ in __xfs_btree_split()
2678 /* Set up left block (current one). */ in __xfs_btree_split()
2689 /* Allocate the new block. If we can't do it, we're toast. Give up. */ in __xfs_btree_split()
2697 /* Set up the new block as "right". */ in __xfs_btree_split()
2702 /* Fill in the btree header for the new right block. */ in __xfs_btree_split()
2706 * Split the entries between the old and the new block evenly. in __xfs_btree_split()
2708 * each new block will have the same number of entries. in __xfs_btree_split()
2724 * Copy btree block entries from the left block over to the in __xfs_btree_split()
2725 * new block, the right. Update the right block and log the in __xfs_btree_split()
2746 /* Copy the keys & pointers to the new block. */ in __xfs_btree_split()
2753 /* Stash the keys of the new block for later insertion. */ in __xfs_btree_split()
2763 /* Copy records to the new block. */ in __xfs_btree_split()
2767 /* Stash the keys of the new block for later insertion. */ in __xfs_btree_split()
2772 * Find the left block number by looking in the buffer. in __xfs_btree_split()
2784 * If there's a block to the new block's right, make that block in __xfs_btree_split()
2796 /* Update the parent high keys of the left block, if needed. */ in __xfs_btree_split()
2804 * If the cursor is really in the right block, move it there. in __xfs_btree_split()
2814 * the right block, no matter where this cursor was. in __xfs_btree_split()
2861 * temporarily to ensure that we don't block waiting for memory reclaim in xfs_btree_split_worker()
2913 * Copy the old inode root contents into a real block and make the
2923 struct xfs_btree_block *block; /* btree block */ in xfs_btree_new_iroot() local
2924 struct xfs_btree_block *cblock; /* child btree block */ in xfs_btree_new_iroot()
2928 union xfs_btree_ptr *pp; /* pointer to block addr */ in xfs_btree_new_iroot()
2929 union xfs_btree_ptr nptr; /* new block addr */ in xfs_btree_new_iroot()
2940 block = xfs_btree_get_iroot(cur); in xfs_btree_new_iroot()
2941 pp = xfs_btree_ptr_addr(cur, 1, block); in xfs_btree_new_iroot()
2943 /* Allocate the new block. If we can't do it, we're toast. Give up. */ in xfs_btree_new_iroot()
2952 /* Copy the root into a real block. */ in xfs_btree_new_iroot()
2961 memcpy(cblock, block, xfs_btree_block_len(cur)); in xfs_btree_new_iroot()
2969 be16_add_cpu(&block->bb_level, 1); in xfs_btree_new_iroot()
2970 xfs_btree_set_numrecs(block, 1); in xfs_btree_new_iroot()
2974 kp = xfs_btree_key_addr(cur, 1, block); in xfs_btree_new_iroot()
3016 * Allocate a new root block, fill it in.
3023 struct xfs_btree_block *block; /* one half of the old root block */ in xfs_btree_new_root() local
3024 struct xfs_buf *bp; /* buffer containing block */ in xfs_btree_new_root()
3027 struct xfs_btree_block *left; /* left btree block */ in xfs_btree_new_root()
3029 struct xfs_btree_block *new; /* new (root) btree block */ in xfs_btree_new_root()
3032 struct xfs_btree_block *right; /* right btree block */ in xfs_btree_new_root()
3041 /* Allocate the new block. If we can't do it, we're toast. Give up. */ in xfs_btree_new_root()
3049 /* Set up the new block. */ in xfs_btree_new_root()
3059 * and the new block generated when it was split. We don't know which in xfs_btree_new_root()
3063 block = xfs_btree_get_block(cur, cur->bc_nlevels - 1, &bp); in xfs_btree_new_root()
3066 error = xfs_btree_check_block(cur, block, cur->bc_nlevels - 1, bp); in xfs_btree_new_root()
3071 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB); in xfs_btree_new_root()
3073 /* Our block is left, pick up the right block. */ in xfs_btree_new_root()
3076 left = block; in xfs_btree_new_root()
3083 /* Our block is right, pick up the left block. */ in xfs_btree_new_root()
3086 right = block; in xfs_btree_new_root()
3095 /* Fill in the new block's btree header and log it. */ in xfs_btree_new_root()
3104 * Get the keys for the left block's keys and put them directly in xfs_btree_new_root()
3105 * in the parent block. Do the same for the right block. in xfs_btree_new_root()
3113 * Get the keys for the left block's records and put them in xfs_btree_new_root()
3114 * directly in the parent block. Do the same for the right in xfs_btree_new_root()
3115 * block. in xfs_btree_new_root()
3148 int numrecs,/* # of recs in block */ in xfs_btree_make_block_unfull()
3153 union xfs_btree_key *key, /* key of new block */ in xfs_btree_make_block_unfull()
3163 /* A root block that can be made bigger. */ in xfs_btree_make_block_unfull()
3167 /* A root block that needs replacing */ in xfs_btree_make_block_unfull()
3196 * Next, try splitting the current block in half. in xfs_btree_make_block_unfull()
3199 * could be in a different block now. in xfs_btree_make_block_unfull()
3218 union xfs_btree_ptr *ptrp, /* i/o: block number inserted */ in xfs_btree_insrec()
3220 union xfs_btree_key *key, /* i/o: block key for ptrp */ in xfs_btree_insrec()
3224 struct xfs_btree_block *block; /* btree block */ in xfs_btree_insrec() local
3225 struct xfs_buf *bp; /* buffer for block */ in xfs_btree_insrec()
3226 union xfs_btree_ptr nptr; /* new block ptr */ in xfs_btree_insrec()
3228 union xfs_btree_key nkey; /* new block key */ in xfs_btree_insrec()
3242 * root level, allocate a new root block and we're done. in xfs_btree_insrec()
3263 /* Get pointers to the btree buffer and block. */ in xfs_btree_insrec()
3264 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_insrec()
3266 numrecs = xfs_btree_get_numrecs(block); in xfs_btree_insrec()
3269 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_insrec()
3277 xfs_btree_rec_addr(cur, ptr, block))); in xfs_btree_insrec()
3280 xfs_btree_key_addr(cur, ptr, block))); in xfs_btree_insrec()
3286 * If the block is full, we can't insert the new entry until we in xfs_btree_insrec()
3287 * make the block un-full. in xfs_btree_insrec()
3298 * The current block may have changed if the block was in xfs_btree_insrec()
3301 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_insrec()
3302 numrecs = xfs_btree_get_numrecs(block); in xfs_btree_insrec()
3305 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_insrec()
3311 * At this point we know there's room for our new entry in the block in xfs_btree_insrec()
3321 kp = xfs_btree_key_addr(cur, ptr, block); in xfs_btree_insrec()
3322 pp = xfs_btree_ptr_addr(cur, ptr, block); in xfs_btree_insrec()
3341 xfs_btree_set_numrecs(block, numrecs); in xfs_btree_insrec()
3347 xfs_btree_key_addr(cur, ptr + 1, block))); in xfs_btree_insrec()
3354 rp = xfs_btree_rec_addr(cur, ptr, block); in xfs_btree_insrec()
3360 xfs_btree_set_numrecs(block, ++numrecs); in xfs_btree_insrec()
3365 xfs_btree_rec_addr(cur, ptr + 1, block))); in xfs_btree_insrec()
3374 * If we just inserted into a new tree block, we have to in xfs_btree_insrec()
3377 * Otherwise we're just updating an existing block (having shoved in xfs_btree_insrec()
3378 * some records into the new tree block), so use the regular key in xfs_btree_insrec()
3382 xfs_btree_get_keys(cur, block, lkey); in xfs_btree_insrec()
3393 if (xfs_btree_is_lastrec(cur, block, level)) { in xfs_btree_insrec()
3394 cur->bc_ops->update_lastrec(cur, block, rec, in xfs_btree_insrec()
3399 * Return the new block number, if any. in xfs_btree_insrec()
3430 union xfs_btree_ptr nptr; /* new block number (split result) */ in xfs_btree_insert()
3433 union xfs_btree_key bkey; /* key of block to insert */ in xfs_btree_insert()
3450 * Stop when we don't get a split block, that must mean that in xfs_btree_insert()
3496 * Try to merge a non-leaf block back into the inode root.
3499 * killing the old root block. But because we can't just delete the
3500 * inode we have to copy the single block it was pointing to into the
3510 struct xfs_btree_block *block; in xfs_btree_kill_iroot() local
3530 * Don't deal with the root block needs to be a leaf case. in xfs_btree_kill_iroot()
3540 block = xfs_btree_get_iroot(cur); in xfs_btree_kill_iroot()
3541 if (xfs_btree_get_numrecs(block) != 1) in xfs_btree_kill_iroot()
3558 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB); in xfs_btree_kill_iroot()
3560 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); in xfs_btree_kill_iroot()
3568 block = ifp->if_broot; in xfs_btree_kill_iroot()
3571 be16_add_cpu(&block->bb_numrecs, index); in xfs_btree_kill_iroot()
3572 ASSERT(block->bb_numrecs == cblock->bb_numrecs); in xfs_btree_kill_iroot()
3574 kp = xfs_btree_key_addr(cur, 1, block); in xfs_btree_kill_iroot()
3578 pp = xfs_btree_ptr_addr(cur, 1, block); in xfs_btree_kill_iroot()
3594 be16_add_cpu(&block->bb_level, -1); in xfs_btree_kill_iroot()
3655 * Remove the record from its block then rebalance the tree.
3664 struct xfs_btree_block *block; /* btree block */ in xfs_btree_delrec() local
3665 union xfs_btree_ptr cptr; /* current block ptr */ in xfs_btree_delrec()
3666 struct xfs_buf *bp; /* buffer for block */ in xfs_btree_delrec()
3669 union xfs_btree_ptr lptr; /* left sibling block ptr */ in xfs_btree_delrec()
3671 struct xfs_btree_block *left; /* left btree block */ in xfs_btree_delrec()
3674 union xfs_btree_ptr rptr; /* right sibling block ptr */ in xfs_btree_delrec()
3676 struct xfs_btree_block *right; /* right btree block */ in xfs_btree_delrec()
3677 struct xfs_btree_block *rrblock; /* right-right btree block */ in xfs_btree_delrec()
3692 /* Get the buffer & block containing the record or key/ptr. */ in xfs_btree_delrec()
3693 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_delrec()
3694 numrecs = xfs_btree_get_numrecs(block); in xfs_btree_delrec()
3697 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_delrec()
3702 /* Fail if we're off the end of the block. */ in xfs_btree_delrec()
3717 lkp = xfs_btree_key_addr(cur, ptr + 1, block); in xfs_btree_delrec()
3718 lpp = xfs_btree_ptr_addr(cur, ptr + 1, block); in xfs_btree_delrec()
3736 xfs_btree_rec_addr(cur, ptr + 1, block), in xfs_btree_delrec()
3743 * Decrement and log the number of entries in the block. in xfs_btree_delrec()
3745 xfs_btree_set_numrecs(block, --numrecs); in xfs_btree_delrec()
3752 if (xfs_btree_is_lastrec(cur, block, level)) { in xfs_btree_delrec()
3753 cur->bc_ops->update_lastrec(cur, block, NULL, in xfs_btree_delrec()
3758 * We're at the root level. First, shrink the root block in-memory. in xfs_btree_delrec()
3786 * pp is still set to the first pointer in the block. in xfs_btree_delrec()
3789 pp = xfs_btree_ptr_addr(cur, 1, block); in xfs_btree_delrec()
3803 * If we deleted the leftmost entry in the block, update the in xfs_btree_delrec()
3813 * If the number of records remaining in the block is at least in xfs_btree_delrec()
3828 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB); in xfs_btree_delrec()
3829 xfs_btree_get_sibling(cur, block, &lptr, XFS_BB_LEFTSIB); in xfs_btree_delrec()
3866 * Move the temp cursor to the last entry in the next block. in xfs_btree_delrec()
3880 /* Grab a pointer to the block. */ in xfs_btree_delrec()
3887 /* Grab the current block number, for future use. */ in xfs_btree_delrec()
3891 * If right block is full enough so that removing one entry in xfs_btree_delrec()
3901 ASSERT(xfs_btree_get_numrecs(block) >= in xfs_btree_delrec()
3917 * to our block again (last record). in xfs_btree_delrec()
3938 * previous block. in xfs_btree_delrec()
3949 /* Grab a pointer to the block. */ in xfs_btree_delrec()
3956 /* Grab the current block number, for future use. */ in xfs_btree_delrec()
3960 * If left block is full enough so that removing one entry in xfs_btree_delrec()
3970 ASSERT(xfs_btree_get_numrecs(block) >= in xfs_btree_delrec()
3997 lrecs + xfs_btree_get_numrecs(block) <= in xfs_btree_delrec()
4000 * Set "right" to be the starting block, in xfs_btree_delrec()
4004 right = block; in xfs_btree_delrec()
4011 * If that won't work, see if we can join with the right neighbor block. in xfs_btree_delrec()
4014 rrecs + xfs_btree_get_numrecs(block) <= in xfs_btree_delrec()
4017 * Set "left" to be the starting block, in xfs_btree_delrec()
4021 left = block; in xfs_btree_delrec()
4084 * Fix up the number of records and right block pointer in the in xfs_btree_delrec()
4085 * surviving block, and log it. in xfs_btree_delrec()
4092 /* If there is a right sibling, point it to the remaining block. */ in xfs_btree_delrec()
4102 /* Free the deleted block. */ in xfs_btree_delrec()
4109 * cursor to the left block, and fix up the index. in xfs_btree_delrec()
4139 * points to the old block so that the caller knows which record to in xfs_btree_delrec()
4221 struct xfs_btree_block *block; /* btree block */ in xfs_btree_get_rec() local
4229 block = xfs_btree_get_block(cur, 0, &bp); in xfs_btree_get_rec()
4232 error = xfs_btree_check_block(cur, block, 0, bp); in xfs_btree_get_rec()
4240 if (ptr > xfs_btree_get_numrecs(block) || ptr <= 0) { in xfs_btree_get_rec()
4248 *recp = xfs_btree_rec_addr(cur, ptr, block); in xfs_btree_get_rec()
4253 /* Visit a block in a btree. */
4261 struct xfs_btree_block *block; in xfs_btree_visit_block() local
4268 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_visit_block()
4270 /* process the block */ in xfs_btree_visit_block()
4275 /* now read rh sibling block for next iteration */ in xfs_btree_visit_block()
4276 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB); in xfs_btree_visit_block()
4280 return xfs_btree_lookup_get_block(cur, level, &rptr, &block); in xfs_btree_visit_block()
4284 /* Visit every block in a btree. */
4293 struct xfs_btree_block *block = NULL; in xfs_btree_visit_blocks() local
4300 /* grab the left hand block */ in xfs_btree_visit_blocks()
4301 error = xfs_btree_lookup_get_block(cur, level, &lptr, &block); in xfs_btree_visit_blocks()
4305 /* readahead the left most block for the next level down */ in xfs_btree_visit_blocks()
4309 ptr = xfs_btree_ptr_addr(cur, 1, block); in xfs_btree_visit_blocks()
4341 * as the amount of CPU work we have to do before moving to the next block is
4344 * For each btree block that we load, modify the owner appropriately, set the
4364 struct xfs_btree_block *block; in xfs_btree_block_change_owner() local
4368 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_block_change_owner()
4370 if (block->bb_u.l.bb_owner == cpu_to_be64(bbcoi->new_owner)) in xfs_btree_block_change_owner()
4372 block->bb_u.l.bb_owner = cpu_to_be64(bbcoi->new_owner); in xfs_btree_block_change_owner()
4374 if (block->bb_u.s.bb_owner == cpu_to_be32(bbcoi->new_owner)) in xfs_btree_block_change_owner()
4376 block->bb_u.s.bb_owner = cpu_to_be32(bbcoi->new_owner); in xfs_btree_block_change_owner()
4380 * If the block is a root block hosted in an inode, we might not have a in xfs_btree_block_change_owner()
4383 * block is formatted into the on-disk inode fork. We still change it, in xfs_btree_block_change_owner()
4419 /* Verify the v5 fields of a long-format btree block. */
4426 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_lblock_v5hdr_verify() local
4430 if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid)) in xfs_btree_lblock_v5hdr_verify()
4432 if (block->bb_u.l.bb_blkno != cpu_to_be64(bp->b_bn)) in xfs_btree_lblock_v5hdr_verify()
4435 be64_to_cpu(block->bb_u.l.bb_owner) != owner) in xfs_btree_lblock_v5hdr_verify()
4440 /* Verify a long-format btree block. */
4447 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_lblock_verify() local
4450 if (be16_to_cpu(block->bb_numrecs) > max_recs) in xfs_btree_lblock_verify()
4454 if (block->bb_u.l.bb_leftsib != cpu_to_be64(NULLFSBLOCK) && in xfs_btree_lblock_verify()
4455 !xfs_verify_fsbno(mp, be64_to_cpu(block->bb_u.l.bb_leftsib))) in xfs_btree_lblock_verify()
4457 if (block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK) && in xfs_btree_lblock_verify()
4458 !xfs_verify_fsbno(mp, be64_to_cpu(block->bb_u.l.bb_rightsib))) in xfs_btree_lblock_verify()
4466 * btree block
4468 * @bp: buffer containing the btree block
4475 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_sblock_v5hdr_verify() local
4480 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid)) in xfs_btree_sblock_v5hdr_verify()
4482 if (block->bb_u.s.bb_blkno != cpu_to_be64(bp->b_bn)) in xfs_btree_sblock_v5hdr_verify()
4484 if (pag && be32_to_cpu(block->bb_u.s.bb_owner) != pag->pag_agno) in xfs_btree_sblock_v5hdr_verify()
4490 * xfs_btree_sblock_verify() -- verify a short-format btree block
4492 * @bp: buffer containing the btree block
4501 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_sblock_verify() local
4505 if (be16_to_cpu(block->bb_numrecs) > max_recs) in xfs_btree_sblock_verify()
4510 if (block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK) && in xfs_btree_sblock_verify()
4511 !xfs_verify_agbno(mp, agno, be32_to_cpu(block->bb_u.s.bb_leftsib))) in xfs_btree_sblock_verify()
4513 if (block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK) && in xfs_btree_sblock_verify()
4514 !xfs_verify_agbno(mp, agno, be32_to_cpu(block->bb_u.s.bb_rightsib))) in xfs_btree_sblock_verify()
4631 * As an optimization, we stop scanning a block when we find a low key
4649 struct xfs_btree_block *block; in xfs_btree_overlapped_query_range() local
4660 error = xfs_btree_lookup_get_block(cur, level, &ptr, &block); in xfs_btree_overlapped_query_range()
4666 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_overlapped_query_range()
4673 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_overlapped_query_range()
4676 if (cur->bc_ptrs[level] > be16_to_cpu(block->bb_numrecs)) { in xfs_btree_overlapped_query_range()
4686 recp = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block); in xfs_btree_overlapped_query_range()
4714 lkp = xfs_btree_key_addr(cur, cur->bc_ptrs[level], block); in xfs_btree_overlapped_query_range()
4715 hkp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level], block); in xfs_btree_overlapped_query_range()
4716 pp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[level], block); in xfs_btree_overlapped_query_range()
4729 &block); in xfs_btree_overlapped_query_range()
4735 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_overlapped_query_range()
4751 * block, a subsequent non-error cursor deletion will not release in xfs_btree_overlapped_query_range()
4918 struct xfs_btree_block *block; in xfs_btree_has_more_records() local
4921 block = xfs_btree_get_block(cur, 0, &bp); in xfs_btree_has_more_records()
4923 /* There are still records in this block. */ in xfs_btree_has_more_records()
4924 if (cur->bc_ptrs[0] < xfs_btree_get_numrecs(block)) in xfs_btree_has_more_records()
4929 return block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK); in xfs_btree_has_more_records()
4931 return block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK); in xfs_btree_has_more_records()