Lines Matching +full:high +full:- +full:level
1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
48 /* Ensure we asked for crc for crc-only magics. */ in xfs_btree_magic()
61 int level, in __xfs_btree_check_lblock() argument
64 struct xfs_mount *mp = cur->bc_mp; in __xfs_btree_check_lblock()
65 xfs_btnum_t btnum = cur->bc_btnum; in __xfs_btree_check_lblock()
66 int crc = xfs_sb_version_hascrc(&mp->m_sb); in __xfs_btree_check_lblock()
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()
72 cpu_to_be64(bp ? bp->b_bn : XFS_BUF_DADDR_NULL)) 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()
83 cur->bc_ops->get_maxrecs(cur, level)) 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()
87 level + 1)) 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()
91 level + 1)) in __xfs_btree_check_lblock()
102 int level, in xfs_btree_check_lblock() argument
105 struct xfs_mount *mp = cur->bc_mp; in xfs_btree_check_lblock()
108 fa = __xfs_btree_check_lblock(cur, block, level, bp); in xfs_btree_check_lblock()
113 return -EFSCORRUPTED; in xfs_btree_check_lblock()
126 int level, in __xfs_btree_check_sblock() argument
129 struct xfs_mount *mp = cur->bc_mp; in __xfs_btree_check_sblock()
130 xfs_btnum_t btnum = cur->bc_btnum; in __xfs_btree_check_sblock()
131 int crc = xfs_sb_version_hascrc(&mp->m_sb); in __xfs_btree_check_sblock()
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()
137 cpu_to_be64(bp ? bp->b_bn : XFS_BUF_DADDR_NULL)) 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()
146 cur->bc_ops->get_maxrecs(cur, level)) 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()
150 level + 1)) 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()
154 level + 1)) in __xfs_btree_check_sblock()
165 int level, in xfs_btree_check_sblock() argument
168 struct xfs_mount *mp = cur->bc_mp; in xfs_btree_check_sblock()
171 fa = __xfs_btree_check_sblock(cur, block, level, bp); in xfs_btree_check_sblock()
176 return -EFSCORRUPTED; in xfs_btree_check_sblock()
188 int level, /* level of the btree block */ in xfs_btree_check_block() argument
191 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) 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()
202 int level) in xfs_btree_check_lptr() argument
204 if (level <= 0) in xfs_btree_check_lptr()
206 return xfs_verify_fsbno(cur->bc_mp, fsbno); in xfs_btree_check_lptr()
214 int level) in xfs_btree_check_sptr() argument
216 if (level <= 0) in xfs_btree_check_sptr()
218 return xfs_verify_agbno(cur->bc_mp, cur->bc_ag.agno, agbno); in xfs_btree_check_sptr()
222 * Check that a given (indexed) btree pointer at a certain level of a
230 int level) in xfs_btree_check_ptr() argument
232 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_check_ptr()
233 if (xfs_btree_check_lptr(cur, be64_to_cpu((&ptr->l)[index]), in xfs_btree_check_ptr()
234 level)) in xfs_btree_check_ptr()
236 xfs_err(cur->bc_mp, in xfs_btree_check_ptr()
237 "Inode %llu fork %d: Corrupt btree %d pointer at level %d index %d.", in xfs_btree_check_ptr()
238 cur->bc_ino.ip->i_ino, in xfs_btree_check_ptr()
239 cur->bc_ino.whichfork, cur->bc_btnum, in xfs_btree_check_ptr()
240 level, index); in xfs_btree_check_ptr()
242 if (xfs_btree_check_sptr(cur, be32_to_cpu((&ptr->s)[index]), in xfs_btree_check_ptr()
243 level)) in xfs_btree_check_ptr()
245 xfs_err(cur->bc_mp, in xfs_btree_check_ptr()
246 "AG %u: Corrupt btree %d pointer at level %d index %d.", in xfs_btree_check_ptr()
247 cur->bc_ag.agno, cur->bc_btnum, in xfs_btree_check_ptr()
248 level, index); in xfs_btree_check_ptr()
251 return -EFSCORRUPTED; in xfs_btree_check_ptr()
262 * long-form btree header.
273 struct xfs_buf_log_item *bip = bp->b_log_item; in xfs_btree_lblock_calc_crc()
275 if (!xfs_sb_version_hascrc(&bp->b_mount->m_sb)) in xfs_btree_lblock_calc_crc()
278 block->bb_u.l.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn); in xfs_btree_lblock_calc_crc()
287 struct xfs_mount *mp = bp->b_mount; in xfs_btree_lblock_verify_crc()
289 if (xfs_sb_version_hascrc(&mp->m_sb)) { in xfs_btree_lblock_verify_crc()
290 if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.l.bb_lsn))) in xfs_btree_lblock_verify_crc()
300 * short-form btree header.
311 struct xfs_buf_log_item *bip = bp->b_log_item; in xfs_btree_sblock_calc_crc()
313 if (!xfs_sb_version_hascrc(&bp->b_mount->m_sb)) in xfs_btree_sblock_calc_crc()
316 block->bb_u.s.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn); in xfs_btree_sblock_calc_crc()
325 struct xfs_mount *mp = bp->b_mount; in xfs_btree_sblock_verify_crc()
327 if (xfs_sb_version_hascrc(&mp->m_sb)) { in xfs_btree_sblock_verify_crc()
328 if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.s.bb_lsn))) in xfs_btree_sblock_verify_crc()
343 error = cur->bc_ops->free_block(cur, bp); in xfs_btree_free_block()
345 xfs_trans_binval(cur->bc_tp, bp); in xfs_btree_free_block()
359 int i; /* btree level */ in xfs_btree_del_cursor()
367 * level n down to 0, and if we get an error along in xfs_btree_del_cursor()
371 for (i = 0; i < cur->bc_nlevels; i++) { in xfs_btree_del_cursor()
372 if (cur->bc_bufs[i]) in xfs_btree_del_cursor()
373 xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[i]); in xfs_btree_del_cursor()
381 ASSERT(cur->bc_btnum != XFS_BTNUM_BMAP || in xfs_btree_del_cursor()
382 cur->bc_ino.allocated == 0); in xfs_btree_del_cursor()
386 if (unlikely(cur->bc_flags & XFS_BTREE_STAGING)) in xfs_btree_del_cursor()
387 kmem_free((void *)cur->bc_ops); in xfs_btree_del_cursor()
393 * Allocate a new one, copy the record, re-get the buffers.
402 int i; /* level number of btree block */ in xfs_btree_dup_cursor()
407 tp = cur->bc_tp; in xfs_btree_dup_cursor()
408 mp = cur->bc_mp; in xfs_btree_dup_cursor()
413 new = cur->bc_ops->dup_cursor(cur); in xfs_btree_dup_cursor()
418 new->bc_rec = cur->bc_rec; in xfs_btree_dup_cursor()
421 * For each level current, re-get the buffer and copy the ptr value. in xfs_btree_dup_cursor()
423 for (i = 0; i < new->bc_nlevels; i++) { in xfs_btree_dup_cursor()
424 new->bc_ptrs[i] = cur->bc_ptrs[i]; in xfs_btree_dup_cursor()
425 new->bc_ra[i] = cur->bc_ra[i]; in xfs_btree_dup_cursor()
426 bp = cur->bc_bufs[i]; in xfs_btree_dup_cursor()
428 error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, in xfs_btree_dup_cursor()
429 XFS_BUF_ADDR(bp), mp->m_bsize, in xfs_btree_dup_cursor()
431 cur->bc_ops->buf_ops); in xfs_btree_dup_cursor()
438 new->bc_bufs[i] = bp; in xfs_btree_dup_cursor()
447 * There are two types of blocks in the btree: leaf and non-leaf blocks.
450 * the values. A non-leaf block also starts with the same header, and
452 * to the btree blocks at the previous level.
454 * +--------+-------+-------+-------+-------+-------+-------+
456 * +--------+-------+-------+-------+-------+-------+-------+
458 * +--------+-------+-------+-------+-------+-------+-------+
459 * Non-Leaf: | header | key 1 | key 2 | key N | ptr 1 | ptr 2 | ptr N |
460 * +--------+-------+-------+-------+-------+-------+-------+
476 * However, nodes are different: each pointer has two associated keys -- one
481 * that matches any record in the leaf and to recursively update the high keys
485 * +--------+-----+-----+-----+-----+-----+-------+-------+-----+
486 * Non-Leaf: | header | lo1 | hi1 | lo2 | hi2 | ... | ptr 1 | ptr 2 | ... |
487 * +--------+-----+-----+-----+-----+-----+-------+-------+-----+
490 * depth-first search and use the low and high keys to decide if we can skip
493 * entries. For a non-overlapped tree, simply search for the record associated
494 * with the lowest key and iterate forward until a non-matching record is
502 * 1: +- file A startblock B offset C length D -----------+
503 * 2: +- file E startblock F offset G length H --------------+
504 * 3: +- file I startblock F offset J length K --+
505 * 4: +- file L... --+
509 * that ends at (B+D-1) (i.e. record 1)? A LE lookup of (B+D-1) would return
511 * query would return records 1 and 2 because they both overlap (B+D-1), and
514 * In the non-overlapped case you can do a LE lookup and decrement the cursor
523 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_block_len()
524 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) in xfs_btree_block_len()
528 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) in xfs_btree_block_len()
538 return (cur->bc_flags & XFS_BTREE_LONG_PTRS) ? in xfs_btree_ptr_len()
543 * Calculate offset of the n-th record in a btree block.
551 (n - 1) * cur->bc_ops->rec_len; in xfs_btree_rec_offset()
555 * Calculate offset of the n-th key in a btree block.
563 (n - 1) * cur->bc_ops->key_len; in xfs_btree_key_offset()
567 * Calculate offset of the n-th high key in a btree block.
575 (n - 1) * cur->bc_ops->key_len + (cur->bc_ops->key_len / 2); in xfs_btree_high_key_offset()
579 * Calculate offset of the n-th block pointer in a btree block.
585 int level) in xfs_btree_ptr_offset() argument
588 cur->bc_ops->get_maxrecs(cur, level) * cur->bc_ops->key_len + in xfs_btree_ptr_offset()
589 (n - 1) * xfs_btree_ptr_len(cur); in xfs_btree_ptr_offset()
593 * Return a pointer to the n-th record in the btree block.
606 * Return a pointer to the n-th key in the btree block.
619 * Return a pointer to the n-th high key in the btree block.
632 * Return a pointer to the n-th block pointer in the btree block.
640 int level = xfs_btree_get_level(block); in xfs_btree_ptr_addr() local
642 ASSERT(block->bb_level != 0); in xfs_btree_ptr_addr()
645 ((char *)block + xfs_btree_ptr_offset(cur, n, level)); in xfs_btree_ptr_addr()
652 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE); in xfs_btree_ifork_ptr()
654 if (cur->bc_flags & XFS_BTREE_STAGING) in xfs_btree_ifork_ptr()
655 return cur->bc_ino.ifake->if_fork; in xfs_btree_ifork_ptr()
656 return XFS_IFORK_PTR(cur->bc_ino.ip, cur->bc_ino.whichfork); in xfs_btree_ifork_ptr()
671 return (struct xfs_btree_block *)ifp->if_broot; in xfs_btree_get_iroot()
675 * Retrieve the block pointer from the cursor at the given level.
681 int level, /* level in btree */ in xfs_btree_get_block() argument
684 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_get_block()
685 (level == cur->bc_nlevels - 1)) { in xfs_btree_get_block()
690 *bpp = cur->bc_bufs[level]; in xfs_btree_get_block()
695 * Change the cursor to point to the first record at the given level.
701 int level) /* level to change */ in xfs_btree_firstrec() argument
707 * Get the block pointer for this level. in xfs_btree_firstrec()
709 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_firstrec()
710 if (xfs_btree_check_block(cur, block, level, bp)) in xfs_btree_firstrec()
715 if (!block->bb_numrecs) in xfs_btree_firstrec()
720 cur->bc_ptrs[level] = 1; in xfs_btree_firstrec()
726 * at the given level. Other levels are unaffected.
731 int level) /* level to change */ in xfs_btree_lastrec() argument
737 * Get the block pointer for this level. in xfs_btree_lastrec()
739 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_lastrec()
740 if (xfs_btree_check_block(cur, block, level, bp)) in xfs_btree_lastrec()
745 if (!block->bb_numrecs) in xfs_btree_lastrec()
750 cur->bc_ptrs[level] = be16_to_cpu(block->bb_numrecs); in xfs_btree_lastrec()
782 for (i = nbits - 1, imask = 1LL << i; ; i--, imask >>= 1) { in xfs_btree_offsets()
784 *last = offsets[i + 1] - 1; in xfs_btree_offsets()
792 * Long-form addressing.
808 return -EFSCORRUPTED; in xfs_btree_read_bufl()
810 error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, d, in xfs_btree_read_bufl()
811 mp->m_bsize, 0, &bp, ops); in xfs_btree_read_bufl()
821 * Read-ahead the block, don't wait for it, don't return a buffer.
822 * Long-form addressing.
836 xfs_buf_readahead(mp->m_ddev_targp, d, mp->m_bsize * count, ops); in xfs_btree_reada_bufl()
840 * Read-ahead the block, don't wait for it, don't return a buffer.
841 * Short-form addressing.
857 xfs_buf_readahead(mp->m_ddev_targp, d, mp->m_bsize * count, ops); in xfs_btree_reada_bufs()
867 xfs_fsblock_t left = be64_to_cpu(block->bb_u.l.bb_leftsib); in xfs_btree_readahead_lblock()
868 xfs_fsblock_t right = be64_to_cpu(block->bb_u.l.bb_rightsib); in xfs_btree_readahead_lblock()
871 xfs_btree_reada_bufl(cur->bc_mp, left, 1, in xfs_btree_readahead_lblock()
872 cur->bc_ops->buf_ops); in xfs_btree_readahead_lblock()
877 xfs_btree_reada_bufl(cur->bc_mp, right, 1, in xfs_btree_readahead_lblock()
878 cur->bc_ops->buf_ops); in xfs_btree_readahead_lblock()
892 xfs_agblock_t left = be32_to_cpu(block->bb_u.s.bb_leftsib); in xfs_btree_readahead_sblock()
893 xfs_agblock_t right = be32_to_cpu(block->bb_u.s.bb_rightsib); in xfs_btree_readahead_sblock()
897 xfs_btree_reada_bufs(cur->bc_mp, cur->bc_ag.agno, in xfs_btree_readahead_sblock()
898 left, 1, cur->bc_ops->buf_ops); in xfs_btree_readahead_sblock()
903 xfs_btree_reada_bufs(cur->bc_mp, cur->bc_ag.agno, in xfs_btree_readahead_sblock()
904 right, 1, cur->bc_ops->buf_ops); in xfs_btree_readahead_sblock()
912 * Read-ahead btree blocks, at the given level.
918 int lev, /* level in btree */ in xfs_btree_readahead()
924 * No readahead needed if we are at the root level and the in xfs_btree_readahead()
927 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_readahead()
928 (lev == cur->bc_nlevels - 1)) in xfs_btree_readahead()
931 if ((cur->bc_ra[lev] | lr) == cur->bc_ra[lev]) in xfs_btree_readahead()
934 cur->bc_ra[lev] |= lr; in xfs_btree_readahead()
935 block = XFS_BUF_TO_BLOCK(cur->bc_bufs[lev]); in xfs_btree_readahead()
937 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_readahead()
956 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_ptr_to_daddr()
957 fsbno = be64_to_cpu(ptr->l); in xfs_btree_ptr_to_daddr()
958 *daddr = XFS_FSB_TO_DADDR(cur->bc_mp, fsbno); in xfs_btree_ptr_to_daddr()
960 agbno = be32_to_cpu(ptr->s); in xfs_btree_ptr_to_daddr()
961 *daddr = XFS_AGB_TO_DADDR(cur->bc_mp, cur->bc_ag.agno, in xfs_btree_ptr_to_daddr()
984 xfs_buf_readahead(cur->bc_mp->m_ddev_targp, daddr, in xfs_btree_readahead_ptr()
985 cur->bc_mp->m_bsize * count, cur->bc_ops->buf_ops); in xfs_btree_readahead_ptr()
989 * Set the buffer for level "lev" in the cursor to bp, releasing
995 int lev, /* level in btree */ in xfs_btree_setbuf()
1000 if (cur->bc_bufs[lev]) in xfs_btree_setbuf()
1001 xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[lev]); in xfs_btree_setbuf()
1002 cur->bc_bufs[lev] = bp; in xfs_btree_setbuf()
1003 cur->bc_ra[lev] = 0; in xfs_btree_setbuf()
1006 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_setbuf()
1007 if (b->bb_u.l.bb_leftsib == cpu_to_be64(NULLFSBLOCK)) in xfs_btree_setbuf()
1008 cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA; in xfs_btree_setbuf()
1009 if (b->bb_u.l.bb_rightsib == cpu_to_be64(NULLFSBLOCK)) in xfs_btree_setbuf()
1010 cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA; in xfs_btree_setbuf()
1012 if (b->bb_u.s.bb_leftsib == cpu_to_be32(NULLAGBLOCK)) in xfs_btree_setbuf()
1013 cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA; in xfs_btree_setbuf()
1014 if (b->bb_u.s.bb_rightsib == cpu_to_be32(NULLAGBLOCK)) in xfs_btree_setbuf()
1015 cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA; in xfs_btree_setbuf()
1024 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_ptr_is_null()
1025 return ptr->l == cpu_to_be64(NULLFSBLOCK); in xfs_btree_ptr_is_null()
1027 return ptr->s == cpu_to_be32(NULLAGBLOCK); in xfs_btree_ptr_is_null()
1035 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_set_ptr_null()
1036 ptr->l = cpu_to_be64(NULLFSBLOCK); in xfs_btree_set_ptr_null()
1038 ptr->s = cpu_to_be32(NULLAGBLOCK); in xfs_btree_set_ptr_null()
1053 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_get_sibling()
1055 ptr->l = block->bb_u.l.bb_rightsib; in xfs_btree_get_sibling()
1057 ptr->l = block->bb_u.l.bb_leftsib; in xfs_btree_get_sibling()
1060 ptr->s = block->bb_u.s.bb_rightsib; in xfs_btree_get_sibling()
1062 ptr->s = block->bb_u.s.bb_leftsib; in xfs_btree_get_sibling()
1075 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_set_sibling()
1077 block->bb_u.l.bb_rightsib = ptr->l; in xfs_btree_set_sibling()
1079 block->bb_u.l.bb_leftsib = ptr->l; in xfs_btree_set_sibling()
1082 block->bb_u.s.bb_rightsib = ptr->s; in xfs_btree_set_sibling()
1084 block->bb_u.s.bb_leftsib = ptr->s; in xfs_btree_set_sibling()
1094 __u16 level, in xfs_btree_init_block_int() argument
1099 int crc = xfs_sb_version_hascrc(&mp->m_sb); in xfs_btree_init_block_int()
1102 buf->bb_magic = cpu_to_be32(magic); in xfs_btree_init_block_int()
1103 buf->bb_level = cpu_to_be16(level); in xfs_btree_init_block_int()
1104 buf->bb_numrecs = cpu_to_be16(numrecs); in xfs_btree_init_block_int()
1107 buf->bb_u.l.bb_leftsib = cpu_to_be64(NULLFSBLOCK); in xfs_btree_init_block_int()
1108 buf->bb_u.l.bb_rightsib = cpu_to_be64(NULLFSBLOCK); in xfs_btree_init_block_int()
1110 buf->bb_u.l.bb_blkno = cpu_to_be64(blkno); in xfs_btree_init_block_int()
1111 buf->bb_u.l.bb_owner = cpu_to_be64(owner); in xfs_btree_init_block_int()
1112 uuid_copy(&buf->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid); in xfs_btree_init_block_int()
1113 buf->bb_u.l.bb_pad = 0; in xfs_btree_init_block_int()
1114 buf->bb_u.l.bb_lsn = 0; in xfs_btree_init_block_int()
1120 buf->bb_u.s.bb_leftsib = cpu_to_be32(NULLAGBLOCK); in xfs_btree_init_block_int()
1121 buf->bb_u.s.bb_rightsib = cpu_to_be32(NULLAGBLOCK); in xfs_btree_init_block_int()
1123 buf->bb_u.s.bb_blkno = cpu_to_be64(blkno); in xfs_btree_init_block_int()
1124 buf->bb_u.s.bb_owner = cpu_to_be32(__owner); in xfs_btree_init_block_int()
1125 uuid_copy(&buf->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid); in xfs_btree_init_block_int()
1126 buf->bb_u.s.bb_lsn = 0; in xfs_btree_init_block_int()
1136 __u16 level, in xfs_btree_init_block() argument
1140 xfs_btree_init_block_int(mp, XFS_BUF_TO_BLOCK(bp), bp->b_bn, in xfs_btree_init_block()
1141 btnum, level, numrecs, owner, 0); in xfs_btree_init_block()
1148 int level, in xfs_btree_init_block_cur() argument
1159 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_init_block_cur()
1160 owner = cur->bc_ino.ip->i_ino; in xfs_btree_init_block_cur()
1162 owner = cur->bc_ag.agno; in xfs_btree_init_block_cur()
1164 xfs_btree_init_block_int(cur->bc_mp, XFS_BUF_TO_BLOCK(bp), bp->b_bn, in xfs_btree_init_block_cur()
1165 cur->bc_btnum, level, numrecs, in xfs_btree_init_block_cur()
1166 owner, cur->bc_flags); in xfs_btree_init_block_cur()
1178 int level) in xfs_btree_is_lastrec() argument
1182 if (level > 0) in xfs_btree_is_lastrec()
1184 if (!(cur->bc_flags & XFS_BTREE_LASTREC_UPDATE)) in xfs_btree_is_lastrec()
1199 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_buf_to_ptr()
1200 ptr->l = cpu_to_be64(XFS_DADDR_TO_FSB(cur->bc_mp, in xfs_btree_buf_to_ptr()
1203 ptr->s = cpu_to_be32(xfs_daddr_to_agbno(cur->bc_mp, in xfs_btree_buf_to_ptr()
1213 switch (cur->bc_btnum) { in xfs_btree_set_refs()
1243 struct xfs_mount *mp = cur->bc_mp; in xfs_btree_get_buf_block()
1250 error = xfs_trans_get_buf(cur->bc_tp, mp->m_ddev_targp, d, mp->m_bsize, in xfs_btree_get_buf_block()
1255 (*bpp)->b_ops = cur->bc_ops->buf_ops; in xfs_btree_get_buf_block()
1272 struct xfs_mount *mp = cur->bc_mp; in xfs_btree_read_buf_block()
1282 error = xfs_trans_read_buf(mp, cur->bc_tp, mp->m_ddev_targp, d, in xfs_btree_read_buf_block()
1283 mp->m_bsize, flags, bpp, in xfs_btree_read_buf_block()
1284 cur->bc_ops->buf_ops); in xfs_btree_read_buf_block()
1304 memcpy(dst_key, src_key, numkeys * cur->bc_ops->key_len); in xfs_btree_copy_keys()
1318 memcpy(dst_rec, src_rec, numrecs * cur->bc_ops->rec_len); in xfs_btree_copy_recs()
1348 ASSERT(dir == 1 || dir == -1); in xfs_btree_shift_keys()
1350 dst_key = (char *)key + (dir * cur->bc_ops->key_len); in xfs_btree_shift_keys()
1351 memmove(dst_key, key, numkeys * cur->bc_ops->key_len); in xfs_btree_shift_keys()
1367 ASSERT(dir == 1 || dir == -1); in xfs_btree_shift_recs()
1369 dst_rec = (char *)rec + (dir * cur->bc_ops->rec_len); in xfs_btree_shift_recs()
1370 memmove(dst_rec, rec, numrecs * cur->bc_ops->rec_len); in xfs_btree_shift_recs()
1386 ASSERT(dir == 1 || dir == -1); in xfs_btree_shift_ptrs()
1404 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF); in xfs_btree_log_keys()
1405 xfs_trans_log_buf(cur->bc_tp, bp, in xfs_btree_log_keys()
1407 xfs_btree_key_offset(cur, last + 1) - 1); in xfs_btree_log_keys()
1409 xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip, in xfs_btree_log_keys()
1410 xfs_ilog_fbroot(cur->bc_ino.whichfork)); in xfs_btree_log_keys()
1425 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF); in xfs_btree_log_recs()
1426 xfs_trans_log_buf(cur->bc_tp, bp, in xfs_btree_log_recs()
1428 xfs_btree_rec_offset(cur, last + 1) - 1); in xfs_btree_log_recs()
1445 int level = xfs_btree_get_level(block); in xfs_btree_log_ptrs() local
1447 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF); in xfs_btree_log_ptrs()
1448 xfs_trans_log_buf(cur->bc_tp, bp, in xfs_btree_log_ptrs()
1449 xfs_btree_ptr_offset(cur, first, level), in xfs_btree_log_ptrs()
1450 xfs_btree_ptr_offset(cur, last + 1, level) - 1); in xfs_btree_log_ptrs()
1452 xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip, in xfs_btree_log_ptrs()
1453 xfs_ilog_fbroot(cur->bc_ino.whichfork)); in xfs_btree_log_ptrs()
1500 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) { in xfs_btree_log_block()
1515 (cur->bc_flags & XFS_BTREE_LONG_PTRS) ? in xfs_btree_log_block()
1518 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF); in xfs_btree_log_block()
1519 xfs_trans_log_buf(cur->bc_tp, bp, first, last); in xfs_btree_log_block()
1521 xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip, in xfs_btree_log_block()
1522 xfs_ilog_fbroot(cur->bc_ino.whichfork)); in xfs_btree_log_block()
1527 * Increment cursor by one record at the level.
1528 * For nonzero levels the leaf-ward information is untouched.
1533 int level, in xfs_btree_increment() argument
1542 ASSERT(level < cur->bc_nlevels); in xfs_btree_increment()
1544 /* Read-ahead to the right at this level. */ in xfs_btree_increment()
1545 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA); in xfs_btree_increment()
1548 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_increment()
1551 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_increment()
1557 if (++cur->bc_ptrs[level] <= xfs_btree_get_numrecs(block)) in xfs_btree_increment()
1571 for (lev = level + 1; lev < cur->bc_nlevels; lev++) { in xfs_btree_increment()
1580 if (++cur->bc_ptrs[lev] <= xfs_btree_get_numrecs(block)) in xfs_btree_increment()
1583 /* Read-ahead the right block for the next loop. */ in xfs_btree_increment()
1591 if (lev == cur->bc_nlevels) { in xfs_btree_increment()
1592 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) in xfs_btree_increment()
1595 error = -EFSCORRUPTED; in xfs_btree_increment()
1598 ASSERT(lev < cur->bc_nlevels); in xfs_btree_increment()
1604 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) { in xfs_btree_increment()
1607 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block); in xfs_btree_increment()
1608 --lev; in xfs_btree_increment()
1614 cur->bc_ptrs[lev] = 1; in xfs_btree_increment()
1629 * Decrement cursor by one record at the level.
1630 * For nonzero levels the leaf-ward information is untouched.
1635 int level, in xfs_btree_decrement() argument
1644 ASSERT(level < cur->bc_nlevels); in xfs_btree_decrement()
1646 /* Read-ahead to the left at this level. */ in xfs_btree_decrement()
1647 xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA); in xfs_btree_decrement()
1650 if (--cur->bc_ptrs[level] > 0) in xfs_btree_decrement()
1654 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_decrement()
1657 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_decrement()
1673 for (lev = level + 1; lev < cur->bc_nlevels; lev++) { in xfs_btree_decrement()
1674 if (--cur->bc_ptrs[lev] > 0) in xfs_btree_decrement()
1676 /* Read-ahead the left block for the next loop. */ in xfs_btree_decrement()
1684 if (lev == cur->bc_nlevels) { in xfs_btree_decrement()
1685 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) in xfs_btree_decrement()
1688 error = -EFSCORRUPTED; in xfs_btree_decrement()
1691 ASSERT(lev < cur->bc_nlevels); in xfs_btree_decrement()
1697 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) { in xfs_btree_decrement()
1700 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block); in xfs_btree_decrement()
1701 --lev; in xfs_btree_decrement()
1706 cur->bc_ptrs[lev] = xfs_btree_get_numrecs(block); in xfs_btree_decrement()
1723 int level, /* level in the btree */ in xfs_btree_lookup_get_block() argument
1732 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_lookup_get_block()
1733 (level == cur->bc_nlevels - 1)) { in xfs_btree_lookup_get_block()
1739 * If the old buffer at this level for the disk address we are in xfs_btree_lookup_get_block()
1740 * looking for re-use it. in xfs_btree_lookup_get_block()
1744 bp = cur->bc_bufs[level]; in xfs_btree_lookup_get_block()
1758 if (xfs_sb_version_hascrc(&cur->bc_mp->m_sb) && in xfs_btree_lookup_get_block()
1759 !(cur->bc_ino.flags & XFS_BTCUR_BMBT_INVALID_OWNER) && in xfs_btree_lookup_get_block()
1760 (cur->bc_flags & XFS_BTREE_LONG_PTRS) && in xfs_btree_lookup_get_block()
1761 be64_to_cpu((*blkp)->bb_u.l.bb_owner) != in xfs_btree_lookup_get_block()
1762 cur->bc_ino.ip->i_ino) in xfs_btree_lookup_get_block()
1765 /* Did we get the level we were looking for? */ in xfs_btree_lookup_get_block()
1766 if (be16_to_cpu((*blkp)->bb_level) != level) in xfs_btree_lookup_get_block()
1770 if (level != 0 && be16_to_cpu((*blkp)->bb_numrecs) == 0) in xfs_btree_lookup_get_block()
1773 xfs_btree_setbuf(cur, level, bp); in xfs_btree_lookup_get_block()
1779 xfs_trans_brelse(cur->bc_tp, bp); in xfs_btree_lookup_get_block()
1780 return -EFSCORRUPTED; in xfs_btree_lookup_get_block()
1784 * Get current search key. For level 0 we don't actually have a key
1791 int level, in xfs_lookup_get_search_key() argument
1796 if (level == 0) { in xfs_lookup_get_search_key()
1797 cur->bc_ops->init_key_from_rec(kp, in xfs_lookup_get_search_key()
1819 int level; /* level in the btree */ in xfs_btree_lookup() local
1825 /* No such thing as a zero-level tree. */ in xfs_btree_lookup()
1826 if (XFS_IS_CORRUPT(cur->bc_mp, cur->bc_nlevels == 0)) in xfs_btree_lookup()
1827 return -EFSCORRUPTED; in xfs_btree_lookup()
1833 cur->bc_ops->init_ptr_from_cur(cur, &ptr); in xfs_btree_lookup()
1837 * Iterate over each level in the btree, starting at the root. in xfs_btree_lookup()
1838 * For each level above the leaves, find the key we need, based in xfs_btree_lookup()
1840 * pointer down to the next level. in xfs_btree_lookup()
1842 for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) { in xfs_btree_lookup()
1844 error = xfs_btree_lookup_get_block(cur, level, pp, &block); in xfs_btree_lookup()
1850 * If we already had a key match at a higher level, we in xfs_btree_lookup()
1857 int high; /* high entry number */ in xfs_btree_lookup() local
1860 /* Set low and high entry numbers, 1-based. */ in xfs_btree_lookup()
1862 high = xfs_btree_get_numrecs(block); in xfs_btree_lookup()
1863 if (!high) { in xfs_btree_lookup()
1865 if (level != 0 || cur->bc_nlevels != 1) { in xfs_btree_lookup()
1868 cur->bc_mp, block, in xfs_btree_lookup()
1870 return -EFSCORRUPTED; in xfs_btree_lookup()
1873 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE; in xfs_btree_lookup()
1879 while (low <= high) { in xfs_btree_lookup()
1885 /* keyno is average of low and high. */ in xfs_btree_lookup()
1886 keyno = (low + high) >> 1; in xfs_btree_lookup()
1889 kp = xfs_lookup_get_search_key(cur, level, in xfs_btree_lookup()
1894 * - less than, move right in xfs_btree_lookup()
1895 * - greater than, move left in xfs_btree_lookup()
1896 * - equal, we're done in xfs_btree_lookup()
1898 diff = cur->bc_ops->key_diff(cur, kp); in xfs_btree_lookup()
1902 high = keyno - 1; in xfs_btree_lookup()
1909 * If there are more levels, set up for the next level in xfs_btree_lookup()
1912 if (level > 0) { in xfs_btree_lookup()
1917 if (diff > 0 && --keyno < 1) in xfs_btree_lookup()
1921 error = xfs_btree_debug_check_ptr(cur, pp, 0, level); in xfs_btree_lookup()
1925 cur->bc_ptrs[level] = keyno; in xfs_btree_lookup()
1942 cur->bc_ptrs[0] = keyno; in xfs_btree_lookup()
1946 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) in xfs_btree_lookup()
1947 return -EFSCORRUPTED; in xfs_btree_lookup()
1952 keyno--; in xfs_btree_lookup()
1953 cur->bc_ptrs[0] = keyno; in xfs_btree_lookup()
1968 /* Find the high key storage area from a regular key. */
1974 ASSERT(cur->bc_flags & XFS_BTREE_OVERLAPPING); in xfs_btree_high_key_from_key()
1976 (cur->bc_ops->key_len / 2)); in xfs_btree_high_key_from_key()
1979 /* Determine the low (and high if overlapped) keys of a leaf block */
1989 union xfs_btree_key *high; in xfs_btree_get_leaf_keys() local
1993 cur->bc_ops->init_key_from_rec(key, rec); in xfs_btree_get_leaf_keys()
1995 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { in xfs_btree_get_leaf_keys()
1997 cur->bc_ops->init_high_key_from_rec(&max_hkey, rec); in xfs_btree_get_leaf_keys()
2000 cur->bc_ops->init_high_key_from_rec(&hkey, rec); in xfs_btree_get_leaf_keys()
2001 if (cur->bc_ops->diff_two_keys(cur, &hkey, &max_hkey) in xfs_btree_get_leaf_keys()
2006 high = xfs_btree_high_key_from_key(cur, key); in xfs_btree_get_leaf_keys()
2007 memcpy(high, &max_hkey, cur->bc_ops->key_len / 2); in xfs_btree_get_leaf_keys()
2011 /* Determine the low (and high if overlapped) keys of a node block */
2020 union xfs_btree_key *high; in xfs_btree_get_node_keys() local
2023 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { in xfs_btree_get_node_keys()
2025 cur->bc_ops->key_len / 2); in xfs_btree_get_node_keys()
2030 if (cur->bc_ops->diff_two_keys(cur, hkey, max_hkey) > 0) in xfs_btree_get_node_keys()
2034 high = xfs_btree_high_key_from_key(cur, key); in xfs_btree_get_node_keys()
2035 memcpy(high, max_hkey, cur->bc_ops->key_len / 2); in xfs_btree_get_node_keys()
2038 cur->bc_ops->key_len); in xfs_btree_get_node_keys()
2049 if (be16_to_cpu(block->bb_level) == 0) in xfs_btree_get_keys()
2067 return (cur->bc_flags & XFS_BTREE_OVERLAPPING) || ptr == 1; in xfs_btree_needs_key_update()
2071 * Update the low and high parent keys of the given level, progressing
2073 * level do not need updating.
2078 int level, in __xfs_btree_updkeys() argument
2083 union xfs_btree_key key; /* keys from current level */ in __xfs_btree_updkeys()
2084 union xfs_btree_key *lkey; /* keys from the next level up */ in __xfs_btree_updkeys()
2086 union xfs_btree_key *nlkey; /* keys from the next level up */ in __xfs_btree_updkeys()
2091 ASSERT(cur->bc_flags & XFS_BTREE_OVERLAPPING); in __xfs_btree_updkeys()
2094 if (level + 1 >= cur->bc_nlevels) in __xfs_btree_updkeys()
2097 trace_xfs_btree_updkeys(cur, level, bp0); in __xfs_btree_updkeys()
2102 for (level++; level < cur->bc_nlevels; level++) { in __xfs_btree_updkeys()
2106 block = xfs_btree_get_block(cur, level, &bp); in __xfs_btree_updkeys()
2107 trace_xfs_btree_updkeys(cur, level, bp); in __xfs_btree_updkeys()
2109 error = xfs_btree_check_block(cur, block, level, bp); in __xfs_btree_updkeys()
2113 ptr = cur->bc_ptrs[level]; in __xfs_btree_updkeys()
2117 !(cur->bc_ops->diff_two_keys(cur, nlkey, lkey) != 0 || in __xfs_btree_updkeys()
2118 cur->bc_ops->diff_two_keys(cur, nhkey, hkey) != 0)) in __xfs_btree_updkeys()
2122 if (level + 1 >= cur->bc_nlevels) in __xfs_btree_updkeys()
2130 /* Update all the keys from some level in cursor back to the root. */
2134 int level) in xfs_btree_updkeys_force() argument
2139 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_updkeys_force()
2140 return __xfs_btree_updkeys(cur, level, block, bp, true); in xfs_btree_updkeys_force()
2144 * Update the parent keys of the given level, progressing towards the root.
2149 int level) in xfs_btree_update_keys() argument
2157 ASSERT(level >= 0); in xfs_btree_update_keys()
2159 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_update_keys()
2160 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) in xfs_btree_update_keys()
2161 return __xfs_btree_updkeys(cur, level, block, bp, false); in xfs_btree_update_keys()
2164 * Go up the tree from this level toward the root. in xfs_btree_update_keys()
2165 * At each level, update the key value to the value input. in xfs_btree_update_keys()
2166 * Stop when we reach a level where the cursor isn't pointing in xfs_btree_update_keys()
2170 for (level++, ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) { in xfs_btree_update_keys()
2174 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_update_keys()
2176 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_update_keys()
2180 ptr = cur->bc_ptrs[level]; in xfs_btree_update_keys()
2214 ptr = cur->bc_ptrs[0]; in xfs_btree_update()
2226 cur->bc_ops->update_lastrec(cur, block, rec, in xfs_btree_update()
2244 * Move 1 record left from cur/level if possible.
2250 int level, in xfs_btree_lshift() argument
2267 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_lshift()
2268 level == cur->bc_nlevels - 1) in xfs_btree_lshift()
2272 right = xfs_btree_get_block(cur, level, &rbp); in xfs_btree_lshift()
2275 error = xfs_btree_check_block(cur, right, level, rbp); in xfs_btree_lshift()
2289 if (cur->bc_ptrs[level] <= 1) in xfs_btree_lshift()
2299 if (lrecs == cur->bc_ops->get_maxrecs(cur, level)) in xfs_btree_lshift()
2310 rrecs--; in xfs_btree_lshift()
2316 * If non-leaf, copy a key and a ptr to the left block. in xfs_btree_lshift()
2319 if (level > 0) { in xfs_btree_lshift()
2320 /* It's a non-leaf. Move keys and pointers. */ in xfs_btree_lshift()
2330 error = xfs_btree_debug_check_ptr(cur, rpp, 0, level); in xfs_btree_lshift()
2340 ASSERT(cur->bc_ops->keys_inorder(cur, in xfs_btree_lshift()
2341 xfs_btree_key_addr(cur, lrecs - 1, left), lkp)); in xfs_btree_lshift()
2352 ASSERT(cur->bc_ops->recs_inorder(cur, in xfs_btree_lshift()
2353 xfs_btree_rec_addr(cur, lrecs - 1, left), lrp)); in xfs_btree_lshift()
2365 XFS_BTREE_STATS_ADD(cur, moves, rrecs - 1); in xfs_btree_lshift()
2366 if (level > 0) { in xfs_btree_lshift()
2369 error = xfs_btree_debug_check_ptr(cur, rpp, i + 1, level); in xfs_btree_lshift()
2376 -1, rrecs); in xfs_btree_lshift()
2379 -1, rrecs); in xfs_btree_lshift()
2387 -1, rrecs); in xfs_btree_lshift()
2395 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { in xfs_btree_lshift()
2399 i = xfs_btree_firstrec(tcur, level); in xfs_btree_lshift()
2400 if (XFS_IS_CORRUPT(tcur->bc_mp, i != 1)) { in xfs_btree_lshift()
2401 error = -EFSCORRUPTED; in xfs_btree_lshift()
2405 error = xfs_btree_decrement(tcur, level, &i); in xfs_btree_lshift()
2409 /* Update the parent high keys of the left block, if needed. */ in xfs_btree_lshift()
2410 error = xfs_btree_update_keys(tcur, level); in xfs_btree_lshift()
2418 error = xfs_btree_update_keys(cur, level); in xfs_btree_lshift()
2423 cur->bc_ptrs[level]--; in xfs_btree_lshift()
2441 * Move 1 record right from cur/level if possible.
2447 int level, in xfs_btree_rshift() argument
2462 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_rshift()
2463 (level == cur->bc_nlevels - 1)) in xfs_btree_rshift()
2467 left = xfs_btree_get_block(cur, level, &lbp); in xfs_btree_rshift()
2470 error = xfs_btree_check_block(cur, left, level, lbp); in xfs_btree_rshift()
2485 if (cur->bc_ptrs[level] >= lrecs) in xfs_btree_rshift()
2495 if (rrecs == cur->bc_ops->get_maxrecs(cur, level)) in xfs_btree_rshift()
2505 if (level > 0) { in xfs_btree_rshift()
2516 for (i = rrecs - 1; i >= 0; i--) { in xfs_btree_rshift()
2517 error = xfs_btree_debug_check_ptr(cur, rpp, i, level); in xfs_btree_rshift()
2525 error = xfs_btree_debug_check_ptr(cur, lpp, 0, level); in xfs_btree_rshift()
2536 ASSERT(cur->bc_ops->keys_inorder(cur, rkp, in xfs_btree_rshift()
2556 xfs_btree_set_numrecs(left, --lrecs); in xfs_btree_rshift()
2569 i = xfs_btree_lastrec(tcur, level); in xfs_btree_rshift()
2570 if (XFS_IS_CORRUPT(tcur->bc_mp, i != 1)) { in xfs_btree_rshift()
2571 error = -EFSCORRUPTED; in xfs_btree_rshift()
2575 error = xfs_btree_increment(tcur, level, &i); in xfs_btree_rshift()
2579 /* Update the parent high keys of the left block, if needed. */ in xfs_btree_rshift()
2580 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { in xfs_btree_rshift()
2581 error = xfs_btree_update_keys(cur, level); in xfs_btree_rshift()
2587 error = xfs_btree_update_keys(tcur, level); in xfs_btree_rshift()
2609 * Split cur/level block in half.
2616 int level, in __xfs_btree_split() argument
2628 union xfs_btree_ptr rrptr; /* right-right sibling ptr */ in __xfs_btree_split()
2629 struct xfs_buf *rrbp; /* right-right buffer pointer */ in __xfs_btree_split()
2630 struct xfs_btree_block *rrblock; /* right-right btree block */ in __xfs_btree_split()
2640 left = xfs_btree_get_block(cur, level, &lbp); in __xfs_btree_split()
2643 error = xfs_btree_check_block(cur, left, level, lbp); in __xfs_btree_split()
2651 error = cur->bc_ops->alloc_block(cur, &lptr, &rptr, stat); in __xfs_btree_split()
2673 if ((lrecs & 1) && cur->bc_ptrs[level] <= rrecs + 1) in __xfs_btree_split()
2675 src_index = (lrecs - rrecs + 1); in __xfs_btree_split()
2680 lrecs -= rrecs; in __xfs_btree_split()
2689 if (level > 0) { in __xfs_btree_split()
2690 /* It's a non-leaf. Move keys and pointers. */ in __xfs_btree_split()
2702 error = xfs_btree_debug_check_ptr(cur, lpp, i, level); in __xfs_btree_split()
2757 /* Update the parent high keys of the left block, if needed. */ in __xfs_btree_split()
2758 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { in __xfs_btree_split()
2759 error = xfs_btree_update_keys(cur, level); in __xfs_btree_split()
2769 if (cur->bc_ptrs[level] > lrecs + 1) { in __xfs_btree_split()
2770 xfs_btree_setbuf(cur, level, rbp); in __xfs_btree_split()
2771 cur->bc_ptrs[level] -= lrecs; in __xfs_btree_split()
2777 if (level + 1 < cur->bc_nlevels) { in __xfs_btree_split()
2781 (*curp)->bc_ptrs[level + 1]++; in __xfs_btree_split()
2796 int level; member
2825 if (args->kswapd) in xfs_btree_split_worker()
2830 args->result = __xfs_btree_split(args->cur, args->level, args->ptrp, in xfs_btree_split_worker()
2831 args->key, args->curp, args->stat); in xfs_btree_split_worker()
2832 complete(args->done); in xfs_btree_split_worker()
2845 int level, in xfs_btree_split() argument
2854 if (cur->bc_btnum != XFS_BTNUM_BMAP) in xfs_btree_split()
2855 return __xfs_btree_split(cur, level, ptrp, key, curp, stat); in xfs_btree_split()
2858 args.level = level; in xfs_btree_split()
2881 int *stat) /* return status - 0 fail */ in xfs_btree_new_iroot()
2891 int level; /* btree level */ in xfs_btree_new_iroot() local
2897 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE); in xfs_btree_new_iroot()
2899 level = cur->bc_nlevels - 1; in xfs_btree_new_iroot()
2905 error = cur->bc_ops->alloc_block(cur, pp, &nptr, stat); in xfs_btree_new_iroot()
2923 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) { in xfs_btree_new_iroot()
2924 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_new_iroot()
2925 cblock->bb_u.l.bb_blkno = cpu_to_be64(cbp->b_bn); in xfs_btree_new_iroot()
2927 cblock->bb_u.s.bb_blkno = cpu_to_be64(cbp->b_bn); in xfs_btree_new_iroot()
2930 be16_add_cpu(&block->bb_level, 1); in xfs_btree_new_iroot()
2932 cur->bc_nlevels++; in xfs_btree_new_iroot()
2933 cur->bc_ptrs[level + 1] = 1; in xfs_btree_new_iroot()
2940 for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) { in xfs_btree_new_iroot()
2941 error = xfs_btree_debug_check_ptr(cur, pp, i, level); in xfs_btree_new_iroot()
2948 error = xfs_btree_debug_check_ptr(cur, &nptr, 0, level); in xfs_btree_new_iroot()
2954 xfs_iroot_realloc(cur->bc_ino.ip, in xfs_btree_new_iroot()
2955 1 - xfs_btree_get_numrecs(cblock), in xfs_btree_new_iroot()
2956 cur->bc_ino.whichfork); in xfs_btree_new_iroot()
2958 xfs_btree_setbuf(cur, level, cbp); in xfs_btree_new_iroot()
2962 * the root is at the right level. in xfs_btree_new_iroot()
2965 xfs_btree_log_keys(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs)); in xfs_btree_new_iroot()
2966 xfs_btree_log_ptrs(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs)); in xfs_btree_new_iroot()
2969 XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_ino.whichfork); in xfs_btree_new_iroot()
3000 cur->bc_ops->init_ptr_from_cur(cur, &rptr); in xfs_btree_new_root()
3003 error = cur->bc_ops->alloc_block(cur, &rptr, &lptr, stat); in xfs_btree_new_root()
3015 /* Set the root in the holding structure increasing the level by 1. */ in xfs_btree_new_root()
3016 cur->bc_ops->set_root(cur, &lptr, 1); in xfs_btree_new_root()
3019 * At the previous root level there are now two blocks: the old root, in xfs_btree_new_root()
3024 block = xfs_btree_get_block(cur, cur->bc_nlevels - 1, &bp); in xfs_btree_new_root()
3027 error = xfs_btree_check_block(cur, block, cur->bc_nlevels - 1, bp); in xfs_btree_new_root()
3057 xfs_btree_init_block_cur(cur, nbp, cur->bc_nlevels, 2); in xfs_btree_new_root()
3093 xfs_btree_setbuf(cur, cur->bc_nlevels, nbp); in xfs_btree_new_root()
3094 cur->bc_ptrs[cur->bc_nlevels] = nptr; in xfs_btree_new_root()
3095 cur->bc_nlevels++; in xfs_btree_new_root()
3108 int level, /* btree level */ in xfs_btree_make_block_unfull() argument
3119 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_make_block_unfull()
3120 level == cur->bc_nlevels - 1) { in xfs_btree_make_block_unfull()
3121 struct xfs_inode *ip = cur->bc_ino.ip; in xfs_btree_make_block_unfull()
3123 if (numrecs < cur->bc_ops->get_dmaxrecs(cur, level)) { in xfs_btree_make_block_unfull()
3125 xfs_iroot_realloc(ip, 1, cur->bc_ino.whichfork); in xfs_btree_make_block_unfull()
3135 xfs_trans_log_inode(cur->bc_tp, ip, logflags); in xfs_btree_make_block_unfull()
3142 error = xfs_btree_rshift(cur, level, stat); in xfs_btree_make_block_unfull()
3147 error = xfs_btree_lshift(cur, level, stat); in xfs_btree_make_block_unfull()
3152 *oindex = *index = cur->bc_ptrs[level]; in xfs_btree_make_block_unfull()
3159 * If this works we have to re-set our variables because we in xfs_btree_make_block_unfull()
3162 error = xfs_btree_split(cur, level, nptr, key, ncur, stat); in xfs_btree_make_block_unfull()
3167 *index = cur->bc_ptrs[level]; in xfs_btree_make_block_unfull()
3172 * Insert one record/level. Return information to the caller
3173 * allowing the next level up to proceed if necessary.
3178 int level, /* level to insert record at */ in xfs_btree_insrec() argument
3203 * root level, allocate a new root block and we're done. in xfs_btree_insrec()
3205 if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_insrec()
3206 (level >= cur->bc_nlevels)) { in xfs_btree_insrec()
3214 ptr = cur->bc_ptrs[level]; in xfs_btree_insrec()
3225 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_insrec()
3226 old_bn = bp ? bp->b_bn : XFS_BUF_DADDR_NULL; in xfs_btree_insrec()
3230 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_insrec()
3236 if (level == 0) { in xfs_btree_insrec()
3237 ASSERT(cur->bc_ops->recs_inorder(cur, rec, in xfs_btree_insrec()
3240 ASSERT(cur->bc_ops->keys_inorder(cur, key, in xfs_btree_insrec()
3248 * make the block un-full. in xfs_btree_insrec()
3251 if (numrecs == cur->bc_ops->get_maxrecs(cur, level)) { in xfs_btree_insrec()
3252 error = xfs_btree_make_block_unfull(cur, level, numrecs, in xfs_btree_insrec()
3262 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_insrec()
3266 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_insrec()
3275 XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr + 1); in xfs_btree_insrec()
3277 if (level > 0) { in xfs_btree_insrec()
3285 for (i = numrecs - ptr; i >= 0; i--) { in xfs_btree_insrec()
3286 error = xfs_btree_debug_check_ptr(cur, pp, i, level); in xfs_btree_insrec()
3291 xfs_btree_shift_keys(cur, kp, 1, numrecs - ptr + 1); in xfs_btree_insrec()
3292 xfs_btree_shift_ptrs(cur, pp, 1, numrecs - ptr + 1); in xfs_btree_insrec()
3294 error = xfs_btree_debug_check_ptr(cur, ptrp, 0, level); in xfs_btree_insrec()
3307 ASSERT(cur->bc_ops->keys_inorder(cur, kp, in xfs_btree_insrec()
3317 xfs_btree_shift_recs(cur, rp, 1, numrecs - ptr + 1); in xfs_btree_insrec()
3325 ASSERT(cur->bc_ops->recs_inorder(cur, rp, in xfs_btree_insrec()
3342 if (bp && bp->b_bn != old_bn) { in xfs_btree_insrec()
3345 error = xfs_btree_update_keys(cur, level); in xfs_btree_insrec()
3354 if (xfs_btree_is_lastrec(cur, block, level)) { in xfs_btree_insrec()
3355 cur->bc_ops->update_lastrec(cur, block, rec, in xfs_btree_insrec()
3379 * A multi-level split of the tree on insert will invalidate the original
3390 int level; /* current level number in btree */ in xfs_btree_insert() local
3393 struct xfs_btree_cur *pcur; /* previous level's cursor */ in xfs_btree_insert()
3398 level = 0; in xfs_btree_insert()
3406 cur->bc_ops->init_rec_from_cur(cur, &rec); in xfs_btree_insert()
3407 cur->bc_ops->init_key_from_rec(key, &rec); in xfs_btree_insert()
3410 * Loop going up the tree, starting at the leaf level. in xfs_btree_insert()
3412 * the insert is finished with this level. in xfs_btree_insert()
3416 * Insert nrec/nptr into this level of the tree. in xfs_btree_insert()
3419 error = xfs_btree_insrec(pcur, level, &nptr, &rec, key, in xfs_btree_insert()
3427 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_insert()
3428 error = -EFSCORRUPTED; in xfs_btree_insert()
3431 level++; in xfs_btree_insert()
3441 if (cur->bc_ops->update_cursor) in xfs_btree_insert()
3442 cur->bc_ops->update_cursor(pcur, cur); in xfs_btree_insert()
3443 cur->bc_nlevels = pcur->bc_nlevels; in xfs_btree_insert()
3460 * Try to merge a non-leaf block back into the inode root.
3471 int whichfork = cur->bc_ino.whichfork; in xfs_btree_kill_iroot()
3472 struct xfs_inode *ip = cur->bc_ino.ip; in xfs_btree_kill_iroot()
3481 int level; in xfs_btree_kill_iroot() local
3490 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE); in xfs_btree_kill_iroot()
3491 ASSERT(cur->bc_nlevels > 1); in xfs_btree_kill_iroot()
3497 level = cur->bc_nlevels - 1; in xfs_btree_kill_iroot()
3498 if (level == 1) in xfs_btree_kill_iroot()
3508 cblock = xfs_btree_get_block(cur, level - 1, &cbp); in xfs_btree_kill_iroot()
3512 * Only do this if the next level will fit. in xfs_btree_kill_iroot()
3514 * instead of freeing the root you free the next level. in xfs_btree_kill_iroot()
3516 if (numrecs > cur->bc_ops->get_dmaxrecs(cur, level)) in xfs_btree_kill_iroot()
3528 index = numrecs - cur->bc_ops->get_maxrecs(cur, level); in xfs_btree_kill_iroot()
3530 xfs_iroot_realloc(cur->bc_ino.ip, index, in xfs_btree_kill_iroot()
3531 cur->bc_ino.whichfork); in xfs_btree_kill_iroot()
3532 block = ifp->if_broot; in xfs_btree_kill_iroot()
3535 be16_add_cpu(&block->bb_numrecs, index); in xfs_btree_kill_iroot()
3536 ASSERT(block->bb_numrecs == cblock->bb_numrecs); in xfs_btree_kill_iroot()
3546 error = xfs_btree_debug_check_ptr(cur, cpp, i, level - 1); in xfs_btree_kill_iroot()
3557 cur->bc_bufs[level - 1] = NULL; in xfs_btree_kill_iroot()
3558 be16_add_cpu(&block->bb_level, -1); in xfs_btree_kill_iroot()
3559 xfs_trans_log_inode(cur->bc_tp, ip, in xfs_btree_kill_iroot()
3560 XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_ino.whichfork)); in xfs_btree_kill_iroot()
3561 cur->bc_nlevels--; in xfs_btree_kill_iroot()
3573 int level, in xfs_btree_kill_root() argument
3581 * Update the root pointer, decreasing the level by 1 and then in xfs_btree_kill_root()
3584 cur->bc_ops->set_root(cur, newroot, -1); in xfs_btree_kill_root()
3590 cur->bc_bufs[level] = NULL; in xfs_btree_kill_root()
3591 cur->bc_ra[level] = 0; in xfs_btree_kill_root()
3592 cur->bc_nlevels--; in xfs_btree_kill_root()
3600 int level, in xfs_btree_dec_cursor() argument
3606 if (level > 0) { in xfs_btree_dec_cursor()
3607 error = xfs_btree_decrement(cur, level, &i); in xfs_btree_dec_cursor()
3617 * Single level of the btree record deletion routine.
3618 * Delete record pointed to by cur/level.
3620 * Return 0 for error, 1 for done, 2 to go on to the next level.
3625 int level, /* level removing record from */ in xfs_btree_delrec() argument
3626 int *stat) /* fail/done/go-on */ in xfs_btree_delrec()
3641 struct xfs_btree_block *rrblock; /* right-right btree block */ in xfs_btree_delrec()
3642 struct xfs_buf *rrbp; /* right-right buffer pointer */ in xfs_btree_delrec()
3650 ptr = cur->bc_ptrs[level]; in xfs_btree_delrec()
3657 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_delrec()
3661 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_delrec()
3673 XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr); in xfs_btree_delrec()
3676 if (level > 0) { in xfs_btree_delrec()
3684 for (i = 0; i < numrecs - ptr; i++) { in xfs_btree_delrec()
3685 error = xfs_btree_debug_check_ptr(cur, lpp, i, level); in xfs_btree_delrec()
3691 xfs_btree_shift_keys(cur, lkp, -1, numrecs - ptr); in xfs_btree_delrec()
3692 xfs_btree_shift_ptrs(cur, lpp, -1, numrecs - ptr); in xfs_btree_delrec()
3693 xfs_btree_log_keys(cur, bp, ptr, numrecs - 1); in xfs_btree_delrec()
3694 xfs_btree_log_ptrs(cur, bp, ptr, numrecs - 1); in xfs_btree_delrec()
3701 -1, numrecs - ptr); in xfs_btree_delrec()
3702 xfs_btree_log_recs(cur, bp, ptr, numrecs - 1); in xfs_btree_delrec()
3709 xfs_btree_set_numrecs(block, --numrecs); in xfs_btree_delrec()
3716 if (xfs_btree_is_lastrec(cur, block, level)) { in xfs_btree_delrec()
3717 cur->bc_ops->update_lastrec(cur, block, NULL, in xfs_btree_delrec()
3722 * We're at the root level. First, shrink the root block in-memory. in xfs_btree_delrec()
3723 * Try to get rid of the next level down. If we can't then there's in xfs_btree_delrec()
3726 if (level == cur->bc_nlevels - 1) { in xfs_btree_delrec()
3727 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) { in xfs_btree_delrec()
3728 xfs_iroot_realloc(cur->bc_ino.ip, -1, in xfs_btree_delrec()
3729 cur->bc_ino.whichfork); in xfs_btree_delrec()
3735 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
3743 * If this is the root level, and there's only one entry left, in xfs_btree_delrec()
3744 * and it's NOT the leaf level, then we can get rid of this in xfs_btree_delrec()
3745 * level. in xfs_btree_delrec()
3747 if (numrecs == 1 && level > 0) { in xfs_btree_delrec()
3754 error = xfs_btree_kill_root(cur, bp, level, pp); in xfs_btree_delrec()
3757 } else if (level > 0) { in xfs_btree_delrec()
3758 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
3771 error = xfs_btree_update_keys(cur, level); in xfs_btree_delrec()
3780 if (numrecs >= cur->bc_ops->get_minrecs(cur, level)) { in xfs_btree_delrec()
3781 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
3790 * see if we can re-balance by moving only one record. in xfs_btree_delrec()
3795 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) { in xfs_btree_delrec()
3798 * into the root and delete it. Can't go up to next level, in xfs_btree_delrec()
3803 level == cur->bc_nlevels - 2) { in xfs_btree_delrec()
3806 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
3818 * disrupt the next level up. in xfs_btree_delrec()
3833 i = xfs_btree_lastrec(tcur, level); in xfs_btree_delrec()
3834 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3835 error = -EFSCORRUPTED; in xfs_btree_delrec()
3839 error = xfs_btree_increment(tcur, level, &i); in xfs_btree_delrec()
3842 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3843 error = -EFSCORRUPTED; in xfs_btree_delrec()
3847 i = xfs_btree_lastrec(tcur, level); in xfs_btree_delrec()
3848 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3849 error = -EFSCORRUPTED; in xfs_btree_delrec()
3854 right = xfs_btree_get_block(tcur, level, &rbp); in xfs_btree_delrec()
3856 error = xfs_btree_check_block(tcur, right, level, rbp); in xfs_btree_delrec()
3865 * won't make it too empty, and left-shifting an entry out in xfs_btree_delrec()
3868 if (xfs_btree_get_numrecs(right) - 1 >= in xfs_btree_delrec()
3869 cur->bc_ops->get_minrecs(tcur, level)) { in xfs_btree_delrec()
3870 error = xfs_btree_lshift(tcur, level, &i); in xfs_btree_delrec()
3875 cur->bc_ops->get_minrecs(tcur, level)); in xfs_btree_delrec()
3880 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
3894 i = xfs_btree_firstrec(tcur, level); in xfs_btree_delrec()
3895 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3896 error = -EFSCORRUPTED; in xfs_btree_delrec()
3900 error = xfs_btree_decrement(tcur, level, &i); in xfs_btree_delrec()
3903 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3904 error = -EFSCORRUPTED; in xfs_btree_delrec()
3919 i = xfs_btree_firstrec(tcur, level); in xfs_btree_delrec()
3920 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3921 error = -EFSCORRUPTED; in xfs_btree_delrec()
3925 error = xfs_btree_decrement(tcur, level, &i); in xfs_btree_delrec()
3928 i = xfs_btree_firstrec(tcur, level); in xfs_btree_delrec()
3929 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3930 error = -EFSCORRUPTED; in xfs_btree_delrec()
3935 left = xfs_btree_get_block(tcur, level, &lbp); in xfs_btree_delrec()
3937 error = xfs_btree_check_block(cur, left, level, lbp); in xfs_btree_delrec()
3946 * won't make it too empty, and right-shifting an entry out in xfs_btree_delrec()
3949 if (xfs_btree_get_numrecs(left) - 1 >= in xfs_btree_delrec()
3950 cur->bc_ops->get_minrecs(tcur, level)) { in xfs_btree_delrec()
3951 error = xfs_btree_rshift(tcur, level, &i); in xfs_btree_delrec()
3956 cur->bc_ops->get_minrecs(tcur, level)); in xfs_btree_delrec()
3959 if (level == 0) in xfs_btree_delrec()
3960 cur->bc_ptrs[0]++; in xfs_btree_delrec()
3983 cur->bc_ops->get_maxrecs(cur, level)) { in xfs_btree_delrec()
4000 cur->bc_ops->get_maxrecs(cur, level)) { in xfs_btree_delrec()
4017 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
4031 if (level > 0) { in xfs_btree_delrec()
4032 /* It's a non-leaf. Move keys and pointers. */ in xfs_btree_delrec()
4044 error = xfs_btree_debug_check_ptr(cur, rpp, i, level); in xfs_btree_delrec()
4097 cur->bc_bufs[level] = lbp; in xfs_btree_delrec()
4098 cur->bc_ptrs[level] += lrecs; in xfs_btree_delrec()
4099 cur->bc_ra[level] = 0; in xfs_btree_delrec()
4102 * If we joined with the right neighbor and there's a level above in xfs_btree_delrec()
4103 * us, increment the cursor at that level. in xfs_btree_delrec()
4105 else if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) || in xfs_btree_delrec()
4106 (level + 1 < cur->bc_nlevels)) { in xfs_btree_delrec()
4107 error = xfs_btree_increment(cur, level + 1, &i); in xfs_btree_delrec()
4113 * Readjust the ptr at this level if it's not a leaf, since it's in xfs_btree_delrec()
4116 * We can't use decrement because it would change the next level up. in xfs_btree_delrec()
4118 if (level > 0) in xfs_btree_delrec()
4119 cur->bc_ptrs[level]--; in xfs_btree_delrec()
4123 * btree supports overlapped intervals. However, bc_ptrs[level + 1] in xfs_btree_delrec()
4131 /* Return value means the next level up has something to do. */ in xfs_btree_delrec()
4152 int level; in xfs_btree_delete() local
4157 * Go up the tree, starting at leaf level. in xfs_btree_delete()
4159 * If 2 is returned then a join was done; go to the next level. in xfs_btree_delete()
4162 for (level = 0, i = 2; i == 2; level++) { in xfs_btree_delete()
4163 error = xfs_btree_delrec(cur, level, &i); in xfs_btree_delete()
4172 * have updated the parent high keys so we have to do that here. in xfs_btree_delete()
4174 if (joined && (cur->bc_flags & XFS_BTREE_OVERLAPPING)) { in xfs_btree_delete()
4181 for (level = 1; level < cur->bc_nlevels; level++) { in xfs_btree_delete()
4182 if (cur->bc_ptrs[level] == 0) { in xfs_btree_delete()
4183 error = xfs_btree_decrement(cur, level, &i); in xfs_btree_delete()
4198 * Get the data from the pointed-to record.
4213 ptr = cur->bc_ptrs[0]; in xfs_btree_get_rec()
4242 int level, in xfs_btree_visit_block() argument
4252 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA); in xfs_btree_visit_block()
4253 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_visit_block()
4256 error = fn(cur, level, data); in xfs_btree_visit_block()
4263 return -ENOENT; in xfs_btree_visit_block()
4265 return xfs_btree_lookup_get_block(cur, level, &rptr, &block); in xfs_btree_visit_block()
4278 int level; in xfs_btree_visit_blocks() local
4282 cur->bc_ops->init_ptr_from_cur(cur, &lptr); in xfs_btree_visit_blocks()
4284 /* for each level */ in xfs_btree_visit_blocks()
4285 for (level = cur->bc_nlevels - 1; level >= 0; level--) { in xfs_btree_visit_blocks()
4287 error = xfs_btree_lookup_get_block(cur, level, &lptr, &block); in xfs_btree_visit_blocks()
4291 /* readahead the left most block for the next level down */ in xfs_btree_visit_blocks()
4292 if (level > 0) { in xfs_btree_visit_blocks()
4307 /* for each buffer in the level */ in xfs_btree_visit_blocks()
4309 error = xfs_btree_visit_block(cur, level, fn, data); in xfs_btree_visit_blocks()
4312 if (error != -ENOENT) in xfs_btree_visit_blocks()
4327 * We do the btree walk in the most optimal manner possible - we have sibling
4328 * pointers so we can just walk all the blocks on each level from left to right
4329 * in a single pass, and then move to the next level and do the same. We can
4351 int level, in xfs_btree_block_change_owner() argument
4359 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_block_change_owner()
4360 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_block_change_owner()
4361 if (block->bb_u.l.bb_owner == cpu_to_be64(bbcoi->new_owner)) in xfs_btree_block_change_owner()
4363 block->bb_u.l.bb_owner = cpu_to_be64(bbcoi->new_owner); in xfs_btree_block_change_owner()
4365 if (block->bb_u.s.bb_owner == cpu_to_be32(bbcoi->new_owner)) in xfs_btree_block_change_owner()
4367 block->bb_u.s.bb_owner = cpu_to_be32(bbcoi->new_owner); in xfs_btree_block_change_owner()
4374 * block is formatted into the on-disk inode fork. We still change it, in xfs_btree_block_change_owner()
4378 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE); in xfs_btree_block_change_owner()
4379 ASSERT(level == cur->bc_nlevels - 1); in xfs_btree_block_change_owner()
4383 if (cur->bc_tp) { in xfs_btree_block_change_owner()
4384 if (!xfs_trans_ordered_buf(cur->bc_tp, bp)) { in xfs_btree_block_change_owner()
4386 return -EAGAIN; in xfs_btree_block_change_owner()
4389 xfs_buf_delwri_queue(bp, bbcoi->buffer_list); in xfs_btree_block_change_owner()
4410 /* Verify the v5 fields of a long-format btree block. */
4416 struct xfs_mount *mp = bp->b_mount; in xfs_btree_lblock_v5hdr_verify()
4419 if (!xfs_sb_version_hascrc(&mp->m_sb)) in xfs_btree_lblock_v5hdr_verify()
4421 if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid)) in xfs_btree_lblock_v5hdr_verify()
4423 if (block->bb_u.l.bb_blkno != cpu_to_be64(bp->b_bn)) in xfs_btree_lblock_v5hdr_verify()
4426 be64_to_cpu(block->bb_u.l.bb_owner) != owner) in xfs_btree_lblock_v5hdr_verify()
4431 /* Verify a long-format btree block. */
4437 struct xfs_mount *mp = bp->b_mount; in xfs_btree_lblock_verify()
4441 if (be16_to_cpu(block->bb_numrecs) > max_recs) in xfs_btree_lblock_verify()
4445 if (block->bb_u.l.bb_leftsib != cpu_to_be64(NULLFSBLOCK) && in xfs_btree_lblock_verify()
4446 !xfs_verify_fsbno(mp, be64_to_cpu(block->bb_u.l.bb_leftsib))) in xfs_btree_lblock_verify()
4448 if (block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK) && in xfs_btree_lblock_verify()
4449 !xfs_verify_fsbno(mp, be64_to_cpu(block->bb_u.l.bb_rightsib))) in xfs_btree_lblock_verify()
4456 * xfs_btree_sblock_v5hdr_verify() -- verify the v5 fields of a short-format
4465 struct xfs_mount *mp = bp->b_mount; in xfs_btree_sblock_v5hdr_verify()
4467 struct xfs_perag *pag = bp->b_pag; in xfs_btree_sblock_v5hdr_verify()
4469 if (!xfs_sb_version_hascrc(&mp->m_sb)) in xfs_btree_sblock_v5hdr_verify()
4471 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid)) in xfs_btree_sblock_v5hdr_verify()
4473 if (block->bb_u.s.bb_blkno != cpu_to_be64(bp->b_bn)) in xfs_btree_sblock_v5hdr_verify()
4475 if (pag && be32_to_cpu(block->bb_u.s.bb_owner) != pag->pag_agno) in xfs_btree_sblock_v5hdr_verify()
4481 * xfs_btree_sblock_verify() -- verify a short-format btree block
4491 struct xfs_mount *mp = bp->b_mount; in xfs_btree_sblock_verify()
4496 if (be16_to_cpu(block->bb_numrecs) > max_recs) in xfs_btree_sblock_verify()
4501 if (block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK) && in xfs_btree_sblock_verify()
4502 !xfs_verify_agbno(mp, agno, be32_to_cpu(block->bb_u.s.bb_leftsib))) in xfs_btree_sblock_verify()
4504 if (block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK) && in xfs_btree_sblock_verify()
4505 !xfs_verify_agbno(mp, agno, be32_to_cpu(block->bb_u.s.bb_rightsib))) in xfs_btree_sblock_verify()
4513 * records in a short-format btree.
4520 uint level; in xfs_btree_compute_maxlevels() local
4523 maxblocks = (len + limits[0] - 1) / limits[0]; in xfs_btree_compute_maxlevels()
4524 for (level = 1; maxblocks > 1; level++) in xfs_btree_compute_maxlevels()
4525 maxblocks = (maxblocks + limits[1] - 1) / limits[1]; in xfs_btree_compute_maxlevels()
4526 return level; in xfs_btree_compute_maxlevels()
4549 ASSERT(cur->bc_ops->init_high_key_from_rec); in xfs_btree_simple_query_range()
4550 ASSERT(cur->bc_ops->diff_two_keys); in xfs_btree_simple_query_range()
4576 cur->bc_ops->init_high_key_from_rec(&rec_key, recp); in xfs_btree_simple_query_range()
4578 diff = cur->bc_ops->diff_two_keys(cur, low_key, in xfs_btree_simple_query_range()
4585 cur->bc_ops->init_key_from_rec(&rec_key, recp); in xfs_btree_simple_query_range()
4586 diff = cur->bc_ops->diff_two_keys(cur, &rec_key, high_key); in xfs_btree_simple_query_range()
4612 * First, generate keys for the low and high records passed in.
4614 * For any leaf node, generate the high and low keys for the record.
4615 * If the record keys overlap with the query low/high keys, pass the
4618 * For any internal node, compare the low and high keys of each
4619 * pointer against the query low/high keys. If there's an overlap,
4623 * that is greater than the query's high key.
4643 int level; in xfs_btree_overlapped_query_range() local
4649 level = cur->bc_nlevels - 1; in xfs_btree_overlapped_query_range()
4650 cur->bc_ops->init_ptr_from_cur(cur, &ptr); in xfs_btree_overlapped_query_range()
4651 error = xfs_btree_lookup_get_block(cur, level, &ptr, &block); in xfs_btree_overlapped_query_range()
4654 xfs_btree_get_block(cur, level, &bp); in xfs_btree_overlapped_query_range()
4655 trace_xfs_btree_overlapped_query_range(cur, level, bp); in xfs_btree_overlapped_query_range()
4657 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_overlapped_query_range()
4661 cur->bc_ptrs[level] = 1; in xfs_btree_overlapped_query_range()
4663 while (level < cur->bc_nlevels) { in xfs_btree_overlapped_query_range()
4664 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_overlapped_query_range()
4667 if (cur->bc_ptrs[level] > be16_to_cpu(block->bb_numrecs)) { in xfs_btree_overlapped_query_range()
4669 if (level < cur->bc_nlevels - 1) in xfs_btree_overlapped_query_range()
4670 cur->bc_ptrs[level + 1]++; in xfs_btree_overlapped_query_range()
4671 level++; in xfs_btree_overlapped_query_range()
4675 if (level == 0) { in xfs_btree_overlapped_query_range()
4677 recp = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block); in xfs_btree_overlapped_query_range()
4679 cur->bc_ops->init_high_key_from_rec(&rec_hkey, recp); in xfs_btree_overlapped_query_range()
4680 ldiff = cur->bc_ops->diff_two_keys(cur, &rec_hkey, in xfs_btree_overlapped_query_range()
4683 cur->bc_ops->init_key_from_rec(&rec_key, recp); in xfs_btree_overlapped_query_range()
4684 hdiff = cur->bc_ops->diff_two_keys(cur, high_key, in xfs_btree_overlapped_query_range()
4688 * If (record's high key >= query's low key) and in xfs_btree_overlapped_query_range()
4689 * (query's high key >= record's low key), then in xfs_btree_overlapped_query_range()
4697 /* Record is larger than high key; pop. */ in xfs_btree_overlapped_query_range()
4700 cur->bc_ptrs[level]++; in xfs_btree_overlapped_query_range()
4705 lkp = xfs_btree_key_addr(cur, cur->bc_ptrs[level], block); in xfs_btree_overlapped_query_range()
4706 hkp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level], block); in xfs_btree_overlapped_query_range()
4707 pp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[level], block); in xfs_btree_overlapped_query_range()
4709 ldiff = cur->bc_ops->diff_two_keys(cur, hkp, low_key); in xfs_btree_overlapped_query_range()
4710 hdiff = cur->bc_ops->diff_two_keys(cur, high_key, lkp); in xfs_btree_overlapped_query_range()
4713 * If (pointer's high key >= query's low key) and in xfs_btree_overlapped_query_range()
4714 * (query's high key >= pointer's low key), then in xfs_btree_overlapped_query_range()
4718 level--; in xfs_btree_overlapped_query_range()
4719 error = xfs_btree_lookup_get_block(cur, level, pp, in xfs_btree_overlapped_query_range()
4723 xfs_btree_get_block(cur, level, &bp); in xfs_btree_overlapped_query_range()
4724 trace_xfs_btree_overlapped_query_range(cur, level, bp); in xfs_btree_overlapped_query_range()
4726 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_overlapped_query_range()
4730 cur->bc_ptrs[level] = 1; in xfs_btree_overlapped_query_range()
4736 cur->bc_ptrs[level]++; in xfs_btree_overlapped_query_range()
4742 * block, a subsequent non-error cursor deletion will not release in xfs_btree_overlapped_query_range()
4743 * node-level buffers, causing a buffer leak. This is quite possible in xfs_btree_overlapped_query_range()
4744 * with a zero-results range query, so release the buffers if we in xfs_btree_overlapped_query_range()
4747 if (cur->bc_bufs[0] == NULL) { in xfs_btree_overlapped_query_range()
4748 for (i = 0; i < cur->bc_nlevels; i++) { in xfs_btree_overlapped_query_range()
4749 if (cur->bc_bufs[i]) { in xfs_btree_overlapped_query_range()
4750 xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[i]); in xfs_btree_overlapped_query_range()
4751 cur->bc_bufs[i] = NULL; in xfs_btree_overlapped_query_range()
4752 cur->bc_ptrs[i] = 0; in xfs_btree_overlapped_query_range()
4753 cur->bc_ra[i] = 0; in xfs_btree_overlapped_query_range()
4765 * code. This function returns -ECANCELED, zero, or a negative error code.
4780 cur->bc_rec = *high_rec; in xfs_btree_query_range()
4781 cur->bc_ops->init_rec_from_cur(cur, &rec); in xfs_btree_query_range()
4782 cur->bc_ops->init_key_from_rec(&high_key, &rec); in xfs_btree_query_range()
4784 cur->bc_rec = *low_rec; in xfs_btree_query_range()
4785 cur->bc_ops->init_rec_from_cur(cur, &rec); in xfs_btree_query_range()
4786 cur->bc_ops->init_key_from_rec(&low_key, &rec); in xfs_btree_query_range()
4788 /* Enforce low key < high key. */ in xfs_btree_query_range()
4789 if (cur->bc_ops->diff_two_keys(cur, &low_key, &high_key) > 0) in xfs_btree_query_range()
4790 return -EINVAL; in xfs_btree_query_range()
4792 if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING)) in xfs_btree_query_range()
4809 memset(&cur->bc_rec, 0, sizeof(cur->bc_rec)); in xfs_btree_query_all()
4818 * in a short-format (per-AG metadata) btree.
4825 int level; in xfs_btree_calc_size() local
4830 for (level = 0, rval = 0; len > 1; level++) { in xfs_btree_calc_size()
4831 len += maxrecs - 1; in xfs_btree_calc_size()
4842 int level, in xfs_btree_count_blocks_helper() argument
4869 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_diff_two_ptrs()
4870 return (int64_t)be64_to_cpu(a->l) - be64_to_cpu(b->l); in xfs_btree_diff_two_ptrs()
4871 return (int64_t)be32_to_cpu(a->s) - be32_to_cpu(b->s); in xfs_btree_diff_two_ptrs()
4881 return -ECANCELED; in xfs_btree_has_record_helper()
4889 union xfs_btree_irec *high, in xfs_btree_has_record() argument
4894 error = xfs_btree_query_range(cur, low, high, in xfs_btree_has_record()
4896 if (error == -ECANCELED) { in xfs_btree_has_record()
4915 if (cur->bc_ptrs[0] < xfs_btree_get_numrecs(block)) in xfs_btree_has_more_records()
4919 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_has_more_records()
4920 return block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK); in xfs_btree_has_more_records()
4922 return block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK); in xfs_btree_has_more_records()