Lines Matching full:block
54 * Check a long btree block header. Return the address of the failing check,
60 struct xfs_btree_block *block, in __xfs_btree_check_lblock() argument
69 if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid)) in __xfs_btree_check_lblock()
71 if (block->bb_u.l.bb_blkno != in __xfs_btree_check_lblock()
74 if (block->bb_u.l.bb_pad != cpu_to_be32(0)) in __xfs_btree_check_lblock()
78 if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(crc, btnum)) in __xfs_btree_check_lblock()
80 if (be16_to_cpu(block->bb_level) != level) in __xfs_btree_check_lblock()
82 if (be16_to_cpu(block->bb_numrecs) > in __xfs_btree_check_lblock()
85 if (block->bb_u.l.bb_leftsib != cpu_to_be64(NULLFSBLOCK) && in __xfs_btree_check_lblock()
86 !xfs_btree_check_lptr(cur, be64_to_cpu(block->bb_u.l.bb_leftsib), in __xfs_btree_check_lblock()
89 if (block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK) && in __xfs_btree_check_lblock()
90 !xfs_btree_check_lptr(cur, be64_to_cpu(block->bb_u.l.bb_rightsib), in __xfs_btree_check_lblock()
97 /* Check a long btree block header. */
101 struct xfs_btree_block *block, in xfs_btree_check_lblock() argument
108 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()
182 * Debug routine: check that block header is ok.
187 struct xfs_btree_block *block, /* generic btree block pointer */ in xfs_btree_check_block() argument
188 int level, /* level of the btree block */ in xfs_btree_check_block()
189 struct xfs_buf *bp) /* buffer containing block, if any */ in xfs_btree_check_block()
192 return xfs_btree_check_lblock(cur, block, level, bp); in xfs_btree_check_block()
194 return xfs_btree_check_sblock(cur, block, level, bp); in xfs_btree_check_block()
261 * Calculate CRC on the whole btree block and stuff it into the
272 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_lblock_calc_crc() local
278 block->bb_u.l.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn); in xfs_btree_lblock_calc_crc()
286 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_lblock_verify_crc() local
290 if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.l.bb_lsn))) in xfs_btree_lblock_verify_crc()
299 * Calculate CRC on the whole btree block and stuff it into the
310 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_sblock_calc_crc() local
316 block->bb_u.s.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn); in xfs_btree_sblock_calc_crc()
324 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_sblock_verify_crc() local
328 if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.s.bb_lsn))) in xfs_btree_sblock_verify_crc()
400 xfs_buf_t *bp; /* btree block's buffer pointer */ in xfs_btree_dup_cursor()
402 int i; /* level number of btree block */ in xfs_btree_dup_cursor()
445 * XFS btree block layout and addressing:
450 * the values. A non-leaf block also starts with the same header, and
463 * and comes in different versions for short (32bit) and long (64bit) block
465 * and opaque to the btree core. The block pointers are simple disk endian
469 * into a btree block (xfs_btree_*_offset) or return a pointer to the given
471 * inside the btree block is done using indices starting at one, not zero!
477 * indexing the lowest key available in the block(s) below (the same behavior
479 * available in the block(s) below. Because records are /not/ sorted by the
480 * highest key, all leaf block updates require us to compute the highest key
507 * Now say we want to map block (B+D) into file A at offset (C+D). Ideally,
519 * Return size of the btree block header for this btree instance.
534 * Return size of btree block pointers for this btree instance.
543 * Calculate offset of the n-th record in a btree block.
555 * Calculate offset of the n-th key in a btree block.
567 * Calculate offset of the n-th high key in a btree block.
579 * Calculate offset of the n-th block pointer in a btree block.
593 * Return a pointer to the n-th record in the btree block.
599 struct xfs_btree_block *block) in xfs_btree_rec_addr() argument
602 ((char *)block + xfs_btree_rec_offset(cur, n)); in xfs_btree_rec_addr()
606 * Return a pointer to the n-th key in the btree block.
612 struct xfs_btree_block *block) in xfs_btree_key_addr() argument
615 ((char *)block + xfs_btree_key_offset(cur, n)); in xfs_btree_key_addr()
619 * Return a pointer to the n-th high key in the btree block.
625 struct xfs_btree_block *block) in xfs_btree_high_key_addr() argument
628 ((char *)block + xfs_btree_high_key_offset(cur, n)); in xfs_btree_high_key_addr()
632 * Return a pointer to the n-th block pointer in the btree block.
638 struct xfs_btree_block *block) in xfs_btree_ptr_addr() argument
640 int level = xfs_btree_get_level(block); in xfs_btree_ptr_addr()
642 ASSERT(block->bb_level != 0); in xfs_btree_ptr_addr()
645 ((char *)block + xfs_btree_ptr_offset(cur, n, level)); in xfs_btree_ptr_addr()
660 * Get the root block which is stored in the inode.
675 * Retrieve the block pointer from the cursor at the given level.
678 struct xfs_btree_block * /* generic btree block pointer */
682 struct xfs_buf **bpp) /* buffer containing the block */ in xfs_btree_get_block()
703 struct xfs_btree_block *block; /* generic btree block pointer */ in xfs_btree_firstrec() local
704 xfs_buf_t *bp; /* buffer containing block */ in xfs_btree_firstrec()
707 * Get the block pointer for this level. in xfs_btree_firstrec()
709 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_firstrec()
710 if (xfs_btree_check_block(cur, block, level, bp)) in xfs_btree_firstrec()
715 if (!block->bb_numrecs) in xfs_btree_firstrec()
725 * Change the cursor to point to the last record in the current block
733 struct xfs_btree_block *block; /* generic btree block pointer */ in xfs_btree_lastrec() local
734 xfs_buf_t *bp; /* buffer containing block */ in xfs_btree_lastrec()
737 * Get the block pointer for this level. in xfs_btree_lastrec()
739 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_lastrec()
740 if (xfs_btree_check_block(cur, block, level, bp)) in xfs_btree_lastrec()
745 if (!block->bb_numrecs) in xfs_btree_lastrec()
750 cur->bc_ptrs[level] = be16_to_cpu(block->bb_numrecs); in xfs_btree_lastrec()
791 * Get a buffer for the block, return it read in.
798 xfs_fsblock_t fsbno, /* file system block number */ in xfs_btree_read_bufl()
804 xfs_daddr_t d; /* real disk block address */ in xfs_btree_read_bufl()
821 * Read-ahead the block, don't wait for it, don't return a buffer.
828 xfs_fsblock_t fsbno, /* file system block number */ in xfs_btree_reada_bufl()
840 * Read-ahead the block, don't wait for it, don't return a buffer.
848 xfs_agblock_t agbno, /* allocation group block number */ in xfs_btree_reada_bufs()
864 struct xfs_btree_block *block) in xfs_btree_readahead_lblock() argument
867 xfs_fsblock_t left = be64_to_cpu(block->bb_u.l.bb_leftsib); in xfs_btree_readahead_lblock()
868 xfs_fsblock_t right = be64_to_cpu(block->bb_u.l.bb_rightsib); in xfs_btree_readahead_lblock()
889 struct xfs_btree_block *block) in xfs_btree_readahead_sblock() argument
892 xfs_agblock_t left = be32_to_cpu(block->bb_u.s.bb_leftsib); in xfs_btree_readahead_sblock()
893 xfs_agblock_t right = be32_to_cpu(block->bb_u.s.bb_rightsib); in xfs_btree_readahead_sblock()
921 struct xfs_btree_block *block; in xfs_btree_readahead() local
935 block = XFS_BUF_TO_BLOCK(cur->bc_bufs[lev]); in xfs_btree_readahead()
938 return xfs_btree_readahead_lblock(cur, lr, block); in xfs_btree_readahead()
939 return xfs_btree_readahead_sblock(cur, lr, block); in xfs_btree_readahead()
998 struct xfs_btree_block *b; /* btree block */ in xfs_btree_setbuf()
1047 struct xfs_btree_block *block, in xfs_btree_get_sibling() argument
1055 ptr->l = block->bb_u.l.bb_rightsib; in xfs_btree_get_sibling()
1057 ptr->l = block->bb_u.l.bb_leftsib; in xfs_btree_get_sibling()
1060 ptr->s = block->bb_u.s.bb_rightsib; in xfs_btree_get_sibling()
1062 ptr->s = block->bb_u.s.bb_leftsib; in xfs_btree_get_sibling()
1069 struct xfs_btree_block *block, in xfs_btree_set_sibling() argument
1077 block->bb_u.l.bb_rightsib = ptr->l; in xfs_btree_set_sibling()
1079 block->bb_u.l.bb_leftsib = ptr->l; in xfs_btree_set_sibling()
1082 block->bb_u.s.bb_rightsib = ptr->s; in xfs_btree_set_sibling()
1084 block->bb_u.s.bb_leftsib = ptr->s; in xfs_btree_set_sibling()
1177 struct xfs_btree_block *block, in xfs_btree_is_lastrec() argument
1187 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); in xfs_btree_is_lastrec()
1240 struct xfs_btree_block **block, in xfs_btree_get_buf_block() argument
1256 *block = XFS_BUF_TO_BLOCK(*bpp); in xfs_btree_get_buf_block()
1262 * the block pointer within the buffer.
1269 struct xfs_btree_block **block, in xfs_btree_read_buf_block() argument
1289 *block = XFS_BUF_TO_BLOCK(*bpp); in xfs_btree_read_buf_block()
1294 * Copy keys from one btree block to another.
1308 * Copy records from one btree block to another.
1322 * Copy block pointers from one btree block to another.
1336 * Shift keys one index left/right inside a single btree block.
1355 * Shift records one index left/right inside a single btree block.
1374 * Shift block pointers one index left/right inside a single btree block.
1393 * Log key values from the btree block.
1415 * Log record values from the btree block.
1433 * Log block pointer fields from a btree block (nonleaf).
1438 struct xfs_buf *bp, /* buffer containing btree block */ in xfs_btree_log_ptrs()
1444 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_log_ptrs() local
1445 int level = xfs_btree_get_level(block); in xfs_btree_log_ptrs()
1459 * Log fields from a btree block header.
1464 struct xfs_buf *bp, /* buffer containing btree block */ in xfs_btree_log_block()
1503 * block but instead recreate it during log in xfs_btree_log_block()
1536 struct xfs_btree_block *block; in xfs_btree_increment() local
1547 /* Get a pointer to the btree block. */ in xfs_btree_increment()
1548 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_increment()
1551 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_increment()
1556 /* We're done if we remain in the block after the increment. */ in xfs_btree_increment()
1557 if (++cur->bc_ptrs[level] <= xfs_btree_get_numrecs(block)) in xfs_btree_increment()
1561 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); in xfs_btree_increment()
1569 * Stop when we don't go off the right edge of a block. in xfs_btree_increment()
1572 block = xfs_btree_get_block(cur, lev, &bp); in xfs_btree_increment()
1575 error = xfs_btree_check_block(cur, block, lev, bp); in xfs_btree_increment()
1580 if (++cur->bc_ptrs[lev] <= xfs_btree_get_numrecs(block)) in xfs_btree_increment()
1583 /* Read-ahead the right block for the next loop. */ in xfs_btree_increment()
1604 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) { in xfs_btree_increment()
1607 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block); in xfs_btree_increment()
1609 error = xfs_btree_read_buf_block(cur, ptrp, 0, &block, &bp); in xfs_btree_increment()
1638 struct xfs_btree_block *block; in xfs_btree_decrement() local
1649 /* We're done if we remain in the block after the decrement. */ in xfs_btree_decrement()
1653 /* Get a pointer to the btree block. */ in xfs_btree_decrement()
1654 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_decrement()
1657 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_decrement()
1663 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB); in xfs_btree_decrement()
1671 * Stop when we don't go off the left edge of a block. in xfs_btree_decrement()
1676 /* Read-ahead the left block for the next loop. */ in xfs_btree_decrement()
1697 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) { in xfs_btree_decrement()
1700 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block); in xfs_btree_decrement()
1702 error = xfs_btree_read_buf_block(cur, ptrp, 0, &block, &bp); in xfs_btree_decrement()
1706 cur->bc_ptrs[lev] = xfs_btree_get_numrecs(block); in xfs_btree_decrement()
1724 union xfs_btree_ptr *pp, /* ptr to btree block */ in xfs_btree_lookup_get_block()
1725 struct xfs_btree_block **blkp) /* return btree block */ in xfs_btree_lookup_get_block()
1727 struct xfs_buf *bp; /* buffer pointer for btree block */ in xfs_btree_lookup_get_block()
1731 /* special case the root block if in an inode */ in xfs_btree_lookup_get_block()
1793 struct xfs_btree_block *block, in xfs_lookup_get_search_key() argument
1798 xfs_btree_rec_addr(cur, keyno, block)); in xfs_lookup_get_search_key()
1802 return xfs_btree_key_addr(cur, keyno, block); in xfs_lookup_get_search_key()
1815 struct xfs_btree_block *block; /* current btree block */ in xfs_btree_lookup() local
1820 union xfs_btree_ptr *pp; /* ptr to btree block */ in xfs_btree_lookup()
1821 union xfs_btree_ptr ptr; /* ptr to btree block */ in xfs_btree_lookup()
1829 block = NULL; in xfs_btree_lookup()
1839 * on the lookup record, then follow the corresponding block in xfs_btree_lookup()
1843 /* Get the block we need to do the lookup on. */ in xfs_btree_lookup()
1844 error = xfs_btree_lookup_get_block(cur, level, pp, &block); in xfs_btree_lookup()
1851 * know we need to use the first entry in this block. in xfs_btree_lookup()
1855 /* Otherwise search this block. Do a binary search. */ in xfs_btree_lookup()
1862 high = xfs_btree_get_numrecs(block); in xfs_btree_lookup()
1864 /* Block is empty, must be an empty leaf. */ in xfs_btree_lookup()
1868 cur->bc_mp, block, in xfs_btree_lookup()
1869 sizeof(*block)); in xfs_btree_lookup()
1878 /* Binary search the block. */ in xfs_btree_lookup()
1890 keyno, block, &key); in xfs_btree_lookup()
1910 * by getting the block number and filling in the cursor. in xfs_btree_lookup()
1919 pp = xfs_btree_ptr_addr(cur, keyno, block); in xfs_btree_lookup()
1933 * If ge search and we went off the end of the block, but it's in xfs_btree_lookup()
1934 * not the last block, we're in the wrong block. in xfs_btree_lookup()
1936 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); in xfs_btree_lookup()
1938 keyno > xfs_btree_get_numrecs(block) && in xfs_btree_lookup()
1956 if (keyno == 0 || keyno > xfs_btree_get_numrecs(block)) in xfs_btree_lookup()
1979 /* Determine the low (and high if overlapped) keys of a leaf block */
1983 struct xfs_btree_block *block, in xfs_btree_get_leaf_keys() argument
1992 rec = xfs_btree_rec_addr(cur, 1, block); in xfs_btree_get_leaf_keys()
1998 for (n = 2; n <= xfs_btree_get_numrecs(block); n++) { in xfs_btree_get_leaf_keys()
1999 rec = xfs_btree_rec_addr(cur, n, block); in xfs_btree_get_leaf_keys()
2011 /* Determine the low (and high if overlapped) keys of a node block */
2015 struct xfs_btree_block *block, in xfs_btree_get_node_keys() argument
2024 memcpy(key, xfs_btree_key_addr(cur, 1, block), in xfs_btree_get_node_keys()
2027 max_hkey = xfs_btree_high_key_addr(cur, 1, block); in xfs_btree_get_node_keys()
2028 for (n = 2; n <= xfs_btree_get_numrecs(block); n++) { in xfs_btree_get_node_keys()
2029 hkey = xfs_btree_high_key_addr(cur, n, block); in xfs_btree_get_node_keys()
2037 memcpy(key, xfs_btree_key_addr(cur, 1, block), in xfs_btree_get_node_keys()
2042 /* Derive the keys for any btree block. */
2046 struct xfs_btree_block *block, in xfs_btree_get_keys() argument
2049 if (be16_to_cpu(block->bb_level) == 0) in xfs_btree_get_keys()
2050 xfs_btree_get_leaf_keys(cur, block, key); in xfs_btree_get_keys()
2052 xfs_btree_get_node_keys(cur, block, key); in xfs_btree_get_keys()
2056 * Decide if we need to update the parent keys of a btree block. For
2060 * in the block.
2079 struct xfs_btree_block *block, in __xfs_btree_updkeys() argument
2101 xfs_btree_get_keys(cur, block, lkey); in __xfs_btree_updkeys()
2106 block = xfs_btree_get_block(cur, level, &bp); in __xfs_btree_updkeys()
2109 error = xfs_btree_check_block(cur, block, level, bp); in __xfs_btree_updkeys()
2114 nlkey = xfs_btree_key_addr(cur, ptr, block); in __xfs_btree_updkeys()
2115 nhkey = xfs_btree_high_key_addr(cur, ptr, block); in __xfs_btree_updkeys()
2124 xfs_btree_get_node_keys(cur, block, lkey); in __xfs_btree_updkeys()
2137 struct xfs_btree_block *block; in xfs_btree_updkeys_force() local
2139 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_updkeys_force()
2140 return __xfs_btree_updkeys(cur, level, block, bp, true); in xfs_btree_updkeys_force()
2151 struct xfs_btree_block *block; in xfs_btree_update_keys() local
2159 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_update_keys()
2161 return __xfs_btree_updkeys(cur, level, block, bp, false); in xfs_btree_update_keys()
2167 * at the first entry in the block. in xfs_btree_update_keys()
2169 xfs_btree_get_keys(cur, block, &key); in xfs_btree_update_keys()
2174 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_update_keys()
2176 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_update_keys()
2181 kp = xfs_btree_key_addr(cur, ptr, block); in xfs_btree_update_keys()
2199 struct xfs_btree_block *block; in xfs_btree_update() local
2205 /* Pick up the current block. */ in xfs_btree_update()
2206 block = xfs_btree_get_block(cur, 0, &bp); in xfs_btree_update()
2209 error = xfs_btree_check_block(cur, block, 0, bp); in xfs_btree_update()
2215 rp = xfs_btree_rec_addr(cur, ptr, block); in xfs_btree_update()
2225 if (xfs_btree_is_lastrec(cur, block, 0)) { in xfs_btree_update()
2226 cur->bc_ops->update_lastrec(cur, block, rec, in xfs_btree_update()
2254 struct xfs_btree_block *left; /* left btree block */ in xfs_btree_lshift()
2257 struct xfs_btree_block *right; /* right btree block */ in xfs_btree_lshift()
2271 /* Set up variables for this block as "right". */ in xfs_btree_lshift()
2316 * If non-leaf, copy a key and a ptr to the left block. in xfs_btree_lshift()
2317 * Log the changes to the left block. in xfs_btree_lshift()
2393 * block on the left. in xfs_btree_lshift()
2409 /* Update the parent high keys of the left block, if needed. */ in xfs_btree_lshift()
2417 /* Update the parent keys of the right block. */ in xfs_btree_lshift()
2451 struct xfs_btree_block *left; /* left btree block */ in xfs_btree_rshift()
2453 struct xfs_btree_block *right; /* right btree block */ in xfs_btree_rshift()
2455 union xfs_btree_ptr rptr; /* right block pointer */ in xfs_btree_rshift()
2466 /* Set up variables for this block as "left". */ in xfs_btree_rshift()
2502 * Make a hole at the start of the right neighbor block, then in xfs_btree_rshift()
2503 * copy the last left block entry to the hole. in xfs_btree_rshift()
2564 * block on the right. in xfs_btree_rshift()
2579 /* Update the parent high keys of the left block, if needed. */ in xfs_btree_rshift()
2586 /* Update the parent keys of the right block. */ in xfs_btree_rshift()
2609 * Split cur/level block in half.
2610 * Return new block number and the key to its first
2622 union xfs_btree_ptr lptr; /* left sibling block ptr */ in __xfs_btree_split()
2624 struct xfs_btree_block *left; /* left btree block */ in __xfs_btree_split()
2625 union xfs_btree_ptr rptr; /* right sibling block ptr */ in __xfs_btree_split()
2627 struct xfs_btree_block *right; /* right btree block */ in __xfs_btree_split()
2630 struct xfs_btree_block *rrblock; /* right-right btree block */ in __xfs_btree_split()
2639 /* Set up left block (current one). */ in __xfs_btree_split()
2650 /* Allocate the new block. If we can't do it, we're toast. Give up. */ in __xfs_btree_split()
2658 /* Set up the new block as "right". */ in __xfs_btree_split()
2663 /* Fill in the btree header for the new right block. */ in __xfs_btree_split()
2667 * Split the entries between the old and the new block evenly. in __xfs_btree_split()
2669 * each new block will have the same number of entries. in __xfs_btree_split()
2685 * Copy btree block entries from the left block over to the in __xfs_btree_split()
2686 * new block, the right. Update the right block and log the in __xfs_btree_split()
2707 /* Copy the keys & pointers to the new block. */ in __xfs_btree_split()
2714 /* Stash the keys of the new block for later insertion. */ in __xfs_btree_split()
2724 /* Copy records to the new block. */ in __xfs_btree_split()
2728 /* Stash the keys of the new block for later insertion. */ in __xfs_btree_split()
2733 * Find the left block number by looking in the buffer. in __xfs_btree_split()
2745 * If there's a block to the new block's right, make that block in __xfs_btree_split()
2757 /* Update the parent high keys of the left block, if needed. */ in __xfs_btree_split()
2765 * If the cursor is really in the right block, move it there. in __xfs_btree_split()
2775 * the right block, no matter where this cursor was. in __xfs_btree_split()
2822 * temporarily to ensure that we don't block waiting for memory reclaim in xfs_btree_split_worker()
2874 * Copy the old inode root contents into a real block and make the
2884 struct xfs_btree_block *block; /* btree block */ in xfs_btree_new_iroot() local
2885 struct xfs_btree_block *cblock; /* child btree block */ in xfs_btree_new_iroot()
2889 union xfs_btree_ptr *pp; /* pointer to block addr */ in xfs_btree_new_iroot()
2890 union xfs_btree_ptr nptr; /* new block addr */ in xfs_btree_new_iroot()
2901 block = xfs_btree_get_iroot(cur); in xfs_btree_new_iroot()
2902 pp = xfs_btree_ptr_addr(cur, 1, block); in xfs_btree_new_iroot()
2904 /* Allocate the new block. If we can't do it, we're toast. Give up. */ in xfs_btree_new_iroot()
2913 /* Copy the root into a real block. */ in xfs_btree_new_iroot()
2922 memcpy(cblock, block, xfs_btree_block_len(cur)); in xfs_btree_new_iroot()
2930 be16_add_cpu(&block->bb_level, 1); in xfs_btree_new_iroot()
2931 xfs_btree_set_numrecs(block, 1); in xfs_btree_new_iroot()
2935 kp = xfs_btree_key_addr(cur, 1, block); in xfs_btree_new_iroot()
2977 * Allocate a new root block, fill it in.
2984 struct xfs_btree_block *block; /* one half of the old root block */ in xfs_btree_new_root() local
2985 struct xfs_buf *bp; /* buffer containing block */ in xfs_btree_new_root()
2988 struct xfs_btree_block *left; /* left btree block */ in xfs_btree_new_root()
2990 struct xfs_btree_block *new; /* new (root) btree block */ in xfs_btree_new_root()
2993 struct xfs_btree_block *right; /* right btree block */ in xfs_btree_new_root()
3002 /* Allocate the new block. If we can't do it, we're toast. Give up. */ in xfs_btree_new_root()
3010 /* Set up the new block. */ in xfs_btree_new_root()
3020 * and the new block generated when it was split. We don't know which in xfs_btree_new_root()
3024 block = xfs_btree_get_block(cur, cur->bc_nlevels - 1, &bp); in xfs_btree_new_root()
3027 error = xfs_btree_check_block(cur, block, cur->bc_nlevels - 1, bp); in xfs_btree_new_root()
3032 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB); in xfs_btree_new_root()
3034 /* Our block is left, pick up the right block. */ in xfs_btree_new_root()
3037 left = block; in xfs_btree_new_root()
3044 /* Our block is right, pick up the left block. */ in xfs_btree_new_root()
3047 right = block; in xfs_btree_new_root()
3056 /* Fill in the new block's btree header and log it. */ in xfs_btree_new_root()
3065 * Get the keys for the left block's keys and put them directly in xfs_btree_new_root()
3066 * in the parent block. Do the same for the right block. in xfs_btree_new_root()
3074 * Get the keys for the left block's records and put them in xfs_btree_new_root()
3075 * directly in the parent block. Do the same for the right in xfs_btree_new_root()
3076 * block. in xfs_btree_new_root()
3109 int numrecs,/* # of recs in block */ in xfs_btree_make_block_unfull()
3114 union xfs_btree_key *key, /* key of new block */ in xfs_btree_make_block_unfull()
3124 /* A root block that can be made bigger. */ in xfs_btree_make_block_unfull()
3128 /* A root block that needs replacing */ in xfs_btree_make_block_unfull()
3157 * Next, try splitting the current block in half. in xfs_btree_make_block_unfull()
3160 * could be in a different block now. in xfs_btree_make_block_unfull()
3179 union xfs_btree_ptr *ptrp, /* i/o: block number inserted */ in xfs_btree_insrec()
3181 union xfs_btree_key *key, /* i/o: block key for ptrp */ in xfs_btree_insrec()
3185 struct xfs_btree_block *block; /* btree block */ in xfs_btree_insrec() local
3186 struct xfs_buf *bp; /* buffer for block */ in xfs_btree_insrec()
3187 union xfs_btree_ptr nptr; /* new block ptr */ in xfs_btree_insrec()
3189 union xfs_btree_key nkey; /* new block key */ in xfs_btree_insrec()
3203 * root level, allocate a new root block and we're done. in xfs_btree_insrec()
3224 /* Get pointers to the btree buffer and block. */ in xfs_btree_insrec()
3225 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_insrec()
3227 numrecs = xfs_btree_get_numrecs(block); in xfs_btree_insrec()
3230 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_insrec()
3238 xfs_btree_rec_addr(cur, ptr, block))); in xfs_btree_insrec()
3241 xfs_btree_key_addr(cur, ptr, block))); in xfs_btree_insrec()
3247 * If the block is full, we can't insert the new entry until we in xfs_btree_insrec()
3248 * make the block un-full. in xfs_btree_insrec()
3259 * The current block may have changed if the block was in xfs_btree_insrec()
3262 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_insrec()
3263 numrecs = xfs_btree_get_numrecs(block); in xfs_btree_insrec()
3266 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_insrec()
3272 * At this point we know there's room for our new entry in the block in xfs_btree_insrec()
3282 kp = xfs_btree_key_addr(cur, ptr, block); in xfs_btree_insrec()
3283 pp = xfs_btree_ptr_addr(cur, ptr, block); in xfs_btree_insrec()
3302 xfs_btree_set_numrecs(block, numrecs); in xfs_btree_insrec()
3308 xfs_btree_key_addr(cur, ptr + 1, block))); in xfs_btree_insrec()
3315 rp = xfs_btree_rec_addr(cur, ptr, block); in xfs_btree_insrec()
3321 xfs_btree_set_numrecs(block, ++numrecs); in xfs_btree_insrec()
3326 xfs_btree_rec_addr(cur, ptr + 1, block))); in xfs_btree_insrec()
3335 * If we just inserted into a new tree block, we have to in xfs_btree_insrec()
3338 * Otherwise we're just updating an existing block (having shoved in xfs_btree_insrec()
3339 * some records into the new tree block), so use the regular key in xfs_btree_insrec()
3343 xfs_btree_get_keys(cur, block, lkey); in xfs_btree_insrec()
3354 if (xfs_btree_is_lastrec(cur, block, level)) { in xfs_btree_insrec()
3355 cur->bc_ops->update_lastrec(cur, block, rec, in xfs_btree_insrec()
3360 * Return the new block number, if any. in xfs_btree_insrec()
3391 union xfs_btree_ptr nptr; /* new block number (split result) */ in xfs_btree_insert()
3394 union xfs_btree_key bkey; /* key of block to insert */ in xfs_btree_insert()
3411 * Stop when we don't get a split block, that must mean that in xfs_btree_insert()
3460 * Try to merge a non-leaf block back into the inode root.
3463 * killing the old root block. But because we can't just delete the
3464 * inode we have to copy the single block it was pointing to into the
3474 struct xfs_btree_block *block; in xfs_btree_kill_iroot() local
3494 * Don't deal with the root block needs to be a leaf case. in xfs_btree_kill_iroot()
3504 block = xfs_btree_get_iroot(cur); in xfs_btree_kill_iroot()
3505 if (xfs_btree_get_numrecs(block) != 1) in xfs_btree_kill_iroot()
3522 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB); in xfs_btree_kill_iroot()
3524 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); in xfs_btree_kill_iroot()
3532 block = ifp->if_broot; in xfs_btree_kill_iroot()
3535 be16_add_cpu(&block->bb_numrecs, index); in xfs_btree_kill_iroot()
3536 ASSERT(block->bb_numrecs == cblock->bb_numrecs); in xfs_btree_kill_iroot()
3538 kp = xfs_btree_key_addr(cur, 1, block); in xfs_btree_kill_iroot()
3542 pp = xfs_btree_ptr_addr(cur, 1, block); in xfs_btree_kill_iroot()
3558 be16_add_cpu(&block->bb_level, -1); in xfs_btree_kill_iroot()
3619 * Remove the record from its block then rebalance the tree.
3628 struct xfs_btree_block *block; /* btree block */ in xfs_btree_delrec() local
3629 union xfs_btree_ptr cptr; /* current block ptr */ in xfs_btree_delrec()
3630 struct xfs_buf *bp; /* buffer for block */ in xfs_btree_delrec()
3633 union xfs_btree_ptr lptr; /* left sibling block ptr */ in xfs_btree_delrec()
3635 struct xfs_btree_block *left; /* left btree block */ in xfs_btree_delrec()
3638 union xfs_btree_ptr rptr; /* right sibling block ptr */ in xfs_btree_delrec()
3640 struct xfs_btree_block *right; /* right btree block */ in xfs_btree_delrec()
3641 struct xfs_btree_block *rrblock; /* right-right btree block */ in xfs_btree_delrec()
3656 /* Get the buffer & block containing the record or key/ptr. */ in xfs_btree_delrec()
3657 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_delrec()
3658 numrecs = xfs_btree_get_numrecs(block); in xfs_btree_delrec()
3661 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_delrec()
3666 /* Fail if we're off the end of the block. */ in xfs_btree_delrec()
3681 lkp = xfs_btree_key_addr(cur, ptr + 1, block); in xfs_btree_delrec()
3682 lpp = xfs_btree_ptr_addr(cur, ptr + 1, block); in xfs_btree_delrec()
3700 xfs_btree_rec_addr(cur, ptr + 1, block), in xfs_btree_delrec()
3707 * Decrement and log the number of entries in the block. in xfs_btree_delrec()
3709 xfs_btree_set_numrecs(block, --numrecs); in xfs_btree_delrec()
3716 if (xfs_btree_is_lastrec(cur, block, level)) { in xfs_btree_delrec()
3717 cur->bc_ops->update_lastrec(cur, block, NULL, in xfs_btree_delrec()
3722 * We're at the root level. First, shrink the root block in-memory. in xfs_btree_delrec()
3750 * pp is still set to the first pointer in the block. in xfs_btree_delrec()
3753 pp = xfs_btree_ptr_addr(cur, 1, block); in xfs_btree_delrec()
3767 * If we deleted the leftmost entry in the block, update the in xfs_btree_delrec()
3777 * If the number of records remaining in the block is at least in xfs_btree_delrec()
3792 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB); in xfs_btree_delrec()
3793 xfs_btree_get_sibling(cur, block, &lptr, XFS_BB_LEFTSIB); in xfs_btree_delrec()
3830 * Move the temp cursor to the last entry in the next block. in xfs_btree_delrec()
3853 /* Grab a pointer to the block. */ in xfs_btree_delrec()
3860 /* Grab the current block number, for future use. */ in xfs_btree_delrec()
3864 * If right block is full enough so that removing one entry in xfs_btree_delrec()
3874 ASSERT(xfs_btree_get_numrecs(block) >= in xfs_btree_delrec()
3890 * to our block again (last record). in xfs_btree_delrec()
3917 * previous block. in xfs_btree_delrec()
3934 /* Grab a pointer to the block. */ in xfs_btree_delrec()
3941 /* Grab the current block number, for future use. */ in xfs_btree_delrec()
3945 * If left block is full enough so that removing one entry in xfs_btree_delrec()
3955 ASSERT(xfs_btree_get_numrecs(block) >= in xfs_btree_delrec()
3982 lrecs + xfs_btree_get_numrecs(block) <= in xfs_btree_delrec()
3985 * Set "right" to be the starting block, in xfs_btree_delrec()
3989 right = block; in xfs_btree_delrec()
3996 * If that won't work, see if we can join with the right neighbor block. in xfs_btree_delrec()
3999 rrecs + xfs_btree_get_numrecs(block) <= in xfs_btree_delrec()
4002 * Set "left" to be the starting block, in xfs_btree_delrec()
4006 left = block; in xfs_btree_delrec()
4069 * Fix up the number of records and right block pointer in the in xfs_btree_delrec()
4070 * surviving block, and log it. in xfs_btree_delrec()
4077 /* If there is a right sibling, point it to the remaining block. */ in xfs_btree_delrec()
4087 /* Free the deleted block. */ in xfs_btree_delrec()
4094 * cursor to the left block, and fix up the index. in xfs_btree_delrec()
4124 * points to the old block so that the caller knows which record to in xfs_btree_delrec()
4206 struct xfs_btree_block *block; /* btree block */ in xfs_btree_get_rec() local
4214 block = xfs_btree_get_block(cur, 0, &bp); in xfs_btree_get_rec()
4217 error = xfs_btree_check_block(cur, block, 0, bp); in xfs_btree_get_rec()
4225 if (ptr > xfs_btree_get_numrecs(block) || ptr <= 0) { in xfs_btree_get_rec()
4233 *recp = xfs_btree_rec_addr(cur, ptr, block); in xfs_btree_get_rec()
4238 /* Visit a block in a btree. */
4246 struct xfs_btree_block *block; in xfs_btree_visit_block() local
4253 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_visit_block()
4255 /* process the block */ in xfs_btree_visit_block()
4260 /* now read rh sibling block for next iteration */ in xfs_btree_visit_block()
4261 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB); in xfs_btree_visit_block()
4265 return xfs_btree_lookup_get_block(cur, level, &rptr, &block); in xfs_btree_visit_block()
4269 /* Visit every block in a btree. */
4279 struct xfs_btree_block *block = NULL; in xfs_btree_visit_blocks() local
4286 /* grab the left hand block */ in xfs_btree_visit_blocks()
4287 error = xfs_btree_lookup_get_block(cur, level, &lptr, &block); in xfs_btree_visit_blocks()
4291 /* readahead the left most block for the next level down */ in xfs_btree_visit_blocks()
4295 ptr = xfs_btree_ptr_addr(cur, 1, block); in xfs_btree_visit_blocks()
4332 * as the amount of CPU work we have to do before moving to the next block is
4335 * For each btree block that we load, modify the owner appropriately, set the
4355 struct xfs_btree_block *block; in xfs_btree_block_change_owner() local
4359 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_block_change_owner()
4361 if (block->bb_u.l.bb_owner == cpu_to_be64(bbcoi->new_owner)) in xfs_btree_block_change_owner()
4363 block->bb_u.l.bb_owner = cpu_to_be64(bbcoi->new_owner); in xfs_btree_block_change_owner()
4365 if (block->bb_u.s.bb_owner == cpu_to_be32(bbcoi->new_owner)) in xfs_btree_block_change_owner()
4367 block->bb_u.s.bb_owner = cpu_to_be32(bbcoi->new_owner); in xfs_btree_block_change_owner()
4371 * If the block is a root block hosted in an inode, we might not have a in xfs_btree_block_change_owner()
4374 * block is formatted into the on-disk inode fork. We still change it, in xfs_btree_block_change_owner()
4410 /* Verify the v5 fields of a long-format btree block. */
4417 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_lblock_v5hdr_verify() local
4421 if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid)) in xfs_btree_lblock_v5hdr_verify()
4423 if (block->bb_u.l.bb_blkno != cpu_to_be64(bp->b_bn)) in xfs_btree_lblock_v5hdr_verify()
4426 be64_to_cpu(block->bb_u.l.bb_owner) != owner) in xfs_btree_lblock_v5hdr_verify()
4431 /* Verify a long-format btree block. */
4438 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_lblock_verify() local
4441 if (be16_to_cpu(block->bb_numrecs) > max_recs) in xfs_btree_lblock_verify()
4445 if (block->bb_u.l.bb_leftsib != cpu_to_be64(NULLFSBLOCK) && in xfs_btree_lblock_verify()
4446 !xfs_verify_fsbno(mp, be64_to_cpu(block->bb_u.l.bb_leftsib))) in xfs_btree_lblock_verify()
4448 if (block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK) && in xfs_btree_lblock_verify()
4449 !xfs_verify_fsbno(mp, be64_to_cpu(block->bb_u.l.bb_rightsib))) in xfs_btree_lblock_verify()
4457 * btree block
4459 * @bp: buffer containing the btree block
4466 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_sblock_v5hdr_verify() local
4471 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid)) in xfs_btree_sblock_v5hdr_verify()
4473 if (block->bb_u.s.bb_blkno != cpu_to_be64(bp->b_bn)) in xfs_btree_sblock_v5hdr_verify()
4475 if (pag && be32_to_cpu(block->bb_u.s.bb_owner) != pag->pag_agno) in xfs_btree_sblock_v5hdr_verify()
4481 * xfs_btree_sblock_verify() -- verify a short-format btree block
4483 * @bp: buffer containing the btree block
4492 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_sblock_verify() local
4496 if (be16_to_cpu(block->bb_numrecs) > max_recs) in xfs_btree_sblock_verify()
4501 if (block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK) && in xfs_btree_sblock_verify()
4502 !xfs_verify_agbno(mp, agno, be32_to_cpu(block->bb_u.s.bb_leftsib))) in xfs_btree_sblock_verify()
4504 if (block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK) && in xfs_btree_sblock_verify()
4505 !xfs_verify_agbno(mp, agno, be32_to_cpu(block->bb_u.s.bb_rightsib))) in xfs_btree_sblock_verify()
4622 * As an optimization, we stop scanning a block when we find a low key
4640 struct xfs_btree_block *block; in xfs_btree_overlapped_query_range() local
4651 error = xfs_btree_lookup_get_block(cur, level, &ptr, &block); in xfs_btree_overlapped_query_range()
4657 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_overlapped_query_range()
4664 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_overlapped_query_range()
4667 if (cur->bc_ptrs[level] > be16_to_cpu(block->bb_numrecs)) { in xfs_btree_overlapped_query_range()
4677 recp = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block); in xfs_btree_overlapped_query_range()
4705 lkp = xfs_btree_key_addr(cur, cur->bc_ptrs[level], block); in xfs_btree_overlapped_query_range()
4706 hkp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level], block); in xfs_btree_overlapped_query_range()
4707 pp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[level], block); in xfs_btree_overlapped_query_range()
4720 &block); in xfs_btree_overlapped_query_range()
4726 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_overlapped_query_range()
4742 * block, a subsequent non-error cursor deletion will not release in xfs_btree_overlapped_query_range()
4909 struct xfs_btree_block *block; in xfs_btree_has_more_records() local
4912 block = xfs_btree_get_block(cur, 0, &bp); in xfs_btree_has_more_records()
4914 /* There are still records in this block. */ in xfs_btree_has_more_records()
4915 if (cur->bc_ptrs[0] < xfs_btree_get_numrecs(block)) in xfs_btree_has_more_records()
4920 return block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK); in xfs_btree_has_more_records()
4922 return block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK); in xfs_btree_has_more_records()