Lines Matching +full:level +full:- +full:high
1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
49 /* Ensure we asked for crc for crc-only magics. */ in xfs_btree_magic()
62 int level, in __xfs_btree_check_lblock() argument
65 struct xfs_mount *mp = cur->bc_mp; in __xfs_btree_check_lblock()
66 xfs_btnum_t btnum = cur->bc_btnum; in __xfs_btree_check_lblock()
70 if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid)) in __xfs_btree_check_lblock()
72 if (block->bb_u.l.bb_blkno != in __xfs_btree_check_lblock()
75 if (block->bb_u.l.bb_pad != cpu_to_be32(0)) in __xfs_btree_check_lblock()
79 if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(crc, btnum)) in __xfs_btree_check_lblock()
81 if (be16_to_cpu(block->bb_level) != level) in __xfs_btree_check_lblock()
83 if (be16_to_cpu(block->bb_numrecs) > in __xfs_btree_check_lblock()
84 cur->bc_ops->get_maxrecs(cur, level)) in __xfs_btree_check_lblock()
86 if (block->bb_u.l.bb_leftsib != cpu_to_be64(NULLFSBLOCK) && in __xfs_btree_check_lblock()
87 !xfs_btree_check_lptr(cur, be64_to_cpu(block->bb_u.l.bb_leftsib), in __xfs_btree_check_lblock()
88 level + 1)) in __xfs_btree_check_lblock()
90 if (block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK) && in __xfs_btree_check_lblock()
91 !xfs_btree_check_lptr(cur, be64_to_cpu(block->bb_u.l.bb_rightsib), in __xfs_btree_check_lblock()
92 level + 1)) in __xfs_btree_check_lblock()
103 int level, in xfs_btree_check_lblock() argument
106 struct xfs_mount *mp = cur->bc_mp; in xfs_btree_check_lblock()
109 fa = __xfs_btree_check_lblock(cur, block, level, bp); in xfs_btree_check_lblock()
114 return -EFSCORRUPTED; in xfs_btree_check_lblock()
127 int level, in __xfs_btree_check_sblock() argument
130 struct xfs_mount *mp = cur->bc_mp; in __xfs_btree_check_sblock()
131 xfs_btnum_t btnum = cur->bc_btnum; in __xfs_btree_check_sblock()
135 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid)) in __xfs_btree_check_sblock()
137 if (block->bb_u.s.bb_blkno != in __xfs_btree_check_sblock()
142 if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(crc, btnum)) in __xfs_btree_check_sblock()
144 if (be16_to_cpu(block->bb_level) != level) in __xfs_btree_check_sblock()
146 if (be16_to_cpu(block->bb_numrecs) > in __xfs_btree_check_sblock()
147 cur->bc_ops->get_maxrecs(cur, level)) in __xfs_btree_check_sblock()
149 if (block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK) && in __xfs_btree_check_sblock()
150 !xfs_btree_check_sptr(cur, be32_to_cpu(block->bb_u.s.bb_leftsib), in __xfs_btree_check_sblock()
151 level + 1)) in __xfs_btree_check_sblock()
153 if (block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK) && in __xfs_btree_check_sblock()
154 !xfs_btree_check_sptr(cur, be32_to_cpu(block->bb_u.s.bb_rightsib), in __xfs_btree_check_sblock()
155 level + 1)) in __xfs_btree_check_sblock()
166 int level, in xfs_btree_check_sblock() argument
169 struct xfs_mount *mp = cur->bc_mp; in xfs_btree_check_sblock()
172 fa = __xfs_btree_check_sblock(cur, block, level, bp); in xfs_btree_check_sblock()
177 return -EFSCORRUPTED; in xfs_btree_check_sblock()
189 int level, /* level of the btree block */ in xfs_btree_check_block() argument
192 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_check_block()
193 return xfs_btree_check_lblock(cur, block, level, bp); in xfs_btree_check_block()
195 return xfs_btree_check_sblock(cur, block, level, bp); in xfs_btree_check_block()
203 int level) in xfs_btree_check_lptr() argument
205 if (level <= 0) in xfs_btree_check_lptr()
207 return xfs_verify_fsbno(cur->bc_mp, fsbno); in xfs_btree_check_lptr()
215 int level) in xfs_btree_check_sptr() argument
217 if (level <= 0) in xfs_btree_check_sptr()
219 return xfs_verify_agbno(cur->bc_mp, cur->bc_ag.pag->pag_agno, agbno); in xfs_btree_check_sptr()
223 * Check that a given (indexed) btree pointer at a certain level of a
231 int level) in xfs_btree_check_ptr() argument
233 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_check_ptr()
234 if (xfs_btree_check_lptr(cur, be64_to_cpu((&ptr->l)[index]), in xfs_btree_check_ptr()
235 level)) in xfs_btree_check_ptr()
237 xfs_err(cur->bc_mp, in xfs_btree_check_ptr()
238 "Inode %llu fork %d: Corrupt btree %d pointer at level %d index %d.", in xfs_btree_check_ptr()
239 cur->bc_ino.ip->i_ino, in xfs_btree_check_ptr()
240 cur->bc_ino.whichfork, cur->bc_btnum, in xfs_btree_check_ptr()
241 level, index); in xfs_btree_check_ptr()
243 if (xfs_btree_check_sptr(cur, be32_to_cpu((&ptr->s)[index]), in xfs_btree_check_ptr()
244 level)) in xfs_btree_check_ptr()
246 xfs_err(cur->bc_mp, in xfs_btree_check_ptr()
247 "AG %u: Corrupt btree %d pointer at level %d index %d.", in xfs_btree_check_ptr()
248 cur->bc_ag.pag->pag_agno, cur->bc_btnum, in xfs_btree_check_ptr()
249 level, index); in xfs_btree_check_ptr()
252 return -EFSCORRUPTED; in xfs_btree_check_ptr()
263 * long-form btree header.
274 struct xfs_buf_log_item *bip = bp->b_log_item; in xfs_btree_lblock_calc_crc()
276 if (!xfs_has_crc(bp->b_mount)) in xfs_btree_lblock_calc_crc()
279 block->bb_u.l.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn); in xfs_btree_lblock_calc_crc()
288 struct xfs_mount *mp = bp->b_mount; in xfs_btree_lblock_verify_crc()
291 if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.l.bb_lsn))) in xfs_btree_lblock_verify_crc()
301 * short-form btree header.
312 struct xfs_buf_log_item *bip = bp->b_log_item; in xfs_btree_sblock_calc_crc()
314 if (!xfs_has_crc(bp->b_mount)) in xfs_btree_sblock_calc_crc()
317 block->bb_u.s.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn); in xfs_btree_sblock_calc_crc()
326 struct xfs_mount *mp = bp->b_mount; in xfs_btree_sblock_verify_crc()
329 if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.s.bb_lsn))) in xfs_btree_sblock_verify_crc()
344 error = cur->bc_ops->free_block(cur, bp); in xfs_btree_free_block()
346 xfs_trans_binval(cur->bc_tp, bp); in xfs_btree_free_block()
360 int i; /* btree level */ in xfs_btree_del_cursor()
366 * code works from level n down to 0, and if we get an error along the in xfs_btree_del_cursor()
369 for (i = 0; i < cur->bc_nlevels; i++) { in xfs_btree_del_cursor()
370 if (cur->bc_bufs[i]) in xfs_btree_del_cursor()
371 xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[i]); in xfs_btree_del_cursor()
376 ASSERT(cur->bc_btnum != XFS_BTNUM_BMAP || cur->bc_ino.allocated == 0 || in xfs_btree_del_cursor()
377 xfs_is_shutdown(cur->bc_mp)); in xfs_btree_del_cursor()
378 if (unlikely(cur->bc_flags & XFS_BTREE_STAGING)) in xfs_btree_del_cursor()
379 kmem_free(cur->bc_ops); in xfs_btree_del_cursor()
380 if (!(cur->bc_flags & XFS_BTREE_LONG_PTRS) && cur->bc_ag.pag) in xfs_btree_del_cursor()
381 xfs_perag_put(cur->bc_ag.pag); in xfs_btree_del_cursor()
387 * Allocate a new one, copy the record, re-get the buffers.
396 int i; /* level number of btree block */ in xfs_btree_dup_cursor()
401 tp = cur->bc_tp; in xfs_btree_dup_cursor()
402 mp = cur->bc_mp; in xfs_btree_dup_cursor()
407 new = cur->bc_ops->dup_cursor(cur); in xfs_btree_dup_cursor()
412 new->bc_rec = cur->bc_rec; in xfs_btree_dup_cursor()
415 * For each level current, re-get the buffer and copy the ptr value. in xfs_btree_dup_cursor()
417 for (i = 0; i < new->bc_nlevels; i++) { in xfs_btree_dup_cursor()
418 new->bc_ptrs[i] = cur->bc_ptrs[i]; in xfs_btree_dup_cursor()
419 new->bc_ra[i] = cur->bc_ra[i]; in xfs_btree_dup_cursor()
420 bp = cur->bc_bufs[i]; in xfs_btree_dup_cursor()
422 error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, in xfs_btree_dup_cursor()
423 xfs_buf_daddr(bp), mp->m_bsize, in xfs_btree_dup_cursor()
425 cur->bc_ops->buf_ops); in xfs_btree_dup_cursor()
432 new->bc_bufs[i] = bp; in xfs_btree_dup_cursor()
441 * There are two types of blocks in the btree: leaf and non-leaf blocks.
444 * the values. A non-leaf block also starts with the same header, and
446 * to the btree blocks at the previous level.
448 * +--------+-------+-------+-------+-------+-------+-------+
450 * +--------+-------+-------+-------+-------+-------+-------+
452 * +--------+-------+-------+-------+-------+-------+-------+
453 * Non-Leaf: | header | key 1 | key 2 | key N | ptr 1 | ptr 2 | ptr N |
454 * +--------+-------+-------+-------+-------+-------+-------+
470 * However, nodes are different: each pointer has two associated keys -- one
475 * that matches any record in the leaf and to recursively update the high keys
479 * +--------+-----+-----+-----+-----+-----+-------+-------+-----+
480 * Non-Leaf: | header | lo1 | hi1 | lo2 | hi2 | ... | ptr 1 | ptr 2 | ... |
481 * +--------+-----+-----+-----+-----+-----+-------+-------+-----+
484 * depth-first search and use the low and high keys to decide if we can skip
487 * entries. For a non-overlapped tree, simply search for the record associated
488 * with the lowest key and iterate forward until a non-matching record is
496 * 1: +- file A startblock B offset C length D -----------+
497 * 2: +- file E startblock F offset G length H --------------+
498 * 3: +- file I startblock F offset J length K --+
499 * 4: +- file L... --+
503 * that ends at (B+D-1) (i.e. record 1)? A LE lookup of (B+D-1) would return
505 * query would return records 1 and 2 because they both overlap (B+D-1), and
508 * In the non-overlapped case you can do a LE lookup and decrement the cursor
517 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_block_len()
518 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) in xfs_btree_block_len()
522 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) in xfs_btree_block_len()
532 return (cur->bc_flags & XFS_BTREE_LONG_PTRS) ? in xfs_btree_ptr_len()
537 * Calculate offset of the n-th record in a btree block.
545 (n - 1) * cur->bc_ops->rec_len; in xfs_btree_rec_offset()
549 * Calculate offset of the n-th key in a btree block.
557 (n - 1) * cur->bc_ops->key_len; in xfs_btree_key_offset()
561 * Calculate offset of the n-th high key in a btree block.
569 (n - 1) * cur->bc_ops->key_len + (cur->bc_ops->key_len / 2); in xfs_btree_high_key_offset()
573 * Calculate offset of the n-th block pointer in a btree block.
579 int level) in xfs_btree_ptr_offset() argument
582 cur->bc_ops->get_maxrecs(cur, level) * cur->bc_ops->key_len + in xfs_btree_ptr_offset()
583 (n - 1) * xfs_btree_ptr_len(cur); in xfs_btree_ptr_offset()
587 * Return a pointer to the n-th record in the btree block.
600 * Return a pointer to the n-th key in the btree block.
613 * Return a pointer to the n-th high key in the btree block.
626 * Return a pointer to the n-th block pointer in the btree block.
634 int level = xfs_btree_get_level(block); in xfs_btree_ptr_addr() local
636 ASSERT(block->bb_level != 0); in xfs_btree_ptr_addr()
639 ((char *)block + xfs_btree_ptr_offset(cur, n, level)); in xfs_btree_ptr_addr()
646 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE); in xfs_btree_ifork_ptr()
648 if (cur->bc_flags & XFS_BTREE_STAGING) in xfs_btree_ifork_ptr()
649 return cur->bc_ino.ifake->if_fork; in xfs_btree_ifork_ptr()
650 return XFS_IFORK_PTR(cur->bc_ino.ip, cur->bc_ino.whichfork); in xfs_btree_ifork_ptr()
665 return (struct xfs_btree_block *)ifp->if_broot; in xfs_btree_get_iroot()
669 * Retrieve the block pointer from the cursor at the given level.
675 int level, /* level in btree */ in xfs_btree_get_block() argument
678 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_get_block()
679 (level == cur->bc_nlevels - 1)) { in xfs_btree_get_block()
684 *bpp = cur->bc_bufs[level]; in xfs_btree_get_block()
689 * Change the cursor to point to the first record at the given level.
695 int level) /* level to change */ in xfs_btree_firstrec() argument
701 * Get the block pointer for this level. in xfs_btree_firstrec()
703 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_firstrec()
704 if (xfs_btree_check_block(cur, block, level, bp)) in xfs_btree_firstrec()
709 if (!block->bb_numrecs) in xfs_btree_firstrec()
714 cur->bc_ptrs[level] = 1; in xfs_btree_firstrec()
720 * at the given level. Other levels are unaffected.
725 int level) /* level to change */ in xfs_btree_lastrec() argument
731 * Get the block pointer for this level. in xfs_btree_lastrec()
733 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_lastrec()
734 if (xfs_btree_check_block(cur, block, level, bp)) in xfs_btree_lastrec()
739 if (!block->bb_numrecs) in xfs_btree_lastrec()
744 cur->bc_ptrs[level] = be16_to_cpu(block->bb_numrecs); in xfs_btree_lastrec()
776 for (i = nbits - 1, imask = 1LL << i; ; i--, imask >>= 1) { in xfs_btree_offsets()
778 *last = offsets[i + 1] - 1; in xfs_btree_offsets()
786 * Long-form addressing.
802 return -EFSCORRUPTED; in xfs_btree_read_bufl()
804 error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, d, in xfs_btree_read_bufl()
805 mp->m_bsize, 0, &bp, ops); in xfs_btree_read_bufl()
815 * Read-ahead the block, don't wait for it, don't return a buffer.
816 * Long-form addressing.
830 xfs_buf_readahead(mp->m_ddev_targp, d, mp->m_bsize * count, ops); in xfs_btree_reada_bufl()
834 * Read-ahead the block, don't wait for it, don't return a buffer.
835 * Short-form addressing.
851 xfs_buf_readahead(mp->m_ddev_targp, d, mp->m_bsize * count, ops); in xfs_btree_reada_bufs()
861 xfs_fsblock_t left = be64_to_cpu(block->bb_u.l.bb_leftsib); in xfs_btree_readahead_lblock()
862 xfs_fsblock_t right = be64_to_cpu(block->bb_u.l.bb_rightsib); in xfs_btree_readahead_lblock()
865 xfs_btree_reada_bufl(cur->bc_mp, left, 1, in xfs_btree_readahead_lblock()
866 cur->bc_ops->buf_ops); in xfs_btree_readahead_lblock()
871 xfs_btree_reada_bufl(cur->bc_mp, right, 1, in xfs_btree_readahead_lblock()
872 cur->bc_ops->buf_ops); in xfs_btree_readahead_lblock()
886 xfs_agblock_t left = be32_to_cpu(block->bb_u.s.bb_leftsib); in xfs_btree_readahead_sblock()
887 xfs_agblock_t right = be32_to_cpu(block->bb_u.s.bb_rightsib); in xfs_btree_readahead_sblock()
891 xfs_btree_reada_bufs(cur->bc_mp, cur->bc_ag.pag->pag_agno, in xfs_btree_readahead_sblock()
892 left, 1, cur->bc_ops->buf_ops); in xfs_btree_readahead_sblock()
897 xfs_btree_reada_bufs(cur->bc_mp, cur->bc_ag.pag->pag_agno, in xfs_btree_readahead_sblock()
898 right, 1, cur->bc_ops->buf_ops); in xfs_btree_readahead_sblock()
906 * Read-ahead btree blocks, at the given level.
912 int lev, /* level in btree */ in xfs_btree_readahead()
918 * No readahead needed if we are at the root level and the in xfs_btree_readahead()
921 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_readahead()
922 (lev == cur->bc_nlevels - 1)) in xfs_btree_readahead()
925 if ((cur->bc_ra[lev] | lr) == cur->bc_ra[lev]) in xfs_btree_readahead()
928 cur->bc_ra[lev] |= lr; in xfs_btree_readahead()
929 block = XFS_BUF_TO_BLOCK(cur->bc_bufs[lev]); in xfs_btree_readahead()
931 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_readahead()
950 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_ptr_to_daddr()
951 fsbno = be64_to_cpu(ptr->l); in xfs_btree_ptr_to_daddr()
952 *daddr = XFS_FSB_TO_DADDR(cur->bc_mp, fsbno); in xfs_btree_ptr_to_daddr()
954 agbno = be32_to_cpu(ptr->s); in xfs_btree_ptr_to_daddr()
955 *daddr = XFS_AGB_TO_DADDR(cur->bc_mp, cur->bc_ag.pag->pag_agno, in xfs_btree_ptr_to_daddr()
978 xfs_buf_readahead(cur->bc_mp->m_ddev_targp, daddr, in xfs_btree_readahead_ptr()
979 cur->bc_mp->m_bsize * count, cur->bc_ops->buf_ops); in xfs_btree_readahead_ptr()
983 * Set the buffer for level "lev" in the cursor to bp, releasing
989 int lev, /* level in btree */ in xfs_btree_setbuf()
994 if (cur->bc_bufs[lev]) in xfs_btree_setbuf()
995 xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[lev]); in xfs_btree_setbuf()
996 cur->bc_bufs[lev] = bp; in xfs_btree_setbuf()
997 cur->bc_ra[lev] = 0; in xfs_btree_setbuf()
1000 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_setbuf()
1001 if (b->bb_u.l.bb_leftsib == cpu_to_be64(NULLFSBLOCK)) in xfs_btree_setbuf()
1002 cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA; in xfs_btree_setbuf()
1003 if (b->bb_u.l.bb_rightsib == cpu_to_be64(NULLFSBLOCK)) in xfs_btree_setbuf()
1004 cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA; in xfs_btree_setbuf()
1006 if (b->bb_u.s.bb_leftsib == cpu_to_be32(NULLAGBLOCK)) in xfs_btree_setbuf()
1007 cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA; in xfs_btree_setbuf()
1008 if (b->bb_u.s.bb_rightsib == cpu_to_be32(NULLAGBLOCK)) in xfs_btree_setbuf()
1009 cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA; in xfs_btree_setbuf()
1018 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_ptr_is_null()
1019 return ptr->l == cpu_to_be64(NULLFSBLOCK); in xfs_btree_ptr_is_null()
1021 return ptr->s == cpu_to_be32(NULLAGBLOCK); in xfs_btree_ptr_is_null()
1029 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_set_ptr_null()
1030 ptr->l = cpu_to_be64(NULLFSBLOCK); in xfs_btree_set_ptr_null()
1032 ptr->s = cpu_to_be32(NULLAGBLOCK); in xfs_btree_set_ptr_null()
1047 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_get_sibling()
1049 ptr->l = block->bb_u.l.bb_rightsib; in xfs_btree_get_sibling()
1051 ptr->l = block->bb_u.l.bb_leftsib; in xfs_btree_get_sibling()
1054 ptr->s = block->bb_u.s.bb_rightsib; in xfs_btree_get_sibling()
1056 ptr->s = block->bb_u.s.bb_leftsib; in xfs_btree_get_sibling()
1069 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_set_sibling()
1071 block->bb_u.l.bb_rightsib = ptr->l; in xfs_btree_set_sibling()
1073 block->bb_u.l.bb_leftsib = ptr->l; in xfs_btree_set_sibling()
1076 block->bb_u.s.bb_rightsib = ptr->s; in xfs_btree_set_sibling()
1078 block->bb_u.s.bb_leftsib = ptr->s; in xfs_btree_set_sibling()
1088 __u16 level, in xfs_btree_init_block_int() argument
1096 buf->bb_magic = cpu_to_be32(magic); in xfs_btree_init_block_int()
1097 buf->bb_level = cpu_to_be16(level); in xfs_btree_init_block_int()
1098 buf->bb_numrecs = cpu_to_be16(numrecs); in xfs_btree_init_block_int()
1101 buf->bb_u.l.bb_leftsib = cpu_to_be64(NULLFSBLOCK); in xfs_btree_init_block_int()
1102 buf->bb_u.l.bb_rightsib = cpu_to_be64(NULLFSBLOCK); in xfs_btree_init_block_int()
1104 buf->bb_u.l.bb_blkno = cpu_to_be64(blkno); in xfs_btree_init_block_int()
1105 buf->bb_u.l.bb_owner = cpu_to_be64(owner); in xfs_btree_init_block_int()
1106 uuid_copy(&buf->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid); in xfs_btree_init_block_int()
1107 buf->bb_u.l.bb_pad = 0; in xfs_btree_init_block_int()
1108 buf->bb_u.l.bb_lsn = 0; in xfs_btree_init_block_int()
1114 buf->bb_u.s.bb_leftsib = cpu_to_be32(NULLAGBLOCK); in xfs_btree_init_block_int()
1115 buf->bb_u.s.bb_rightsib = cpu_to_be32(NULLAGBLOCK); in xfs_btree_init_block_int()
1117 buf->bb_u.s.bb_blkno = cpu_to_be64(blkno); in xfs_btree_init_block_int()
1118 buf->bb_u.s.bb_owner = cpu_to_be32(__owner); in xfs_btree_init_block_int()
1119 uuid_copy(&buf->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid); in xfs_btree_init_block_int()
1120 buf->bb_u.s.bb_lsn = 0; in xfs_btree_init_block_int()
1130 __u16 level, in xfs_btree_init_block() argument
1135 btnum, level, numrecs, owner, 0); in xfs_btree_init_block()
1142 int level, in xfs_btree_init_block_cur() argument
1153 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_init_block_cur()
1154 owner = cur->bc_ino.ip->i_ino; in xfs_btree_init_block_cur()
1156 owner = cur->bc_ag.pag->pag_agno; in xfs_btree_init_block_cur()
1158 xfs_btree_init_block_int(cur->bc_mp, XFS_BUF_TO_BLOCK(bp), in xfs_btree_init_block_cur()
1159 xfs_buf_daddr(bp), cur->bc_btnum, level, in xfs_btree_init_block_cur()
1160 numrecs, owner, cur->bc_flags); in xfs_btree_init_block_cur()
1172 int level) in xfs_btree_is_lastrec() argument
1176 if (level > 0) in xfs_btree_is_lastrec()
1178 if (!(cur->bc_flags & XFS_BTREE_LASTREC_UPDATE)) in xfs_btree_is_lastrec()
1193 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_buf_to_ptr()
1194 ptr->l = cpu_to_be64(XFS_DADDR_TO_FSB(cur->bc_mp, in xfs_btree_buf_to_ptr()
1197 ptr->s = cpu_to_be32(xfs_daddr_to_agbno(cur->bc_mp, in xfs_btree_buf_to_ptr()
1207 switch (cur->bc_btnum) { in xfs_btree_set_refs()
1237 struct xfs_mount *mp = cur->bc_mp; in xfs_btree_get_buf_block()
1244 error = xfs_trans_get_buf(cur->bc_tp, mp->m_ddev_targp, d, mp->m_bsize, in xfs_btree_get_buf_block()
1249 (*bpp)->b_ops = cur->bc_ops->buf_ops; in xfs_btree_get_buf_block()
1266 struct xfs_mount *mp = cur->bc_mp; in xfs_btree_read_buf_block()
1276 error = xfs_trans_read_buf(mp, cur->bc_tp, mp->m_ddev_targp, d, in xfs_btree_read_buf_block()
1277 mp->m_bsize, flags, bpp, in xfs_btree_read_buf_block()
1278 cur->bc_ops->buf_ops); in xfs_btree_read_buf_block()
1298 memcpy(dst_key, src_key, numkeys * cur->bc_ops->key_len); in xfs_btree_copy_keys()
1312 memcpy(dst_rec, src_rec, numrecs * cur->bc_ops->rec_len); in xfs_btree_copy_recs()
1342 ASSERT(dir == 1 || dir == -1); in xfs_btree_shift_keys()
1344 dst_key = (char *)key + (dir * cur->bc_ops->key_len); in xfs_btree_shift_keys()
1345 memmove(dst_key, key, numkeys * cur->bc_ops->key_len); in xfs_btree_shift_keys()
1361 ASSERT(dir == 1 || dir == -1); in xfs_btree_shift_recs()
1363 dst_rec = (char *)rec + (dir * cur->bc_ops->rec_len); in xfs_btree_shift_recs()
1364 memmove(dst_rec, rec, numrecs * cur->bc_ops->rec_len); in xfs_btree_shift_recs()
1380 ASSERT(dir == 1 || dir == -1); in xfs_btree_shift_ptrs()
1398 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF); in xfs_btree_log_keys()
1399 xfs_trans_log_buf(cur->bc_tp, bp, in xfs_btree_log_keys()
1401 xfs_btree_key_offset(cur, last + 1) - 1); in xfs_btree_log_keys()
1403 xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip, in xfs_btree_log_keys()
1404 xfs_ilog_fbroot(cur->bc_ino.whichfork)); in xfs_btree_log_keys()
1419 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF); in xfs_btree_log_recs()
1420 xfs_trans_log_buf(cur->bc_tp, bp, in xfs_btree_log_recs()
1422 xfs_btree_rec_offset(cur, last + 1) - 1); in xfs_btree_log_recs()
1439 int level = xfs_btree_get_level(block); in xfs_btree_log_ptrs() local
1441 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF); in xfs_btree_log_ptrs()
1442 xfs_trans_log_buf(cur->bc_tp, bp, in xfs_btree_log_ptrs()
1443 xfs_btree_ptr_offset(cur, first, level), in xfs_btree_log_ptrs()
1444 xfs_btree_ptr_offset(cur, last + 1, level) - 1); in xfs_btree_log_ptrs()
1446 xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip, in xfs_btree_log_ptrs()
1447 xfs_ilog_fbroot(cur->bc_ino.whichfork)); in xfs_btree_log_ptrs()
1494 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) { in xfs_btree_log_block()
1509 (cur->bc_flags & XFS_BTREE_LONG_PTRS) ? in xfs_btree_log_block()
1512 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF); in xfs_btree_log_block()
1513 xfs_trans_log_buf(cur->bc_tp, bp, first, last); in xfs_btree_log_block()
1515 xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip, in xfs_btree_log_block()
1516 xfs_ilog_fbroot(cur->bc_ino.whichfork)); in xfs_btree_log_block()
1521 * Increment cursor by one record at the level.
1522 * For nonzero levels the leaf-ward information is untouched.
1527 int level, in xfs_btree_increment() argument
1536 ASSERT(level < cur->bc_nlevels); in xfs_btree_increment()
1538 /* Read-ahead to the right at this level. */ in xfs_btree_increment()
1539 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA); in xfs_btree_increment()
1542 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_increment()
1545 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_increment()
1551 if (++cur->bc_ptrs[level] <= xfs_btree_get_numrecs(block)) in xfs_btree_increment()
1565 for (lev = level + 1; lev < cur->bc_nlevels; lev++) { in xfs_btree_increment()
1574 if (++cur->bc_ptrs[lev] <= xfs_btree_get_numrecs(block)) in xfs_btree_increment()
1577 /* Read-ahead the right block for the next loop. */ in xfs_btree_increment()
1585 if (lev == cur->bc_nlevels) { in xfs_btree_increment()
1586 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) in xfs_btree_increment()
1589 error = -EFSCORRUPTED; in xfs_btree_increment()
1592 ASSERT(lev < cur->bc_nlevels); in xfs_btree_increment()
1598 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) { in xfs_btree_increment()
1601 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block); in xfs_btree_increment()
1602 --lev; in xfs_btree_increment()
1608 cur->bc_ptrs[lev] = 1; in xfs_btree_increment()
1623 * Decrement cursor by one record at the level.
1624 * For nonzero levels the leaf-ward information is untouched.
1629 int level, in xfs_btree_decrement() argument
1638 ASSERT(level < cur->bc_nlevels); in xfs_btree_decrement()
1640 /* Read-ahead to the left at this level. */ in xfs_btree_decrement()
1641 xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA); in xfs_btree_decrement()
1644 if (--cur->bc_ptrs[level] > 0) in xfs_btree_decrement()
1648 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_decrement()
1651 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_decrement()
1667 for (lev = level + 1; lev < cur->bc_nlevels; lev++) { in xfs_btree_decrement()
1668 if (--cur->bc_ptrs[lev] > 0) in xfs_btree_decrement()
1670 /* Read-ahead the left block for the next loop. */ in xfs_btree_decrement()
1678 if (lev == cur->bc_nlevels) { in xfs_btree_decrement()
1679 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) in xfs_btree_decrement()
1682 error = -EFSCORRUPTED; in xfs_btree_decrement()
1685 ASSERT(lev < cur->bc_nlevels); in xfs_btree_decrement()
1691 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) { in xfs_btree_decrement()
1694 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block); in xfs_btree_decrement()
1695 --lev; in xfs_btree_decrement()
1700 cur->bc_ptrs[lev] = xfs_btree_get_numrecs(block); in xfs_btree_decrement()
1717 int level, /* level in the btree */ in xfs_btree_lookup_get_block() argument
1726 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_lookup_get_block()
1727 (level == cur->bc_nlevels - 1)) { in xfs_btree_lookup_get_block()
1733 * If the old buffer at this level for the disk address we are in xfs_btree_lookup_get_block()
1734 * looking for re-use it. in xfs_btree_lookup_get_block()
1738 bp = cur->bc_bufs[level]; in xfs_btree_lookup_get_block()
1752 if (xfs_has_crc(cur->bc_mp) && in xfs_btree_lookup_get_block()
1753 !(cur->bc_ino.flags & XFS_BTCUR_BMBT_INVALID_OWNER) && in xfs_btree_lookup_get_block()
1754 (cur->bc_flags & XFS_BTREE_LONG_PTRS) && in xfs_btree_lookup_get_block()
1755 be64_to_cpu((*blkp)->bb_u.l.bb_owner) != in xfs_btree_lookup_get_block()
1756 cur->bc_ino.ip->i_ino) in xfs_btree_lookup_get_block()
1759 /* Did we get the level we were looking for? */ in xfs_btree_lookup_get_block()
1760 if (be16_to_cpu((*blkp)->bb_level) != level) in xfs_btree_lookup_get_block()
1764 if (level != 0 && be16_to_cpu((*blkp)->bb_numrecs) == 0) in xfs_btree_lookup_get_block()
1767 xfs_btree_setbuf(cur, level, bp); in xfs_btree_lookup_get_block()
1773 xfs_trans_brelse(cur->bc_tp, bp); in xfs_btree_lookup_get_block()
1774 return -EFSCORRUPTED; in xfs_btree_lookup_get_block()
1778 * Get current search key. For level 0 we don't actually have a key
1785 int level, in xfs_lookup_get_search_key() argument
1790 if (level == 0) { in xfs_lookup_get_search_key()
1791 cur->bc_ops->init_key_from_rec(kp, in xfs_lookup_get_search_key()
1813 int level; /* level in the btree */ in xfs_btree_lookup() local
1819 /* No such thing as a zero-level tree. */ in xfs_btree_lookup()
1820 if (XFS_IS_CORRUPT(cur->bc_mp, cur->bc_nlevels == 0)) in xfs_btree_lookup()
1821 return -EFSCORRUPTED; in xfs_btree_lookup()
1827 cur->bc_ops->init_ptr_from_cur(cur, &ptr); in xfs_btree_lookup()
1831 * Iterate over each level in the btree, starting at the root. in xfs_btree_lookup()
1832 * For each level above the leaves, find the key we need, based in xfs_btree_lookup()
1834 * pointer down to the next level. in xfs_btree_lookup()
1836 for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) { in xfs_btree_lookup()
1838 error = xfs_btree_lookup_get_block(cur, level, pp, &block); in xfs_btree_lookup()
1844 * If we already had a key match at a higher level, we in xfs_btree_lookup()
1851 int high; /* high entry number */ in xfs_btree_lookup() local
1854 /* Set low and high entry numbers, 1-based. */ in xfs_btree_lookup()
1856 high = xfs_btree_get_numrecs(block); in xfs_btree_lookup()
1857 if (!high) { in xfs_btree_lookup()
1859 if (level != 0 || cur->bc_nlevels != 1) { in xfs_btree_lookup()
1862 cur->bc_mp, block, in xfs_btree_lookup()
1864 return -EFSCORRUPTED; in xfs_btree_lookup()
1867 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE; in xfs_btree_lookup()
1873 while (low <= high) { in xfs_btree_lookup()
1879 /* keyno is average of low and high. */ in xfs_btree_lookup()
1880 keyno = (low + high) >> 1; in xfs_btree_lookup()
1883 kp = xfs_lookup_get_search_key(cur, level, in xfs_btree_lookup()
1888 * - less than, move right in xfs_btree_lookup()
1889 * - greater than, move left in xfs_btree_lookup()
1890 * - equal, we're done in xfs_btree_lookup()
1892 diff = cur->bc_ops->key_diff(cur, kp); in xfs_btree_lookup()
1896 high = keyno - 1; in xfs_btree_lookup()
1903 * If there are more levels, set up for the next level in xfs_btree_lookup()
1906 if (level > 0) { in xfs_btree_lookup()
1911 if (diff > 0 && --keyno < 1) in xfs_btree_lookup()
1915 error = xfs_btree_debug_check_ptr(cur, pp, 0, level); in xfs_btree_lookup()
1919 cur->bc_ptrs[level] = keyno; in xfs_btree_lookup()
1936 cur->bc_ptrs[0] = keyno; in xfs_btree_lookup()
1940 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) in xfs_btree_lookup()
1941 return -EFSCORRUPTED; in xfs_btree_lookup()
1946 keyno--; in xfs_btree_lookup()
1947 cur->bc_ptrs[0] = keyno; in xfs_btree_lookup()
1962 /* Find the high key storage area from a regular key. */
1968 ASSERT(cur->bc_flags & XFS_BTREE_OVERLAPPING); in xfs_btree_high_key_from_key()
1970 (cur->bc_ops->key_len / 2)); in xfs_btree_high_key_from_key()
1973 /* Determine the low (and high if overlapped) keys of a leaf block */
1983 union xfs_btree_key *high; in xfs_btree_get_leaf_keys() local
1987 cur->bc_ops->init_key_from_rec(key, rec); in xfs_btree_get_leaf_keys()
1989 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { in xfs_btree_get_leaf_keys()
1991 cur->bc_ops->init_high_key_from_rec(&max_hkey, rec); in xfs_btree_get_leaf_keys()
1994 cur->bc_ops->init_high_key_from_rec(&hkey, rec); in xfs_btree_get_leaf_keys()
1995 if (cur->bc_ops->diff_two_keys(cur, &hkey, &max_hkey) in xfs_btree_get_leaf_keys()
2000 high = xfs_btree_high_key_from_key(cur, key); in xfs_btree_get_leaf_keys()
2001 memcpy(high, &max_hkey, cur->bc_ops->key_len / 2); in xfs_btree_get_leaf_keys()
2005 /* Determine the low (and high if overlapped) keys of a node block */
2014 union xfs_btree_key *high; in xfs_btree_get_node_keys() local
2017 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { in xfs_btree_get_node_keys()
2019 cur->bc_ops->key_len / 2); in xfs_btree_get_node_keys()
2024 if (cur->bc_ops->diff_two_keys(cur, hkey, max_hkey) > 0) in xfs_btree_get_node_keys()
2028 high = xfs_btree_high_key_from_key(cur, key); in xfs_btree_get_node_keys()
2029 memcpy(high, max_hkey, cur->bc_ops->key_len / 2); in xfs_btree_get_node_keys()
2032 cur->bc_ops->key_len); in xfs_btree_get_node_keys()
2043 if (be16_to_cpu(block->bb_level) == 0) in xfs_btree_get_keys()
2061 return (cur->bc_flags & XFS_BTREE_OVERLAPPING) || ptr == 1; in xfs_btree_needs_key_update()
2065 * Update the low and high parent keys of the given level, progressing
2067 * level do not need updating.
2072 int level, in __xfs_btree_updkeys() argument
2077 union xfs_btree_key key; /* keys from current level */ in __xfs_btree_updkeys()
2078 union xfs_btree_key *lkey; /* keys from the next level up */ in __xfs_btree_updkeys()
2080 union xfs_btree_key *nlkey; /* keys from the next level up */ in __xfs_btree_updkeys()
2085 ASSERT(cur->bc_flags & XFS_BTREE_OVERLAPPING); in __xfs_btree_updkeys()
2088 if (level + 1 >= cur->bc_nlevels) in __xfs_btree_updkeys()
2091 trace_xfs_btree_updkeys(cur, level, bp0); in __xfs_btree_updkeys()
2096 for (level++; level < cur->bc_nlevels; level++) { in __xfs_btree_updkeys()
2100 block = xfs_btree_get_block(cur, level, &bp); in __xfs_btree_updkeys()
2101 trace_xfs_btree_updkeys(cur, level, bp); in __xfs_btree_updkeys()
2103 error = xfs_btree_check_block(cur, block, level, bp); in __xfs_btree_updkeys()
2107 ptr = cur->bc_ptrs[level]; in __xfs_btree_updkeys()
2111 !(cur->bc_ops->diff_two_keys(cur, nlkey, lkey) != 0 || in __xfs_btree_updkeys()
2112 cur->bc_ops->diff_two_keys(cur, nhkey, hkey) != 0)) in __xfs_btree_updkeys()
2116 if (level + 1 >= cur->bc_nlevels) in __xfs_btree_updkeys()
2124 /* Update all the keys from some level in cursor back to the root. */
2128 int level) in xfs_btree_updkeys_force() argument
2133 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_updkeys_force()
2134 return __xfs_btree_updkeys(cur, level, block, bp, true); in xfs_btree_updkeys_force()
2138 * Update the parent keys of the given level, progressing towards the root.
2143 int level) in xfs_btree_update_keys() argument
2151 ASSERT(level >= 0); in xfs_btree_update_keys()
2153 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_update_keys()
2154 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) in xfs_btree_update_keys()
2155 return __xfs_btree_updkeys(cur, level, block, bp, false); in xfs_btree_update_keys()
2158 * Go up the tree from this level toward the root. in xfs_btree_update_keys()
2159 * At each level, update the key value to the value input. in xfs_btree_update_keys()
2160 * Stop when we reach a level where the cursor isn't pointing in xfs_btree_update_keys()
2164 for (level++, ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) { in xfs_btree_update_keys()
2168 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_update_keys()
2170 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_update_keys()
2174 ptr = cur->bc_ptrs[level]; in xfs_btree_update_keys()
2208 ptr = cur->bc_ptrs[0]; in xfs_btree_update()
2220 cur->bc_ops->update_lastrec(cur, block, rec, in xfs_btree_update()
2238 * Move 1 record left from cur/level if possible.
2244 int level, in xfs_btree_lshift() argument
2261 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_lshift()
2262 level == cur->bc_nlevels - 1) in xfs_btree_lshift()
2266 right = xfs_btree_get_block(cur, level, &rbp); in xfs_btree_lshift()
2269 error = xfs_btree_check_block(cur, right, level, rbp); in xfs_btree_lshift()
2283 if (cur->bc_ptrs[level] <= 1) in xfs_btree_lshift()
2293 if (lrecs == cur->bc_ops->get_maxrecs(cur, level)) in xfs_btree_lshift()
2304 rrecs--; in xfs_btree_lshift()
2310 * If non-leaf, copy a key and a ptr to the left block. in xfs_btree_lshift()
2313 if (level > 0) { in xfs_btree_lshift()
2314 /* It's a non-leaf. Move keys and pointers. */ in xfs_btree_lshift()
2324 error = xfs_btree_debug_check_ptr(cur, rpp, 0, level); in xfs_btree_lshift()
2334 ASSERT(cur->bc_ops->keys_inorder(cur, in xfs_btree_lshift()
2335 xfs_btree_key_addr(cur, lrecs - 1, left), lkp)); in xfs_btree_lshift()
2346 ASSERT(cur->bc_ops->recs_inorder(cur, in xfs_btree_lshift()
2347 xfs_btree_rec_addr(cur, lrecs - 1, left), lrp)); in xfs_btree_lshift()
2359 XFS_BTREE_STATS_ADD(cur, moves, rrecs - 1); in xfs_btree_lshift()
2360 if (level > 0) { in xfs_btree_lshift()
2363 error = xfs_btree_debug_check_ptr(cur, rpp, i + 1, level); in xfs_btree_lshift()
2370 -1, rrecs); in xfs_btree_lshift()
2373 -1, rrecs); in xfs_btree_lshift()
2381 -1, rrecs); in xfs_btree_lshift()
2389 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { in xfs_btree_lshift()
2393 i = xfs_btree_firstrec(tcur, level); in xfs_btree_lshift()
2394 if (XFS_IS_CORRUPT(tcur->bc_mp, i != 1)) { in xfs_btree_lshift()
2395 error = -EFSCORRUPTED; in xfs_btree_lshift()
2399 error = xfs_btree_decrement(tcur, level, &i); in xfs_btree_lshift()
2403 /* Update the parent high keys of the left block, if needed. */ in xfs_btree_lshift()
2404 error = xfs_btree_update_keys(tcur, level); in xfs_btree_lshift()
2412 error = xfs_btree_update_keys(cur, level); in xfs_btree_lshift()
2417 cur->bc_ptrs[level]--; in xfs_btree_lshift()
2435 * Move 1 record right from cur/level if possible.
2441 int level, in xfs_btree_rshift() argument
2456 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_rshift()
2457 (level == cur->bc_nlevels - 1)) in xfs_btree_rshift()
2461 left = xfs_btree_get_block(cur, level, &lbp); in xfs_btree_rshift()
2464 error = xfs_btree_check_block(cur, left, level, lbp); in xfs_btree_rshift()
2479 if (cur->bc_ptrs[level] >= lrecs) in xfs_btree_rshift()
2489 if (rrecs == cur->bc_ops->get_maxrecs(cur, level)) in xfs_btree_rshift()
2499 if (level > 0) { in xfs_btree_rshift()
2510 for (i = rrecs - 1; i >= 0; i--) { in xfs_btree_rshift()
2511 error = xfs_btree_debug_check_ptr(cur, rpp, i, level); in xfs_btree_rshift()
2519 error = xfs_btree_debug_check_ptr(cur, lpp, 0, level); in xfs_btree_rshift()
2530 ASSERT(cur->bc_ops->keys_inorder(cur, rkp, in xfs_btree_rshift()
2550 xfs_btree_set_numrecs(left, --lrecs); in xfs_btree_rshift()
2563 i = xfs_btree_lastrec(tcur, level); in xfs_btree_rshift()
2564 if (XFS_IS_CORRUPT(tcur->bc_mp, i != 1)) { in xfs_btree_rshift()
2565 error = -EFSCORRUPTED; in xfs_btree_rshift()
2569 error = xfs_btree_increment(tcur, level, &i); in xfs_btree_rshift()
2573 /* Update the parent high keys of the left block, if needed. */ in xfs_btree_rshift()
2574 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { in xfs_btree_rshift()
2575 error = xfs_btree_update_keys(cur, level); in xfs_btree_rshift()
2581 error = xfs_btree_update_keys(tcur, level); in xfs_btree_rshift()
2603 * Split cur/level block in half.
2610 int level, in __xfs_btree_split() argument
2622 union xfs_btree_ptr rrptr; /* right-right sibling ptr */ in __xfs_btree_split()
2623 struct xfs_buf *rrbp; /* right-right buffer pointer */ in __xfs_btree_split()
2624 struct xfs_btree_block *rrblock; /* right-right btree block */ in __xfs_btree_split()
2634 left = xfs_btree_get_block(cur, level, &lbp); in __xfs_btree_split()
2637 error = xfs_btree_check_block(cur, left, level, lbp); in __xfs_btree_split()
2645 error = cur->bc_ops->alloc_block(cur, &lptr, &rptr, stat); in __xfs_btree_split()
2667 if ((lrecs & 1) && cur->bc_ptrs[level] <= rrecs + 1) in __xfs_btree_split()
2669 src_index = (lrecs - rrecs + 1); in __xfs_btree_split()
2674 lrecs -= rrecs; in __xfs_btree_split()
2683 if (level > 0) { in __xfs_btree_split()
2684 /* It's a non-leaf. Move keys and pointers. */ in __xfs_btree_split()
2696 error = xfs_btree_debug_check_ptr(cur, lpp, i, level); in __xfs_btree_split()
2751 /* Update the parent high keys of the left block, if needed. */ in __xfs_btree_split()
2752 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { in __xfs_btree_split()
2753 error = xfs_btree_update_keys(cur, level); in __xfs_btree_split()
2763 if (cur->bc_ptrs[level] > lrecs + 1) { in __xfs_btree_split()
2764 xfs_btree_setbuf(cur, level, rbp); in __xfs_btree_split()
2765 cur->bc_ptrs[level] -= lrecs; in __xfs_btree_split()
2771 if (level + 1 < cur->bc_nlevels) { in __xfs_btree_split()
2775 (*curp)->bc_ptrs[level + 1]++; in __xfs_btree_split()
2790 int level; member
2819 if (args->kswapd) in xfs_btree_split_worker()
2823 xfs_trans_set_context(args->cur->bc_tp); in xfs_btree_split_worker()
2825 args->result = __xfs_btree_split(args->cur, args->level, args->ptrp, in xfs_btree_split_worker()
2826 args->key, args->curp, args->stat); in xfs_btree_split_worker()
2828 xfs_trans_clear_context(args->cur->bc_tp); in xfs_btree_split_worker()
2835 complete(args->done); in xfs_btree_split_worker()
2847 int level, in xfs_btree_split() argument
2856 if (cur->bc_btnum != XFS_BTNUM_BMAP) in xfs_btree_split()
2857 return __xfs_btree_split(cur, level, ptrp, key, curp, stat); in xfs_btree_split()
2860 args.level = level; in xfs_btree_split()
2883 int *stat) /* return status - 0 fail */ in xfs_btree_new_iroot()
2893 int level; /* btree level */ in xfs_btree_new_iroot() local
2899 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE); in xfs_btree_new_iroot()
2901 level = cur->bc_nlevels - 1; in xfs_btree_new_iroot()
2907 error = cur->bc_ops->alloc_block(cur, pp, &nptr, stat); in xfs_btree_new_iroot()
2925 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) { in xfs_btree_new_iroot()
2927 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_new_iroot()
2928 cblock->bb_u.l.bb_blkno = bno; in xfs_btree_new_iroot()
2930 cblock->bb_u.s.bb_blkno = bno; in xfs_btree_new_iroot()
2933 be16_add_cpu(&block->bb_level, 1); in xfs_btree_new_iroot()
2935 cur->bc_nlevels++; in xfs_btree_new_iroot()
2936 cur->bc_ptrs[level + 1] = 1; in xfs_btree_new_iroot()
2943 for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) { in xfs_btree_new_iroot()
2944 error = xfs_btree_debug_check_ptr(cur, pp, i, level); in xfs_btree_new_iroot()
2951 error = xfs_btree_debug_check_ptr(cur, &nptr, 0, level); in xfs_btree_new_iroot()
2957 xfs_iroot_realloc(cur->bc_ino.ip, in xfs_btree_new_iroot()
2958 1 - xfs_btree_get_numrecs(cblock), in xfs_btree_new_iroot()
2959 cur->bc_ino.whichfork); in xfs_btree_new_iroot()
2961 xfs_btree_setbuf(cur, level, cbp); in xfs_btree_new_iroot()
2965 * the root is at the right level. in xfs_btree_new_iroot()
2968 xfs_btree_log_keys(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs)); in xfs_btree_new_iroot()
2969 xfs_btree_log_ptrs(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs)); in xfs_btree_new_iroot()
2972 XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_ino.whichfork); in xfs_btree_new_iroot()
3003 cur->bc_ops->init_ptr_from_cur(cur, &rptr); in xfs_btree_new_root()
3006 error = cur->bc_ops->alloc_block(cur, &rptr, &lptr, stat); in xfs_btree_new_root()
3018 /* Set the root in the holding structure increasing the level by 1. */ in xfs_btree_new_root()
3019 cur->bc_ops->set_root(cur, &lptr, 1); in xfs_btree_new_root()
3022 * At the previous root level there are now two blocks: the old root, in xfs_btree_new_root()
3027 block = xfs_btree_get_block(cur, cur->bc_nlevels - 1, &bp); in xfs_btree_new_root()
3030 error = xfs_btree_check_block(cur, block, cur->bc_nlevels - 1, bp); in xfs_btree_new_root()
3060 xfs_btree_init_block_cur(cur, nbp, cur->bc_nlevels, 2); in xfs_btree_new_root()
3096 xfs_btree_setbuf(cur, cur->bc_nlevels, nbp); in xfs_btree_new_root()
3097 cur->bc_ptrs[cur->bc_nlevels] = nptr; in xfs_btree_new_root()
3098 cur->bc_nlevels++; in xfs_btree_new_root()
3111 int level, /* btree level */ in xfs_btree_make_block_unfull() argument
3122 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_make_block_unfull()
3123 level == cur->bc_nlevels - 1) { in xfs_btree_make_block_unfull()
3124 struct xfs_inode *ip = cur->bc_ino.ip; in xfs_btree_make_block_unfull()
3126 if (numrecs < cur->bc_ops->get_dmaxrecs(cur, level)) { in xfs_btree_make_block_unfull()
3128 xfs_iroot_realloc(ip, 1, cur->bc_ino.whichfork); in xfs_btree_make_block_unfull()
3138 xfs_trans_log_inode(cur->bc_tp, ip, logflags); in xfs_btree_make_block_unfull()
3145 error = xfs_btree_rshift(cur, level, stat); in xfs_btree_make_block_unfull()
3150 error = xfs_btree_lshift(cur, level, stat); in xfs_btree_make_block_unfull()
3155 *oindex = *index = cur->bc_ptrs[level]; in xfs_btree_make_block_unfull()
3162 * If this works we have to re-set our variables because we in xfs_btree_make_block_unfull()
3165 error = xfs_btree_split(cur, level, nptr, key, ncur, stat); in xfs_btree_make_block_unfull()
3170 *index = cur->bc_ptrs[level]; in xfs_btree_make_block_unfull()
3175 * Insert one record/level. Return information to the caller
3176 * allowing the next level up to proceed if necessary.
3181 int level, /* level to insert record at */ in xfs_btree_insrec() argument
3206 * root level, allocate a new root block and we're done. in xfs_btree_insrec()
3208 if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_insrec()
3209 (level >= cur->bc_nlevels)) { in xfs_btree_insrec()
3217 ptr = cur->bc_ptrs[level]; in xfs_btree_insrec()
3228 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_insrec()
3233 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_insrec()
3239 if (level == 0) { in xfs_btree_insrec()
3240 ASSERT(cur->bc_ops->recs_inorder(cur, rec, in xfs_btree_insrec()
3243 ASSERT(cur->bc_ops->keys_inorder(cur, key, in xfs_btree_insrec()
3251 * make the block un-full. in xfs_btree_insrec()
3254 if (numrecs == cur->bc_ops->get_maxrecs(cur, level)) { in xfs_btree_insrec()
3255 error = xfs_btree_make_block_unfull(cur, level, numrecs, in xfs_btree_insrec()
3265 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_insrec()
3269 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_insrec()
3278 XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr + 1); in xfs_btree_insrec()
3280 if (level > 0) { in xfs_btree_insrec()
3288 for (i = numrecs - ptr; i >= 0; i--) { in xfs_btree_insrec()
3289 error = xfs_btree_debug_check_ptr(cur, pp, i, level); in xfs_btree_insrec()
3294 xfs_btree_shift_keys(cur, kp, 1, numrecs - ptr + 1); in xfs_btree_insrec()
3295 xfs_btree_shift_ptrs(cur, pp, 1, numrecs - ptr + 1); in xfs_btree_insrec()
3297 error = xfs_btree_debug_check_ptr(cur, ptrp, 0, level); in xfs_btree_insrec()
3310 ASSERT(cur->bc_ops->keys_inorder(cur, kp, in xfs_btree_insrec()
3320 xfs_btree_shift_recs(cur, rp, 1, numrecs - ptr + 1); in xfs_btree_insrec()
3328 ASSERT(cur->bc_ops->recs_inorder(cur, rp, in xfs_btree_insrec()
3348 error = xfs_btree_update_keys(cur, level); in xfs_btree_insrec()
3357 if (xfs_btree_is_lastrec(cur, block, level)) { in xfs_btree_insrec()
3358 cur->bc_ops->update_lastrec(cur, block, rec, in xfs_btree_insrec()
3382 * A multi-level split of the tree on insert will invalidate the original
3393 int level; /* current level number in btree */ in xfs_btree_insert() local
3396 struct xfs_btree_cur *pcur; /* previous level's cursor */ in xfs_btree_insert()
3401 level = 0; in xfs_btree_insert()
3409 cur->bc_ops->init_rec_from_cur(cur, &rec); in xfs_btree_insert()
3410 cur->bc_ops->init_key_from_rec(key, &rec); in xfs_btree_insert()
3413 * Loop going up the tree, starting at the leaf level. in xfs_btree_insert()
3415 * the insert is finished with this level. in xfs_btree_insert()
3419 * Insert nrec/nptr into this level of the tree. in xfs_btree_insert()
3422 error = xfs_btree_insrec(pcur, level, &nptr, &rec, key, in xfs_btree_insert()
3430 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_insert()
3431 error = -EFSCORRUPTED; in xfs_btree_insert()
3434 level++; in xfs_btree_insert()
3444 if (cur->bc_ops->update_cursor) in xfs_btree_insert()
3445 cur->bc_ops->update_cursor(pcur, cur); in xfs_btree_insert()
3446 cur->bc_nlevels = pcur->bc_nlevels; in xfs_btree_insert()
3463 * Try to merge a non-leaf block back into the inode root.
3474 int whichfork = cur->bc_ino.whichfork; in xfs_btree_kill_iroot()
3475 struct xfs_inode *ip = cur->bc_ino.ip; in xfs_btree_kill_iroot()
3484 int level; in xfs_btree_kill_iroot() local
3493 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE); in xfs_btree_kill_iroot()
3494 ASSERT(cur->bc_nlevels > 1); in xfs_btree_kill_iroot()
3500 level = cur->bc_nlevels - 1; in xfs_btree_kill_iroot()
3501 if (level == 1) in xfs_btree_kill_iroot()
3511 cblock = xfs_btree_get_block(cur, level - 1, &cbp); in xfs_btree_kill_iroot()
3515 * Only do this if the next level will fit. in xfs_btree_kill_iroot()
3517 * instead of freeing the root you free the next level. in xfs_btree_kill_iroot()
3519 if (numrecs > cur->bc_ops->get_dmaxrecs(cur, level)) in xfs_btree_kill_iroot()
3531 index = numrecs - cur->bc_ops->get_maxrecs(cur, level); in xfs_btree_kill_iroot()
3533 xfs_iroot_realloc(cur->bc_ino.ip, index, in xfs_btree_kill_iroot()
3534 cur->bc_ino.whichfork); in xfs_btree_kill_iroot()
3535 block = ifp->if_broot; in xfs_btree_kill_iroot()
3538 be16_add_cpu(&block->bb_numrecs, index); in xfs_btree_kill_iroot()
3539 ASSERT(block->bb_numrecs == cblock->bb_numrecs); in xfs_btree_kill_iroot()
3549 error = xfs_btree_debug_check_ptr(cur, cpp, i, level - 1); in xfs_btree_kill_iroot()
3560 cur->bc_bufs[level - 1] = NULL; in xfs_btree_kill_iroot()
3561 be16_add_cpu(&block->bb_level, -1); in xfs_btree_kill_iroot()
3562 xfs_trans_log_inode(cur->bc_tp, ip, in xfs_btree_kill_iroot()
3563 XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_ino.whichfork)); in xfs_btree_kill_iroot()
3564 cur->bc_nlevels--; in xfs_btree_kill_iroot()
3576 int level, in xfs_btree_kill_root() argument
3584 * Update the root pointer, decreasing the level by 1 and then in xfs_btree_kill_root()
3587 cur->bc_ops->set_root(cur, newroot, -1); in xfs_btree_kill_root()
3593 cur->bc_bufs[level] = NULL; in xfs_btree_kill_root()
3594 cur->bc_ra[level] = 0; in xfs_btree_kill_root()
3595 cur->bc_nlevels--; in xfs_btree_kill_root()
3603 int level, in xfs_btree_dec_cursor() argument
3609 if (level > 0) { in xfs_btree_dec_cursor()
3610 error = xfs_btree_decrement(cur, level, &i); in xfs_btree_dec_cursor()
3620 * Single level of the btree record deletion routine.
3621 * Delete record pointed to by cur/level.
3623 * Return 0 for error, 1 for done, 2 to go on to the next level.
3628 int level, /* level removing record from */ in xfs_btree_delrec() argument
3629 int *stat) /* fail/done/go-on */ in xfs_btree_delrec()
3644 struct xfs_btree_block *rrblock; /* right-right btree block */ in xfs_btree_delrec()
3645 struct xfs_buf *rrbp; /* right-right buffer pointer */ in xfs_btree_delrec()
3653 ptr = cur->bc_ptrs[level]; in xfs_btree_delrec()
3660 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_delrec()
3664 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_delrec()
3676 XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr); in xfs_btree_delrec()
3679 if (level > 0) { in xfs_btree_delrec()
3687 for (i = 0; i < numrecs - ptr; i++) { in xfs_btree_delrec()
3688 error = xfs_btree_debug_check_ptr(cur, lpp, i, level); in xfs_btree_delrec()
3694 xfs_btree_shift_keys(cur, lkp, -1, numrecs - ptr); in xfs_btree_delrec()
3695 xfs_btree_shift_ptrs(cur, lpp, -1, numrecs - ptr); in xfs_btree_delrec()
3696 xfs_btree_log_keys(cur, bp, ptr, numrecs - 1); in xfs_btree_delrec()
3697 xfs_btree_log_ptrs(cur, bp, ptr, numrecs - 1); in xfs_btree_delrec()
3704 -1, numrecs - ptr); in xfs_btree_delrec()
3705 xfs_btree_log_recs(cur, bp, ptr, numrecs - 1); in xfs_btree_delrec()
3712 xfs_btree_set_numrecs(block, --numrecs); in xfs_btree_delrec()
3719 if (xfs_btree_is_lastrec(cur, block, level)) { in xfs_btree_delrec()
3720 cur->bc_ops->update_lastrec(cur, block, NULL, in xfs_btree_delrec()
3725 * We're at the root level. First, shrink the root block in-memory. in xfs_btree_delrec()
3726 * Try to get rid of the next level down. If we can't then there's in xfs_btree_delrec()
3729 if (level == cur->bc_nlevels - 1) { in xfs_btree_delrec()
3730 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) { in xfs_btree_delrec()
3731 xfs_iroot_realloc(cur->bc_ino.ip, -1, in xfs_btree_delrec()
3732 cur->bc_ino.whichfork); in xfs_btree_delrec()
3738 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
3746 * If this is the root level, and there's only one entry left, in xfs_btree_delrec()
3747 * and it's NOT the leaf level, then we can get rid of this in xfs_btree_delrec()
3748 * level. in xfs_btree_delrec()
3750 if (numrecs == 1 && level > 0) { in xfs_btree_delrec()
3757 error = xfs_btree_kill_root(cur, bp, level, pp); in xfs_btree_delrec()
3760 } else if (level > 0) { in xfs_btree_delrec()
3761 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
3774 error = xfs_btree_update_keys(cur, level); in xfs_btree_delrec()
3783 if (numrecs >= cur->bc_ops->get_minrecs(cur, level)) { in xfs_btree_delrec()
3784 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
3793 * see if we can re-balance by moving only one record. in xfs_btree_delrec()
3798 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) { in xfs_btree_delrec()
3801 * into the root and delete it. Can't go up to next level, in xfs_btree_delrec()
3806 level == cur->bc_nlevels - 2) { in xfs_btree_delrec()
3809 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
3821 * disrupt the next level up. in xfs_btree_delrec()
3836 i = xfs_btree_lastrec(tcur, level); in xfs_btree_delrec()
3837 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3838 error = -EFSCORRUPTED; in xfs_btree_delrec()
3842 error = xfs_btree_increment(tcur, level, &i); in xfs_btree_delrec()
3845 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3846 error = -EFSCORRUPTED; in xfs_btree_delrec()
3850 i = xfs_btree_lastrec(tcur, level); in xfs_btree_delrec()
3851 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3852 error = -EFSCORRUPTED; in xfs_btree_delrec()
3857 right = xfs_btree_get_block(tcur, level, &rbp); in xfs_btree_delrec()
3859 error = xfs_btree_check_block(tcur, right, level, rbp); in xfs_btree_delrec()
3868 * won't make it too empty, and left-shifting an entry out in xfs_btree_delrec()
3871 if (xfs_btree_get_numrecs(right) - 1 >= in xfs_btree_delrec()
3872 cur->bc_ops->get_minrecs(tcur, level)) { in xfs_btree_delrec()
3873 error = xfs_btree_lshift(tcur, level, &i); in xfs_btree_delrec()
3878 cur->bc_ops->get_minrecs(tcur, level)); in xfs_btree_delrec()
3883 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
3897 i = xfs_btree_firstrec(tcur, level); in xfs_btree_delrec()
3898 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3899 error = -EFSCORRUPTED; in xfs_btree_delrec()
3903 error = xfs_btree_decrement(tcur, level, &i); in xfs_btree_delrec()
3906 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3907 error = -EFSCORRUPTED; in xfs_btree_delrec()
3922 i = xfs_btree_firstrec(tcur, level); in xfs_btree_delrec()
3923 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3924 error = -EFSCORRUPTED; in xfs_btree_delrec()
3928 error = xfs_btree_decrement(tcur, level, &i); in xfs_btree_delrec()
3931 i = xfs_btree_firstrec(tcur, level); in xfs_btree_delrec()
3932 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3933 error = -EFSCORRUPTED; in xfs_btree_delrec()
3938 left = xfs_btree_get_block(tcur, level, &lbp); in xfs_btree_delrec()
3940 error = xfs_btree_check_block(cur, left, level, lbp); in xfs_btree_delrec()
3949 * won't make it too empty, and right-shifting an entry out in xfs_btree_delrec()
3952 if (xfs_btree_get_numrecs(left) - 1 >= in xfs_btree_delrec()
3953 cur->bc_ops->get_minrecs(tcur, level)) { in xfs_btree_delrec()
3954 error = xfs_btree_rshift(tcur, level, &i); in xfs_btree_delrec()
3959 cur->bc_ops->get_minrecs(tcur, level)); in xfs_btree_delrec()
3962 if (level == 0) in xfs_btree_delrec()
3963 cur->bc_ptrs[0]++; in xfs_btree_delrec()
3986 cur->bc_ops->get_maxrecs(cur, level)) { in xfs_btree_delrec()
4003 cur->bc_ops->get_maxrecs(cur, level)) { in xfs_btree_delrec()
4020 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
4034 if (level > 0) { in xfs_btree_delrec()
4035 /* It's a non-leaf. Move keys and pointers. */ in xfs_btree_delrec()
4047 error = xfs_btree_debug_check_ptr(cur, rpp, i, level); in xfs_btree_delrec()
4100 cur->bc_bufs[level] = lbp; in xfs_btree_delrec()
4101 cur->bc_ptrs[level] += lrecs; in xfs_btree_delrec()
4102 cur->bc_ra[level] = 0; in xfs_btree_delrec()
4105 * If we joined with the right neighbor and there's a level above in xfs_btree_delrec()
4106 * us, increment the cursor at that level. in xfs_btree_delrec()
4108 else if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) || in xfs_btree_delrec()
4109 (level + 1 < cur->bc_nlevels)) { in xfs_btree_delrec()
4110 error = xfs_btree_increment(cur, level + 1, &i); in xfs_btree_delrec()
4116 * Readjust the ptr at this level if it's not a leaf, since it's in xfs_btree_delrec()
4119 * We can't use decrement because it would change the next level up. in xfs_btree_delrec()
4121 if (level > 0) in xfs_btree_delrec()
4122 cur->bc_ptrs[level]--; in xfs_btree_delrec()
4126 * btree supports overlapped intervals. However, bc_ptrs[level + 1] in xfs_btree_delrec()
4134 /* Return value means the next level up has something to do. */ in xfs_btree_delrec()
4155 int level; in xfs_btree_delete() local
4160 * Go up the tree, starting at leaf level. in xfs_btree_delete()
4162 * If 2 is returned then a join was done; go to the next level. in xfs_btree_delete()
4165 for (level = 0, i = 2; i == 2; level++) { in xfs_btree_delete()
4166 error = xfs_btree_delrec(cur, level, &i); in xfs_btree_delete()
4175 * have updated the parent high keys so we have to do that here. in xfs_btree_delete()
4177 if (joined && (cur->bc_flags & XFS_BTREE_OVERLAPPING)) { in xfs_btree_delete()
4184 for (level = 1; level < cur->bc_nlevels; level++) { in xfs_btree_delete()
4185 if (cur->bc_ptrs[level] == 0) { in xfs_btree_delete()
4186 error = xfs_btree_decrement(cur, level, &i); in xfs_btree_delete()
4201 * Get the data from the pointed-to record.
4216 ptr = cur->bc_ptrs[0]; in xfs_btree_get_rec()
4245 int level, in xfs_btree_visit_block() argument
4255 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA); in xfs_btree_visit_block()
4256 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_visit_block()
4259 error = fn(cur, level, data); in xfs_btree_visit_block()
4266 return -ENOENT; in xfs_btree_visit_block()
4268 return xfs_btree_lookup_get_block(cur, level, &rptr, &block); in xfs_btree_visit_block()
4281 int level; in xfs_btree_visit_blocks() local
4285 cur->bc_ops->init_ptr_from_cur(cur, &lptr); in xfs_btree_visit_blocks()
4287 /* for each level */ in xfs_btree_visit_blocks()
4288 for (level = cur->bc_nlevels - 1; level >= 0; level--) { in xfs_btree_visit_blocks()
4290 error = xfs_btree_lookup_get_block(cur, level, &lptr, &block); in xfs_btree_visit_blocks()
4294 /* readahead the left most block for the next level down */ in xfs_btree_visit_blocks()
4295 if (level > 0) { in xfs_btree_visit_blocks()
4310 /* for each buffer in the level */ in xfs_btree_visit_blocks()
4312 error = xfs_btree_visit_block(cur, level, fn, data); in xfs_btree_visit_blocks()
4315 if (error != -ENOENT) in xfs_btree_visit_blocks()
4330 * We do the btree walk in the most optimal manner possible - we have sibling
4331 * pointers so we can just walk all the blocks on each level from left to right
4332 * in a single pass, and then move to the next level and do the same. We can
4354 int level, in xfs_btree_block_change_owner() argument
4362 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_block_change_owner()
4363 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_block_change_owner()
4364 if (block->bb_u.l.bb_owner == cpu_to_be64(bbcoi->new_owner)) in xfs_btree_block_change_owner()
4366 block->bb_u.l.bb_owner = cpu_to_be64(bbcoi->new_owner); in xfs_btree_block_change_owner()
4368 if (block->bb_u.s.bb_owner == cpu_to_be32(bbcoi->new_owner)) in xfs_btree_block_change_owner()
4370 block->bb_u.s.bb_owner = cpu_to_be32(bbcoi->new_owner); in xfs_btree_block_change_owner()
4377 * block is formatted into the on-disk inode fork. We still change it, in xfs_btree_block_change_owner()
4381 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE); in xfs_btree_block_change_owner()
4382 ASSERT(level == cur->bc_nlevels - 1); in xfs_btree_block_change_owner()
4386 if (cur->bc_tp) { in xfs_btree_block_change_owner()
4387 if (!xfs_trans_ordered_buf(cur->bc_tp, bp)) { in xfs_btree_block_change_owner()
4389 return -EAGAIN; in xfs_btree_block_change_owner()
4392 xfs_buf_delwri_queue(bp, bbcoi->buffer_list); in xfs_btree_block_change_owner()
4413 /* Verify the v5 fields of a long-format btree block. */
4419 struct xfs_mount *mp = bp->b_mount; in xfs_btree_lblock_v5hdr_verify()
4424 if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid)) in xfs_btree_lblock_v5hdr_verify()
4426 if (block->bb_u.l.bb_blkno != cpu_to_be64(xfs_buf_daddr(bp))) in xfs_btree_lblock_v5hdr_verify()
4429 be64_to_cpu(block->bb_u.l.bb_owner) != owner) in xfs_btree_lblock_v5hdr_verify()
4434 /* Verify a long-format btree block. */
4440 struct xfs_mount *mp = bp->b_mount; in xfs_btree_lblock_verify()
4444 if (be16_to_cpu(block->bb_numrecs) > max_recs) in xfs_btree_lblock_verify()
4448 if (block->bb_u.l.bb_leftsib != cpu_to_be64(NULLFSBLOCK) && in xfs_btree_lblock_verify()
4449 !xfs_verify_fsbno(mp, be64_to_cpu(block->bb_u.l.bb_leftsib))) in xfs_btree_lblock_verify()
4451 if (block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK) && in xfs_btree_lblock_verify()
4452 !xfs_verify_fsbno(mp, be64_to_cpu(block->bb_u.l.bb_rightsib))) in xfs_btree_lblock_verify()
4459 * xfs_btree_sblock_v5hdr_verify() -- verify the v5 fields of a short-format
4468 struct xfs_mount *mp = bp->b_mount; in xfs_btree_sblock_v5hdr_verify()
4470 struct xfs_perag *pag = bp->b_pag; in xfs_btree_sblock_v5hdr_verify()
4474 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid)) in xfs_btree_sblock_v5hdr_verify()
4476 if (block->bb_u.s.bb_blkno != cpu_to_be64(xfs_buf_daddr(bp))) in xfs_btree_sblock_v5hdr_verify()
4478 if (pag && be32_to_cpu(block->bb_u.s.bb_owner) != pag->pag_agno) in xfs_btree_sblock_v5hdr_verify()
4484 * xfs_btree_sblock_verify() -- verify a short-format btree block
4494 struct xfs_mount *mp = bp->b_mount; in xfs_btree_sblock_verify()
4499 if (be16_to_cpu(block->bb_numrecs) > max_recs) in xfs_btree_sblock_verify()
4504 if (block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK) && in xfs_btree_sblock_verify()
4505 !xfs_verify_agbno(mp, agno, be32_to_cpu(block->bb_u.s.bb_leftsib))) in xfs_btree_sblock_verify()
4507 if (block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK) && in xfs_btree_sblock_verify()
4508 !xfs_verify_agbno(mp, agno, be32_to_cpu(block->bb_u.s.bb_rightsib))) in xfs_btree_sblock_verify()
4516 * records in a short-format btree.
4523 uint level; in xfs_btree_compute_maxlevels() local
4526 maxblocks = (len + limits[0] - 1) / limits[0]; in xfs_btree_compute_maxlevels()
4527 for (level = 1; maxblocks > 1; level++) in xfs_btree_compute_maxlevels()
4528 maxblocks = (maxblocks + limits[1] - 1) / limits[1]; in xfs_btree_compute_maxlevels()
4529 return level; in xfs_btree_compute_maxlevels()
4552 ASSERT(cur->bc_ops->init_high_key_from_rec); in xfs_btree_simple_query_range()
4553 ASSERT(cur->bc_ops->diff_two_keys); in xfs_btree_simple_query_range()
4579 cur->bc_ops->init_high_key_from_rec(&rec_key, recp); in xfs_btree_simple_query_range()
4581 diff = cur->bc_ops->diff_two_keys(cur, low_key, in xfs_btree_simple_query_range()
4588 cur->bc_ops->init_key_from_rec(&rec_key, recp); in xfs_btree_simple_query_range()
4589 diff = cur->bc_ops->diff_two_keys(cur, &rec_key, high_key); in xfs_btree_simple_query_range()
4615 * First, generate keys for the low and high records passed in.
4617 * For any leaf node, generate the high and low keys for the record.
4618 * If the record keys overlap with the query low/high keys, pass the
4621 * For any internal node, compare the low and high keys of each
4622 * pointer against the query low/high keys. If there's an overlap,
4626 * that is greater than the query's high key.
4646 int level; in xfs_btree_overlapped_query_range() local
4652 level = cur->bc_nlevels - 1; in xfs_btree_overlapped_query_range()
4653 cur->bc_ops->init_ptr_from_cur(cur, &ptr); in xfs_btree_overlapped_query_range()
4654 error = xfs_btree_lookup_get_block(cur, level, &ptr, &block); in xfs_btree_overlapped_query_range()
4657 xfs_btree_get_block(cur, level, &bp); in xfs_btree_overlapped_query_range()
4658 trace_xfs_btree_overlapped_query_range(cur, level, bp); in xfs_btree_overlapped_query_range()
4660 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_overlapped_query_range()
4664 cur->bc_ptrs[level] = 1; in xfs_btree_overlapped_query_range()
4666 while (level < cur->bc_nlevels) { in xfs_btree_overlapped_query_range()
4667 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_overlapped_query_range()
4670 if (cur->bc_ptrs[level] > be16_to_cpu(block->bb_numrecs)) { in xfs_btree_overlapped_query_range()
4672 if (level < cur->bc_nlevels - 1) in xfs_btree_overlapped_query_range()
4673 cur->bc_ptrs[level + 1]++; in xfs_btree_overlapped_query_range()
4674 level++; in xfs_btree_overlapped_query_range()
4678 if (level == 0) { in xfs_btree_overlapped_query_range()
4680 recp = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block); in xfs_btree_overlapped_query_range()
4682 cur->bc_ops->init_high_key_from_rec(&rec_hkey, recp); in xfs_btree_overlapped_query_range()
4683 ldiff = cur->bc_ops->diff_two_keys(cur, &rec_hkey, in xfs_btree_overlapped_query_range()
4686 cur->bc_ops->init_key_from_rec(&rec_key, recp); in xfs_btree_overlapped_query_range()
4687 hdiff = cur->bc_ops->diff_two_keys(cur, high_key, in xfs_btree_overlapped_query_range()
4691 * If (record's high key >= query's low key) and in xfs_btree_overlapped_query_range()
4692 * (query's high key >= record's low key), then in xfs_btree_overlapped_query_range()
4700 /* Record is larger than high key; pop. */ in xfs_btree_overlapped_query_range()
4703 cur->bc_ptrs[level]++; in xfs_btree_overlapped_query_range()
4708 lkp = xfs_btree_key_addr(cur, cur->bc_ptrs[level], block); in xfs_btree_overlapped_query_range()
4709 hkp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level], block); in xfs_btree_overlapped_query_range()
4710 pp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[level], block); in xfs_btree_overlapped_query_range()
4712 ldiff = cur->bc_ops->diff_two_keys(cur, hkp, low_key); in xfs_btree_overlapped_query_range()
4713 hdiff = cur->bc_ops->diff_two_keys(cur, high_key, lkp); in xfs_btree_overlapped_query_range()
4716 * If (pointer's high key >= query's low key) and in xfs_btree_overlapped_query_range()
4717 * (query's high key >= pointer's low key), then in xfs_btree_overlapped_query_range()
4721 level--; in xfs_btree_overlapped_query_range()
4722 error = xfs_btree_lookup_get_block(cur, level, pp, in xfs_btree_overlapped_query_range()
4726 xfs_btree_get_block(cur, level, &bp); in xfs_btree_overlapped_query_range()
4727 trace_xfs_btree_overlapped_query_range(cur, level, bp); in xfs_btree_overlapped_query_range()
4729 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_overlapped_query_range()
4733 cur->bc_ptrs[level] = 1; in xfs_btree_overlapped_query_range()
4739 cur->bc_ptrs[level]++; in xfs_btree_overlapped_query_range()
4745 * block, a subsequent non-error cursor deletion will not release in xfs_btree_overlapped_query_range()
4746 * node-level buffers, causing a buffer leak. This is quite possible in xfs_btree_overlapped_query_range()
4747 * with a zero-results range query, so release the buffers if we in xfs_btree_overlapped_query_range()
4750 if (cur->bc_bufs[0] == NULL) { in xfs_btree_overlapped_query_range()
4751 for (i = 0; i < cur->bc_nlevels; i++) { in xfs_btree_overlapped_query_range()
4752 if (cur->bc_bufs[i]) { in xfs_btree_overlapped_query_range()
4753 xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[i]); in xfs_btree_overlapped_query_range()
4754 cur->bc_bufs[i] = NULL; in xfs_btree_overlapped_query_range()
4755 cur->bc_ptrs[i] = 0; in xfs_btree_overlapped_query_range()
4756 cur->bc_ra[i] = 0; in xfs_btree_overlapped_query_range()
4768 * code. This function returns -ECANCELED, zero, or a negative error code.
4783 cur->bc_rec = *high_rec; in xfs_btree_query_range()
4784 cur->bc_ops->init_rec_from_cur(cur, &rec); in xfs_btree_query_range()
4785 cur->bc_ops->init_key_from_rec(&high_key, &rec); in xfs_btree_query_range()
4787 cur->bc_rec = *low_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(&low_key, &rec); in xfs_btree_query_range()
4791 /* Enforce low key < high key. */ in xfs_btree_query_range()
4792 if (cur->bc_ops->diff_two_keys(cur, &low_key, &high_key) > 0) in xfs_btree_query_range()
4793 return -EINVAL; in xfs_btree_query_range()
4795 if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING)) in xfs_btree_query_range()
4812 memset(&cur->bc_rec, 0, sizeof(cur->bc_rec)); in xfs_btree_query_all()
4821 * in a short-format (per-AG metadata) btree.
4828 int level; in xfs_btree_calc_size() local
4833 for (level = 0, rval = 0; len > 1; level++) { in xfs_btree_calc_size()
4834 len += maxrecs - 1; in xfs_btree_calc_size()
4845 int level, in xfs_btree_count_blocks_helper() argument
4872 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_diff_two_ptrs()
4873 return (int64_t)be64_to_cpu(a->l) - be64_to_cpu(b->l); in xfs_btree_diff_two_ptrs()
4874 return (int64_t)be32_to_cpu(a->s) - be32_to_cpu(b->s); in xfs_btree_diff_two_ptrs()
4884 return -ECANCELED; in xfs_btree_has_record_helper()
4892 const union xfs_btree_irec *high, in xfs_btree_has_record() argument
4897 error = xfs_btree_query_range(cur, low, high, in xfs_btree_has_record()
4899 if (error == -ECANCELED) { in xfs_btree_has_record()
4918 if (cur->bc_ptrs[0] < xfs_btree_get_numrecs(block)) in xfs_btree_has_more_records()
4922 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_has_more_records()
4923 return block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK); in xfs_btree_has_more_records()
4925 return block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK); in xfs_btree_has_more_records()