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()
397 xfs_buf_t *bp; /* btree block's buffer pointer */ in xfs_btree_dup_cursor()
399 int i; /* level number of btree block */ in xfs_btree_dup_cursor()
442 * XFS btree block layout and addressing:
447 * the values. A non-leaf block also starts with the same header, and
460 * and comes in different versions for short (32bit) and long (64bit) block
462 * and opaque to the btree core. The block pointers are simple disk endian
466 * into a btree block (xfs_btree_*_offset) or return a pointer to the given
468 * inside the btree block is done using indices starting at one, not zero!
474 * indexing the lowest key available in the block(s) below (the same behavior
476 * available in the block(s) below. Because records are /not/ sorted by the
477 * highest key, all leaf block updates require us to compute the highest key
504 * Now say we want to map block (B+D) into file A at offset (C+D). Ideally,
516 * Return size of the btree block header for this btree instance.
531 * Return size of btree block pointers for this btree instance.
540 * Calculate offset of the n-th record in a btree block.
552 * Calculate offset of the n-th key in a btree block.
564 * Calculate offset of the n-th high key in a btree block.
576 * Calculate offset of the n-th block pointer in a btree block.
590 * Return a pointer to the n-th record in the btree block.
596 struct xfs_btree_block *block) in xfs_btree_rec_addr() argument
599 ((char *)block + xfs_btree_rec_offset(cur, n)); in xfs_btree_rec_addr()
603 * Return a pointer to the n-th key in the btree block.
609 struct xfs_btree_block *block) in xfs_btree_key_addr() argument
612 ((char *)block + xfs_btree_key_offset(cur, n)); in xfs_btree_key_addr()
616 * Return a pointer to the n-th high key in the btree block.
622 struct xfs_btree_block *block) in xfs_btree_high_key_addr() argument
625 ((char *)block + xfs_btree_high_key_offset(cur, n)); in xfs_btree_high_key_addr()
629 * Return a pointer to the n-th block pointer in the btree block.
635 struct xfs_btree_block *block) in xfs_btree_ptr_addr() argument
637 int level = xfs_btree_get_level(block); in xfs_btree_ptr_addr()
639 ASSERT(block->bb_level != 0); in xfs_btree_ptr_addr()
642 ((char *)block + xfs_btree_ptr_offset(cur, n, level)); in xfs_btree_ptr_addr()
657 * Get the root block which is stored in the inode.
672 * Retrieve the block pointer from the cursor at the given level.
675 struct xfs_btree_block * /* generic btree block pointer */
679 struct xfs_buf **bpp) /* buffer containing the block */ in xfs_btree_get_block()
700 struct xfs_btree_block *block; /* generic btree block pointer */ in xfs_btree_firstrec() local
701 xfs_buf_t *bp; /* buffer containing block */ in xfs_btree_firstrec()
704 * Get the block pointer for this level. in xfs_btree_firstrec()
706 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_firstrec()
707 if (xfs_btree_check_block(cur, block, level, bp)) in xfs_btree_firstrec()
712 if (!block->bb_numrecs) in xfs_btree_firstrec()
722 * Change the cursor to point to the last record in the current block
730 struct xfs_btree_block *block; /* generic btree block pointer */ in xfs_btree_lastrec() local
731 xfs_buf_t *bp; /* buffer containing block */ in xfs_btree_lastrec()
734 * Get the block pointer for this level. in xfs_btree_lastrec()
736 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_lastrec()
737 if (xfs_btree_check_block(cur, block, level, bp)) in xfs_btree_lastrec()
742 if (!block->bb_numrecs) in xfs_btree_lastrec()
747 cur->bc_ptrs[level] = be16_to_cpu(block->bb_numrecs); in xfs_btree_lastrec()
788 * Get a buffer for the block, return it read in.
795 xfs_fsblock_t fsbno, /* file system block number */ in xfs_btree_read_bufl()
801 xfs_daddr_t d; /* real disk block address */ in xfs_btree_read_bufl()
818 * Read-ahead the block, don't wait for it, don't return a buffer.
825 xfs_fsblock_t fsbno, /* file system block number */ in xfs_btree_reada_bufl()
837 * Read-ahead the block, don't wait for it, don't return a buffer.
845 xfs_agblock_t agbno, /* allocation group block number */ in xfs_btree_reada_bufs()
861 struct xfs_btree_block *block) in xfs_btree_readahead_lblock() argument
864 xfs_fsblock_t left = be64_to_cpu(block->bb_u.l.bb_leftsib); in xfs_btree_readahead_lblock()
865 xfs_fsblock_t right = be64_to_cpu(block->bb_u.l.bb_rightsib); in xfs_btree_readahead_lblock()
886 struct xfs_btree_block *block) in xfs_btree_readahead_sblock() argument
889 xfs_agblock_t left = be32_to_cpu(block->bb_u.s.bb_leftsib); in xfs_btree_readahead_sblock()
890 xfs_agblock_t right = be32_to_cpu(block->bb_u.s.bb_rightsib); in xfs_btree_readahead_sblock()
918 struct xfs_btree_block *block; in xfs_btree_readahead() local
932 block = XFS_BUF_TO_BLOCK(cur->bc_bufs[lev]); in xfs_btree_readahead()
935 return xfs_btree_readahead_lblock(cur, lr, block); in xfs_btree_readahead()
936 return xfs_btree_readahead_sblock(cur, lr, block); in xfs_btree_readahead()
995 struct xfs_btree_block *b; /* btree block */ in xfs_btree_setbuf()
1044 struct xfs_btree_block *block, in xfs_btree_get_sibling() argument
1052 ptr->l = block->bb_u.l.bb_rightsib; in xfs_btree_get_sibling()
1054 ptr->l = block->bb_u.l.bb_leftsib; in xfs_btree_get_sibling()
1057 ptr->s = block->bb_u.s.bb_rightsib; in xfs_btree_get_sibling()
1059 ptr->s = block->bb_u.s.bb_leftsib; in xfs_btree_get_sibling()
1066 struct xfs_btree_block *block, in xfs_btree_set_sibling() argument
1074 block->bb_u.l.bb_rightsib = ptr->l; in xfs_btree_set_sibling()
1076 block->bb_u.l.bb_leftsib = ptr->l; in xfs_btree_set_sibling()
1079 block->bb_u.s.bb_rightsib = ptr->s; in xfs_btree_set_sibling()
1081 block->bb_u.s.bb_leftsib = ptr->s; in xfs_btree_set_sibling()
1174 struct xfs_btree_block *block, in xfs_btree_is_lastrec() argument
1184 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); in xfs_btree_is_lastrec()
1237 struct xfs_btree_block **block, in xfs_btree_get_buf_block() argument
1253 *block = XFS_BUF_TO_BLOCK(*bpp); in xfs_btree_get_buf_block()
1259 * the block pointer within the buffer.
1266 struct xfs_btree_block **block, in xfs_btree_read_buf_block() argument
1286 *block = XFS_BUF_TO_BLOCK(*bpp); in xfs_btree_read_buf_block()
1291 * Copy keys from one btree block to another.
1305 * Copy records from one btree block to another.
1319 * Copy block pointers from one btree block to another.
1333 * Shift keys one index left/right inside a single btree block.
1352 * Shift records one index left/right inside a single btree block.
1371 * Shift block pointers one index left/right inside a single btree block.
1390 * Log key values from the btree block.
1412 * Log record values from the btree block.
1430 * Log block pointer fields from a btree block (nonleaf).
1435 struct xfs_buf *bp, /* buffer containing btree block */ in xfs_btree_log_ptrs()
1441 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_log_ptrs() local
1442 int level = xfs_btree_get_level(block); in xfs_btree_log_ptrs()
1456 * Log fields from a btree block header.
1461 struct xfs_buf *bp, /* buffer containing btree block */ in xfs_btree_log_block()
1500 * block but instead recreate it during log in xfs_btree_log_block()
1533 struct xfs_btree_block *block; in xfs_btree_increment() local
1544 /* Get a pointer to the btree block. */ in xfs_btree_increment()
1545 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_increment()
1548 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_increment()
1553 /* We're done if we remain in the block after the increment. */ in xfs_btree_increment()
1554 if (++cur->bc_ptrs[level] <= xfs_btree_get_numrecs(block)) in xfs_btree_increment()
1558 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); in xfs_btree_increment()
1566 * Stop when we don't go off the right edge of a block. in xfs_btree_increment()
1569 block = xfs_btree_get_block(cur, lev, &bp); in xfs_btree_increment()
1572 error = xfs_btree_check_block(cur, block, lev, bp); in xfs_btree_increment()
1577 if (++cur->bc_ptrs[lev] <= xfs_btree_get_numrecs(block)) in xfs_btree_increment()
1580 /* Read-ahead the right block for the next loop. */ in xfs_btree_increment()
1601 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) { in xfs_btree_increment()
1604 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block); in xfs_btree_increment()
1606 error = xfs_btree_read_buf_block(cur, ptrp, 0, &block, &bp); in xfs_btree_increment()
1635 struct xfs_btree_block *block; in xfs_btree_decrement() local
1646 /* We're done if we remain in the block after the decrement. */ in xfs_btree_decrement()
1650 /* Get a pointer to the btree block. */ in xfs_btree_decrement()
1651 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_decrement()
1654 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_decrement()
1660 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB); in xfs_btree_decrement()
1668 * Stop when we don't go off the left edge of a block. in xfs_btree_decrement()
1673 /* Read-ahead the left block for the next loop. */ in xfs_btree_decrement()
1694 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) { in xfs_btree_decrement()
1697 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block); in xfs_btree_decrement()
1699 error = xfs_btree_read_buf_block(cur, ptrp, 0, &block, &bp); in xfs_btree_decrement()
1703 cur->bc_ptrs[lev] = xfs_btree_get_numrecs(block); in xfs_btree_decrement()
1721 union xfs_btree_ptr *pp, /* ptr to btree block */ in xfs_btree_lookup_get_block()
1722 struct xfs_btree_block **blkp) /* return btree block */ in xfs_btree_lookup_get_block()
1724 struct xfs_buf *bp; /* buffer pointer for btree block */ in xfs_btree_lookup_get_block()
1728 /* special case the root block if in an inode */ in xfs_btree_lookup_get_block()
1790 struct xfs_btree_block *block, in xfs_lookup_get_search_key() argument
1795 xfs_btree_rec_addr(cur, keyno, block)); in xfs_lookup_get_search_key()
1799 return xfs_btree_key_addr(cur, keyno, block); in xfs_lookup_get_search_key()
1812 struct xfs_btree_block *block; /* current btree block */ in xfs_btree_lookup() local
1817 union xfs_btree_ptr *pp; /* ptr to btree block */ in xfs_btree_lookup()
1818 union xfs_btree_ptr ptr; /* ptr to btree block */ in xfs_btree_lookup()
1826 block = NULL; in xfs_btree_lookup()
1836 * on the lookup record, then follow the corresponding block in xfs_btree_lookup()
1840 /* Get the block we need to do the lookup on. */ in xfs_btree_lookup()
1841 error = xfs_btree_lookup_get_block(cur, level, pp, &block); in xfs_btree_lookup()
1848 * know we need to use the first entry in this block. in xfs_btree_lookup()
1852 /* Otherwise search this block. Do a binary search. */ in xfs_btree_lookup()
1859 high = xfs_btree_get_numrecs(block); in xfs_btree_lookup()
1861 /* Block is empty, must be an empty leaf. */ in xfs_btree_lookup()
1865 cur->bc_mp, block, in xfs_btree_lookup()
1866 sizeof(*block)); in xfs_btree_lookup()
1875 /* Binary search the block. */ in xfs_btree_lookup()
1887 keyno, block, &key); in xfs_btree_lookup()
1907 * by getting the block number and filling in the cursor. in xfs_btree_lookup()
1916 pp = xfs_btree_ptr_addr(cur, keyno, block); in xfs_btree_lookup()
1930 * If ge search and we went off the end of the block, but it's in xfs_btree_lookup()
1931 * not the last block, we're in the wrong block. in xfs_btree_lookup()
1933 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); in xfs_btree_lookup()
1935 keyno > xfs_btree_get_numrecs(block) && in xfs_btree_lookup()
1953 if (keyno == 0 || keyno > xfs_btree_get_numrecs(block)) in xfs_btree_lookup()
1976 /* Determine the low (and high if overlapped) keys of a leaf block */
1980 struct xfs_btree_block *block, in xfs_btree_get_leaf_keys() argument
1989 rec = xfs_btree_rec_addr(cur, 1, block); in xfs_btree_get_leaf_keys()
1995 for (n = 2; n <= xfs_btree_get_numrecs(block); n++) { in xfs_btree_get_leaf_keys()
1996 rec = xfs_btree_rec_addr(cur, n, block); in xfs_btree_get_leaf_keys()
2008 /* Determine the low (and high if overlapped) keys of a node block */
2012 struct xfs_btree_block *block, in xfs_btree_get_node_keys() argument
2021 memcpy(key, xfs_btree_key_addr(cur, 1, block), in xfs_btree_get_node_keys()
2024 max_hkey = xfs_btree_high_key_addr(cur, 1, block); in xfs_btree_get_node_keys()
2025 for (n = 2; n <= xfs_btree_get_numrecs(block); n++) { in xfs_btree_get_node_keys()
2026 hkey = xfs_btree_high_key_addr(cur, n, block); in xfs_btree_get_node_keys()
2034 memcpy(key, xfs_btree_key_addr(cur, 1, block), in xfs_btree_get_node_keys()
2039 /* Derive the keys for any btree block. */
2043 struct xfs_btree_block *block, in xfs_btree_get_keys() argument
2046 if (be16_to_cpu(block->bb_level) == 0) in xfs_btree_get_keys()
2047 xfs_btree_get_leaf_keys(cur, block, key); in xfs_btree_get_keys()
2049 xfs_btree_get_node_keys(cur, block, key); in xfs_btree_get_keys()
2053 * Decide if we need to update the parent keys of a btree block. For
2057 * in the block.
2076 struct xfs_btree_block *block, in __xfs_btree_updkeys() argument
2098 xfs_btree_get_keys(cur, block, lkey); in __xfs_btree_updkeys()
2103 block = xfs_btree_get_block(cur, level, &bp); in __xfs_btree_updkeys()
2106 error = xfs_btree_check_block(cur, block, level, bp); in __xfs_btree_updkeys()
2111 nlkey = xfs_btree_key_addr(cur, ptr, block); in __xfs_btree_updkeys()
2112 nhkey = xfs_btree_high_key_addr(cur, ptr, block); in __xfs_btree_updkeys()
2121 xfs_btree_get_node_keys(cur, block, lkey); in __xfs_btree_updkeys()
2134 struct xfs_btree_block *block; in xfs_btree_updkeys_force() local
2136 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_updkeys_force()
2137 return __xfs_btree_updkeys(cur, level, block, bp, true); in xfs_btree_updkeys_force()
2148 struct xfs_btree_block *block; in xfs_btree_update_keys() local
2156 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_update_keys()
2158 return __xfs_btree_updkeys(cur, level, block, bp, false); in xfs_btree_update_keys()
2164 * at the first entry in the block. in xfs_btree_update_keys()
2166 xfs_btree_get_keys(cur, block, &key); in xfs_btree_update_keys()
2171 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_update_keys()
2173 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_update_keys()
2178 kp = xfs_btree_key_addr(cur, ptr, block); in xfs_btree_update_keys()
2196 struct xfs_btree_block *block; in xfs_btree_update() local
2202 /* Pick up the current block. */ in xfs_btree_update()
2203 block = xfs_btree_get_block(cur, 0, &bp); in xfs_btree_update()
2206 error = xfs_btree_check_block(cur, block, 0, bp); in xfs_btree_update()
2212 rp = xfs_btree_rec_addr(cur, ptr, block); in xfs_btree_update()
2222 if (xfs_btree_is_lastrec(cur, block, 0)) { in xfs_btree_update()
2223 cur->bc_ops->update_lastrec(cur, block, rec, in xfs_btree_update()
2251 struct xfs_btree_block *left; /* left btree block */ in xfs_btree_lshift()
2254 struct xfs_btree_block *right; /* right btree block */ in xfs_btree_lshift()
2268 /* Set up variables for this block as "right". */ in xfs_btree_lshift()
2313 * If non-leaf, copy a key and a ptr to the left block. in xfs_btree_lshift()
2314 * Log the changes to the left block. in xfs_btree_lshift()
2390 * block on the left. in xfs_btree_lshift()
2406 /* Update the parent high keys of the left block, if needed. */ in xfs_btree_lshift()
2414 /* Update the parent keys of the right block. */ in xfs_btree_lshift()
2448 struct xfs_btree_block *left; /* left btree block */ in xfs_btree_rshift()
2450 struct xfs_btree_block *right; /* right btree block */ in xfs_btree_rshift()
2452 union xfs_btree_ptr rptr; /* right block pointer */ in xfs_btree_rshift()
2463 /* Set up variables for this block as "left". */ in xfs_btree_rshift()
2499 * Make a hole at the start of the right neighbor block, then in xfs_btree_rshift()
2500 * copy the last left block entry to the hole. in xfs_btree_rshift()
2561 * block on the right. in xfs_btree_rshift()
2576 /* Update the parent high keys of the left block, if needed. */ in xfs_btree_rshift()
2583 /* Update the parent keys of the right block. */ in xfs_btree_rshift()
2606 * Split cur/level block in half.
2607 * Return new block number and the key to its first
2619 union xfs_btree_ptr lptr; /* left sibling block ptr */ in __xfs_btree_split()
2621 struct xfs_btree_block *left; /* left btree block */ in __xfs_btree_split()
2622 union xfs_btree_ptr rptr; /* right sibling block ptr */ in __xfs_btree_split()
2624 struct xfs_btree_block *right; /* right btree block */ in __xfs_btree_split()
2627 struct xfs_btree_block *rrblock; /* right-right btree block */ in __xfs_btree_split()
2636 /* Set up left block (current one). */ in __xfs_btree_split()
2647 /* Allocate the new block. If we can't do it, we're toast. Give up. */ in __xfs_btree_split()
2655 /* Set up the new block as "right". */ in __xfs_btree_split()
2660 /* Fill in the btree header for the new right block. */ in __xfs_btree_split()
2664 * Split the entries between the old and the new block evenly. in __xfs_btree_split()
2666 * each new block will have the same number of entries. in __xfs_btree_split()
2682 * Copy btree block entries from the left block over to the in __xfs_btree_split()
2683 * new block, the right. Update the right block and log the in __xfs_btree_split()
2704 /* Copy the keys & pointers to the new block. */ in __xfs_btree_split()
2711 /* Stash the keys of the new block for later insertion. */ in __xfs_btree_split()
2721 /* Copy records to the new block. */ in __xfs_btree_split()
2725 /* Stash the keys of the new block for later insertion. */ in __xfs_btree_split()
2730 * Find the left block number by looking in the buffer. in __xfs_btree_split()
2742 * If there's a block to the new block's right, make that block in __xfs_btree_split()
2754 /* Update the parent high keys of the left block, if needed. */ in __xfs_btree_split()
2762 * If the cursor is really in the right block, move it there. in __xfs_btree_split()
2772 * the right block, no matter where this cursor was. in __xfs_btree_split()
2819 * temporarily to ensure that we don't block waiting for memory reclaim in xfs_btree_split_worker()
2879 * Copy the old inode root contents into a real block and make the
2889 struct xfs_btree_block *block; /* btree block */ in xfs_btree_new_iroot() local
2890 struct xfs_btree_block *cblock; /* child btree block */ in xfs_btree_new_iroot()
2894 union xfs_btree_ptr *pp; /* pointer to block addr */ in xfs_btree_new_iroot()
2895 union xfs_btree_ptr nptr; /* new block addr */ in xfs_btree_new_iroot()
2906 block = xfs_btree_get_iroot(cur); in xfs_btree_new_iroot()
2907 pp = xfs_btree_ptr_addr(cur, 1, block); in xfs_btree_new_iroot()
2909 /* Allocate the new block. If we can't do it, we're toast. Give up. */ in xfs_btree_new_iroot()
2918 /* Copy the root into a real block. */ in xfs_btree_new_iroot()
2927 memcpy(cblock, block, xfs_btree_block_len(cur)); in xfs_btree_new_iroot()
2935 be16_add_cpu(&block->bb_level, 1); in xfs_btree_new_iroot()
2936 xfs_btree_set_numrecs(block, 1); in xfs_btree_new_iroot()
2940 kp = xfs_btree_key_addr(cur, 1, block); in xfs_btree_new_iroot()
2982 * Allocate a new root block, fill it in.
2989 struct xfs_btree_block *block; /* one half of the old root block */ in xfs_btree_new_root() local
2990 struct xfs_buf *bp; /* buffer containing block */ in xfs_btree_new_root()
2993 struct xfs_btree_block *left; /* left btree block */ in xfs_btree_new_root()
2995 struct xfs_btree_block *new; /* new (root) btree block */ in xfs_btree_new_root()
2998 struct xfs_btree_block *right; /* right btree block */ in xfs_btree_new_root()
3007 /* Allocate the new block. If we can't do it, we're toast. Give up. */ in xfs_btree_new_root()
3015 /* Set up the new block. */ in xfs_btree_new_root()
3025 * and the new block generated when it was split. We don't know which in xfs_btree_new_root()
3029 block = xfs_btree_get_block(cur, cur->bc_nlevels - 1, &bp); in xfs_btree_new_root()
3032 error = xfs_btree_check_block(cur, block, cur->bc_nlevels - 1, bp); in xfs_btree_new_root()
3037 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB); in xfs_btree_new_root()
3039 /* Our block is left, pick up the right block. */ in xfs_btree_new_root()
3042 left = block; in xfs_btree_new_root()
3049 /* Our block is right, pick up the left block. */ in xfs_btree_new_root()
3052 right = block; in xfs_btree_new_root()
3061 /* Fill in the new block's btree header and log it. */ in xfs_btree_new_root()
3070 * Get the keys for the left block's keys and put them directly in xfs_btree_new_root()
3071 * in the parent block. Do the same for the right block. in xfs_btree_new_root()
3079 * Get the keys for the left block's records and put them in xfs_btree_new_root()
3080 * directly in the parent block. Do the same for the right in xfs_btree_new_root()
3081 * block. in xfs_btree_new_root()
3114 int numrecs,/* # of recs in block */ in xfs_btree_make_block_unfull()
3119 union xfs_btree_key *key, /* key of new block */ in xfs_btree_make_block_unfull()
3129 /* A root block that can be made bigger. */ in xfs_btree_make_block_unfull()
3133 /* A root block that needs replacing */ in xfs_btree_make_block_unfull()
3162 * Next, try splitting the current block in half. in xfs_btree_make_block_unfull()
3165 * could be in a different block now. in xfs_btree_make_block_unfull()
3184 union xfs_btree_ptr *ptrp, /* i/o: block number inserted */ in xfs_btree_insrec()
3186 union xfs_btree_key *key, /* i/o: block key for ptrp */ in xfs_btree_insrec()
3190 struct xfs_btree_block *block; /* btree block */ in xfs_btree_insrec() local
3191 struct xfs_buf *bp; /* buffer for block */ in xfs_btree_insrec()
3192 union xfs_btree_ptr nptr; /* new block ptr */ in xfs_btree_insrec()
3194 union xfs_btree_key nkey; /* new block key */ in xfs_btree_insrec()
3208 * root level, allocate a new root block and we're done. in xfs_btree_insrec()
3229 /* Get pointers to the btree buffer and block. */ in xfs_btree_insrec()
3230 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_insrec()
3232 numrecs = xfs_btree_get_numrecs(block); in xfs_btree_insrec()
3235 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_insrec()
3243 xfs_btree_rec_addr(cur, ptr, block))); in xfs_btree_insrec()
3246 xfs_btree_key_addr(cur, ptr, block))); in xfs_btree_insrec()
3252 * If the block is full, we can't insert the new entry until we in xfs_btree_insrec()
3253 * make the block un-full. in xfs_btree_insrec()
3264 * The current block may have changed if the block was in xfs_btree_insrec()
3267 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_insrec()
3268 numrecs = xfs_btree_get_numrecs(block); in xfs_btree_insrec()
3271 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_insrec()
3277 * At this point we know there's room for our new entry in the block in xfs_btree_insrec()
3287 kp = xfs_btree_key_addr(cur, ptr, block); in xfs_btree_insrec()
3288 pp = xfs_btree_ptr_addr(cur, ptr, block); in xfs_btree_insrec()
3307 xfs_btree_set_numrecs(block, numrecs); in xfs_btree_insrec()
3313 xfs_btree_key_addr(cur, ptr + 1, block))); in xfs_btree_insrec()
3320 rp = xfs_btree_rec_addr(cur, ptr, block); in xfs_btree_insrec()
3326 xfs_btree_set_numrecs(block, ++numrecs); in xfs_btree_insrec()
3331 xfs_btree_rec_addr(cur, ptr + 1, block))); in xfs_btree_insrec()
3340 * If we just inserted into a new tree block, we have to in xfs_btree_insrec()
3343 * Otherwise we're just updating an existing block (having shoved in xfs_btree_insrec()
3344 * some records into the new tree block), so use the regular key in xfs_btree_insrec()
3348 xfs_btree_get_keys(cur, block, lkey); in xfs_btree_insrec()
3359 if (xfs_btree_is_lastrec(cur, block, level)) { in xfs_btree_insrec()
3360 cur->bc_ops->update_lastrec(cur, block, rec, in xfs_btree_insrec()
3365 * Return the new block number, if any. in xfs_btree_insrec()
3396 union xfs_btree_ptr nptr; /* new block number (split result) */ in xfs_btree_insert()
3399 union xfs_btree_key bkey; /* key of block to insert */ in xfs_btree_insert()
3416 * Stop when we don't get a split block, that must mean that in xfs_btree_insert()
3465 * Try to merge a non-leaf block back into the inode root.
3468 * killing the old root block. But because we can't just delete the
3469 * inode we have to copy the single block it was pointing to into the
3479 struct xfs_btree_block *block; in xfs_btree_kill_iroot() local
3499 * Don't deal with the root block needs to be a leaf case. in xfs_btree_kill_iroot()
3509 block = xfs_btree_get_iroot(cur); in xfs_btree_kill_iroot()
3510 if (xfs_btree_get_numrecs(block) != 1) in xfs_btree_kill_iroot()
3527 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB); in xfs_btree_kill_iroot()
3529 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); in xfs_btree_kill_iroot()
3537 block = ifp->if_broot; in xfs_btree_kill_iroot()
3540 be16_add_cpu(&block->bb_numrecs, index); in xfs_btree_kill_iroot()
3541 ASSERT(block->bb_numrecs == cblock->bb_numrecs); in xfs_btree_kill_iroot()
3543 kp = xfs_btree_key_addr(cur, 1, block); in xfs_btree_kill_iroot()
3547 pp = xfs_btree_ptr_addr(cur, 1, block); in xfs_btree_kill_iroot()
3563 be16_add_cpu(&block->bb_level, -1); in xfs_btree_kill_iroot()
3624 * Remove the record from its block then rebalance the tree.
3633 struct xfs_btree_block *block; /* btree block */ in xfs_btree_delrec() local
3634 union xfs_btree_ptr cptr; /* current block ptr */ in xfs_btree_delrec()
3635 struct xfs_buf *bp; /* buffer for block */ in xfs_btree_delrec()
3638 union xfs_btree_ptr lptr; /* left sibling block ptr */ in xfs_btree_delrec()
3640 struct xfs_btree_block *left; /* left btree block */ in xfs_btree_delrec()
3643 union xfs_btree_ptr rptr; /* right sibling block ptr */ in xfs_btree_delrec()
3645 struct xfs_btree_block *right; /* right btree block */ in xfs_btree_delrec()
3646 struct xfs_btree_block *rrblock; /* right-right btree block */ in xfs_btree_delrec()
3661 /* Get the buffer & block containing the record or key/ptr. */ in xfs_btree_delrec()
3662 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_delrec()
3663 numrecs = xfs_btree_get_numrecs(block); in xfs_btree_delrec()
3666 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_delrec()
3671 /* Fail if we're off the end of the block. */ in xfs_btree_delrec()
3686 lkp = xfs_btree_key_addr(cur, ptr + 1, block); in xfs_btree_delrec()
3687 lpp = xfs_btree_ptr_addr(cur, ptr + 1, block); in xfs_btree_delrec()
3705 xfs_btree_rec_addr(cur, ptr + 1, block), in xfs_btree_delrec()
3712 * Decrement and log the number of entries in the block. in xfs_btree_delrec()
3714 xfs_btree_set_numrecs(block, --numrecs); in xfs_btree_delrec()
3721 if (xfs_btree_is_lastrec(cur, block, level)) { in xfs_btree_delrec()
3722 cur->bc_ops->update_lastrec(cur, block, NULL, in xfs_btree_delrec()
3727 * We're at the root level. First, shrink the root block in-memory. in xfs_btree_delrec()
3755 * pp is still set to the first pointer in the block. in xfs_btree_delrec()
3758 pp = xfs_btree_ptr_addr(cur, 1, block); in xfs_btree_delrec()
3772 * If we deleted the leftmost entry in the block, update the in xfs_btree_delrec()
3782 * If the number of records remaining in the block is at least in xfs_btree_delrec()
3797 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB); in xfs_btree_delrec()
3798 xfs_btree_get_sibling(cur, block, &lptr, XFS_BB_LEFTSIB); in xfs_btree_delrec()
3835 * Move the temp cursor to the last entry in the next block. in xfs_btree_delrec()
3858 /* Grab a pointer to the block. */ in xfs_btree_delrec()
3865 /* Grab the current block number, for future use. */ in xfs_btree_delrec()
3869 * If right block is full enough so that removing one entry in xfs_btree_delrec()
3879 ASSERT(xfs_btree_get_numrecs(block) >= in xfs_btree_delrec()
3895 * to our block again (last record). in xfs_btree_delrec()
3922 * previous block. in xfs_btree_delrec()
3939 /* Grab a pointer to the block. */ in xfs_btree_delrec()
3946 /* Grab the current block number, for future use. */ in xfs_btree_delrec()
3950 * If left block is full enough so that removing one entry in xfs_btree_delrec()
3960 ASSERT(xfs_btree_get_numrecs(block) >= in xfs_btree_delrec()
3987 lrecs + xfs_btree_get_numrecs(block) <= in xfs_btree_delrec()
3990 * Set "right" to be the starting block, in xfs_btree_delrec()
3994 right = block; in xfs_btree_delrec()
4001 * If that won't work, see if we can join with the right neighbor block. in xfs_btree_delrec()
4004 rrecs + xfs_btree_get_numrecs(block) <= in xfs_btree_delrec()
4007 * Set "left" to be the starting block, in xfs_btree_delrec()
4011 left = block; in xfs_btree_delrec()
4074 * Fix up the number of records and right block pointer in the in xfs_btree_delrec()
4075 * surviving block, and log it. in xfs_btree_delrec()
4082 /* If there is a right sibling, point it to the remaining block. */ in xfs_btree_delrec()
4092 /* Free the deleted block. */ in xfs_btree_delrec()
4099 * cursor to the left block, and fix up the index. in xfs_btree_delrec()
4129 * points to the old block so that the caller knows which record to in xfs_btree_delrec()
4211 struct xfs_btree_block *block; /* btree block */ in xfs_btree_get_rec() local
4219 block = xfs_btree_get_block(cur, 0, &bp); in xfs_btree_get_rec()
4222 error = xfs_btree_check_block(cur, block, 0, bp); in xfs_btree_get_rec()
4230 if (ptr > xfs_btree_get_numrecs(block) || ptr <= 0) { in xfs_btree_get_rec()
4238 *recp = xfs_btree_rec_addr(cur, ptr, block); in xfs_btree_get_rec()
4243 /* Visit a block in a btree. */
4251 struct xfs_btree_block *block; in xfs_btree_visit_block() local
4258 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_visit_block()
4260 /* process the block */ in xfs_btree_visit_block()
4265 /* now read rh sibling block for next iteration */ in xfs_btree_visit_block()
4266 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB); in xfs_btree_visit_block()
4270 return xfs_btree_lookup_get_block(cur, level, &rptr, &block); in xfs_btree_visit_block()
4274 /* Visit every block in a btree. */
4284 struct xfs_btree_block *block = NULL; in xfs_btree_visit_blocks() local
4291 /* grab the left hand block */ in xfs_btree_visit_blocks()
4292 error = xfs_btree_lookup_get_block(cur, level, &lptr, &block); in xfs_btree_visit_blocks()
4296 /* readahead the left most block for the next level down */ in xfs_btree_visit_blocks()
4300 ptr = xfs_btree_ptr_addr(cur, 1, block); in xfs_btree_visit_blocks()
4337 * as the amount of CPU work we have to do before moving to the next block is
4340 * For each btree block that we load, modify the owner appropriately, set the
4360 struct xfs_btree_block *block; in xfs_btree_block_change_owner() local
4364 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_block_change_owner()
4366 if (block->bb_u.l.bb_owner == cpu_to_be64(bbcoi->new_owner)) in xfs_btree_block_change_owner()
4368 block->bb_u.l.bb_owner = cpu_to_be64(bbcoi->new_owner); in xfs_btree_block_change_owner()
4370 if (block->bb_u.s.bb_owner == cpu_to_be32(bbcoi->new_owner)) in xfs_btree_block_change_owner()
4372 block->bb_u.s.bb_owner = cpu_to_be32(bbcoi->new_owner); in xfs_btree_block_change_owner()
4376 * If the block is a root block hosted in an inode, we might not have a in xfs_btree_block_change_owner()
4379 * block is formatted into the on-disk inode fork. We still change it, in xfs_btree_block_change_owner()
4415 /* Verify the v5 fields of a long-format btree block. */
4422 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_lblock_v5hdr_verify() local
4426 if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid)) in xfs_btree_lblock_v5hdr_verify()
4428 if (block->bb_u.l.bb_blkno != cpu_to_be64(bp->b_bn)) in xfs_btree_lblock_v5hdr_verify()
4431 be64_to_cpu(block->bb_u.l.bb_owner) != owner) in xfs_btree_lblock_v5hdr_verify()
4436 /* Verify a long-format btree block. */
4443 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_lblock_verify() local
4446 if (be16_to_cpu(block->bb_numrecs) > max_recs) in xfs_btree_lblock_verify()
4450 if (block->bb_u.l.bb_leftsib != cpu_to_be64(NULLFSBLOCK) && in xfs_btree_lblock_verify()
4451 !xfs_verify_fsbno(mp, be64_to_cpu(block->bb_u.l.bb_leftsib))) in xfs_btree_lblock_verify()
4453 if (block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK) && in xfs_btree_lblock_verify()
4454 !xfs_verify_fsbno(mp, be64_to_cpu(block->bb_u.l.bb_rightsib))) in xfs_btree_lblock_verify()
4462 * btree block
4464 * @bp: buffer containing the btree block
4471 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_sblock_v5hdr_verify() local
4476 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid)) in xfs_btree_sblock_v5hdr_verify()
4478 if (block->bb_u.s.bb_blkno != cpu_to_be64(bp->b_bn)) in xfs_btree_sblock_v5hdr_verify()
4480 if (pag && be32_to_cpu(block->bb_u.s.bb_owner) != pag->pag_agno) in xfs_btree_sblock_v5hdr_verify()
4486 * xfs_btree_sblock_verify() -- verify a short-format btree block
4488 * @bp: buffer containing the btree block
4497 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_sblock_verify() local
4501 if (be16_to_cpu(block->bb_numrecs) > max_recs) in xfs_btree_sblock_verify()
4506 if (block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK) && in xfs_btree_sblock_verify()
4507 !xfs_verify_agbno(mp, agno, be32_to_cpu(block->bb_u.s.bb_leftsib))) in xfs_btree_sblock_verify()
4509 if (block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK) && in xfs_btree_sblock_verify()
4510 !xfs_verify_agbno(mp, agno, be32_to_cpu(block->bb_u.s.bb_rightsib))) in xfs_btree_sblock_verify()
4627 * As an optimization, we stop scanning a block when we find a low key
4645 struct xfs_btree_block *block; in xfs_btree_overlapped_query_range() local
4656 error = xfs_btree_lookup_get_block(cur, level, &ptr, &block); in xfs_btree_overlapped_query_range()
4662 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_overlapped_query_range()
4669 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_overlapped_query_range()
4672 if (cur->bc_ptrs[level] > be16_to_cpu(block->bb_numrecs)) { in xfs_btree_overlapped_query_range()
4682 recp = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block); in xfs_btree_overlapped_query_range()
4710 lkp = xfs_btree_key_addr(cur, cur->bc_ptrs[level], block); in xfs_btree_overlapped_query_range()
4711 hkp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level], block); in xfs_btree_overlapped_query_range()
4712 pp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[level], block); in xfs_btree_overlapped_query_range()
4725 &block); in xfs_btree_overlapped_query_range()
4731 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_overlapped_query_range()
4747 * block, a subsequent non-error cursor deletion will not release in xfs_btree_overlapped_query_range()
4914 struct xfs_btree_block *block; in xfs_btree_has_more_records() local
4917 block = xfs_btree_get_block(cur, 0, &bp); in xfs_btree_has_more_records()
4919 /* There are still records in this block. */ in xfs_btree_has_more_records()
4920 if (cur->bc_ptrs[0] < xfs_btree_get_numrecs(block)) in xfs_btree_has_more_records()
4925 return block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK); in xfs_btree_has_more_records()
4927 return block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK); in xfs_btree_has_more_records()