Lines Matching full:block
55 * Check a long btree block header. Return the address of the failing check,
61 struct xfs_btree_block *block, in __xfs_btree_check_lblock() argument
70 if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid)) in __xfs_btree_check_lblock()
72 if (block->bb_u.l.bb_blkno != in __xfs_btree_check_lblock()
75 if (block->bb_u.l.bb_pad != cpu_to_be32(0)) in __xfs_btree_check_lblock()
79 if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(crc, btnum)) in __xfs_btree_check_lblock()
81 if (be16_to_cpu(block->bb_level) != level) in __xfs_btree_check_lblock()
83 if (be16_to_cpu(block->bb_numrecs) > in __xfs_btree_check_lblock()
86 if (block->bb_u.l.bb_leftsib != cpu_to_be64(NULLFSBLOCK) && in __xfs_btree_check_lblock()
87 !xfs_btree_check_lptr(cur, be64_to_cpu(block->bb_u.l.bb_leftsib), in __xfs_btree_check_lblock()
90 if (block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK) && in __xfs_btree_check_lblock()
91 !xfs_btree_check_lptr(cur, be64_to_cpu(block->bb_u.l.bb_rightsib), in __xfs_btree_check_lblock()
98 /* Check a long btree block header. */
102 struct xfs_btree_block *block, in xfs_btree_check_lblock() argument
109 fa = __xfs_btree_check_lblock(cur, block, level, bp); in xfs_btree_check_lblock()
120 * Check a short btree block header. Return the address of the failing check,
126 struct xfs_btree_block *block, in __xfs_btree_check_sblock() argument
135 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid)) in __xfs_btree_check_sblock()
137 if (block->bb_u.s.bb_blkno != in __xfs_btree_check_sblock()
142 if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(crc, btnum)) in __xfs_btree_check_sblock()
144 if (be16_to_cpu(block->bb_level) != level) in __xfs_btree_check_sblock()
146 if (be16_to_cpu(block->bb_numrecs) > in __xfs_btree_check_sblock()
149 if (block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK) && in __xfs_btree_check_sblock()
150 !xfs_btree_check_sptr(cur, be32_to_cpu(block->bb_u.s.bb_leftsib), in __xfs_btree_check_sblock()
153 if (block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK) && in __xfs_btree_check_sblock()
154 !xfs_btree_check_sptr(cur, be32_to_cpu(block->bb_u.s.bb_rightsib), in __xfs_btree_check_sblock()
161 /* Check a short btree block header. */
165 struct xfs_btree_block *block, in xfs_btree_check_sblock() argument
172 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()
394 struct xfs_buf *bp; /* btree block's buffer pointer */ in xfs_btree_dup_cursor()
396 int i; /* level number of btree block */ in xfs_btree_dup_cursor()
439 * XFS btree block layout and addressing:
444 * the values. A non-leaf block also starts with the same header, and
457 * and comes in different versions for short (32bit) and long (64bit) block
459 * and opaque to the btree core. The block pointers are simple disk endian
463 * into a btree block (xfs_btree_*_offset) or return a pointer to the given
465 * inside the btree block is done using indices starting at one, not zero!
471 * indexing the lowest key available in the block(s) below (the same behavior
473 * available in the block(s) below. Because records are /not/ sorted by the
474 * highest key, all leaf block updates require us to compute the highest key
501 * Now say we want to map block (B+D) into file A at offset (C+D). Ideally,
513 * Return size of the btree block header for this btree instance.
528 * Return size of btree block pointers for this btree instance.
537 * Calculate offset of the n-th record in a btree block.
549 * Calculate offset of the n-th key in a btree block.
561 * Calculate offset of the n-th high key in a btree block.
573 * Calculate offset of the n-th block pointer in a btree block.
587 * Return a pointer to the n-th record in the btree block.
593 struct xfs_btree_block *block) in xfs_btree_rec_addr() argument
596 ((char *)block + xfs_btree_rec_offset(cur, n)); in xfs_btree_rec_addr()
600 * Return a pointer to the n-th key in the btree block.
606 struct xfs_btree_block *block) in xfs_btree_key_addr() argument
609 ((char *)block + xfs_btree_key_offset(cur, n)); in xfs_btree_key_addr()
613 * Return a pointer to the n-th high key in the btree block.
619 struct xfs_btree_block *block) in xfs_btree_high_key_addr() argument
622 ((char *)block + xfs_btree_high_key_offset(cur, n)); in xfs_btree_high_key_addr()
626 * Return a pointer to the n-th block pointer in the btree block.
632 struct xfs_btree_block *block) in xfs_btree_ptr_addr() argument
634 int level = xfs_btree_get_level(block); in xfs_btree_ptr_addr()
636 ASSERT(block->bb_level != 0); in xfs_btree_ptr_addr()
639 ((char *)block + xfs_btree_ptr_offset(cur, n, level)); in xfs_btree_ptr_addr()
654 * Get the root block which is stored in the inode.
669 * Retrieve the block pointer from the cursor at the given level.
672 struct xfs_btree_block * /* generic btree block pointer */
676 struct xfs_buf **bpp) /* buffer containing the block */ in xfs_btree_get_block()
697 struct xfs_btree_block *block; /* generic btree block pointer */ in xfs_btree_firstrec() local
698 struct xfs_buf *bp; /* buffer containing block */ in xfs_btree_firstrec()
701 * Get the block pointer for this level. in xfs_btree_firstrec()
703 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_firstrec()
704 if (xfs_btree_check_block(cur, block, level, bp)) in xfs_btree_firstrec()
709 if (!block->bb_numrecs) in xfs_btree_firstrec()
719 * Change the cursor to point to the last record in the current block
727 struct xfs_btree_block *block; /* generic btree block pointer */ in xfs_btree_lastrec() local
728 struct xfs_buf *bp; /* buffer containing block */ in xfs_btree_lastrec()
731 * Get the block pointer for this level. in xfs_btree_lastrec()
733 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_lastrec()
734 if (xfs_btree_check_block(cur, block, level, bp)) in xfs_btree_lastrec()
739 if (!block->bb_numrecs) in xfs_btree_lastrec()
744 cur->bc_ptrs[level] = be16_to_cpu(block->bb_numrecs); in xfs_btree_lastrec()
785 * Get a buffer for the block, return it read in.
792 xfs_fsblock_t fsbno, /* file system block number */ in xfs_btree_read_bufl()
798 xfs_daddr_t d; /* real disk block address */ in xfs_btree_read_bufl()
815 * Read-ahead the block, don't wait for it, don't return a buffer.
822 xfs_fsblock_t fsbno, /* file system block number */ in xfs_btree_reada_bufl()
834 * Read-ahead the block, don't wait for it, don't return a buffer.
842 xfs_agblock_t agbno, /* allocation group block number */ in xfs_btree_reada_bufs()
858 struct xfs_btree_block *block) in xfs_btree_readahead_lblock() argument
861 xfs_fsblock_t left = be64_to_cpu(block->bb_u.l.bb_leftsib); in xfs_btree_readahead_lblock()
862 xfs_fsblock_t right = be64_to_cpu(block->bb_u.l.bb_rightsib); in xfs_btree_readahead_lblock()
883 struct xfs_btree_block *block) in xfs_btree_readahead_sblock() argument
886 xfs_agblock_t left = be32_to_cpu(block->bb_u.s.bb_leftsib); in xfs_btree_readahead_sblock()
887 xfs_agblock_t right = be32_to_cpu(block->bb_u.s.bb_rightsib); in xfs_btree_readahead_sblock()
915 struct xfs_btree_block *block; in xfs_btree_readahead() local
929 block = XFS_BUF_TO_BLOCK(cur->bc_bufs[lev]); in xfs_btree_readahead()
932 return xfs_btree_readahead_lblock(cur, lr, block); in xfs_btree_readahead()
933 return xfs_btree_readahead_sblock(cur, lr, block); in xfs_btree_readahead()
992 struct xfs_btree_block *b; /* btree block */ in xfs_btree_setbuf()
1041 struct xfs_btree_block *block, in xfs_btree_get_sibling() argument
1049 ptr->l = block->bb_u.l.bb_rightsib; in xfs_btree_get_sibling()
1051 ptr->l = block->bb_u.l.bb_leftsib; in xfs_btree_get_sibling()
1054 ptr->s = block->bb_u.s.bb_rightsib; in xfs_btree_get_sibling()
1056 ptr->s = block->bb_u.s.bb_leftsib; in xfs_btree_get_sibling()
1063 struct xfs_btree_block *block, in xfs_btree_set_sibling() argument
1071 block->bb_u.l.bb_rightsib = ptr->l; in xfs_btree_set_sibling()
1073 block->bb_u.l.bb_leftsib = ptr->l; in xfs_btree_set_sibling()
1076 block->bb_u.s.bb_rightsib = ptr->s; in xfs_btree_set_sibling()
1078 block->bb_u.s.bb_leftsib = ptr->s; in xfs_btree_set_sibling()
1171 struct xfs_btree_block *block, in xfs_btree_is_lastrec() argument
1181 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); in xfs_btree_is_lastrec()
1234 struct xfs_btree_block **block, in xfs_btree_get_buf_block() argument
1250 *block = XFS_BUF_TO_BLOCK(*bpp); in xfs_btree_get_buf_block()
1256 * the block pointer within the buffer.
1263 struct xfs_btree_block **block, in xfs_btree_read_buf_block() argument
1283 *block = XFS_BUF_TO_BLOCK(*bpp); in xfs_btree_read_buf_block()
1288 * Copy keys from one btree block to another.
1302 * Copy records from one btree block to another.
1316 * Copy block pointers from one btree block to another.
1330 * Shift keys one index left/right inside a single btree block.
1349 * Shift records one index left/right inside a single btree block.
1368 * Shift block pointers one index left/right inside a single btree block.
1387 * Log key values from the btree block.
1409 * Log record values from the btree block.
1427 * Log block pointer fields from a btree block (nonleaf).
1432 struct xfs_buf *bp, /* buffer containing btree block */ in xfs_btree_log_ptrs()
1438 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_log_ptrs() local
1439 int level = xfs_btree_get_level(block); in xfs_btree_log_ptrs()
1453 * Log fields from a btree block header.
1458 struct xfs_buf *bp, /* buffer containing btree block */ in xfs_btree_log_block()
1497 * block but instead recreate it during log in xfs_btree_log_block()
1530 struct xfs_btree_block *block; in xfs_btree_increment() local
1541 /* Get a pointer to the btree block. */ in xfs_btree_increment()
1542 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_increment()
1545 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_increment()
1550 /* We're done if we remain in the block after the increment. */ in xfs_btree_increment()
1551 if (++cur->bc_ptrs[level] <= xfs_btree_get_numrecs(block)) in xfs_btree_increment()
1555 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); in xfs_btree_increment()
1563 * Stop when we don't go off the right edge of a block. in xfs_btree_increment()
1566 block = xfs_btree_get_block(cur, lev, &bp); in xfs_btree_increment()
1569 error = xfs_btree_check_block(cur, block, lev, bp); in xfs_btree_increment()
1574 if (++cur->bc_ptrs[lev] <= xfs_btree_get_numrecs(block)) in xfs_btree_increment()
1577 /* Read-ahead the right block for the next loop. */ in xfs_btree_increment()
1598 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) { in xfs_btree_increment()
1601 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block); in xfs_btree_increment()
1603 error = xfs_btree_read_buf_block(cur, ptrp, 0, &block, &bp); in xfs_btree_increment()
1632 struct xfs_btree_block *block; in xfs_btree_decrement() local
1643 /* We're done if we remain in the block after the decrement. */ in xfs_btree_decrement()
1647 /* Get a pointer to the btree block. */ in xfs_btree_decrement()
1648 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_decrement()
1651 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_decrement()
1657 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB); in xfs_btree_decrement()
1665 * Stop when we don't go off the left edge of a block. in xfs_btree_decrement()
1670 /* Read-ahead the left block for the next loop. */ in xfs_btree_decrement()
1691 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) { in xfs_btree_decrement()
1694 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block); in xfs_btree_decrement()
1696 error = xfs_btree_read_buf_block(cur, ptrp, 0, &block, &bp); in xfs_btree_decrement()
1700 cur->bc_ptrs[lev] = xfs_btree_get_numrecs(block); in xfs_btree_decrement()
1718 const union xfs_btree_ptr *pp, /* ptr to btree block */ in xfs_btree_lookup_get_block()
1719 struct xfs_btree_block **blkp) /* return btree block */ in xfs_btree_lookup_get_block()
1721 struct xfs_buf *bp; /* buffer pointer for btree block */ in xfs_btree_lookup_get_block()
1725 /* special case the root block if in an inode */ in xfs_btree_lookup_get_block()
1787 struct xfs_btree_block *block, in xfs_lookup_get_search_key() argument
1792 xfs_btree_rec_addr(cur, keyno, block)); in xfs_lookup_get_search_key()
1796 return xfs_btree_key_addr(cur, keyno, block); in xfs_lookup_get_search_key()
1809 struct xfs_btree_block *block; /* current btree block */ in xfs_btree_lookup() local
1814 union xfs_btree_ptr *pp; /* ptr to btree block */ in xfs_btree_lookup()
1815 union xfs_btree_ptr ptr; /* ptr to btree block */ in xfs_btree_lookup()
1823 block = NULL; in xfs_btree_lookup()
1833 * on the lookup record, then follow the corresponding block in xfs_btree_lookup()
1837 /* Get the block we need to do the lookup on. */ in xfs_btree_lookup()
1838 error = xfs_btree_lookup_get_block(cur, level, pp, &block); in xfs_btree_lookup()
1845 * know we need to use the first entry in this block. in xfs_btree_lookup()
1849 /* Otherwise search this block. Do a binary search. */ in xfs_btree_lookup()
1856 high = xfs_btree_get_numrecs(block); in xfs_btree_lookup()
1858 /* Block is empty, must be an empty leaf. */ in xfs_btree_lookup()
1862 cur->bc_mp, block, in xfs_btree_lookup()
1863 sizeof(*block)); in xfs_btree_lookup()
1872 /* Binary search the block. */ in xfs_btree_lookup()
1884 keyno, block, &key); in xfs_btree_lookup()
1904 * by getting the block number and filling in the cursor. in xfs_btree_lookup()
1913 pp = xfs_btree_ptr_addr(cur, keyno, block); in xfs_btree_lookup()
1927 * If ge search and we went off the end of the block, but it's in xfs_btree_lookup()
1928 * not the last block, we're in the wrong block. in xfs_btree_lookup()
1930 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); in xfs_btree_lookup()
1932 keyno > xfs_btree_get_numrecs(block) && in xfs_btree_lookup()
1950 if (keyno == 0 || keyno > xfs_btree_get_numrecs(block)) in xfs_btree_lookup()
1973 /* Determine the low (and high if overlapped) keys of a leaf block */
1977 struct xfs_btree_block *block, in xfs_btree_get_leaf_keys() argument
1986 rec = xfs_btree_rec_addr(cur, 1, block); in xfs_btree_get_leaf_keys()
1992 for (n = 2; n <= xfs_btree_get_numrecs(block); n++) { in xfs_btree_get_leaf_keys()
1993 rec = xfs_btree_rec_addr(cur, n, block); in xfs_btree_get_leaf_keys()
2005 /* Determine the low (and high if overlapped) keys of a node block */
2009 struct xfs_btree_block *block, in xfs_btree_get_node_keys() argument
2018 memcpy(key, xfs_btree_key_addr(cur, 1, block), in xfs_btree_get_node_keys()
2021 max_hkey = xfs_btree_high_key_addr(cur, 1, block); in xfs_btree_get_node_keys()
2022 for (n = 2; n <= xfs_btree_get_numrecs(block); n++) { in xfs_btree_get_node_keys()
2023 hkey = xfs_btree_high_key_addr(cur, n, block); in xfs_btree_get_node_keys()
2031 memcpy(key, xfs_btree_key_addr(cur, 1, block), in xfs_btree_get_node_keys()
2036 /* Derive the keys for any btree block. */
2040 struct xfs_btree_block *block, in xfs_btree_get_keys() argument
2043 if (be16_to_cpu(block->bb_level) == 0) in xfs_btree_get_keys()
2044 xfs_btree_get_leaf_keys(cur, block, key); in xfs_btree_get_keys()
2046 xfs_btree_get_node_keys(cur, block, key); in xfs_btree_get_keys()
2050 * Decide if we need to update the parent keys of a btree block. For
2054 * in the block.
2073 struct xfs_btree_block *block, in __xfs_btree_updkeys() argument
2095 xfs_btree_get_keys(cur, block, lkey); in __xfs_btree_updkeys()
2100 block = xfs_btree_get_block(cur, level, &bp); in __xfs_btree_updkeys()
2103 error = xfs_btree_check_block(cur, block, level, bp); in __xfs_btree_updkeys()
2108 nlkey = xfs_btree_key_addr(cur, ptr, block); in __xfs_btree_updkeys()
2109 nhkey = xfs_btree_high_key_addr(cur, ptr, block); in __xfs_btree_updkeys()
2118 xfs_btree_get_node_keys(cur, block, lkey); in __xfs_btree_updkeys()
2131 struct xfs_btree_block *block; in xfs_btree_updkeys_force() local
2133 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_updkeys_force()
2134 return __xfs_btree_updkeys(cur, level, block, bp, true); in xfs_btree_updkeys_force()
2145 struct xfs_btree_block *block; in xfs_btree_update_keys() local
2153 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_update_keys()
2155 return __xfs_btree_updkeys(cur, level, block, bp, false); in xfs_btree_update_keys()
2161 * at the first entry in the block. in xfs_btree_update_keys()
2163 xfs_btree_get_keys(cur, block, &key); in xfs_btree_update_keys()
2168 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_update_keys()
2170 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_update_keys()
2175 kp = xfs_btree_key_addr(cur, ptr, block); in xfs_btree_update_keys()
2193 struct xfs_btree_block *block; in xfs_btree_update() local
2199 /* Pick up the current block. */ in xfs_btree_update()
2200 block = xfs_btree_get_block(cur, 0, &bp); in xfs_btree_update()
2203 error = xfs_btree_check_block(cur, block, 0, bp); in xfs_btree_update()
2209 rp = xfs_btree_rec_addr(cur, ptr, block); in xfs_btree_update()
2219 if (xfs_btree_is_lastrec(cur, block, 0)) { in xfs_btree_update()
2220 cur->bc_ops->update_lastrec(cur, block, rec, in xfs_btree_update()
2248 struct xfs_btree_block *left; /* left btree block */ in xfs_btree_lshift()
2251 struct xfs_btree_block *right; /* right btree block */ in xfs_btree_lshift()
2265 /* Set up variables for this block as "right". */ in xfs_btree_lshift()
2310 * If non-leaf, copy a key and a ptr to the left block. in xfs_btree_lshift()
2311 * Log the changes to the left block. in xfs_btree_lshift()
2387 * block on the left. in xfs_btree_lshift()
2403 /* Update the parent high keys of the left block, if needed. */ in xfs_btree_lshift()
2411 /* Update the parent keys of the right block. */ in xfs_btree_lshift()
2445 struct xfs_btree_block *left; /* left btree block */ in xfs_btree_rshift()
2447 struct xfs_btree_block *right; /* right btree block */ in xfs_btree_rshift()
2449 union xfs_btree_ptr rptr; /* right block pointer */ in xfs_btree_rshift()
2460 /* Set up variables for this block as "left". */ in xfs_btree_rshift()
2496 * Make a hole at the start of the right neighbor block, then in xfs_btree_rshift()
2497 * copy the last left block entry to the hole. in xfs_btree_rshift()
2558 * block on the right. in xfs_btree_rshift()
2573 /* Update the parent high keys of the left block, if needed. */ in xfs_btree_rshift()
2580 /* Update the parent keys of the right block. */ in xfs_btree_rshift()
2603 * Split cur/level block in half.
2604 * Return new block number and the key to its first
2616 union xfs_btree_ptr lptr; /* left sibling block ptr */ in __xfs_btree_split()
2618 struct xfs_btree_block *left; /* left btree block */ in __xfs_btree_split()
2619 union xfs_btree_ptr rptr; /* right sibling block ptr */ in __xfs_btree_split()
2621 struct xfs_btree_block *right; /* right btree block */ in __xfs_btree_split()
2624 struct xfs_btree_block *rrblock; /* right-right btree block */ in __xfs_btree_split()
2633 /* Set up left block (current one). */ in __xfs_btree_split()
2644 /* Allocate the new block. If we can't do it, we're toast. Give up. */ in __xfs_btree_split()
2652 /* Set up the new block as "right". */ in __xfs_btree_split()
2657 /* Fill in the btree header for the new right block. */ in __xfs_btree_split()
2661 * Split the entries between the old and the new block evenly. in __xfs_btree_split()
2663 * each new block will have the same number of entries. in __xfs_btree_split()
2679 * Copy btree block entries from the left block over to the in __xfs_btree_split()
2680 * new block, the right. Update the right block and log the in __xfs_btree_split()
2701 /* Copy the keys & pointers to the new block. */ in __xfs_btree_split()
2708 /* Stash the keys of the new block for later insertion. */ in __xfs_btree_split()
2718 /* Copy records to the new block. */ in __xfs_btree_split()
2722 /* Stash the keys of the new block for later insertion. */ in __xfs_btree_split()
2727 * Find the left block number by looking in the buffer. in __xfs_btree_split()
2739 * If there's a block to the new block's right, make that block in __xfs_btree_split()
2751 /* Update the parent high keys of the left block, if needed. */ in __xfs_btree_split()
2759 * If the cursor is really in the right block, move it there. in __xfs_btree_split()
2769 * the right block, no matter where this cursor was. in __xfs_btree_split()
2816 * temporarily to ensure that we don't block waiting for memory reclaim in xfs_btree_split_worker()
2876 * Copy the old inode root contents into a real block and make the
2886 struct xfs_btree_block *block; /* btree block */ in xfs_btree_new_iroot() local
2887 struct xfs_btree_block *cblock; /* child btree block */ in xfs_btree_new_iroot()
2891 union xfs_btree_ptr *pp; /* pointer to block addr */ in xfs_btree_new_iroot()
2892 union xfs_btree_ptr nptr; /* new block addr */ in xfs_btree_new_iroot()
2903 block = xfs_btree_get_iroot(cur); in xfs_btree_new_iroot()
2904 pp = xfs_btree_ptr_addr(cur, 1, block); in xfs_btree_new_iroot()
2906 /* Allocate the new block. If we can't do it, we're toast. Give up. */ in xfs_btree_new_iroot()
2915 /* Copy the root into a real block. */ in xfs_btree_new_iroot()
2924 memcpy(cblock, block, xfs_btree_block_len(cur)); in xfs_btree_new_iroot()
2933 be16_add_cpu(&block->bb_level, 1); in xfs_btree_new_iroot()
2934 xfs_btree_set_numrecs(block, 1); in xfs_btree_new_iroot()
2938 kp = xfs_btree_key_addr(cur, 1, block); in xfs_btree_new_iroot()
2980 * Allocate a new root block, fill it in.
2987 struct xfs_btree_block *block; /* one half of the old root block */ in xfs_btree_new_root() local
2988 struct xfs_buf *bp; /* buffer containing block */ in xfs_btree_new_root()
2991 struct xfs_btree_block *left; /* left btree block */ in xfs_btree_new_root()
2993 struct xfs_btree_block *new; /* new (root) btree block */ in xfs_btree_new_root()
2996 struct xfs_btree_block *right; /* right btree block */ in xfs_btree_new_root()
3005 /* Allocate the new block. If we can't do it, we're toast. Give up. */ in xfs_btree_new_root()
3013 /* Set up the new block. */ in xfs_btree_new_root()
3023 * and the new block generated when it was split. We don't know which in xfs_btree_new_root()
3027 block = xfs_btree_get_block(cur, cur->bc_nlevels - 1, &bp); in xfs_btree_new_root()
3030 error = xfs_btree_check_block(cur, block, cur->bc_nlevels - 1, bp); in xfs_btree_new_root()
3035 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB); in xfs_btree_new_root()
3037 /* Our block is left, pick up the right block. */ in xfs_btree_new_root()
3040 left = block; in xfs_btree_new_root()
3047 /* Our block is right, pick up the left block. */ in xfs_btree_new_root()
3050 right = block; in xfs_btree_new_root()
3059 /* Fill in the new block's btree header and log it. */ in xfs_btree_new_root()
3068 * Get the keys for the left block's keys and put them directly in xfs_btree_new_root()
3069 * in the parent block. Do the same for the right block. in xfs_btree_new_root()
3077 * Get the keys for the left block's records and put them in xfs_btree_new_root()
3078 * directly in the parent block. Do the same for the right in xfs_btree_new_root()
3079 * block. in xfs_btree_new_root()
3112 int numrecs,/* # of recs in block */ in xfs_btree_make_block_unfull()
3117 union xfs_btree_key *key, /* key of new block */ in xfs_btree_make_block_unfull()
3127 /* A root block that can be made bigger. */ in xfs_btree_make_block_unfull()
3131 /* A root block that needs replacing */ in xfs_btree_make_block_unfull()
3160 * Next, try splitting the current block in half. in xfs_btree_make_block_unfull()
3163 * could be in a different block now. in xfs_btree_make_block_unfull()
3182 union xfs_btree_ptr *ptrp, /* i/o: block number inserted */ in xfs_btree_insrec()
3184 union xfs_btree_key *key, /* i/o: block key for ptrp */ in xfs_btree_insrec()
3188 struct xfs_btree_block *block; /* btree block */ in xfs_btree_insrec() local
3189 struct xfs_buf *bp; /* buffer for block */ in xfs_btree_insrec()
3190 union xfs_btree_ptr nptr; /* new block ptr */ in xfs_btree_insrec()
3192 union xfs_btree_key nkey; /* new block key */ in xfs_btree_insrec()
3206 * root level, allocate a new root block and we're done. in xfs_btree_insrec()
3227 /* Get pointers to the btree buffer and block. */ in xfs_btree_insrec()
3228 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_insrec()
3230 numrecs = xfs_btree_get_numrecs(block); in xfs_btree_insrec()
3233 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_insrec()
3241 xfs_btree_rec_addr(cur, ptr, block))); in xfs_btree_insrec()
3244 xfs_btree_key_addr(cur, ptr, block))); in xfs_btree_insrec()
3250 * If the block is full, we can't insert the new entry until we in xfs_btree_insrec()
3251 * make the block un-full. in xfs_btree_insrec()
3262 * The current block may have changed if the block was in xfs_btree_insrec()
3265 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()
3275 * At this point we know there's room for our new entry in the block in xfs_btree_insrec()
3285 kp = xfs_btree_key_addr(cur, ptr, block); in xfs_btree_insrec()
3286 pp = xfs_btree_ptr_addr(cur, ptr, block); in xfs_btree_insrec()
3305 xfs_btree_set_numrecs(block, numrecs); in xfs_btree_insrec()
3311 xfs_btree_key_addr(cur, ptr + 1, block))); in xfs_btree_insrec()
3318 rp = xfs_btree_rec_addr(cur, ptr, block); in xfs_btree_insrec()
3324 xfs_btree_set_numrecs(block, ++numrecs); in xfs_btree_insrec()
3329 xfs_btree_rec_addr(cur, ptr + 1, block))); in xfs_btree_insrec()
3338 * If we just inserted into a new tree block, we have to in xfs_btree_insrec()
3341 * Otherwise we're just updating an existing block (having shoved in xfs_btree_insrec()
3342 * some records into the new tree block), so use the regular key in xfs_btree_insrec()
3346 xfs_btree_get_keys(cur, block, lkey); in xfs_btree_insrec()
3357 if (xfs_btree_is_lastrec(cur, block, level)) { in xfs_btree_insrec()
3358 cur->bc_ops->update_lastrec(cur, block, rec, in xfs_btree_insrec()
3363 * Return the new block number, if any. in xfs_btree_insrec()
3394 union xfs_btree_ptr nptr; /* new block number (split result) */ in xfs_btree_insert()
3397 union xfs_btree_key bkey; /* key of block to insert */ in xfs_btree_insert()
3414 * Stop when we don't get a split block, that must mean that in xfs_btree_insert()
3463 * Try to merge a non-leaf block back into the inode root.
3466 * killing the old root block. But because we can't just delete the
3467 * inode we have to copy the single block it was pointing to into the
3477 struct xfs_btree_block *block; in xfs_btree_kill_iroot() local
3497 * Don't deal with the root block needs to be a leaf case. in xfs_btree_kill_iroot()
3507 block = xfs_btree_get_iroot(cur); in xfs_btree_kill_iroot()
3508 if (xfs_btree_get_numrecs(block) != 1) in xfs_btree_kill_iroot()
3525 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB); in xfs_btree_kill_iroot()
3527 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); in xfs_btree_kill_iroot()
3535 block = ifp->if_broot; in xfs_btree_kill_iroot()
3538 be16_add_cpu(&block->bb_numrecs, index); in xfs_btree_kill_iroot()
3539 ASSERT(block->bb_numrecs == cblock->bb_numrecs); in xfs_btree_kill_iroot()
3541 kp = xfs_btree_key_addr(cur, 1, block); in xfs_btree_kill_iroot()
3545 pp = xfs_btree_ptr_addr(cur, 1, block); in xfs_btree_kill_iroot()
3561 be16_add_cpu(&block->bb_level, -1); in xfs_btree_kill_iroot()
3622 * Remove the record from its block then rebalance the tree.
3631 struct xfs_btree_block *block; /* btree block */ in xfs_btree_delrec() local
3632 union xfs_btree_ptr cptr; /* current block ptr */ in xfs_btree_delrec()
3633 struct xfs_buf *bp; /* buffer for block */ in xfs_btree_delrec()
3636 union xfs_btree_ptr lptr; /* left sibling block ptr */ in xfs_btree_delrec()
3638 struct xfs_btree_block *left; /* left btree block */ in xfs_btree_delrec()
3641 union xfs_btree_ptr rptr; /* right sibling block ptr */ in xfs_btree_delrec()
3643 struct xfs_btree_block *right; /* right btree block */ in xfs_btree_delrec()
3644 struct xfs_btree_block *rrblock; /* right-right btree block */ in xfs_btree_delrec()
3659 /* Get the buffer & block containing the record or key/ptr. */ in xfs_btree_delrec()
3660 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_delrec()
3661 numrecs = xfs_btree_get_numrecs(block); in xfs_btree_delrec()
3664 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_delrec()
3669 /* Fail if we're off the end of the block. */ in xfs_btree_delrec()
3684 lkp = xfs_btree_key_addr(cur, ptr + 1, block); in xfs_btree_delrec()
3685 lpp = xfs_btree_ptr_addr(cur, ptr + 1, block); in xfs_btree_delrec()
3703 xfs_btree_rec_addr(cur, ptr + 1, block), in xfs_btree_delrec()
3710 * Decrement and log the number of entries in the block. in xfs_btree_delrec()
3712 xfs_btree_set_numrecs(block, --numrecs); in xfs_btree_delrec()
3719 if (xfs_btree_is_lastrec(cur, block, level)) { in xfs_btree_delrec()
3720 cur->bc_ops->update_lastrec(cur, block, NULL, in xfs_btree_delrec()
3725 * We're at the root level. First, shrink the root block in-memory. in xfs_btree_delrec()
3753 * pp is still set to the first pointer in the block. in xfs_btree_delrec()
3756 pp = xfs_btree_ptr_addr(cur, 1, block); in xfs_btree_delrec()
3770 * If we deleted the leftmost entry in the block, update the in xfs_btree_delrec()
3780 * If the number of records remaining in the block is at least in xfs_btree_delrec()
3795 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB); in xfs_btree_delrec()
3796 xfs_btree_get_sibling(cur, block, &lptr, XFS_BB_LEFTSIB); in xfs_btree_delrec()
3833 * Move the temp cursor to the last entry in the next block. in xfs_btree_delrec()
3856 /* Grab a pointer to the block. */ in xfs_btree_delrec()
3863 /* Grab the current block number, for future use. */ in xfs_btree_delrec()
3867 * If right block is full enough so that removing one entry in xfs_btree_delrec()
3877 ASSERT(xfs_btree_get_numrecs(block) >= in xfs_btree_delrec()
3893 * to our block again (last record). in xfs_btree_delrec()
3920 * previous block. in xfs_btree_delrec()
3937 /* Grab a pointer to the block. */ in xfs_btree_delrec()
3944 /* Grab the current block number, for future use. */ in xfs_btree_delrec()
3948 * If left block is full enough so that removing one entry in xfs_btree_delrec()
3958 ASSERT(xfs_btree_get_numrecs(block) >= in xfs_btree_delrec()
3985 lrecs + xfs_btree_get_numrecs(block) <= in xfs_btree_delrec()
3988 * Set "right" to be the starting block, in xfs_btree_delrec()
3992 right = block; in xfs_btree_delrec()
3999 * If that won't work, see if we can join with the right neighbor block. in xfs_btree_delrec()
4002 rrecs + xfs_btree_get_numrecs(block) <= in xfs_btree_delrec()
4005 * Set "left" to be the starting block, in xfs_btree_delrec()
4009 left = block; in xfs_btree_delrec()
4072 * Fix up the number of records and right block pointer in the in xfs_btree_delrec()
4073 * surviving block, and log it. in xfs_btree_delrec()
4080 /* If there is a right sibling, point it to the remaining block. */ in xfs_btree_delrec()
4090 /* Free the deleted block. */ in xfs_btree_delrec()
4097 * cursor to the left block, and fix up the index. in xfs_btree_delrec()
4127 * points to the old block so that the caller knows which record to in xfs_btree_delrec()
4209 struct xfs_btree_block *block; /* btree block */ in xfs_btree_get_rec() local
4217 block = xfs_btree_get_block(cur, 0, &bp); in xfs_btree_get_rec()
4220 error = xfs_btree_check_block(cur, block, 0, bp); in xfs_btree_get_rec()
4228 if (ptr > xfs_btree_get_numrecs(block) || ptr <= 0) { in xfs_btree_get_rec()
4236 *recp = xfs_btree_rec_addr(cur, ptr, block); in xfs_btree_get_rec()
4241 /* Visit a block in a btree. */
4249 struct xfs_btree_block *block; in xfs_btree_visit_block() local
4256 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_visit_block()
4258 /* process the block */ in xfs_btree_visit_block()
4263 /* now read rh sibling block for next iteration */ in xfs_btree_visit_block()
4264 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB); in xfs_btree_visit_block()
4268 return xfs_btree_lookup_get_block(cur, level, &rptr, &block); in xfs_btree_visit_block()
4272 /* Visit every block in a btree. */
4282 struct xfs_btree_block *block = NULL; in xfs_btree_visit_blocks() local
4289 /* grab the left hand block */ in xfs_btree_visit_blocks()
4290 error = xfs_btree_lookup_get_block(cur, level, &lptr, &block); in xfs_btree_visit_blocks()
4294 /* readahead the left most block for the next level down */ in xfs_btree_visit_blocks()
4298 ptr = xfs_btree_ptr_addr(cur, 1, block); in xfs_btree_visit_blocks()
4335 * as the amount of CPU work we have to do before moving to the next block is
4338 * For each btree block that we load, modify the owner appropriately, set the
4358 struct xfs_btree_block *block; in xfs_btree_block_change_owner() local
4362 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_block_change_owner()
4364 if (block->bb_u.l.bb_owner == cpu_to_be64(bbcoi->new_owner)) in xfs_btree_block_change_owner()
4366 block->bb_u.l.bb_owner = cpu_to_be64(bbcoi->new_owner); in xfs_btree_block_change_owner()
4368 if (block->bb_u.s.bb_owner == cpu_to_be32(bbcoi->new_owner)) in xfs_btree_block_change_owner()
4370 block->bb_u.s.bb_owner = cpu_to_be32(bbcoi->new_owner); in xfs_btree_block_change_owner()
4374 * If the block is a root block hosted in an inode, we might not have a in xfs_btree_block_change_owner()
4377 * block is formatted into the on-disk inode fork. We still change it, in xfs_btree_block_change_owner()
4413 /* Verify the v5 fields of a long-format btree block. */
4420 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_lblock_v5hdr_verify() local
4424 if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid)) in xfs_btree_lblock_v5hdr_verify()
4426 if (block->bb_u.l.bb_blkno != cpu_to_be64(xfs_buf_daddr(bp))) in xfs_btree_lblock_v5hdr_verify()
4429 be64_to_cpu(block->bb_u.l.bb_owner) != owner) in xfs_btree_lblock_v5hdr_verify()
4434 /* Verify a long-format btree block. */
4441 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_lblock_verify() local
4444 if (be16_to_cpu(block->bb_numrecs) > max_recs) in xfs_btree_lblock_verify()
4448 if (block->bb_u.l.bb_leftsib != cpu_to_be64(NULLFSBLOCK) && in xfs_btree_lblock_verify()
4449 !xfs_verify_fsbno(mp, be64_to_cpu(block->bb_u.l.bb_leftsib))) in xfs_btree_lblock_verify()
4451 if (block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK) && in xfs_btree_lblock_verify()
4452 !xfs_verify_fsbno(mp, be64_to_cpu(block->bb_u.l.bb_rightsib))) in xfs_btree_lblock_verify()
4460 * btree block
4462 * @bp: buffer containing the btree block
4469 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_sblock_v5hdr_verify() local
4474 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid)) in xfs_btree_sblock_v5hdr_verify()
4476 if (block->bb_u.s.bb_blkno != cpu_to_be64(xfs_buf_daddr(bp))) in xfs_btree_sblock_v5hdr_verify()
4478 if (pag && be32_to_cpu(block->bb_u.s.bb_owner) != pag->pag_agno) in xfs_btree_sblock_v5hdr_verify()
4484 * xfs_btree_sblock_verify() -- verify a short-format btree block
4486 * @bp: buffer containing the btree block
4495 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_sblock_verify() local
4499 if (be16_to_cpu(block->bb_numrecs) > max_recs) in xfs_btree_sblock_verify()
4504 if (block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK) && in xfs_btree_sblock_verify()
4505 !xfs_verify_agbno(mp, agno, be32_to_cpu(block->bb_u.s.bb_leftsib))) in xfs_btree_sblock_verify()
4507 if (block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK) && in xfs_btree_sblock_verify()
4508 !xfs_verify_agbno(mp, agno, be32_to_cpu(block->bb_u.s.bb_rightsib))) in xfs_btree_sblock_verify()
4625 * As an optimization, we stop scanning a block when we find a low key
4643 struct xfs_btree_block *block; in xfs_btree_overlapped_query_range() local
4654 error = xfs_btree_lookup_get_block(cur, level, &ptr, &block); in xfs_btree_overlapped_query_range()
4660 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_overlapped_query_range()
4667 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_overlapped_query_range()
4670 if (cur->bc_ptrs[level] > be16_to_cpu(block->bb_numrecs)) { in xfs_btree_overlapped_query_range()
4680 recp = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block); in xfs_btree_overlapped_query_range()
4708 lkp = xfs_btree_key_addr(cur, cur->bc_ptrs[level], block); in xfs_btree_overlapped_query_range()
4709 hkp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level], block); in xfs_btree_overlapped_query_range()
4710 pp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[level], block); in xfs_btree_overlapped_query_range()
4723 &block); in xfs_btree_overlapped_query_range()
4729 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_overlapped_query_range()
4745 * block, a subsequent non-error cursor deletion will not release in xfs_btree_overlapped_query_range()
4912 struct xfs_btree_block *block; in xfs_btree_has_more_records() local
4915 block = xfs_btree_get_block(cur, 0, &bp); in xfs_btree_has_more_records()
4917 /* There are still records in this block. */ in xfs_btree_has_more_records()
4918 if (cur->bc_ptrs[0] < xfs_btree_get_numrecs(block)) in xfs_btree_has_more_records()
4923 return block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK); in xfs_btree_has_more_records()
4925 return block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK); in xfs_btree_has_more_records()