Lines Matching +full:last +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.
265 * it into the buffer so recovery knows what the last modification was that made
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.
303 * it into the buffer so recovery knows what the last modification was that made
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()
365 * code works from level n down to 0, and if we get an error along the in xfs_btree_del_cursor()
368 for (i = 0; i < cur->bc_nlevels; i++) { in xfs_btree_del_cursor()
369 if (cur->bc_bufs[i]) in xfs_btree_del_cursor()
370 xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[i]); in xfs_btree_del_cursor()
381 ASSERT(cur->bc_btnum != XFS_BTNUM_BMAP || cur->bc_ino.allocated == 0 || in xfs_btree_del_cursor()
382 XFS_FORCED_SHUTDOWN(cur->bc_mp) || error != 0); in xfs_btree_del_cursor()
383 if (unlikely(cur->bc_flags & XFS_BTREE_STAGING)) in xfs_btree_del_cursor()
384 kmem_free(cur->bc_ops); in xfs_btree_del_cursor()
390 * Allocate a new one, copy the record, re-get the buffers.
399 int i; /* level number of btree block */ in xfs_btree_dup_cursor()
404 tp = cur->bc_tp; in xfs_btree_dup_cursor()
405 mp = cur->bc_mp; in xfs_btree_dup_cursor()
410 new = cur->bc_ops->dup_cursor(cur); in xfs_btree_dup_cursor()
415 new->bc_rec = cur->bc_rec; in xfs_btree_dup_cursor()
418 * For each level current, re-get the buffer and copy the ptr value. in xfs_btree_dup_cursor()
420 for (i = 0; i < new->bc_nlevels; i++) { in xfs_btree_dup_cursor()
421 new->bc_ptrs[i] = cur->bc_ptrs[i]; in xfs_btree_dup_cursor()
422 new->bc_ra[i] = cur->bc_ra[i]; in xfs_btree_dup_cursor()
423 bp = cur->bc_bufs[i]; in xfs_btree_dup_cursor()
425 error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, in xfs_btree_dup_cursor()
426 XFS_BUF_ADDR(bp), mp->m_bsize, in xfs_btree_dup_cursor()
428 cur->bc_ops->buf_ops); in xfs_btree_dup_cursor()
435 new->bc_bufs[i] = bp; in xfs_btree_dup_cursor()
444 * There are two types of blocks in the btree: leaf and non-leaf blocks.
447 * the values. A non-leaf block also starts with the same header, and
449 * to the btree blocks at the previous level.
451 * +--------+-------+-------+-------+-------+-------+-------+
453 * +--------+-------+-------+-------+-------+-------+-------+
455 * +--------+-------+-------+-------+-------+-------+-------+
456 * Non-Leaf: | header | key 1 | key 2 | key N | ptr 1 | ptr 2 | ptr N |
457 * +--------+-------+-------+-------+-------+-------+-------+
473 * However, nodes are different: each pointer has two associated keys -- one
482 * +--------+-----+-----+-----+-----+-----+-------+-------+-----+
483 * Non-Leaf: | header | lo1 | hi1 | lo2 | hi2 | ... | ptr 1 | ptr 2 | ... |
484 * +--------+-----+-----+-----+-----+-----+-------+-------+-----+
487 * depth-first search and use the low and high keys to decide if we can skip
490 * entries. For a non-overlapped tree, simply search for the record associated
491 * with the lowest key and iterate forward until a non-matching record is
499 * 1: +- file A startblock B offset C length D -----------+
500 * 2: +- file E startblock F offset G length H --------------+
501 * 3: +- file I startblock F offset J length K --+
502 * 4: +- file L... --+
506 * that ends at (B+D-1) (i.e. record 1)? A LE lookup of (B+D-1) would return
508 * query would return records 1 and 2 because they both overlap (B+D-1), and
511 * In the non-overlapped case you can do a LE lookup and decrement the cursor
520 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_block_len()
521 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) in xfs_btree_block_len()
525 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) in xfs_btree_block_len()
535 return (cur->bc_flags & XFS_BTREE_LONG_PTRS) ? in xfs_btree_ptr_len()
540 * Calculate offset of the n-th record in a btree block.
548 (n - 1) * cur->bc_ops->rec_len; in xfs_btree_rec_offset()
552 * Calculate offset of the n-th key in a btree block.
560 (n - 1) * cur->bc_ops->key_len; in xfs_btree_key_offset()
564 * Calculate offset of the n-th high key in a btree block.
572 (n - 1) * cur->bc_ops->key_len + (cur->bc_ops->key_len / 2); in xfs_btree_high_key_offset()
576 * Calculate offset of the n-th block pointer in a btree block.
582 int level) in xfs_btree_ptr_offset() argument
585 cur->bc_ops->get_maxrecs(cur, level) * cur->bc_ops->key_len + in xfs_btree_ptr_offset()
586 (n - 1) * xfs_btree_ptr_len(cur); in xfs_btree_ptr_offset()
590 * Return a pointer to the n-th record in the btree block.
603 * Return a pointer to the n-th key in the btree block.
616 * Return a pointer to the n-th high key in the btree block.
629 * Return a pointer to the n-th block pointer in the btree block.
637 int level = xfs_btree_get_level(block); in xfs_btree_ptr_addr() local
639 ASSERT(block->bb_level != 0); in xfs_btree_ptr_addr()
642 ((char *)block + xfs_btree_ptr_offset(cur, n, level)); in xfs_btree_ptr_addr()
649 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE); in xfs_btree_ifork_ptr()
651 if (cur->bc_flags & XFS_BTREE_STAGING) in xfs_btree_ifork_ptr()
652 return cur->bc_ino.ifake->if_fork; in xfs_btree_ifork_ptr()
653 return XFS_IFORK_PTR(cur->bc_ino.ip, cur->bc_ino.whichfork); in xfs_btree_ifork_ptr()
668 return (struct xfs_btree_block *)ifp->if_broot; in xfs_btree_get_iroot()
672 * Retrieve the block pointer from the cursor at the given level.
678 int level, /* level in btree */ in xfs_btree_get_block() argument
681 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_get_block()
682 (level == cur->bc_nlevels - 1)) { in xfs_btree_get_block()
687 *bpp = cur->bc_bufs[level]; in xfs_btree_get_block()
692 * Change the cursor to point to the first record at the given level.
698 int level) /* level to change */ in xfs_btree_firstrec() argument
704 * Get the block pointer for this level. in xfs_btree_firstrec()
706 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_firstrec()
707 if (xfs_btree_check_block(cur, block, level, bp)) in xfs_btree_firstrec()
712 if (!block->bb_numrecs) in xfs_btree_firstrec()
717 cur->bc_ptrs[level] = 1; in xfs_btree_firstrec()
722 * Change the cursor to point to the last record in the current block
723 * at the given level. Other levels are unaffected.
728 int level) /* level to change */ in xfs_btree_lastrec() argument
734 * Get the block pointer for this level. in xfs_btree_lastrec()
736 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_lastrec()
737 if (xfs_btree_check_block(cur, block, level, bp)) in xfs_btree_lastrec()
742 if (!block->bb_numrecs) in xfs_btree_lastrec()
745 * Set the ptr value to numrecs, that's the last record/key. in xfs_btree_lastrec()
747 cur->bc_ptrs[level] = be16_to_cpu(block->bb_numrecs); in xfs_btree_lastrec()
752 * Compute first and last byte offsets for the fields given.
761 int *last) /* output: last byte offset */ in xfs_btree_offsets() argument
777 * Find the highest bit, so the last byte offset. in xfs_btree_offsets()
779 for (i = nbits - 1, imask = 1LL << i; ; i--, imask >>= 1) { in xfs_btree_offsets()
781 *last = offsets[i + 1] - 1; in xfs_btree_offsets()
789 * Long-form addressing.
805 return -EFSCORRUPTED; in xfs_btree_read_bufl()
807 error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, d, in xfs_btree_read_bufl()
808 mp->m_bsize, 0, &bp, ops); in xfs_btree_read_bufl()
818 * Read-ahead the block, don't wait for it, don't return a buffer.
819 * Long-form addressing.
833 xfs_buf_readahead(mp->m_ddev_targp, d, mp->m_bsize * count, ops); in xfs_btree_reada_bufl()
837 * Read-ahead the block, don't wait for it, don't return a buffer.
838 * Short-form addressing.
854 xfs_buf_readahead(mp->m_ddev_targp, d, mp->m_bsize * count, ops); in xfs_btree_reada_bufs()
864 xfs_fsblock_t left = be64_to_cpu(block->bb_u.l.bb_leftsib); in xfs_btree_readahead_lblock()
865 xfs_fsblock_t right = be64_to_cpu(block->bb_u.l.bb_rightsib); in xfs_btree_readahead_lblock()
868 xfs_btree_reada_bufl(cur->bc_mp, left, 1, in xfs_btree_readahead_lblock()
869 cur->bc_ops->buf_ops); in xfs_btree_readahead_lblock()
874 xfs_btree_reada_bufl(cur->bc_mp, right, 1, in xfs_btree_readahead_lblock()
875 cur->bc_ops->buf_ops); in xfs_btree_readahead_lblock()
889 xfs_agblock_t left = be32_to_cpu(block->bb_u.s.bb_leftsib); in xfs_btree_readahead_sblock()
890 xfs_agblock_t right = be32_to_cpu(block->bb_u.s.bb_rightsib); in xfs_btree_readahead_sblock()
894 xfs_btree_reada_bufs(cur->bc_mp, cur->bc_ag.agno, in xfs_btree_readahead_sblock()
895 left, 1, cur->bc_ops->buf_ops); in xfs_btree_readahead_sblock()
900 xfs_btree_reada_bufs(cur->bc_mp, cur->bc_ag.agno, in xfs_btree_readahead_sblock()
901 right, 1, cur->bc_ops->buf_ops); in xfs_btree_readahead_sblock()
909 * Read-ahead btree blocks, at the given level.
915 int lev, /* level in btree */ in xfs_btree_readahead()
921 * No readahead needed if we are at the root level and the in xfs_btree_readahead()
924 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_readahead()
925 (lev == cur->bc_nlevels - 1)) in xfs_btree_readahead()
928 if ((cur->bc_ra[lev] | lr) == cur->bc_ra[lev]) in xfs_btree_readahead()
931 cur->bc_ra[lev] |= lr; in xfs_btree_readahead()
932 block = XFS_BUF_TO_BLOCK(cur->bc_bufs[lev]); in xfs_btree_readahead()
934 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_readahead()
953 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_ptr_to_daddr()
954 fsbno = be64_to_cpu(ptr->l); in xfs_btree_ptr_to_daddr()
955 *daddr = XFS_FSB_TO_DADDR(cur->bc_mp, fsbno); in xfs_btree_ptr_to_daddr()
957 agbno = be32_to_cpu(ptr->s); in xfs_btree_ptr_to_daddr()
958 *daddr = XFS_AGB_TO_DADDR(cur->bc_mp, cur->bc_ag.agno, in xfs_btree_ptr_to_daddr()
981 xfs_buf_readahead(cur->bc_mp->m_ddev_targp, daddr, in xfs_btree_readahead_ptr()
982 cur->bc_mp->m_bsize * count, cur->bc_ops->buf_ops); in xfs_btree_readahead_ptr()
986 * Set the buffer for level "lev" in the cursor to bp, releasing
992 int lev, /* level in btree */ in xfs_btree_setbuf()
997 if (cur->bc_bufs[lev]) in xfs_btree_setbuf()
998 xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[lev]); in xfs_btree_setbuf()
999 cur->bc_bufs[lev] = bp; in xfs_btree_setbuf()
1000 cur->bc_ra[lev] = 0; in xfs_btree_setbuf()
1003 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_setbuf()
1004 if (b->bb_u.l.bb_leftsib == cpu_to_be64(NULLFSBLOCK)) in xfs_btree_setbuf()
1005 cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA; in xfs_btree_setbuf()
1006 if (b->bb_u.l.bb_rightsib == cpu_to_be64(NULLFSBLOCK)) in xfs_btree_setbuf()
1007 cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA; in xfs_btree_setbuf()
1009 if (b->bb_u.s.bb_leftsib == cpu_to_be32(NULLAGBLOCK)) in xfs_btree_setbuf()
1010 cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA; in xfs_btree_setbuf()
1011 if (b->bb_u.s.bb_rightsib == cpu_to_be32(NULLAGBLOCK)) in xfs_btree_setbuf()
1012 cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA; in xfs_btree_setbuf()
1021 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_ptr_is_null()
1022 return ptr->l == cpu_to_be64(NULLFSBLOCK); in xfs_btree_ptr_is_null()
1024 return ptr->s == cpu_to_be32(NULLAGBLOCK); in xfs_btree_ptr_is_null()
1032 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_set_ptr_null()
1033 ptr->l = cpu_to_be64(NULLFSBLOCK); in xfs_btree_set_ptr_null()
1035 ptr->s = cpu_to_be32(NULLAGBLOCK); in xfs_btree_set_ptr_null()
1050 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_get_sibling()
1052 ptr->l = block->bb_u.l.bb_rightsib; in xfs_btree_get_sibling()
1054 ptr->l = block->bb_u.l.bb_leftsib; in xfs_btree_get_sibling()
1057 ptr->s = block->bb_u.s.bb_rightsib; in xfs_btree_get_sibling()
1059 ptr->s = block->bb_u.s.bb_leftsib; in xfs_btree_get_sibling()
1072 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_set_sibling()
1074 block->bb_u.l.bb_rightsib = ptr->l; in xfs_btree_set_sibling()
1076 block->bb_u.l.bb_leftsib = ptr->l; in xfs_btree_set_sibling()
1079 block->bb_u.s.bb_rightsib = ptr->s; in xfs_btree_set_sibling()
1081 block->bb_u.s.bb_leftsib = ptr->s; in xfs_btree_set_sibling()
1091 __u16 level, in xfs_btree_init_block_int() argument
1096 int crc = xfs_sb_version_hascrc(&mp->m_sb); in xfs_btree_init_block_int()
1099 buf->bb_magic = cpu_to_be32(magic); in xfs_btree_init_block_int()
1100 buf->bb_level = cpu_to_be16(level); in xfs_btree_init_block_int()
1101 buf->bb_numrecs = cpu_to_be16(numrecs); in xfs_btree_init_block_int()
1104 buf->bb_u.l.bb_leftsib = cpu_to_be64(NULLFSBLOCK); in xfs_btree_init_block_int()
1105 buf->bb_u.l.bb_rightsib = cpu_to_be64(NULLFSBLOCK); in xfs_btree_init_block_int()
1107 buf->bb_u.l.bb_blkno = cpu_to_be64(blkno); in xfs_btree_init_block_int()
1108 buf->bb_u.l.bb_owner = cpu_to_be64(owner); in xfs_btree_init_block_int()
1109 uuid_copy(&buf->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid); in xfs_btree_init_block_int()
1110 buf->bb_u.l.bb_pad = 0; in xfs_btree_init_block_int()
1111 buf->bb_u.l.bb_lsn = 0; in xfs_btree_init_block_int()
1117 buf->bb_u.s.bb_leftsib = cpu_to_be32(NULLAGBLOCK); in xfs_btree_init_block_int()
1118 buf->bb_u.s.bb_rightsib = cpu_to_be32(NULLAGBLOCK); in xfs_btree_init_block_int()
1120 buf->bb_u.s.bb_blkno = cpu_to_be64(blkno); in xfs_btree_init_block_int()
1121 buf->bb_u.s.bb_owner = cpu_to_be32(__owner); in xfs_btree_init_block_int()
1122 uuid_copy(&buf->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid); in xfs_btree_init_block_int()
1123 buf->bb_u.s.bb_lsn = 0; in xfs_btree_init_block_int()
1133 __u16 level, in xfs_btree_init_block() argument
1137 xfs_btree_init_block_int(mp, XFS_BUF_TO_BLOCK(bp), bp->b_bn, in xfs_btree_init_block()
1138 btnum, level, numrecs, owner, 0); in xfs_btree_init_block()
1145 int level, in xfs_btree_init_block_cur() argument
1156 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_init_block_cur()
1157 owner = cur->bc_ino.ip->i_ino; in xfs_btree_init_block_cur()
1159 owner = cur->bc_ag.agno; in xfs_btree_init_block_cur()
1161 xfs_btree_init_block_int(cur->bc_mp, XFS_BUF_TO_BLOCK(bp), bp->b_bn, in xfs_btree_init_block_cur()
1162 cur->bc_btnum, level, numrecs, in xfs_btree_init_block_cur()
1163 owner, cur->bc_flags); in xfs_btree_init_block_cur()
1167 * Return true if ptr is the last record in the btree and
1175 int level) in xfs_btree_is_lastrec() argument
1179 if (level > 0) in xfs_btree_is_lastrec()
1181 if (!(cur->bc_flags & XFS_BTREE_LASTREC_UPDATE)) in xfs_btree_is_lastrec()
1196 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_buf_to_ptr()
1197 ptr->l = cpu_to_be64(XFS_DADDR_TO_FSB(cur->bc_mp, in xfs_btree_buf_to_ptr()
1200 ptr->s = cpu_to_be32(xfs_daddr_to_agbno(cur->bc_mp, in xfs_btree_buf_to_ptr()
1210 switch (cur->bc_btnum) { in xfs_btree_set_refs()
1240 struct xfs_mount *mp = cur->bc_mp; in xfs_btree_get_buf_block()
1247 error = xfs_trans_get_buf(cur->bc_tp, mp->m_ddev_targp, d, mp->m_bsize, in xfs_btree_get_buf_block()
1252 (*bpp)->b_ops = cur->bc_ops->buf_ops; in xfs_btree_get_buf_block()
1269 struct xfs_mount *mp = cur->bc_mp; in xfs_btree_read_buf_block()
1279 error = xfs_trans_read_buf(mp, cur->bc_tp, mp->m_ddev_targp, d, in xfs_btree_read_buf_block()
1280 mp->m_bsize, flags, bpp, in xfs_btree_read_buf_block()
1281 cur->bc_ops->buf_ops); in xfs_btree_read_buf_block()
1301 memcpy(dst_key, src_key, numkeys * cur->bc_ops->key_len); in xfs_btree_copy_keys()
1315 memcpy(dst_rec, src_rec, numrecs * cur->bc_ops->rec_len); in xfs_btree_copy_recs()
1345 ASSERT(dir == 1 || dir == -1); in xfs_btree_shift_keys()
1347 dst_key = (char *)key + (dir * cur->bc_ops->key_len); in xfs_btree_shift_keys()
1348 memmove(dst_key, key, numkeys * cur->bc_ops->key_len); in xfs_btree_shift_keys()
1364 ASSERT(dir == 1 || dir == -1); in xfs_btree_shift_recs()
1366 dst_rec = (char *)rec + (dir * cur->bc_ops->rec_len); in xfs_btree_shift_recs()
1367 memmove(dst_rec, rec, numrecs * cur->bc_ops->rec_len); in xfs_btree_shift_recs()
1383 ASSERT(dir == 1 || dir == -1); in xfs_btree_shift_ptrs()
1397 int last) in xfs_btree_log_keys() argument
1401 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF); in xfs_btree_log_keys()
1402 xfs_trans_log_buf(cur->bc_tp, bp, in xfs_btree_log_keys()
1404 xfs_btree_key_offset(cur, last + 1) - 1); in xfs_btree_log_keys()
1406 xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip, in xfs_btree_log_keys()
1407 xfs_ilog_fbroot(cur->bc_ino.whichfork)); in xfs_btree_log_keys()
1419 int last) in xfs_btree_log_recs() argument
1422 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF); in xfs_btree_log_recs()
1423 xfs_trans_log_buf(cur->bc_tp, bp, in xfs_btree_log_recs()
1425 xfs_btree_rec_offset(cur, last + 1) - 1); in xfs_btree_log_recs()
1437 int last) /* index of last pointer to log */ in xfs_btree_log_ptrs() argument
1442 int level = xfs_btree_get_level(block); in xfs_btree_log_ptrs() local
1444 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF); in xfs_btree_log_ptrs()
1445 xfs_trans_log_buf(cur->bc_tp, bp, in xfs_btree_log_ptrs()
1446 xfs_btree_ptr_offset(cur, first, level), in xfs_btree_log_ptrs()
1447 xfs_btree_ptr_offset(cur, last + 1, level) - 1); in xfs_btree_log_ptrs()
1449 xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip, in xfs_btree_log_ptrs()
1450 xfs_ilog_fbroot(cur->bc_ino.whichfork)); in xfs_btree_log_ptrs()
1465 int last; /* last byte offset logged */ in xfs_btree_log_block() local
1497 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) { in xfs_btree_log_block()
1512 (cur->bc_flags & XFS_BTREE_LONG_PTRS) ? in xfs_btree_log_block()
1514 nbits, &first, &last); in xfs_btree_log_block()
1515 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF); in xfs_btree_log_block()
1516 xfs_trans_log_buf(cur->bc_tp, bp, first, last); in xfs_btree_log_block()
1518 xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip, in xfs_btree_log_block()
1519 xfs_ilog_fbroot(cur->bc_ino.whichfork)); in xfs_btree_log_block()
1524 * Increment cursor by one record at the level.
1525 * For nonzero levels the leaf-ward information is untouched.
1530 int level, in xfs_btree_increment() argument
1539 ASSERT(level < cur->bc_nlevels); in xfs_btree_increment()
1541 /* Read-ahead to the right at this level. */ in xfs_btree_increment()
1542 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA); in xfs_btree_increment()
1545 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_increment()
1548 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_increment()
1554 if (++cur->bc_ptrs[level] <= xfs_btree_get_numrecs(block)) in xfs_btree_increment()
1568 for (lev = level + 1; lev < cur->bc_nlevels; lev++) { in xfs_btree_increment()
1577 if (++cur->bc_ptrs[lev] <= xfs_btree_get_numrecs(block)) in xfs_btree_increment()
1580 /* Read-ahead the right block for the next loop. */ in xfs_btree_increment()
1588 if (lev == cur->bc_nlevels) { in xfs_btree_increment()
1589 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) in xfs_btree_increment()
1592 error = -EFSCORRUPTED; in xfs_btree_increment()
1595 ASSERT(lev < cur->bc_nlevels); in xfs_btree_increment()
1601 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) { in xfs_btree_increment()
1604 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block); in xfs_btree_increment()
1605 --lev; in xfs_btree_increment()
1611 cur->bc_ptrs[lev] = 1; in xfs_btree_increment()
1626 * Decrement cursor by one record at the level.
1627 * For nonzero levels the leaf-ward information is untouched.
1632 int level, in xfs_btree_decrement() argument
1641 ASSERT(level < cur->bc_nlevels); in xfs_btree_decrement()
1643 /* Read-ahead to the left at this level. */ in xfs_btree_decrement()
1644 xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA); in xfs_btree_decrement()
1647 if (--cur->bc_ptrs[level] > 0) in xfs_btree_decrement()
1651 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_decrement()
1654 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_decrement()
1670 for (lev = level + 1; lev < cur->bc_nlevels; lev++) { in xfs_btree_decrement()
1671 if (--cur->bc_ptrs[lev] > 0) in xfs_btree_decrement()
1673 /* Read-ahead the left block for the next loop. */ in xfs_btree_decrement()
1681 if (lev == cur->bc_nlevels) { in xfs_btree_decrement()
1682 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) in xfs_btree_decrement()
1685 error = -EFSCORRUPTED; in xfs_btree_decrement()
1688 ASSERT(lev < cur->bc_nlevels); in xfs_btree_decrement()
1694 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) { in xfs_btree_decrement()
1697 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block); in xfs_btree_decrement()
1698 --lev; in xfs_btree_decrement()
1703 cur->bc_ptrs[lev] = xfs_btree_get_numrecs(block); in xfs_btree_decrement()
1720 int level, /* level in the btree */ in xfs_btree_lookup_get_block() argument
1729 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_lookup_get_block()
1730 (level == cur->bc_nlevels - 1)) { in xfs_btree_lookup_get_block()
1736 * If the old buffer at this level for the disk address we are in xfs_btree_lookup_get_block()
1737 * looking for re-use it. in xfs_btree_lookup_get_block()
1741 bp = cur->bc_bufs[level]; in xfs_btree_lookup_get_block()
1755 if (xfs_sb_version_hascrc(&cur->bc_mp->m_sb) && in xfs_btree_lookup_get_block()
1756 !(cur->bc_ino.flags & XFS_BTCUR_BMBT_INVALID_OWNER) && in xfs_btree_lookup_get_block()
1757 (cur->bc_flags & XFS_BTREE_LONG_PTRS) && in xfs_btree_lookup_get_block()
1758 be64_to_cpu((*blkp)->bb_u.l.bb_owner) != in xfs_btree_lookup_get_block()
1759 cur->bc_ino.ip->i_ino) in xfs_btree_lookup_get_block()
1762 /* Did we get the level we were looking for? */ in xfs_btree_lookup_get_block()
1763 if (be16_to_cpu((*blkp)->bb_level) != level) in xfs_btree_lookup_get_block()
1767 if (level != 0 && be16_to_cpu((*blkp)->bb_numrecs) == 0) in xfs_btree_lookup_get_block()
1770 xfs_btree_setbuf(cur, level, bp); in xfs_btree_lookup_get_block()
1776 xfs_trans_brelse(cur->bc_tp, bp); in xfs_btree_lookup_get_block()
1777 return -EFSCORRUPTED; in xfs_btree_lookup_get_block()
1781 * Get current search key. For level 0 we don't actually have a key
1788 int level, in xfs_lookup_get_search_key() argument
1793 if (level == 0) { in xfs_lookup_get_search_key()
1794 cur->bc_ops->init_key_from_rec(kp, in xfs_lookup_get_search_key()
1816 int level; /* level in the btree */ in xfs_btree_lookup() local
1822 /* No such thing as a zero-level tree. */ in xfs_btree_lookup()
1823 if (XFS_IS_CORRUPT(cur->bc_mp, cur->bc_nlevels == 0)) in xfs_btree_lookup()
1824 return -EFSCORRUPTED; in xfs_btree_lookup()
1830 cur->bc_ops->init_ptr_from_cur(cur, &ptr); in xfs_btree_lookup()
1834 * Iterate over each level in the btree, starting at the root. in xfs_btree_lookup()
1835 * For each level above the leaves, find the key we need, based in xfs_btree_lookup()
1837 * pointer down to the next level. in xfs_btree_lookup()
1839 for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) { in xfs_btree_lookup()
1841 error = xfs_btree_lookup_get_block(cur, level, pp, &block); in xfs_btree_lookup()
1847 * If we already had a key match at a higher level, we in xfs_btree_lookup()
1857 /* Set low and high entry numbers, 1-based. */ in xfs_btree_lookup()
1862 if (level != 0 || cur->bc_nlevels != 1) { in xfs_btree_lookup()
1865 cur->bc_mp, block, in xfs_btree_lookup()
1867 return -EFSCORRUPTED; in xfs_btree_lookup()
1870 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE; in xfs_btree_lookup()
1886 kp = xfs_lookup_get_search_key(cur, level, in xfs_btree_lookup()
1891 * - less than, move right in xfs_btree_lookup()
1892 * - greater than, move left in xfs_btree_lookup()
1893 * - equal, we're done in xfs_btree_lookup()
1895 diff = cur->bc_ops->key_diff(cur, kp); in xfs_btree_lookup()
1899 high = keyno - 1; in xfs_btree_lookup()
1906 * If there are more levels, set up for the next level in xfs_btree_lookup()
1909 if (level > 0) { in xfs_btree_lookup()
1914 if (diff > 0 && --keyno < 1) in xfs_btree_lookup()
1918 error = xfs_btree_debug_check_ptr(cur, pp, 0, level); in xfs_btree_lookup()
1922 cur->bc_ptrs[level] = keyno; in xfs_btree_lookup()
1931 * not the last block, we're in the wrong block. in xfs_btree_lookup()
1939 cur->bc_ptrs[0] = keyno; in xfs_btree_lookup()
1943 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) in xfs_btree_lookup()
1944 return -EFSCORRUPTED; in xfs_btree_lookup()
1949 keyno--; in xfs_btree_lookup()
1950 cur->bc_ptrs[0] = keyno; in xfs_btree_lookup()
1971 ASSERT(cur->bc_flags & XFS_BTREE_OVERLAPPING); in xfs_btree_high_key_from_key()
1973 (cur->bc_ops->key_len / 2)); in xfs_btree_high_key_from_key()
1990 cur->bc_ops->init_key_from_rec(key, rec); in xfs_btree_get_leaf_keys()
1992 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { in xfs_btree_get_leaf_keys()
1994 cur->bc_ops->init_high_key_from_rec(&max_hkey, rec); in xfs_btree_get_leaf_keys()
1997 cur->bc_ops->init_high_key_from_rec(&hkey, rec); in xfs_btree_get_leaf_keys()
1998 if (cur->bc_ops->diff_two_keys(cur, &hkey, &max_hkey) in xfs_btree_get_leaf_keys()
2004 memcpy(high, &max_hkey, cur->bc_ops->key_len / 2); in xfs_btree_get_leaf_keys()
2020 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { in xfs_btree_get_node_keys()
2022 cur->bc_ops->key_len / 2); in xfs_btree_get_node_keys()
2027 if (cur->bc_ops->diff_two_keys(cur, hkey, max_hkey) > 0) in xfs_btree_get_node_keys()
2032 memcpy(high, max_hkey, cur->bc_ops->key_len / 2); in xfs_btree_get_node_keys()
2035 cur->bc_ops->key_len); in xfs_btree_get_node_keys()
2046 if (be16_to_cpu(block->bb_level) == 0) in xfs_btree_get_keys()
2064 return (cur->bc_flags & XFS_BTREE_OVERLAPPING) || ptr == 1; in xfs_btree_needs_key_update()
2068 * Update the low and high parent keys of the given level, progressing
2070 * level do not need updating.
2075 int level, in __xfs_btree_updkeys() argument
2080 union xfs_btree_key key; /* keys from current level */ in __xfs_btree_updkeys()
2081 union xfs_btree_key *lkey; /* keys from the next level up */ in __xfs_btree_updkeys()
2083 union xfs_btree_key *nlkey; /* keys from the next level up */ in __xfs_btree_updkeys()
2088 ASSERT(cur->bc_flags & XFS_BTREE_OVERLAPPING); in __xfs_btree_updkeys()
2091 if (level + 1 >= cur->bc_nlevels) in __xfs_btree_updkeys()
2094 trace_xfs_btree_updkeys(cur, level, bp0); in __xfs_btree_updkeys()
2099 for (level++; level < cur->bc_nlevels; level++) { in __xfs_btree_updkeys()
2103 block = xfs_btree_get_block(cur, level, &bp); in __xfs_btree_updkeys()
2104 trace_xfs_btree_updkeys(cur, level, bp); in __xfs_btree_updkeys()
2106 error = xfs_btree_check_block(cur, block, level, bp); in __xfs_btree_updkeys()
2110 ptr = cur->bc_ptrs[level]; in __xfs_btree_updkeys()
2114 !(cur->bc_ops->diff_two_keys(cur, nlkey, lkey) != 0 || in __xfs_btree_updkeys()
2115 cur->bc_ops->diff_two_keys(cur, nhkey, hkey) != 0)) in __xfs_btree_updkeys()
2119 if (level + 1 >= cur->bc_nlevels) in __xfs_btree_updkeys()
2127 /* Update all the keys from some level in cursor back to the root. */
2131 int level) in xfs_btree_updkeys_force() argument
2136 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_updkeys_force()
2137 return __xfs_btree_updkeys(cur, level, block, bp, true); in xfs_btree_updkeys_force()
2141 * Update the parent keys of the given level, progressing towards the root.
2146 int level) in xfs_btree_update_keys() argument
2154 ASSERT(level >= 0); in xfs_btree_update_keys()
2156 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_update_keys()
2157 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) in xfs_btree_update_keys()
2158 return __xfs_btree_updkeys(cur, level, block, bp, false); in xfs_btree_update_keys()
2161 * Go up the tree from this level toward the root. in xfs_btree_update_keys()
2162 * At each level, update the key value to the value input. in xfs_btree_update_keys()
2163 * Stop when we reach a level where the cursor isn't pointing in xfs_btree_update_keys()
2167 for (level++, ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) { in xfs_btree_update_keys()
2171 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_update_keys()
2173 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_update_keys()
2177 ptr = cur->bc_ptrs[level]; in xfs_btree_update_keys()
2211 ptr = cur->bc_ptrs[0]; in xfs_btree_update()
2219 * If we are tracking the last record in the tree and in xfs_btree_update()
2223 cur->bc_ops->update_lastrec(cur, block, rec, in xfs_btree_update()
2241 * Move 1 record left from cur/level if possible.
2247 int level, in xfs_btree_lshift() argument
2264 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_lshift()
2265 level == cur->bc_nlevels - 1) in xfs_btree_lshift()
2269 right = xfs_btree_get_block(cur, level, &rbp); in xfs_btree_lshift()
2272 error = xfs_btree_check_block(cur, right, level, rbp); in xfs_btree_lshift()
2286 if (cur->bc_ptrs[level] <= 1) in xfs_btree_lshift()
2296 if (lrecs == cur->bc_ops->get_maxrecs(cur, level)) in xfs_btree_lshift()
2307 rrecs--; in xfs_btree_lshift()
2313 * If non-leaf, copy a key and a ptr to the left block. in xfs_btree_lshift()
2316 if (level > 0) { in xfs_btree_lshift()
2317 /* It's a non-leaf. Move keys and pointers. */ in xfs_btree_lshift()
2327 error = xfs_btree_debug_check_ptr(cur, rpp, 0, level); in xfs_btree_lshift()
2337 ASSERT(cur->bc_ops->keys_inorder(cur, in xfs_btree_lshift()
2338 xfs_btree_key_addr(cur, lrecs - 1, left), lkp)); in xfs_btree_lshift()
2349 ASSERT(cur->bc_ops->recs_inorder(cur, in xfs_btree_lshift()
2350 xfs_btree_rec_addr(cur, lrecs - 1, left), lrp)); in xfs_btree_lshift()
2362 XFS_BTREE_STATS_ADD(cur, moves, rrecs - 1); in xfs_btree_lshift()
2363 if (level > 0) { in xfs_btree_lshift()
2366 error = xfs_btree_debug_check_ptr(cur, rpp, i + 1, level); in xfs_btree_lshift()
2373 -1, rrecs); in xfs_btree_lshift()
2376 -1, rrecs); in xfs_btree_lshift()
2384 -1, rrecs); in xfs_btree_lshift()
2392 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { in xfs_btree_lshift()
2396 i = xfs_btree_firstrec(tcur, level); in xfs_btree_lshift()
2397 if (XFS_IS_CORRUPT(tcur->bc_mp, i != 1)) { in xfs_btree_lshift()
2398 error = -EFSCORRUPTED; in xfs_btree_lshift()
2402 error = xfs_btree_decrement(tcur, level, &i); in xfs_btree_lshift()
2407 error = xfs_btree_update_keys(tcur, level); in xfs_btree_lshift()
2415 error = xfs_btree_update_keys(cur, level); in xfs_btree_lshift()
2420 cur->bc_ptrs[level]--; in xfs_btree_lshift()
2438 * Move 1 record right from cur/level if possible.
2444 int level, in xfs_btree_rshift() argument
2459 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_rshift()
2460 (level == cur->bc_nlevels - 1)) in xfs_btree_rshift()
2464 left = xfs_btree_get_block(cur, level, &lbp); in xfs_btree_rshift()
2467 error = xfs_btree_check_block(cur, left, level, lbp); in xfs_btree_rshift()
2482 if (cur->bc_ptrs[level] >= lrecs) in xfs_btree_rshift()
2492 if (rrecs == cur->bc_ops->get_maxrecs(cur, level)) in xfs_btree_rshift()
2500 * copy the last left block entry to the hole. in xfs_btree_rshift()
2502 if (level > 0) { in xfs_btree_rshift()
2513 for (i = rrecs - 1; i >= 0; i--) { in xfs_btree_rshift()
2514 error = xfs_btree_debug_check_ptr(cur, rpp, i, level); in xfs_btree_rshift()
2522 error = xfs_btree_debug_check_ptr(cur, lpp, 0, level); in xfs_btree_rshift()
2533 ASSERT(cur->bc_ops->keys_inorder(cur, rkp, in xfs_btree_rshift()
2553 xfs_btree_set_numrecs(left, --lrecs); in xfs_btree_rshift()
2566 i = xfs_btree_lastrec(tcur, level); in xfs_btree_rshift()
2567 if (XFS_IS_CORRUPT(tcur->bc_mp, i != 1)) { in xfs_btree_rshift()
2568 error = -EFSCORRUPTED; in xfs_btree_rshift()
2572 error = xfs_btree_increment(tcur, level, &i); in xfs_btree_rshift()
2577 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { in xfs_btree_rshift()
2578 error = xfs_btree_update_keys(cur, level); in xfs_btree_rshift()
2584 error = xfs_btree_update_keys(tcur, level); in xfs_btree_rshift()
2606 * Split cur/level block in half.
2613 int level, in __xfs_btree_split() argument
2625 union xfs_btree_ptr rrptr; /* right-right sibling ptr */ in __xfs_btree_split()
2626 struct xfs_buf *rrbp; /* right-right buffer pointer */ in __xfs_btree_split()
2627 struct xfs_btree_block *rrblock; /* right-right btree block */ in __xfs_btree_split()
2637 left = xfs_btree_get_block(cur, level, &lbp); in __xfs_btree_split()
2640 error = xfs_btree_check_block(cur, left, level, lbp); in __xfs_btree_split()
2648 error = cur->bc_ops->alloc_block(cur, &lptr, &rptr, stat); in __xfs_btree_split()
2670 if ((lrecs & 1) && cur->bc_ptrs[level] <= rrecs + 1) in __xfs_btree_split()
2672 src_index = (lrecs - rrecs + 1); in __xfs_btree_split()
2677 lrecs -= rrecs; in __xfs_btree_split()
2686 if (level > 0) { in __xfs_btree_split()
2687 /* It's a non-leaf. Move keys and pointers. */ in __xfs_btree_split()
2699 error = xfs_btree_debug_check_ptr(cur, lpp, i, level); in __xfs_btree_split()
2755 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { in __xfs_btree_split()
2756 error = xfs_btree_update_keys(cur, level); in __xfs_btree_split()
2763 * If it's just pointing past the last entry in left, then we'll in __xfs_btree_split()
2766 if (cur->bc_ptrs[level] > lrecs + 1) { in __xfs_btree_split()
2767 xfs_btree_setbuf(cur, level, rbp); in __xfs_btree_split()
2768 cur->bc_ptrs[level] -= lrecs; in __xfs_btree_split()
2774 if (level + 1 < cur->bc_nlevels) { in __xfs_btree_split()
2778 (*curp)->bc_ptrs[level + 1]++; in __xfs_btree_split()
2793 int level; member
2822 if (args->kswapd) in xfs_btree_split_worker()
2826 xfs_trans_set_context(args->cur->bc_tp); in xfs_btree_split_worker()
2828 args->result = __xfs_btree_split(args->cur, args->level, args->ptrp, in xfs_btree_split_worker()
2829 args->key, args->curp, args->stat); in xfs_btree_split_worker()
2831 xfs_trans_clear_context(args->cur->bc_tp); in xfs_btree_split_worker()
2838 complete(args->done); in xfs_btree_split_worker()
2850 int level, in xfs_btree_split() argument
2859 if (cur->bc_btnum != XFS_BTNUM_BMAP) in xfs_btree_split()
2860 return __xfs_btree_split(cur, level, ptrp, key, curp, stat); in xfs_btree_split()
2863 args.level = level; in xfs_btree_split()
2886 int *stat) /* return status - 0 fail */ in xfs_btree_new_iroot()
2896 int level; /* btree level */ in xfs_btree_new_iroot() local
2902 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE); in xfs_btree_new_iroot()
2904 level = cur->bc_nlevels - 1; in xfs_btree_new_iroot()
2910 error = cur->bc_ops->alloc_block(cur, pp, &nptr, stat); in xfs_btree_new_iroot()
2928 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) { in xfs_btree_new_iroot()
2929 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_new_iroot()
2930 cblock->bb_u.l.bb_blkno = cpu_to_be64(cbp->b_bn); in xfs_btree_new_iroot()
2932 cblock->bb_u.s.bb_blkno = cpu_to_be64(cbp->b_bn); in xfs_btree_new_iroot()
2935 be16_add_cpu(&block->bb_level, 1); in xfs_btree_new_iroot()
2937 cur->bc_nlevels++; in xfs_btree_new_iroot()
2938 cur->bc_ptrs[level + 1] = 1; in xfs_btree_new_iroot()
2945 for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) { in xfs_btree_new_iroot()
2946 error = xfs_btree_debug_check_ptr(cur, pp, i, level); in xfs_btree_new_iroot()
2953 error = xfs_btree_debug_check_ptr(cur, &nptr, 0, level); in xfs_btree_new_iroot()
2959 xfs_iroot_realloc(cur->bc_ino.ip, in xfs_btree_new_iroot()
2960 1 - xfs_btree_get_numrecs(cblock), in xfs_btree_new_iroot()
2961 cur->bc_ino.whichfork); in xfs_btree_new_iroot()
2963 xfs_btree_setbuf(cur, level, cbp); in xfs_btree_new_iroot()
2967 * the root is at the right level. in xfs_btree_new_iroot()
2970 xfs_btree_log_keys(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs)); in xfs_btree_new_iroot()
2971 xfs_btree_log_ptrs(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs)); in xfs_btree_new_iroot()
2974 XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_ino.whichfork); in xfs_btree_new_iroot()
3005 cur->bc_ops->init_ptr_from_cur(cur, &rptr); in xfs_btree_new_root()
3008 error = cur->bc_ops->alloc_block(cur, &rptr, &lptr, stat); in xfs_btree_new_root()
3020 /* Set the root in the holding structure increasing the level by 1. */ in xfs_btree_new_root()
3021 cur->bc_ops->set_root(cur, &lptr, 1); in xfs_btree_new_root()
3024 * At the previous root level there are now two blocks: the old root, in xfs_btree_new_root()
3029 block = xfs_btree_get_block(cur, cur->bc_nlevels - 1, &bp); in xfs_btree_new_root()
3032 error = xfs_btree_check_block(cur, block, cur->bc_nlevels - 1, bp); in xfs_btree_new_root()
3062 xfs_btree_init_block_cur(cur, nbp, cur->bc_nlevels, 2); in xfs_btree_new_root()
3098 xfs_btree_setbuf(cur, cur->bc_nlevels, nbp); in xfs_btree_new_root()
3099 cur->bc_ptrs[cur->bc_nlevels] = nptr; in xfs_btree_new_root()
3100 cur->bc_nlevels++; in xfs_btree_new_root()
3113 int level, /* btree level */ in xfs_btree_make_block_unfull() argument
3124 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_make_block_unfull()
3125 level == cur->bc_nlevels - 1) { in xfs_btree_make_block_unfull()
3126 struct xfs_inode *ip = cur->bc_ino.ip; in xfs_btree_make_block_unfull()
3128 if (numrecs < cur->bc_ops->get_dmaxrecs(cur, level)) { in xfs_btree_make_block_unfull()
3130 xfs_iroot_realloc(ip, 1, cur->bc_ino.whichfork); in xfs_btree_make_block_unfull()
3140 xfs_trans_log_inode(cur->bc_tp, ip, logflags); in xfs_btree_make_block_unfull()
3147 error = xfs_btree_rshift(cur, level, stat); in xfs_btree_make_block_unfull()
3152 error = xfs_btree_lshift(cur, level, stat); in xfs_btree_make_block_unfull()
3157 *oindex = *index = cur->bc_ptrs[level]; in xfs_btree_make_block_unfull()
3164 * If this works we have to re-set our variables because we in xfs_btree_make_block_unfull()
3167 error = xfs_btree_split(cur, level, nptr, key, ncur, stat); in xfs_btree_make_block_unfull()
3172 *index = cur->bc_ptrs[level]; in xfs_btree_make_block_unfull()
3177 * Insert one record/level. Return information to the caller
3178 * allowing the next level up to proceed if necessary.
3183 int level, /* level to insert record at */ in xfs_btree_insrec() argument
3208 * root level, allocate a new root block and we're done. in xfs_btree_insrec()
3210 if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_insrec()
3211 (level >= cur->bc_nlevels)) { in xfs_btree_insrec()
3219 ptr = cur->bc_ptrs[level]; in xfs_btree_insrec()
3230 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_insrec()
3231 old_bn = bp ? bp->b_bn : XFS_BUF_DADDR_NULL; in xfs_btree_insrec()
3235 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_insrec()
3241 if (level == 0) { in xfs_btree_insrec()
3242 ASSERT(cur->bc_ops->recs_inorder(cur, rec, in xfs_btree_insrec()
3245 ASSERT(cur->bc_ops->keys_inorder(cur, key, in xfs_btree_insrec()
3253 * make the block un-full. in xfs_btree_insrec()
3256 if (numrecs == cur->bc_ops->get_maxrecs(cur, level)) { in xfs_btree_insrec()
3257 error = xfs_btree_make_block_unfull(cur, level, numrecs, in xfs_btree_insrec()
3267 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_insrec()
3271 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_insrec()
3280 XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr + 1); in xfs_btree_insrec()
3282 if (level > 0) { in xfs_btree_insrec()
3290 for (i = numrecs - ptr; i >= 0; i--) { in xfs_btree_insrec()
3291 error = xfs_btree_debug_check_ptr(cur, pp, i, level); in xfs_btree_insrec()
3296 xfs_btree_shift_keys(cur, kp, 1, numrecs - ptr + 1); in xfs_btree_insrec()
3297 xfs_btree_shift_ptrs(cur, pp, 1, numrecs - ptr + 1); in xfs_btree_insrec()
3299 error = xfs_btree_debug_check_ptr(cur, ptrp, 0, level); in xfs_btree_insrec()
3312 ASSERT(cur->bc_ops->keys_inorder(cur, kp, in xfs_btree_insrec()
3322 xfs_btree_shift_recs(cur, rp, 1, numrecs - ptr + 1); in xfs_btree_insrec()
3330 ASSERT(cur->bc_ops->recs_inorder(cur, rp, in xfs_btree_insrec()
3347 if (bp && bp->b_bn != old_bn) { in xfs_btree_insrec()
3350 error = xfs_btree_update_keys(cur, level); in xfs_btree_insrec()
3356 * If we are tracking the last record in the tree and in xfs_btree_insrec()
3359 if (xfs_btree_is_lastrec(cur, block, level)) { in xfs_btree_insrec()
3360 cur->bc_ops->update_lastrec(cur, block, rec, in xfs_btree_insrec()
3386 * A multi-level split of the tree on insert will invalidate the original
3397 int level; /* current level number in btree */ in xfs_btree_insert() local
3400 struct xfs_btree_cur *pcur; /* previous level's cursor */ in xfs_btree_insert()
3405 level = 0; in xfs_btree_insert()
3413 cur->bc_ops->init_rec_from_cur(cur, &rec); in xfs_btree_insert()
3414 cur->bc_ops->init_key_from_rec(key, &rec); in xfs_btree_insert()
3417 * Loop going up the tree, starting at the leaf level. in xfs_btree_insert()
3419 * the insert is finished with this level. in xfs_btree_insert()
3423 * Insert nrec/nptr into this level of the tree. in xfs_btree_insert()
3426 error = xfs_btree_insrec(pcur, level, &nptr, &rec, key, in xfs_btree_insert()
3434 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_insert()
3435 error = -EFSCORRUPTED; in xfs_btree_insert()
3438 level++; in xfs_btree_insert()
3448 if (cur->bc_ops->update_cursor) in xfs_btree_insert()
3449 cur->bc_ops->update_cursor(pcur, cur); in xfs_btree_insert()
3450 cur->bc_nlevels = pcur->bc_nlevels; in xfs_btree_insert()
3467 * Try to merge a non-leaf block back into the inode root.
3478 int whichfork = cur->bc_ino.whichfork; in xfs_btree_kill_iroot()
3479 struct xfs_inode *ip = cur->bc_ino.ip; in xfs_btree_kill_iroot()
3488 int level; in xfs_btree_kill_iroot() local
3497 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE); in xfs_btree_kill_iroot()
3498 ASSERT(cur->bc_nlevels > 1); in xfs_btree_kill_iroot()
3504 level = cur->bc_nlevels - 1; in xfs_btree_kill_iroot()
3505 if (level == 1) in xfs_btree_kill_iroot()
3515 cblock = xfs_btree_get_block(cur, level - 1, &cbp); in xfs_btree_kill_iroot()
3519 * Only do this if the next level will fit. in xfs_btree_kill_iroot()
3521 * instead of freeing the root you free the next level. in xfs_btree_kill_iroot()
3523 if (numrecs > cur->bc_ops->get_dmaxrecs(cur, level)) in xfs_btree_kill_iroot()
3535 index = numrecs - cur->bc_ops->get_maxrecs(cur, level); in xfs_btree_kill_iroot()
3537 xfs_iroot_realloc(cur->bc_ino.ip, index, in xfs_btree_kill_iroot()
3538 cur->bc_ino.whichfork); in xfs_btree_kill_iroot()
3539 block = ifp->if_broot; in xfs_btree_kill_iroot()
3542 be16_add_cpu(&block->bb_numrecs, index); in xfs_btree_kill_iroot()
3543 ASSERT(block->bb_numrecs == cblock->bb_numrecs); in xfs_btree_kill_iroot()
3553 error = xfs_btree_debug_check_ptr(cur, cpp, i, level - 1); in xfs_btree_kill_iroot()
3564 cur->bc_bufs[level - 1] = NULL; in xfs_btree_kill_iroot()
3565 be16_add_cpu(&block->bb_level, -1); in xfs_btree_kill_iroot()
3566 xfs_trans_log_inode(cur->bc_tp, ip, in xfs_btree_kill_iroot()
3567 XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_ino.whichfork)); in xfs_btree_kill_iroot()
3568 cur->bc_nlevels--; in xfs_btree_kill_iroot()
3580 int level, in xfs_btree_kill_root() argument
3588 * Update the root pointer, decreasing the level by 1 and then in xfs_btree_kill_root()
3591 cur->bc_ops->set_root(cur, newroot, -1); in xfs_btree_kill_root()
3597 cur->bc_bufs[level] = NULL; in xfs_btree_kill_root()
3598 cur->bc_ra[level] = 0; in xfs_btree_kill_root()
3599 cur->bc_nlevels--; in xfs_btree_kill_root()
3607 int level, in xfs_btree_dec_cursor() argument
3613 if (level > 0) { in xfs_btree_dec_cursor()
3614 error = xfs_btree_decrement(cur, level, &i); in xfs_btree_dec_cursor()
3624 * Single level of the btree record deletion routine.
3625 * Delete record pointed to by cur/level.
3627 * Return 0 for error, 1 for done, 2 to go on to the next level.
3632 int level, /* level removing record from */ in xfs_btree_delrec() argument
3633 int *stat) /* fail/done/go-on */ in xfs_btree_delrec()
3648 struct xfs_btree_block *rrblock; /* right-right btree block */ in xfs_btree_delrec()
3649 struct xfs_buf *rrbp; /* right-right buffer pointer */ in xfs_btree_delrec()
3657 ptr = cur->bc_ptrs[level]; in xfs_btree_delrec()
3664 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_delrec()
3668 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_delrec()
3680 XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr); in xfs_btree_delrec()
3683 if (level > 0) { in xfs_btree_delrec()
3691 for (i = 0; i < numrecs - ptr; i++) { in xfs_btree_delrec()
3692 error = xfs_btree_debug_check_ptr(cur, lpp, i, level); in xfs_btree_delrec()
3698 xfs_btree_shift_keys(cur, lkp, -1, numrecs - ptr); in xfs_btree_delrec()
3699 xfs_btree_shift_ptrs(cur, lpp, -1, numrecs - ptr); in xfs_btree_delrec()
3700 xfs_btree_log_keys(cur, bp, ptr, numrecs - 1); in xfs_btree_delrec()
3701 xfs_btree_log_ptrs(cur, bp, ptr, numrecs - 1); in xfs_btree_delrec()
3708 -1, numrecs - ptr); in xfs_btree_delrec()
3709 xfs_btree_log_recs(cur, bp, ptr, numrecs - 1); in xfs_btree_delrec()
3716 xfs_btree_set_numrecs(block, --numrecs); in xfs_btree_delrec()
3720 * If we are tracking the last record in the tree and in xfs_btree_delrec()
3723 if (xfs_btree_is_lastrec(cur, block, level)) { in xfs_btree_delrec()
3724 cur->bc_ops->update_lastrec(cur, block, NULL, in xfs_btree_delrec()
3729 * We're at the root level. First, shrink the root block in-memory. in xfs_btree_delrec()
3730 * Try to get rid of the next level down. If we can't then there's in xfs_btree_delrec()
3733 if (level == cur->bc_nlevels - 1) { in xfs_btree_delrec()
3734 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) { in xfs_btree_delrec()
3735 xfs_iroot_realloc(cur->bc_ino.ip, -1, in xfs_btree_delrec()
3736 cur->bc_ino.whichfork); in xfs_btree_delrec()
3742 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
3750 * If this is the root level, and there's only one entry left, in xfs_btree_delrec()
3751 * and it's NOT the leaf level, then we can get rid of this in xfs_btree_delrec()
3752 * level. in xfs_btree_delrec()
3754 if (numrecs == 1 && level > 0) { in xfs_btree_delrec()
3761 error = xfs_btree_kill_root(cur, bp, level, pp); in xfs_btree_delrec()
3764 } else if (level > 0) { in xfs_btree_delrec()
3765 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
3778 error = xfs_btree_update_keys(cur, level); in xfs_btree_delrec()
3787 if (numrecs >= cur->bc_ops->get_minrecs(cur, level)) { in xfs_btree_delrec()
3788 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
3797 * see if we can re-balance by moving only one record. in xfs_btree_delrec()
3802 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) { in xfs_btree_delrec()
3805 * into the root and delete it. Can't go up to next level, in xfs_btree_delrec()
3810 level == cur->bc_nlevels - 2) { in xfs_btree_delrec()
3813 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
3825 * disrupt the next level up. in xfs_btree_delrec()
3837 * Move the temp cursor to the last entry in the next block. in xfs_btree_delrec()
3840 i = xfs_btree_lastrec(tcur, level); in xfs_btree_delrec()
3841 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3842 error = -EFSCORRUPTED; in xfs_btree_delrec()
3846 error = xfs_btree_increment(tcur, level, &i); in xfs_btree_delrec()
3849 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3850 error = -EFSCORRUPTED; in xfs_btree_delrec()
3854 i = xfs_btree_lastrec(tcur, level); in xfs_btree_delrec()
3855 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3856 error = -EFSCORRUPTED; in xfs_btree_delrec()
3861 right = xfs_btree_get_block(tcur, level, &rbp); in xfs_btree_delrec()
3863 error = xfs_btree_check_block(tcur, right, level, rbp); in xfs_btree_delrec()
3872 * won't make it too empty, and left-shifting an entry out in xfs_btree_delrec()
3875 if (xfs_btree_get_numrecs(right) - 1 >= in xfs_btree_delrec()
3876 cur->bc_ops->get_minrecs(tcur, level)) { in xfs_btree_delrec()
3877 error = xfs_btree_lshift(tcur, level, &i); in xfs_btree_delrec()
3882 cur->bc_ops->get_minrecs(tcur, level)); in xfs_btree_delrec()
3887 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
3897 * to our block again (last record). in xfs_btree_delrec()
3901 i = xfs_btree_firstrec(tcur, level); in xfs_btree_delrec()
3902 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3903 error = -EFSCORRUPTED; in xfs_btree_delrec()
3907 error = xfs_btree_decrement(tcur, level, &i); in xfs_btree_delrec()
3910 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3911 error = -EFSCORRUPTED; in xfs_btree_delrec()
3926 i = xfs_btree_firstrec(tcur, level); in xfs_btree_delrec()
3927 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3928 error = -EFSCORRUPTED; in xfs_btree_delrec()
3932 error = xfs_btree_decrement(tcur, level, &i); in xfs_btree_delrec()
3935 i = xfs_btree_firstrec(tcur, level); in xfs_btree_delrec()
3936 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3937 error = -EFSCORRUPTED; in xfs_btree_delrec()
3942 left = xfs_btree_get_block(tcur, level, &lbp); in xfs_btree_delrec()
3944 error = xfs_btree_check_block(cur, left, level, lbp); in xfs_btree_delrec()
3953 * won't make it too empty, and right-shifting an entry out in xfs_btree_delrec()
3956 if (xfs_btree_get_numrecs(left) - 1 >= in xfs_btree_delrec()
3957 cur->bc_ops->get_minrecs(tcur, level)) { in xfs_btree_delrec()
3958 error = xfs_btree_rshift(tcur, level, &i); in xfs_btree_delrec()
3963 cur->bc_ops->get_minrecs(tcur, level)); in xfs_btree_delrec()
3966 if (level == 0) in xfs_btree_delrec()
3967 cur->bc_ptrs[0]++; in xfs_btree_delrec()
3990 cur->bc_ops->get_maxrecs(cur, level)) { in xfs_btree_delrec()
4007 cur->bc_ops->get_maxrecs(cur, level)) { in xfs_btree_delrec()
4024 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
4038 if (level > 0) { in xfs_btree_delrec()
4039 /* It's a non-leaf. Move keys and pointers. */ in xfs_btree_delrec()
4051 error = xfs_btree_debug_check_ptr(cur, rpp, i, level); in xfs_btree_delrec()
4104 cur->bc_bufs[level] = lbp; in xfs_btree_delrec()
4105 cur->bc_ptrs[level] += lrecs; in xfs_btree_delrec()
4106 cur->bc_ra[level] = 0; in xfs_btree_delrec()
4109 * If we joined with the right neighbor and there's a level above in xfs_btree_delrec()
4110 * us, increment the cursor at that level. in xfs_btree_delrec()
4112 else if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) || in xfs_btree_delrec()
4113 (level + 1 < cur->bc_nlevels)) { in xfs_btree_delrec()
4114 error = xfs_btree_increment(cur, level + 1, &i); in xfs_btree_delrec()
4120 * Readjust the ptr at this level if it's not a leaf, since it's in xfs_btree_delrec()
4123 * We can't use decrement because it would change the next level up. in xfs_btree_delrec()
4125 if (level > 0) in xfs_btree_delrec()
4126 cur->bc_ptrs[level]--; in xfs_btree_delrec()
4130 * btree supports overlapped intervals. However, bc_ptrs[level + 1] in xfs_btree_delrec()
4138 /* Return value means the next level up has something to do. */ in xfs_btree_delrec()
4159 int level; in xfs_btree_delete() local
4164 * Go up the tree, starting at leaf level. in xfs_btree_delete()
4166 * If 2 is returned then a join was done; go to the next level. in xfs_btree_delete()
4169 for (level = 0, i = 2; i == 2; level++) { in xfs_btree_delete()
4170 error = xfs_btree_delrec(cur, level, &i); in xfs_btree_delete()
4181 if (joined && (cur->bc_flags & XFS_BTREE_OVERLAPPING)) { in xfs_btree_delete()
4188 for (level = 1; level < cur->bc_nlevels; level++) { in xfs_btree_delete()
4189 if (cur->bc_ptrs[level] == 0) { in xfs_btree_delete()
4190 error = xfs_btree_decrement(cur, level, &i); in xfs_btree_delete()
4205 * Get the data from the pointed-to record.
4220 ptr = cur->bc_ptrs[0]; in xfs_btree_get_rec()
4249 int level, in xfs_btree_visit_block() argument
4259 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA); in xfs_btree_visit_block()
4260 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_visit_block()
4263 error = fn(cur, level, data); in xfs_btree_visit_block()
4270 return -ENOENT; in xfs_btree_visit_block()
4272 return xfs_btree_lookup_get_block(cur, level, &rptr, &block); in xfs_btree_visit_block()
4285 int level; in xfs_btree_visit_blocks() local
4289 cur->bc_ops->init_ptr_from_cur(cur, &lptr); in xfs_btree_visit_blocks()
4291 /* for each level */ in xfs_btree_visit_blocks()
4292 for (level = cur->bc_nlevels - 1; level >= 0; level--) { in xfs_btree_visit_blocks()
4294 error = xfs_btree_lookup_get_block(cur, level, &lptr, &block); in xfs_btree_visit_blocks()
4298 /* readahead the left most block for the next level down */ in xfs_btree_visit_blocks()
4299 if (level > 0) { in xfs_btree_visit_blocks()
4314 /* for each buffer in the level */ in xfs_btree_visit_blocks()
4316 error = xfs_btree_visit_block(cur, level, fn, data); in xfs_btree_visit_blocks()
4319 if (error != -ENOENT) in xfs_btree_visit_blocks()
4334 * We do the btree walk in the most optimal manner possible - we have sibling
4335 * pointers so we can just walk all the blocks on each level from left to right
4336 * in a single pass, and then move to the next level and do the same. We can
4358 int level, in xfs_btree_block_change_owner() argument
4366 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_block_change_owner()
4367 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_block_change_owner()
4368 if (block->bb_u.l.bb_owner == cpu_to_be64(bbcoi->new_owner)) in xfs_btree_block_change_owner()
4370 block->bb_u.l.bb_owner = cpu_to_be64(bbcoi->new_owner); in xfs_btree_block_change_owner()
4372 if (block->bb_u.s.bb_owner == cpu_to_be32(bbcoi->new_owner)) in xfs_btree_block_change_owner()
4374 block->bb_u.s.bb_owner = cpu_to_be32(bbcoi->new_owner); in xfs_btree_block_change_owner()
4381 * block is formatted into the on-disk inode fork. We still change it, in xfs_btree_block_change_owner()
4385 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE); in xfs_btree_block_change_owner()
4386 ASSERT(level == cur->bc_nlevels - 1); in xfs_btree_block_change_owner()
4390 if (cur->bc_tp) { in xfs_btree_block_change_owner()
4391 if (!xfs_trans_ordered_buf(cur->bc_tp, bp)) { in xfs_btree_block_change_owner()
4393 return -EAGAIN; in xfs_btree_block_change_owner()
4396 xfs_buf_delwri_queue(bp, bbcoi->buffer_list); in xfs_btree_block_change_owner()
4417 /* Verify the v5 fields of a long-format btree block. */
4423 struct xfs_mount *mp = bp->b_mount; in xfs_btree_lblock_v5hdr_verify()
4426 if (!xfs_sb_version_hascrc(&mp->m_sb)) in xfs_btree_lblock_v5hdr_verify()
4428 if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid)) in xfs_btree_lblock_v5hdr_verify()
4430 if (block->bb_u.l.bb_blkno != cpu_to_be64(bp->b_bn)) in xfs_btree_lblock_v5hdr_verify()
4433 be64_to_cpu(block->bb_u.l.bb_owner) != owner) in xfs_btree_lblock_v5hdr_verify()
4438 /* Verify a long-format btree block. */
4444 struct xfs_mount *mp = bp->b_mount; in xfs_btree_lblock_verify()
4448 if (be16_to_cpu(block->bb_numrecs) > max_recs) in xfs_btree_lblock_verify()
4452 if (block->bb_u.l.bb_leftsib != cpu_to_be64(NULLFSBLOCK) && in xfs_btree_lblock_verify()
4453 !xfs_verify_fsbno(mp, be64_to_cpu(block->bb_u.l.bb_leftsib))) in xfs_btree_lblock_verify()
4455 if (block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK) && in xfs_btree_lblock_verify()
4456 !xfs_verify_fsbno(mp, be64_to_cpu(block->bb_u.l.bb_rightsib))) in xfs_btree_lblock_verify()
4463 * xfs_btree_sblock_v5hdr_verify() -- verify the v5 fields of a short-format
4472 struct xfs_mount *mp = bp->b_mount; in xfs_btree_sblock_v5hdr_verify()
4474 struct xfs_perag *pag = bp->b_pag; in xfs_btree_sblock_v5hdr_verify()
4476 if (!xfs_sb_version_hascrc(&mp->m_sb)) in xfs_btree_sblock_v5hdr_verify()
4478 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid)) in xfs_btree_sblock_v5hdr_verify()
4480 if (block->bb_u.s.bb_blkno != cpu_to_be64(bp->b_bn)) in xfs_btree_sblock_v5hdr_verify()
4482 if (pag && be32_to_cpu(block->bb_u.s.bb_owner) != pag->pag_agno) in xfs_btree_sblock_v5hdr_verify()
4488 * xfs_btree_sblock_verify() -- verify a short-format btree block
4498 struct xfs_mount *mp = bp->b_mount; in xfs_btree_sblock_verify()
4503 if (be16_to_cpu(block->bb_numrecs) > max_recs) in xfs_btree_sblock_verify()
4508 if (block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK) && in xfs_btree_sblock_verify()
4509 !xfs_verify_agbno(mp, agno, be32_to_cpu(block->bb_u.s.bb_leftsib))) in xfs_btree_sblock_verify()
4511 if (block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK) && in xfs_btree_sblock_verify()
4512 !xfs_verify_agbno(mp, agno, be32_to_cpu(block->bb_u.s.bb_rightsib))) in xfs_btree_sblock_verify()
4520 * records in a short-format btree.
4527 uint level; in xfs_btree_compute_maxlevels() local
4530 maxblocks = (len + limits[0] - 1) / limits[0]; in xfs_btree_compute_maxlevels()
4531 for (level = 1; maxblocks > 1; level++) in xfs_btree_compute_maxlevels()
4532 maxblocks = (maxblocks + limits[1] - 1) / limits[1]; in xfs_btree_compute_maxlevels()
4533 return level; in xfs_btree_compute_maxlevels()
4556 ASSERT(cur->bc_ops->init_high_key_from_rec); in xfs_btree_simple_query_range()
4557 ASSERT(cur->bc_ops->diff_two_keys); in xfs_btree_simple_query_range()
4583 cur->bc_ops->init_high_key_from_rec(&rec_key, recp); in xfs_btree_simple_query_range()
4585 diff = cur->bc_ops->diff_two_keys(cur, low_key, in xfs_btree_simple_query_range()
4592 cur->bc_ops->init_key_from_rec(&rec_key, recp); in xfs_btree_simple_query_range()
4593 diff = cur->bc_ops->diff_two_keys(cur, &rec_key, high_key); in xfs_btree_simple_query_range()
4650 int level; in xfs_btree_overlapped_query_range() local
4656 level = cur->bc_nlevels - 1; in xfs_btree_overlapped_query_range()
4657 cur->bc_ops->init_ptr_from_cur(cur, &ptr); in xfs_btree_overlapped_query_range()
4658 error = xfs_btree_lookup_get_block(cur, level, &ptr, &block); in xfs_btree_overlapped_query_range()
4661 xfs_btree_get_block(cur, level, &bp); in xfs_btree_overlapped_query_range()
4662 trace_xfs_btree_overlapped_query_range(cur, level, bp); in xfs_btree_overlapped_query_range()
4664 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_overlapped_query_range()
4668 cur->bc_ptrs[level] = 1; in xfs_btree_overlapped_query_range()
4670 while (level < cur->bc_nlevels) { in xfs_btree_overlapped_query_range()
4671 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_overlapped_query_range()
4674 if (cur->bc_ptrs[level] > be16_to_cpu(block->bb_numrecs)) { in xfs_btree_overlapped_query_range()
4676 if (level < cur->bc_nlevels - 1) in xfs_btree_overlapped_query_range()
4677 cur->bc_ptrs[level + 1]++; in xfs_btree_overlapped_query_range()
4678 level++; in xfs_btree_overlapped_query_range()
4682 if (level == 0) { in xfs_btree_overlapped_query_range()
4684 recp = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block); in xfs_btree_overlapped_query_range()
4686 cur->bc_ops->init_high_key_from_rec(&rec_hkey, recp); in xfs_btree_overlapped_query_range()
4687 ldiff = cur->bc_ops->diff_two_keys(cur, &rec_hkey, in xfs_btree_overlapped_query_range()
4690 cur->bc_ops->init_key_from_rec(&rec_key, recp); in xfs_btree_overlapped_query_range()
4691 hdiff = cur->bc_ops->diff_two_keys(cur, high_key, in xfs_btree_overlapped_query_range()
4707 cur->bc_ptrs[level]++; in xfs_btree_overlapped_query_range()
4712 lkp = xfs_btree_key_addr(cur, cur->bc_ptrs[level], block); in xfs_btree_overlapped_query_range()
4713 hkp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level], block); in xfs_btree_overlapped_query_range()
4714 pp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[level], block); in xfs_btree_overlapped_query_range()
4716 ldiff = cur->bc_ops->diff_two_keys(cur, hkp, low_key); in xfs_btree_overlapped_query_range()
4717 hdiff = cur->bc_ops->diff_two_keys(cur, high_key, lkp); in xfs_btree_overlapped_query_range()
4725 level--; in xfs_btree_overlapped_query_range()
4726 error = xfs_btree_lookup_get_block(cur, level, pp, in xfs_btree_overlapped_query_range()
4730 xfs_btree_get_block(cur, level, &bp); in xfs_btree_overlapped_query_range()
4731 trace_xfs_btree_overlapped_query_range(cur, level, bp); in xfs_btree_overlapped_query_range()
4733 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_overlapped_query_range()
4737 cur->bc_ptrs[level] = 1; in xfs_btree_overlapped_query_range()
4743 cur->bc_ptrs[level]++; in xfs_btree_overlapped_query_range()
4749 * block, a subsequent non-error cursor deletion will not release in xfs_btree_overlapped_query_range()
4750 * node-level buffers, causing a buffer leak. This is quite possible in xfs_btree_overlapped_query_range()
4751 * with a zero-results range query, so release the buffers if we in xfs_btree_overlapped_query_range()
4754 if (cur->bc_bufs[0] == NULL) { in xfs_btree_overlapped_query_range()
4755 for (i = 0; i < cur->bc_nlevels; i++) { in xfs_btree_overlapped_query_range()
4756 if (cur->bc_bufs[i]) { in xfs_btree_overlapped_query_range()
4757 xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[i]); in xfs_btree_overlapped_query_range()
4758 cur->bc_bufs[i] = NULL; in xfs_btree_overlapped_query_range()
4759 cur->bc_ptrs[i] = 0; in xfs_btree_overlapped_query_range()
4760 cur->bc_ra[i] = 0; in xfs_btree_overlapped_query_range()
4772 * code. This function returns -ECANCELED, zero, or a negative error code.
4787 cur->bc_rec = *high_rec; in xfs_btree_query_range()
4788 cur->bc_ops->init_rec_from_cur(cur, &rec); in xfs_btree_query_range()
4789 cur->bc_ops->init_key_from_rec(&high_key, &rec); in xfs_btree_query_range()
4791 cur->bc_rec = *low_rec; in xfs_btree_query_range()
4792 cur->bc_ops->init_rec_from_cur(cur, &rec); in xfs_btree_query_range()
4793 cur->bc_ops->init_key_from_rec(&low_key, &rec); in xfs_btree_query_range()
4796 if (cur->bc_ops->diff_two_keys(cur, &low_key, &high_key) > 0) in xfs_btree_query_range()
4797 return -EINVAL; in xfs_btree_query_range()
4799 if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING)) in xfs_btree_query_range()
4816 memset(&cur->bc_rec, 0, sizeof(cur->bc_rec)); in xfs_btree_query_all()
4825 * in a short-format (per-AG metadata) btree.
4832 int level; in xfs_btree_calc_size() local
4837 for (level = 0, rval = 0; len > 1; level++) { in xfs_btree_calc_size()
4838 len += maxrecs - 1; in xfs_btree_calc_size()
4849 int level, in xfs_btree_count_blocks_helper() argument
4876 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_diff_two_ptrs()
4877 return (int64_t)be64_to_cpu(a->l) - be64_to_cpu(b->l); in xfs_btree_diff_two_ptrs()
4878 return (int64_t)be32_to_cpu(a->s) - be32_to_cpu(b->s); in xfs_btree_diff_two_ptrs()
4888 return -ECANCELED; in xfs_btree_has_record_helper()
4903 if (error == -ECANCELED) { in xfs_btree_has_record()
4922 if (cur->bc_ptrs[0] < xfs_btree_get_numrecs(block)) in xfs_btree_has_more_records()
4926 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_has_more_records()
4927 return block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK); in xfs_btree_has_more_records()
4929 return block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK); in xfs_btree_has_more_records()