Lines Matching full:block
119 * Check a long btree block header. Return the address of the failing check,
125 struct xfs_btree_block *block, in __xfs_btree_check_lblock() argument
136 if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid)) in __xfs_btree_check_lblock()
138 if (block->bb_u.l.bb_blkno != in __xfs_btree_check_lblock()
141 if (block->bb_u.l.bb_pad != cpu_to_be32(0)) in __xfs_btree_check_lblock()
145 if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(crc, btnum)) in __xfs_btree_check_lblock()
147 if (be16_to_cpu(block->bb_level) != level) in __xfs_btree_check_lblock()
149 if (be16_to_cpu(block->bb_numrecs) > in __xfs_btree_check_lblock()
157 block->bb_u.l.bb_leftsib); in __xfs_btree_check_lblock()
160 block->bb_u.l.bb_rightsib); in __xfs_btree_check_lblock()
164 /* Check a long btree block header. */
168 struct xfs_btree_block *block, in xfs_btree_check_lblock() argument
175 fa = __xfs_btree_check_lblock(cur, block, level, bp); in xfs_btree_check_lblock()
186 * Check a short btree block header. Return the address of the failing check,
192 struct xfs_btree_block *block, in __xfs_btree_check_sblock() argument
204 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid)) in __xfs_btree_check_sblock()
206 if (block->bb_u.s.bb_blkno != in __xfs_btree_check_sblock()
211 if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(crc, btnum)) in __xfs_btree_check_sblock()
213 if (be16_to_cpu(block->bb_level) != level) in __xfs_btree_check_sblock()
215 if (be16_to_cpu(block->bb_numrecs) > in __xfs_btree_check_sblock()
223 block->bb_u.s.bb_leftsib); in __xfs_btree_check_sblock()
226 block->bb_u.s.bb_rightsib); in __xfs_btree_check_sblock()
230 /* Check a short btree block header. */
234 struct xfs_btree_block *block, in xfs_btree_check_sblock() argument
241 fa = __xfs_btree_check_sblock(cur, block, level, bp); in xfs_btree_check_sblock()
252 * Debug routine: check that block header is ok.
257 struct xfs_btree_block *block, /* generic btree block pointer */ in xfs_btree_check_block() argument
258 int level, /* level of the btree block */ in xfs_btree_check_block()
259 struct xfs_buf *bp) /* buffer containing block, if any */ in xfs_btree_check_block()
262 return xfs_btree_check_lblock(cur, block, level, bp); in xfs_btree_check_block()
264 return xfs_btree_check_sblock(cur, block, level, bp); in xfs_btree_check_block()
331 * Calculate CRC on the whole btree block and stuff it into the
342 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_lblock_calc_crc() local
348 block->bb_u.l.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn); in xfs_btree_lblock_calc_crc()
356 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_lblock_verify_crc() local
360 if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.l.bb_lsn))) in xfs_btree_lblock_verify_crc()
369 * Calculate CRC on the whole btree block and stuff it into the
380 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_sblock_calc_crc() local
386 block->bb_u.s.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn); in xfs_btree_sblock_calc_crc()
394 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_sblock_verify_crc() local
398 if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.s.bb_lsn))) in xfs_btree_sblock_verify_crc()
469 struct xfs_buf *bp; /* btree block's buffer pointer */ in xfs_btree_dup_cursor()
471 int i; /* level number of btree block */ in xfs_btree_dup_cursor()
514 * XFS btree block layout and addressing:
519 * the values. A non-leaf block also starts with the same header, and
532 * and comes in different versions for short (32bit) and long (64bit) block
534 * and opaque to the btree core. The block pointers are simple disk endian
538 * into a btree block (xfs_btree_*_offset) or return a pointer to the given
540 * inside the btree block is done using indices starting at one, not zero!
546 * indexing the lowest key available in the block(s) below (the same behavior
548 * available in the block(s) below. Because records are /not/ sorted by the
549 * highest key, all leaf block updates require us to compute the highest key
576 * Now say we want to map block (B+D) into file A at offset (C+D). Ideally,
588 * Return size of the btree block header for this btree instance.
603 * Return size of btree block pointers for this btree instance.
612 * Calculate offset of the n-th record in a btree block.
624 * Calculate offset of the n-th key in a btree block.
636 * Calculate offset of the n-th high key in a btree block.
648 * Calculate offset of the n-th block pointer in a btree block.
662 * Return a pointer to the n-th record in the btree block.
668 struct xfs_btree_block *block) in xfs_btree_rec_addr() argument
671 ((char *)block + xfs_btree_rec_offset(cur, n)); in xfs_btree_rec_addr()
675 * Return a pointer to the n-th key in the btree block.
681 struct xfs_btree_block *block) in xfs_btree_key_addr() argument
684 ((char *)block + xfs_btree_key_offset(cur, n)); in xfs_btree_key_addr()
688 * Return a pointer to the n-th high key in the btree block.
694 struct xfs_btree_block *block) in xfs_btree_high_key_addr() argument
697 ((char *)block + xfs_btree_high_key_offset(cur, n)); in xfs_btree_high_key_addr()
701 * Return a pointer to the n-th block pointer in the btree block.
707 struct xfs_btree_block *block) in xfs_btree_ptr_addr() argument
709 int level = xfs_btree_get_level(block); in xfs_btree_ptr_addr()
711 ASSERT(block->bb_level != 0); in xfs_btree_ptr_addr()
714 ((char *)block + xfs_btree_ptr_offset(cur, n, level)); in xfs_btree_ptr_addr()
729 * Get the root block which is stored in the inode.
744 * Retrieve the block pointer from the cursor at the given level.
747 struct xfs_btree_block * /* generic btree block pointer */
751 struct xfs_buf **bpp) /* buffer containing the block */ in xfs_btree_get_block()
772 struct xfs_btree_block *block; /* generic btree block pointer */ in xfs_btree_firstrec() local
773 struct xfs_buf *bp; /* buffer containing block */ in xfs_btree_firstrec()
776 * Get the block pointer for this level. in xfs_btree_firstrec()
778 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_firstrec()
779 if (xfs_btree_check_block(cur, block, level, bp)) in xfs_btree_firstrec()
784 if (!block->bb_numrecs) in xfs_btree_firstrec()
794 * Change the cursor to point to the last record in the current block
802 struct xfs_btree_block *block; /* generic btree block pointer */ in xfs_btree_lastrec() local
803 struct xfs_buf *bp; /* buffer containing block */ in xfs_btree_lastrec()
806 * Get the block pointer for this level. in xfs_btree_lastrec()
808 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_lastrec()
809 if (xfs_btree_check_block(cur, block, level, bp)) in xfs_btree_lastrec()
814 if (!block->bb_numrecs) in xfs_btree_lastrec()
819 cur->bc_levels[level].ptr = be16_to_cpu(block->bb_numrecs); in xfs_btree_lastrec()
860 * Get a buffer for the block, return it read in.
867 xfs_fsblock_t fsbno, /* file system block number */ in xfs_btree_read_bufl()
873 xfs_daddr_t d; /* real disk block address */ in xfs_btree_read_bufl()
890 * Read-ahead the block, don't wait for it, don't return a buffer.
897 xfs_fsblock_t fsbno, /* file system block number */ in xfs_btree_reada_bufl()
909 * Read-ahead the block, don't wait for it, don't return a buffer.
917 xfs_agblock_t agbno, /* allocation group block number */ in xfs_btree_reada_bufs()
933 struct xfs_btree_block *block) in xfs_btree_readahead_lblock() argument
936 xfs_fsblock_t left = be64_to_cpu(block->bb_u.l.bb_leftsib); in xfs_btree_readahead_lblock()
937 xfs_fsblock_t right = be64_to_cpu(block->bb_u.l.bb_rightsib); in xfs_btree_readahead_lblock()
958 struct xfs_btree_block *block) in xfs_btree_readahead_sblock() argument
961 xfs_agblock_t left = be32_to_cpu(block->bb_u.s.bb_leftsib); in xfs_btree_readahead_sblock()
962 xfs_agblock_t right = be32_to_cpu(block->bb_u.s.bb_rightsib); in xfs_btree_readahead_sblock()
990 struct xfs_btree_block *block; in xfs_btree_readahead() local
1004 block = XFS_BUF_TO_BLOCK(cur->bc_levels[lev].bp); in xfs_btree_readahead()
1007 return xfs_btree_readahead_lblock(cur, lr, block); in xfs_btree_readahead()
1008 return xfs_btree_readahead_sblock(cur, lr, block); in xfs_btree_readahead()
1067 struct xfs_btree_block *b; /* btree block */ in xfs_btree_setbuf()
1116 struct xfs_btree_block *block, in xfs_btree_get_sibling() argument
1124 ptr->l = block->bb_u.l.bb_rightsib; in xfs_btree_get_sibling()
1126 ptr->l = block->bb_u.l.bb_leftsib; in xfs_btree_get_sibling()
1129 ptr->s = block->bb_u.s.bb_rightsib; in xfs_btree_get_sibling()
1131 ptr->s = block->bb_u.s.bb_leftsib; in xfs_btree_get_sibling()
1138 struct xfs_btree_block *block, in xfs_btree_set_sibling() argument
1146 block->bb_u.l.bb_rightsib = ptr->l; in xfs_btree_set_sibling()
1148 block->bb_u.l.bb_leftsib = ptr->l; in xfs_btree_set_sibling()
1151 block->bb_u.s.bb_rightsib = ptr->s; in xfs_btree_set_sibling()
1153 block->bb_u.s.bb_leftsib = ptr->s; in xfs_btree_set_sibling()
1246 struct xfs_btree_block *block, in xfs_btree_is_lastrec() argument
1256 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); in xfs_btree_is_lastrec()
1309 struct xfs_btree_block **block, in xfs_btree_get_buf_block() argument
1325 *block = XFS_BUF_TO_BLOCK(*bpp); in xfs_btree_get_buf_block()
1331 * the block pointer within the buffer.
1338 struct xfs_btree_block **block, in xfs_btree_read_buf_block() argument
1358 *block = XFS_BUF_TO_BLOCK(*bpp); in xfs_btree_read_buf_block()
1363 * Copy keys from one btree block to another.
1377 * Copy records from one btree block to another.
1391 * Copy block pointers from one btree block to another.
1405 * Shift keys one index left/right inside a single btree block.
1424 * Shift records one index left/right inside a single btree block.
1443 * Shift block pointers one index left/right inside a single btree block.
1462 * Log key values from the btree block.
1484 * Log record values from the btree block.
1502 * Log block pointer fields from a btree block (nonleaf).
1507 struct xfs_buf *bp, /* buffer containing btree block */ in xfs_btree_log_ptrs()
1513 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_log_ptrs() local
1514 int level = xfs_btree_get_level(block); in xfs_btree_log_ptrs()
1528 * Log fields from a btree block header.
1533 struct xfs_buf *bp, /* buffer containing btree block */ in xfs_btree_log_block()
1572 * block but instead recreate it during log in xfs_btree_log_block()
1605 struct xfs_btree_block *block; in xfs_btree_increment() local
1616 /* Get a pointer to the btree block. */ in xfs_btree_increment()
1617 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_increment()
1620 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_increment()
1625 /* We're done if we remain in the block after the increment. */ in xfs_btree_increment()
1626 if (++cur->bc_levels[level].ptr <= xfs_btree_get_numrecs(block)) in xfs_btree_increment()
1630 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); in xfs_btree_increment()
1638 * Stop when we don't go off the right edge of a block. in xfs_btree_increment()
1641 block = xfs_btree_get_block(cur, lev, &bp); in xfs_btree_increment()
1644 error = xfs_btree_check_block(cur, block, lev, bp); in xfs_btree_increment()
1649 if (++cur->bc_levels[lev].ptr <= xfs_btree_get_numrecs(block)) in xfs_btree_increment()
1652 /* Read-ahead the right block for the next loop. */ in xfs_btree_increment()
1673 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) { in xfs_btree_increment()
1676 ptrp = xfs_btree_ptr_addr(cur, cur->bc_levels[lev].ptr, block); in xfs_btree_increment()
1678 error = xfs_btree_read_buf_block(cur, ptrp, 0, &block, &bp); in xfs_btree_increment()
1707 struct xfs_btree_block *block; in xfs_btree_decrement() local
1718 /* We're done if we remain in the block after the decrement. */ in xfs_btree_decrement()
1722 /* Get a pointer to the btree block. */ in xfs_btree_decrement()
1723 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_decrement()
1726 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_decrement()
1732 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB); in xfs_btree_decrement()
1740 * Stop when we don't go off the left edge of a block. in xfs_btree_decrement()
1745 /* Read-ahead the left block for the next loop. */ in xfs_btree_decrement()
1766 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) { in xfs_btree_decrement()
1769 ptrp = xfs_btree_ptr_addr(cur, cur->bc_levels[lev].ptr, block); in xfs_btree_decrement()
1771 error = xfs_btree_read_buf_block(cur, ptrp, 0, &block, &bp); in xfs_btree_decrement()
1775 cur->bc_levels[lev].ptr = xfs_btree_get_numrecs(block); in xfs_btree_decrement()
1793 const union xfs_btree_ptr *pp, /* ptr to btree block */ in xfs_btree_lookup_get_block()
1794 struct xfs_btree_block **blkp) /* return btree block */ in xfs_btree_lookup_get_block()
1796 struct xfs_buf *bp; /* buffer pointer for btree block */ in xfs_btree_lookup_get_block()
1800 /* special case the root block if in an inode */ in xfs_btree_lookup_get_block()
1862 struct xfs_btree_block *block, in xfs_lookup_get_search_key() argument
1867 xfs_btree_rec_addr(cur, keyno, block)); in xfs_lookup_get_search_key()
1871 return xfs_btree_key_addr(cur, keyno, block); in xfs_lookup_get_search_key()
1884 struct xfs_btree_block *block; /* current btree block */ in xfs_btree_lookup() local
1889 union xfs_btree_ptr *pp; /* ptr to btree block */ in xfs_btree_lookup()
1890 union xfs_btree_ptr ptr; /* ptr to btree block */ in xfs_btree_lookup()
1898 block = NULL; in xfs_btree_lookup()
1908 * on the lookup record, then follow the corresponding block in xfs_btree_lookup()
1912 /* Get the block we need to do the lookup on. */ in xfs_btree_lookup()
1913 error = xfs_btree_lookup_get_block(cur, level, pp, &block); in xfs_btree_lookup()
1920 * know we need to use the first entry in this block. in xfs_btree_lookup()
1924 /* Otherwise search this block. Do a binary search. */ in xfs_btree_lookup()
1931 high = xfs_btree_get_numrecs(block); in xfs_btree_lookup()
1933 /* Block is empty, must be an empty leaf. */ in xfs_btree_lookup()
1937 cur->bc_mp, block, in xfs_btree_lookup()
1938 sizeof(*block)); in xfs_btree_lookup()
1947 /* Binary search the block. */ in xfs_btree_lookup()
1959 keyno, block, &key); in xfs_btree_lookup()
1979 * by getting the block number and filling in the cursor. in xfs_btree_lookup()
1988 pp = xfs_btree_ptr_addr(cur, keyno, block); in xfs_btree_lookup()
2002 * If ge search and we went off the end of the block, but it's in xfs_btree_lookup()
2003 * not the last block, we're in the wrong block. in xfs_btree_lookup()
2005 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); in xfs_btree_lookup()
2007 keyno > xfs_btree_get_numrecs(block) && in xfs_btree_lookup()
2025 if (keyno == 0 || keyno > xfs_btree_get_numrecs(block)) in xfs_btree_lookup()
2048 /* Determine the low (and high if overlapped) keys of a leaf block */
2052 struct xfs_btree_block *block, in xfs_btree_get_leaf_keys() argument
2061 rec = xfs_btree_rec_addr(cur, 1, block); in xfs_btree_get_leaf_keys()
2067 for (n = 2; n <= xfs_btree_get_numrecs(block); n++) { in xfs_btree_get_leaf_keys()
2068 rec = xfs_btree_rec_addr(cur, n, block); in xfs_btree_get_leaf_keys()
2079 /* Determine the low (and high if overlapped) keys of a node block */
2083 struct xfs_btree_block *block, in xfs_btree_get_node_keys() argument
2092 memcpy(key, xfs_btree_key_addr(cur, 1, block), in xfs_btree_get_node_keys()
2095 max_hkey = xfs_btree_high_key_addr(cur, 1, block); in xfs_btree_get_node_keys()
2096 for (n = 2; n <= xfs_btree_get_numrecs(block); n++) { in xfs_btree_get_node_keys()
2097 hkey = xfs_btree_high_key_addr(cur, n, block); in xfs_btree_get_node_keys()
2105 memcpy(key, xfs_btree_key_addr(cur, 1, block), in xfs_btree_get_node_keys()
2110 /* Derive the keys for any btree block. */
2114 struct xfs_btree_block *block, in xfs_btree_get_keys() argument
2117 if (be16_to_cpu(block->bb_level) == 0) in xfs_btree_get_keys()
2118 xfs_btree_get_leaf_keys(cur, block, key); in xfs_btree_get_keys()
2120 xfs_btree_get_node_keys(cur, block, key); in xfs_btree_get_keys()
2124 * Decide if we need to update the parent keys of a btree block. For
2128 * in the block.
2147 struct xfs_btree_block *block, in __xfs_btree_updkeys() argument
2169 xfs_btree_get_keys(cur, block, lkey); in __xfs_btree_updkeys()
2174 block = xfs_btree_get_block(cur, level, &bp); in __xfs_btree_updkeys()
2177 error = xfs_btree_check_block(cur, block, level, bp); in __xfs_btree_updkeys()
2182 nlkey = xfs_btree_key_addr(cur, ptr, block); in __xfs_btree_updkeys()
2183 nhkey = xfs_btree_high_key_addr(cur, ptr, block); in __xfs_btree_updkeys()
2192 xfs_btree_get_node_keys(cur, block, lkey); in __xfs_btree_updkeys()
2205 struct xfs_btree_block *block; in xfs_btree_updkeys_force() local
2207 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_updkeys_force()
2208 return __xfs_btree_updkeys(cur, level, block, bp, true); in xfs_btree_updkeys_force()
2219 struct xfs_btree_block *block; in xfs_btree_update_keys() local
2227 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_update_keys()
2229 return __xfs_btree_updkeys(cur, level, block, bp, false); in xfs_btree_update_keys()
2235 * at the first entry in the block. in xfs_btree_update_keys()
2237 xfs_btree_get_keys(cur, block, &key); in xfs_btree_update_keys()
2242 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_update_keys()
2244 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_update_keys()
2249 kp = xfs_btree_key_addr(cur, ptr, block); in xfs_btree_update_keys()
2267 struct xfs_btree_block *block; in xfs_btree_update() local
2273 /* Pick up the current block. */ in xfs_btree_update()
2274 block = xfs_btree_get_block(cur, 0, &bp); in xfs_btree_update()
2277 error = xfs_btree_check_block(cur, block, 0, bp); in xfs_btree_update()
2283 rp = xfs_btree_rec_addr(cur, ptr, block); in xfs_btree_update()
2293 if (xfs_btree_is_lastrec(cur, block, 0)) { in xfs_btree_update()
2294 cur->bc_ops->update_lastrec(cur, block, rec, in xfs_btree_update()
2322 struct xfs_btree_block *left; /* left btree block */ in xfs_btree_lshift()
2325 struct xfs_btree_block *right; /* right btree block */ in xfs_btree_lshift()
2339 /* Set up variables for this block as "right". */ in xfs_btree_lshift()
2384 * If non-leaf, copy a key and a ptr to the left block. in xfs_btree_lshift()
2385 * Log the changes to the left block. in xfs_btree_lshift()
2461 * block on the left. in xfs_btree_lshift()
2477 /* Update the parent high keys of the left block, if needed. */ in xfs_btree_lshift()
2485 /* Update the parent keys of the right block. */ in xfs_btree_lshift()
2519 struct xfs_btree_block *left; /* left btree block */ in xfs_btree_rshift()
2521 struct xfs_btree_block *right; /* right btree block */ in xfs_btree_rshift()
2523 union xfs_btree_ptr rptr; /* right block pointer */ in xfs_btree_rshift()
2534 /* Set up variables for this block as "left". */ in xfs_btree_rshift()
2570 * Make a hole at the start of the right neighbor block, then in xfs_btree_rshift()
2571 * copy the last left block entry to the hole. in xfs_btree_rshift()
2632 * block on the right. in xfs_btree_rshift()
2647 /* Update the parent high keys of the left block, if needed. */ in xfs_btree_rshift()
2654 /* Update the parent keys of the right block. */ in xfs_btree_rshift()
2677 * Split cur/level block in half.
2678 * Return new block number and the key to its first
2690 union xfs_btree_ptr lptr; /* left sibling block ptr */ in __xfs_btree_split()
2692 struct xfs_btree_block *left; /* left btree block */ in __xfs_btree_split()
2693 union xfs_btree_ptr rptr; /* right sibling block ptr */ in __xfs_btree_split()
2695 struct xfs_btree_block *right; /* right btree block */ in __xfs_btree_split()
2698 struct xfs_btree_block *rrblock; /* right-right btree block */ in __xfs_btree_split()
2707 /* Set up left block (current one). */ in __xfs_btree_split()
2718 /* Allocate the new block. If we can't do it, we're toast. Give up. */ in __xfs_btree_split()
2726 /* Set up the new block as "right". */ in __xfs_btree_split()
2731 /* Fill in the btree header for the new right block. */ in __xfs_btree_split()
2735 * Split the entries between the old and the new block evenly. in __xfs_btree_split()
2737 * each new block will have the same number of entries. in __xfs_btree_split()
2753 * Copy btree block entries from the left block over to the in __xfs_btree_split()
2754 * new block, the right. Update the right block and log the in __xfs_btree_split()
2775 /* Copy the keys & pointers to the new block. */ in __xfs_btree_split()
2782 /* Stash the keys of the new block for later insertion. */ in __xfs_btree_split()
2792 /* Copy records to the new block. */ in __xfs_btree_split()
2796 /* Stash the keys of the new block for later insertion. */ in __xfs_btree_split()
2801 * Find the left block number by looking in the buffer. in __xfs_btree_split()
2813 * If there's a block to the new block's right, make that block in __xfs_btree_split()
2825 /* Update the parent high keys of the left block, if needed. */ in __xfs_btree_split()
2833 * If the cursor is really in the right block, move it there. in __xfs_btree_split()
2843 * the right block, no matter where this cursor was. in __xfs_btree_split()
2891 * temporarily to ensure that we don't block waiting for memory reclaim in xfs_btree_split_worker()
2920 * AGF <> worker queue deadlocks if the BMBT block allocation has to lock new
2968 * Copy the old inode root contents into a real block and make the
2978 struct xfs_btree_block *block; /* btree block */ in xfs_btree_new_iroot() local
2979 struct xfs_btree_block *cblock; /* child btree block */ in xfs_btree_new_iroot()
2983 union xfs_btree_ptr *pp; /* pointer to block addr */ in xfs_btree_new_iroot()
2984 union xfs_btree_ptr nptr; /* new block addr */ in xfs_btree_new_iroot()
2995 block = xfs_btree_get_iroot(cur); in xfs_btree_new_iroot()
2996 pp = xfs_btree_ptr_addr(cur, 1, block); in xfs_btree_new_iroot()
2998 /* Allocate the new block. If we can't do it, we're toast. Give up. */ in xfs_btree_new_iroot()
3007 /* Copy the root into a real block. */ in xfs_btree_new_iroot()
3016 memcpy(cblock, block, xfs_btree_block_len(cur)); in xfs_btree_new_iroot()
3025 be16_add_cpu(&block->bb_level, 1); in xfs_btree_new_iroot()
3026 xfs_btree_set_numrecs(block, 1); in xfs_btree_new_iroot()
3031 kp = xfs_btree_key_addr(cur, 1, block); in xfs_btree_new_iroot()
3073 * Allocate a new root block, fill it in.
3080 struct xfs_btree_block *block; /* one half of the old root block */ in xfs_btree_new_root() local
3081 struct xfs_buf *bp; /* buffer containing block */ in xfs_btree_new_root()
3084 struct xfs_btree_block *left; /* left btree block */ in xfs_btree_new_root()
3086 struct xfs_btree_block *new; /* new (root) btree block */ in xfs_btree_new_root()
3089 struct xfs_btree_block *right; /* right btree block */ in xfs_btree_new_root()
3098 /* Allocate the new block. If we can't do it, we're toast. Give up. */ in xfs_btree_new_root()
3106 /* Set up the new block. */ in xfs_btree_new_root()
3116 * and the new block generated when it was split. We don't know which in xfs_btree_new_root()
3120 block = xfs_btree_get_block(cur, cur->bc_nlevels - 1, &bp); in xfs_btree_new_root()
3123 error = xfs_btree_check_block(cur, block, cur->bc_nlevels - 1, bp); in xfs_btree_new_root()
3128 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB); in xfs_btree_new_root()
3130 /* Our block is left, pick up the right block. */ in xfs_btree_new_root()
3133 left = block; in xfs_btree_new_root()
3140 /* Our block is right, pick up the left block. */ in xfs_btree_new_root()
3143 right = block; in xfs_btree_new_root()
3152 /* Fill in the new block's btree header and log it. */ in xfs_btree_new_root()
3161 * Get the keys for the left block's keys and put them directly in xfs_btree_new_root()
3162 * in the parent block. Do the same for the right block. in xfs_btree_new_root()
3170 * Get the keys for the left block's records and put them in xfs_btree_new_root()
3171 * directly in the parent block. Do the same for the right in xfs_btree_new_root()
3172 * block. in xfs_btree_new_root()
3206 int numrecs,/* # of recs in block */ in xfs_btree_make_block_unfull()
3211 union xfs_btree_key *key, /* key of new block */ in xfs_btree_make_block_unfull()
3221 /* A root block that can be made bigger. */ in xfs_btree_make_block_unfull()
3225 /* A root block that needs replacing */ in xfs_btree_make_block_unfull()
3254 * Next, try splitting the current block in half. in xfs_btree_make_block_unfull()
3257 * could be in a different block now. in xfs_btree_make_block_unfull()
3276 union xfs_btree_ptr *ptrp, /* i/o: block number inserted */ in xfs_btree_insrec()
3278 union xfs_btree_key *key, /* i/o: block key for ptrp */ in xfs_btree_insrec()
3282 struct xfs_btree_block *block; /* btree block */ in xfs_btree_insrec() local
3283 struct xfs_buf *bp; /* buffer for block */ in xfs_btree_insrec()
3284 union xfs_btree_ptr nptr; /* new block ptr */ in xfs_btree_insrec()
3286 union xfs_btree_key nkey; /* new block key */ in xfs_btree_insrec()
3300 * root level, allocate a new root block and we're done. in xfs_btree_insrec()
3321 /* Get pointers to the btree buffer and block. */ in xfs_btree_insrec()
3322 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_insrec()
3324 numrecs = xfs_btree_get_numrecs(block); in xfs_btree_insrec()
3327 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_insrec()
3335 xfs_btree_rec_addr(cur, ptr, block))); in xfs_btree_insrec()
3338 xfs_btree_key_addr(cur, ptr, block))); in xfs_btree_insrec()
3344 * If the block is full, we can't insert the new entry until we in xfs_btree_insrec()
3345 * make the block un-full. in xfs_btree_insrec()
3356 * The current block may have changed if the block was in xfs_btree_insrec()
3359 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_insrec()
3360 numrecs = xfs_btree_get_numrecs(block); in xfs_btree_insrec()
3363 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_insrec()
3369 * At this point we know there's room for our new entry in the block in xfs_btree_insrec()
3379 kp = xfs_btree_key_addr(cur, ptr, block); in xfs_btree_insrec()
3380 pp = xfs_btree_ptr_addr(cur, ptr, block); in xfs_btree_insrec()
3399 xfs_btree_set_numrecs(block, numrecs); in xfs_btree_insrec()
3405 xfs_btree_key_addr(cur, ptr + 1, block))); in xfs_btree_insrec()
3412 rp = xfs_btree_rec_addr(cur, ptr, block); in xfs_btree_insrec()
3418 xfs_btree_set_numrecs(block, ++numrecs); in xfs_btree_insrec()
3423 xfs_btree_rec_addr(cur, ptr + 1, block))); in xfs_btree_insrec()
3432 * If we just inserted into a new tree block, we have to in xfs_btree_insrec()
3435 * Otherwise we're just updating an existing block (having shoved in xfs_btree_insrec()
3436 * some records into the new tree block), so use the regular key in xfs_btree_insrec()
3440 xfs_btree_get_keys(cur, block, lkey); in xfs_btree_insrec()
3451 if (xfs_btree_is_lastrec(cur, block, level)) { in xfs_btree_insrec()
3452 cur->bc_ops->update_lastrec(cur, block, rec, in xfs_btree_insrec()
3457 * Return the new block number, if any. in xfs_btree_insrec()
3490 union xfs_btree_ptr nptr; /* new block number (split result) */ in xfs_btree_insert()
3493 union xfs_btree_key bkey; /* key of block to insert */ in xfs_btree_insert()
3510 * Stop when we don't get a split block, that must mean that in xfs_btree_insert()
3559 * Try to merge a non-leaf block back into the inode root.
3562 * killing the old root block. But because we can't just delete the
3563 * inode we have to copy the single block it was pointing to into the
3573 struct xfs_btree_block *block; in xfs_btree_kill_iroot() local
3593 * Don't deal with the root block needs to be a leaf case. in xfs_btree_kill_iroot()
3603 block = xfs_btree_get_iroot(cur); in xfs_btree_kill_iroot()
3604 if (xfs_btree_get_numrecs(block) != 1) in xfs_btree_kill_iroot()
3621 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB); in xfs_btree_kill_iroot()
3623 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); in xfs_btree_kill_iroot()
3631 block = ifp->if_broot; in xfs_btree_kill_iroot()
3634 be16_add_cpu(&block->bb_numrecs, index); in xfs_btree_kill_iroot()
3635 ASSERT(block->bb_numrecs == cblock->bb_numrecs); in xfs_btree_kill_iroot()
3637 kp = xfs_btree_key_addr(cur, 1, block); in xfs_btree_kill_iroot()
3641 pp = xfs_btree_ptr_addr(cur, 1, block); in xfs_btree_kill_iroot()
3657 be16_add_cpu(&block->bb_level, -1); in xfs_btree_kill_iroot()
3718 * Remove the record from its block then rebalance the tree.
3727 struct xfs_btree_block *block; /* btree block */ in xfs_btree_delrec() local
3728 union xfs_btree_ptr cptr; /* current block ptr */ in xfs_btree_delrec()
3729 struct xfs_buf *bp; /* buffer for block */ in xfs_btree_delrec()
3732 union xfs_btree_ptr lptr; /* left sibling block ptr */ in xfs_btree_delrec()
3734 struct xfs_btree_block *left; /* left btree block */ in xfs_btree_delrec()
3737 union xfs_btree_ptr rptr; /* right sibling block ptr */ in xfs_btree_delrec()
3739 struct xfs_btree_block *right; /* right btree block */ in xfs_btree_delrec()
3740 struct xfs_btree_block *rrblock; /* right-right btree block */ in xfs_btree_delrec()
3755 /* Get the buffer & block containing the record or key/ptr. */ in xfs_btree_delrec()
3756 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_delrec()
3757 numrecs = xfs_btree_get_numrecs(block); in xfs_btree_delrec()
3760 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_delrec()
3765 /* Fail if we're off the end of the block. */ in xfs_btree_delrec()
3780 lkp = xfs_btree_key_addr(cur, ptr + 1, block); in xfs_btree_delrec()
3781 lpp = xfs_btree_ptr_addr(cur, ptr + 1, block); in xfs_btree_delrec()
3799 xfs_btree_rec_addr(cur, ptr + 1, block), in xfs_btree_delrec()
3806 * Decrement and log the number of entries in the block. in xfs_btree_delrec()
3808 xfs_btree_set_numrecs(block, --numrecs); in xfs_btree_delrec()
3815 if (xfs_btree_is_lastrec(cur, block, level)) { in xfs_btree_delrec()
3816 cur->bc_ops->update_lastrec(cur, block, NULL, in xfs_btree_delrec()
3821 * We're at the root level. First, shrink the root block in-memory. in xfs_btree_delrec()
3849 * pp is still set to the first pointer in the block. in xfs_btree_delrec()
3852 pp = xfs_btree_ptr_addr(cur, 1, block); in xfs_btree_delrec()
3866 * If we deleted the leftmost entry in the block, update the in xfs_btree_delrec()
3876 * If the number of records remaining in the block is at least in xfs_btree_delrec()
3891 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB); in xfs_btree_delrec()
3892 xfs_btree_get_sibling(cur, block, &lptr, XFS_BB_LEFTSIB); in xfs_btree_delrec()
3929 * Move the temp cursor to the last entry in the next block. in xfs_btree_delrec()
3952 /* Grab a pointer to the block. */ in xfs_btree_delrec()
3959 /* Grab the current block number, for future use. */ in xfs_btree_delrec()
3963 * If right block is full enough so that removing one entry in xfs_btree_delrec()
3973 ASSERT(xfs_btree_get_numrecs(block) >= in xfs_btree_delrec()
3989 * to our block again (last record). in xfs_btree_delrec()
4016 * previous block. in xfs_btree_delrec()
4033 /* Grab a pointer to the block. */ in xfs_btree_delrec()
4040 /* Grab the current block number, for future use. */ in xfs_btree_delrec()
4044 * If left block is full enough so that removing one entry in xfs_btree_delrec()
4054 ASSERT(xfs_btree_get_numrecs(block) >= in xfs_btree_delrec()
4081 lrecs + xfs_btree_get_numrecs(block) <= in xfs_btree_delrec()
4084 * Set "right" to be the starting block, in xfs_btree_delrec()
4088 right = block; in xfs_btree_delrec()
4095 * If that won't work, see if we can join with the right neighbor block. in xfs_btree_delrec()
4098 rrecs + xfs_btree_get_numrecs(block) <= in xfs_btree_delrec()
4101 * Set "left" to be the starting block, in xfs_btree_delrec()
4105 left = block; in xfs_btree_delrec()
4168 * Fix up the number of records and right block pointer in the in xfs_btree_delrec()
4169 * surviving block, and log it. in xfs_btree_delrec()
4176 /* If there is a right sibling, point it to the remaining block. */ in xfs_btree_delrec()
4186 /* Free the deleted block. */ in xfs_btree_delrec()
4193 * cursor to the left block, and fix up the index. in xfs_btree_delrec()
4223 * bc_levels[level + 1].ptr points to the old block so that the caller in xfs_btree_delrec()
4305 struct xfs_btree_block *block; /* btree block */ in xfs_btree_get_rec() local
4313 block = xfs_btree_get_block(cur, 0, &bp); in xfs_btree_get_rec()
4316 error = xfs_btree_check_block(cur, block, 0, bp); in xfs_btree_get_rec()
4324 if (ptr > xfs_btree_get_numrecs(block) || ptr <= 0) { in xfs_btree_get_rec()
4332 *recp = xfs_btree_rec_addr(cur, ptr, block); in xfs_btree_get_rec()
4337 /* Visit a block in a btree. */
4345 struct xfs_btree_block *block; in xfs_btree_visit_block() local
4352 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_visit_block()
4354 /* process the block */ in xfs_btree_visit_block()
4359 /* now read rh sibling block for next iteration */ in xfs_btree_visit_block()
4360 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB); in xfs_btree_visit_block()
4367 * return the same block without checking if the right sibling points in xfs_btree_visit_block()
4379 return xfs_btree_lookup_get_block(cur, level, &rptr, &block); in xfs_btree_visit_block()
4383 /* Visit every block in a btree. */
4393 struct xfs_btree_block *block = NULL; in xfs_btree_visit_blocks() local
4400 /* grab the left hand block */ in xfs_btree_visit_blocks()
4401 error = xfs_btree_lookup_get_block(cur, level, &lptr, &block); in xfs_btree_visit_blocks()
4405 /* readahead the left most block for the next level down */ in xfs_btree_visit_blocks()
4409 ptr = xfs_btree_ptr_addr(cur, 1, block); in xfs_btree_visit_blocks()
4446 * as the amount of CPU work we have to do before moving to the next block is
4449 * For each btree block that we load, modify the owner appropriately, set the
4469 struct xfs_btree_block *block; in xfs_btree_block_change_owner() local
4473 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_block_change_owner()
4475 if (block->bb_u.l.bb_owner == cpu_to_be64(bbcoi->new_owner)) in xfs_btree_block_change_owner()
4477 block->bb_u.l.bb_owner = cpu_to_be64(bbcoi->new_owner); in xfs_btree_block_change_owner()
4479 if (block->bb_u.s.bb_owner == cpu_to_be32(bbcoi->new_owner)) in xfs_btree_block_change_owner()
4481 block->bb_u.s.bb_owner = cpu_to_be32(bbcoi->new_owner); in xfs_btree_block_change_owner()
4485 * If the block is a root block hosted in an inode, we might not have a in xfs_btree_block_change_owner()
4488 * block is formatted into the on-disk inode fork. We still change it, in xfs_btree_block_change_owner()
4524 /* Verify the v5 fields of a long-format btree block. */
4531 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_lblock_v5hdr_verify() local
4535 if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid)) in xfs_btree_lblock_v5hdr_verify()
4537 if (block->bb_u.l.bb_blkno != cpu_to_be64(xfs_buf_daddr(bp))) in xfs_btree_lblock_v5hdr_verify()
4540 be64_to_cpu(block->bb_u.l.bb_owner) != owner) in xfs_btree_lblock_v5hdr_verify()
4545 /* Verify a long-format btree block. */
4552 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_lblock_verify() local
4557 if (be16_to_cpu(block->bb_numrecs) > max_recs) in xfs_btree_lblock_verify()
4563 block->bb_u.l.bb_leftsib); in xfs_btree_lblock_verify()
4566 block->bb_u.l.bb_rightsib); in xfs_btree_lblock_verify()
4572 * btree block
4574 * @bp: buffer containing the btree block
4581 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_sblock_v5hdr_verify() local
4586 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid)) in xfs_btree_sblock_v5hdr_verify()
4588 if (block->bb_u.s.bb_blkno != cpu_to_be64(xfs_buf_daddr(bp))) in xfs_btree_sblock_v5hdr_verify()
4590 if (pag && be32_to_cpu(block->bb_u.s.bb_owner) != pag->pag_agno) in xfs_btree_sblock_v5hdr_verify()
4596 * xfs_btree_sblock_verify() -- verify a short-format btree block
4598 * @bp: buffer containing the btree block
4607 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); in xfs_btree_sblock_verify() local
4612 if (be16_to_cpu(block->bb_numrecs) > max_recs) in xfs_btree_sblock_verify()
4618 block->bb_u.s.bb_leftsib); in xfs_btree_sblock_verify()
4621 block->bb_u.s.bb_rightsib); in xfs_btree_sblock_verify()
4626 * For the given limits on leaf and keyptr records per block, calculate the
4646 * For the given limits on leaf and keyptr records per block, calculate the
4671 * We start by assuming a single level tree consumes a single block, then track
4683 * The root btree block can have fewer than minrecs pointers in it in xfs_btree_space_to_height()
4792 * As an optimization, we stop scanning a block when we find a low key
4810 struct xfs_btree_block *block; in xfs_btree_overlapped_query_range() local
4819 error = xfs_btree_lookup_get_block(cur, level, &ptr, &block); in xfs_btree_overlapped_query_range()
4825 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_overlapped_query_range()
4832 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_overlapped_query_range()
4836 be16_to_cpu(block->bb_numrecs)) { in xfs_btree_overlapped_query_range()
4847 block); in xfs_btree_overlapped_query_range()
4854 * are no more interesting records in this block. Pop in xfs_btree_overlapped_query_range()
4873 lkp = xfs_btree_key_addr(cur, cur->bc_levels[level].ptr, block); in xfs_btree_overlapped_query_range()
4875 block); in xfs_btree_overlapped_query_range()
4876 pp = xfs_btree_ptr_addr(cur, cur->bc_levels[level].ptr, block); in xfs_btree_overlapped_query_range()
4880 * more interesting keys in this block. Pop up one leaf level in xfs_btree_overlapped_query_range()
4892 &block); in xfs_btree_overlapped_query_range()
4898 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_overlapped_query_range()
4911 * block, a subsequent non-error cursor deletion will not release in xfs_btree_overlapped_query_range()
5161 struct xfs_btree_block *block; in xfs_btree_has_more_records() local
5164 block = xfs_btree_get_block(cur, 0, &bp); in xfs_btree_has_more_records()
5166 /* There are still records in this block. */ in xfs_btree_has_more_records()
5167 if (cur->bc_levels[0].ptr < xfs_btree_get_numrecs(block)) in xfs_btree_has_more_records()
5172 return block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK); in xfs_btree_has_more_records()
5174 return block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK); in xfs_btree_has_more_records()