Lines Matching +full:last +full:- +full:level
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()
61 * on x86-64. Yes, gcc-11 fails to inline them, and explicit inlining of these
69 int level, in xfs_btree_check_lblock_siblings() argument
81 if (level >= 0) { in xfs_btree_check_lblock_siblings()
82 if (!xfs_btree_check_lptr(cur, sibling, level + 1)) in xfs_btree_check_lblock_siblings()
96 int level, in xfs_btree_check_sblock_siblings() argument
108 if (level >= 0) { in xfs_btree_check_sblock_siblings()
109 if (!xfs_btree_check_sptr(cur, sibling, level + 1)) in xfs_btree_check_sblock_siblings()
126 int level, in __xfs_btree_check_lblock() argument
129 struct xfs_mount *mp = cur->bc_mp; in __xfs_btree_check_lblock()
130 xfs_btnum_t btnum = cur->bc_btnum; in __xfs_btree_check_lblock()
136 if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid)) in __xfs_btree_check_lblock()
138 if (block->bb_u.l.bb_blkno != in __xfs_btree_check_lblock()
141 if (block->bb_u.l.bb_pad != cpu_to_be32(0)) in __xfs_btree_check_lblock()
145 if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(crc, btnum)) in __xfs_btree_check_lblock()
147 if (be16_to_cpu(block->bb_level) != level) in __xfs_btree_check_lblock()
149 if (be16_to_cpu(block->bb_numrecs) > in __xfs_btree_check_lblock()
150 cur->bc_ops->get_maxrecs(cur, level)) in __xfs_btree_check_lblock()
156 fa = xfs_btree_check_lblock_siblings(mp, cur, level, fsb, in __xfs_btree_check_lblock()
157 block->bb_u.l.bb_leftsib); in __xfs_btree_check_lblock()
159 fa = xfs_btree_check_lblock_siblings(mp, cur, level, fsb, in __xfs_btree_check_lblock()
160 block->bb_u.l.bb_rightsib); in __xfs_btree_check_lblock()
169 int level, in xfs_btree_check_lblock() argument
172 struct xfs_mount *mp = cur->bc_mp; in xfs_btree_check_lblock()
175 fa = __xfs_btree_check_lblock(cur, block, level, bp); in xfs_btree_check_lblock()
180 return -EFSCORRUPTED; in xfs_btree_check_lblock()
193 int level, in __xfs_btree_check_sblock() argument
196 struct xfs_mount *mp = cur->bc_mp; in __xfs_btree_check_sblock()
197 struct xfs_perag *pag = cur->bc_ag.pag; in __xfs_btree_check_sblock()
198 xfs_btnum_t btnum = cur->bc_btnum; in __xfs_btree_check_sblock()
204 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid)) in __xfs_btree_check_sblock()
206 if (block->bb_u.s.bb_blkno != in __xfs_btree_check_sblock()
211 if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(crc, btnum)) in __xfs_btree_check_sblock()
213 if (be16_to_cpu(block->bb_level) != level) in __xfs_btree_check_sblock()
215 if (be16_to_cpu(block->bb_numrecs) > in __xfs_btree_check_sblock()
216 cur->bc_ops->get_maxrecs(cur, level)) in __xfs_btree_check_sblock()
222 fa = xfs_btree_check_sblock_siblings(pag, cur, level, agbno, in __xfs_btree_check_sblock()
223 block->bb_u.s.bb_leftsib); in __xfs_btree_check_sblock()
225 fa = xfs_btree_check_sblock_siblings(pag, cur, level, agbno, in __xfs_btree_check_sblock()
226 block->bb_u.s.bb_rightsib); in __xfs_btree_check_sblock()
235 int level, in xfs_btree_check_sblock() argument
238 struct xfs_mount *mp = cur->bc_mp; in xfs_btree_check_sblock()
241 fa = __xfs_btree_check_sblock(cur, block, level, bp); in xfs_btree_check_sblock()
246 return -EFSCORRUPTED; in xfs_btree_check_sblock()
258 int level, /* level of the btree block */ in xfs_btree_check_block() argument
261 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_check_block()
262 return xfs_btree_check_lblock(cur, block, level, bp); in xfs_btree_check_block()
264 return xfs_btree_check_sblock(cur, block, level, bp); in xfs_btree_check_block()
272 int level) in xfs_btree_check_lptr() argument
274 if (level <= 0) in xfs_btree_check_lptr()
276 return xfs_verify_fsbno(cur->bc_mp, fsbno); in xfs_btree_check_lptr()
284 int level) in xfs_btree_check_sptr() argument
286 if (level <= 0) in xfs_btree_check_sptr()
288 return xfs_verify_agbno(cur->bc_ag.pag, agbno); in xfs_btree_check_sptr()
292 * Check that a given (indexed) btree pointer at a certain level of a
300 int level) in xfs_btree_check_ptr() argument
302 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_check_ptr()
303 if (xfs_btree_check_lptr(cur, be64_to_cpu((&ptr->l)[index]), in xfs_btree_check_ptr()
304 level)) in xfs_btree_check_ptr()
306 xfs_err(cur->bc_mp, in xfs_btree_check_ptr()
307 "Inode %llu fork %d: Corrupt btree %d pointer at level %d index %d.", in xfs_btree_check_ptr()
308 cur->bc_ino.ip->i_ino, in xfs_btree_check_ptr()
309 cur->bc_ino.whichfork, cur->bc_btnum, in xfs_btree_check_ptr()
310 level, index); in xfs_btree_check_ptr()
312 if (xfs_btree_check_sptr(cur, be32_to_cpu((&ptr->s)[index]), in xfs_btree_check_ptr()
313 level)) in xfs_btree_check_ptr()
315 xfs_err(cur->bc_mp, in xfs_btree_check_ptr()
316 "AG %u: Corrupt btree %d pointer at level %d index %d.", in xfs_btree_check_ptr()
317 cur->bc_ag.pag->pag_agno, cur->bc_btnum, in xfs_btree_check_ptr()
318 level, index); in xfs_btree_check_ptr()
321 return -EFSCORRUPTED; in xfs_btree_check_ptr()
332 * long-form btree header.
335 * it into the buffer so recovery knows what the last modification was that made
343 struct xfs_buf_log_item *bip = bp->b_log_item; in xfs_btree_lblock_calc_crc()
345 if (!xfs_has_crc(bp->b_mount)) in xfs_btree_lblock_calc_crc()
348 block->bb_u.l.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn); in xfs_btree_lblock_calc_crc()
357 struct xfs_mount *mp = bp->b_mount; in xfs_btree_lblock_verify_crc()
360 if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.l.bb_lsn))) in xfs_btree_lblock_verify_crc()
370 * short-form btree header.
373 * it into the buffer so recovery knows what the last modification was that made
381 struct xfs_buf_log_item *bip = bp->b_log_item; in xfs_btree_sblock_calc_crc()
383 if (!xfs_has_crc(bp->b_mount)) in xfs_btree_sblock_calc_crc()
386 block->bb_u.s.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn); in xfs_btree_sblock_calc_crc()
395 struct xfs_mount *mp = bp->b_mount; in xfs_btree_sblock_verify_crc()
398 if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.s.bb_lsn))) in xfs_btree_sblock_verify_crc()
413 error = cur->bc_ops->free_block(cur, bp); in xfs_btree_free_block()
415 xfs_trans_binval(cur->bc_tp, bp); in xfs_btree_free_block()
429 int i; /* btree level */ in xfs_btree_del_cursor()
435 * code works from level n down to 0, and if we get an error along the in xfs_btree_del_cursor()
438 for (i = 0; i < cur->bc_nlevels; i++) { in xfs_btree_del_cursor()
439 if (cur->bc_levels[i].bp) in xfs_btree_del_cursor()
440 xfs_trans_brelse(cur->bc_tp, cur->bc_levels[i].bp); in xfs_btree_del_cursor()
451 ASSERT(cur->bc_btnum != XFS_BTNUM_BMAP || cur->bc_ino.allocated == 0 || in xfs_btree_del_cursor()
452 xfs_is_shutdown(cur->bc_mp) || error != 0); in xfs_btree_del_cursor()
453 if (unlikely(cur->bc_flags & XFS_BTREE_STAGING)) in xfs_btree_del_cursor()
454 kmem_free(cur->bc_ops); in xfs_btree_del_cursor()
455 if (!(cur->bc_flags & XFS_BTREE_LONG_PTRS) && cur->bc_ag.pag) in xfs_btree_del_cursor()
456 xfs_perag_put(cur->bc_ag.pag); in xfs_btree_del_cursor()
457 kmem_cache_free(cur->bc_cache, cur); in xfs_btree_del_cursor()
462 * Allocate a new one, copy the record, re-get the buffers.
471 int i; /* level number of btree block */ in xfs_btree_dup_cursor()
476 tp = cur->bc_tp; in xfs_btree_dup_cursor()
477 mp = cur->bc_mp; in xfs_btree_dup_cursor()
482 new = cur->bc_ops->dup_cursor(cur); in xfs_btree_dup_cursor()
487 new->bc_rec = cur->bc_rec; in xfs_btree_dup_cursor()
490 * For each level current, re-get the buffer and copy the ptr value. in xfs_btree_dup_cursor()
492 for (i = 0; i < new->bc_nlevels; i++) { in xfs_btree_dup_cursor()
493 new->bc_levels[i].ptr = cur->bc_levels[i].ptr; in xfs_btree_dup_cursor()
494 new->bc_levels[i].ra = cur->bc_levels[i].ra; in xfs_btree_dup_cursor()
495 bp = cur->bc_levels[i].bp; in xfs_btree_dup_cursor()
497 error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, in xfs_btree_dup_cursor()
498 xfs_buf_daddr(bp), mp->m_bsize, in xfs_btree_dup_cursor()
500 cur->bc_ops->buf_ops); in xfs_btree_dup_cursor()
507 new->bc_levels[i].bp = bp; in xfs_btree_dup_cursor()
516 * There are two types of blocks in the btree: leaf and non-leaf blocks.
519 * the values. A non-leaf block also starts with the same header, and
521 * to the btree blocks at the previous level.
523 * +--------+-------+-------+-------+-------+-------+-------+
525 * +--------+-------+-------+-------+-------+-------+-------+
527 * +--------+-------+-------+-------+-------+-------+-------+
528 * Non-Leaf: | header | key 1 | key 2 | key N | ptr 1 | ptr 2 | ptr N |
529 * +--------+-------+-------+-------+-------+-------+-------+
545 * However, nodes are different: each pointer has two associated keys -- one
554 * +--------+-----+-----+-----+-----+-----+-------+-------+-----+
555 * Non-Leaf: | header | lo1 | hi1 | lo2 | hi2 | ... | ptr 1 | ptr 2 | ... |
556 * +--------+-----+-----+-----+-----+-----+-------+-------+-----+
559 * depth-first search and use the low and high keys to decide if we can skip
562 * entries. For a non-overlapped tree, simply search for the record associated
563 * with the lowest key and iterate forward until a non-matching record is
571 * 1: +- file A startblock B offset C length D -----------+
572 * 2: +- file E startblock F offset G length H --------------+
573 * 3: +- file I startblock F offset J length K --+
574 * 4: +- file L... --+
578 * that ends at (B+D-1) (i.e. record 1)? A LE lookup of (B+D-1) would return
580 * query would return records 1 and 2 because they both overlap (B+D-1), and
583 * In the non-overlapped case you can do a LE lookup and decrement the cursor
592 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_block_len()
593 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) in xfs_btree_block_len()
597 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) in xfs_btree_block_len()
607 return (cur->bc_flags & XFS_BTREE_LONG_PTRS) ? in xfs_btree_ptr_len()
612 * Calculate offset of the n-th record in a btree block.
620 (n - 1) * cur->bc_ops->rec_len; in xfs_btree_rec_offset()
624 * Calculate offset of the n-th key in a btree block.
632 (n - 1) * cur->bc_ops->key_len; in xfs_btree_key_offset()
636 * Calculate offset of the n-th high key in a btree block.
644 (n - 1) * cur->bc_ops->key_len + (cur->bc_ops->key_len / 2); in xfs_btree_high_key_offset()
648 * Calculate offset of the n-th block pointer in a btree block.
654 int level) in xfs_btree_ptr_offset() argument
657 cur->bc_ops->get_maxrecs(cur, level) * cur->bc_ops->key_len + in xfs_btree_ptr_offset()
658 (n - 1) * xfs_btree_ptr_len(cur); in xfs_btree_ptr_offset()
662 * Return a pointer to the n-th record in the btree block.
675 * Return a pointer to the n-th key in the btree block.
688 * Return a pointer to the n-th high key in the btree block.
701 * Return a pointer to the n-th block pointer in the btree block.
709 int level = xfs_btree_get_level(block); in xfs_btree_ptr_addr() local
711 ASSERT(block->bb_level != 0); in xfs_btree_ptr_addr()
714 ((char *)block + xfs_btree_ptr_offset(cur, n, level)); in xfs_btree_ptr_addr()
721 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE); in xfs_btree_ifork_ptr()
723 if (cur->bc_flags & XFS_BTREE_STAGING) in xfs_btree_ifork_ptr()
724 return cur->bc_ino.ifake->if_fork; in xfs_btree_ifork_ptr()
725 return xfs_ifork_ptr(cur->bc_ino.ip, cur->bc_ino.whichfork); in xfs_btree_ifork_ptr()
740 return (struct xfs_btree_block *)ifp->if_broot; in xfs_btree_get_iroot()
744 * Retrieve the block pointer from the cursor at the given level.
750 int level, /* level in btree */ in xfs_btree_get_block() argument
753 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_get_block()
754 (level == cur->bc_nlevels - 1)) { in xfs_btree_get_block()
759 *bpp = cur->bc_levels[level].bp; in xfs_btree_get_block()
764 * Change the cursor to point to the first record at the given level.
770 int level) /* level to change */ in xfs_btree_firstrec() argument
776 * Get the block pointer for this level. in xfs_btree_firstrec()
778 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_firstrec()
779 if (xfs_btree_check_block(cur, block, level, bp)) in xfs_btree_firstrec()
784 if (!block->bb_numrecs) in xfs_btree_firstrec()
789 cur->bc_levels[level].ptr = 1; in xfs_btree_firstrec()
794 * Change the cursor to point to the last record in the current block
795 * at the given level. Other levels are unaffected.
800 int level) /* level to change */ in xfs_btree_lastrec() argument
806 * Get the block pointer for this level. in xfs_btree_lastrec()
808 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_lastrec()
809 if (xfs_btree_check_block(cur, block, level, bp)) in xfs_btree_lastrec()
814 if (!block->bb_numrecs) in xfs_btree_lastrec()
817 * Set the ptr value to numrecs, that's the last record/key. in xfs_btree_lastrec()
819 cur->bc_levels[level].ptr = be16_to_cpu(block->bb_numrecs); in xfs_btree_lastrec()
824 * Compute first and last byte offsets for the fields given.
833 int *last) /* output: last byte offset */ in xfs_btree_offsets() argument
849 * Find the highest bit, so the last byte offset. in xfs_btree_offsets()
851 for (i = nbits - 1, imask = 1u << i; ; i--, imask >>= 1) { in xfs_btree_offsets()
853 *last = offsets[i + 1] - 1; in xfs_btree_offsets()
861 * Long-form addressing.
877 return -EFSCORRUPTED; in xfs_btree_read_bufl()
879 error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, d, in xfs_btree_read_bufl()
880 mp->m_bsize, 0, &bp, ops); in xfs_btree_read_bufl()
890 * Read-ahead the block, don't wait for it, don't return a buffer.
891 * Long-form addressing.
905 xfs_buf_readahead(mp->m_ddev_targp, d, mp->m_bsize * count, ops); in xfs_btree_reada_bufl()
909 * Read-ahead the block, don't wait for it, don't return a buffer.
910 * Short-form addressing.
926 xfs_buf_readahead(mp->m_ddev_targp, d, mp->m_bsize * count, ops); in xfs_btree_reada_bufs()
936 xfs_fsblock_t left = be64_to_cpu(block->bb_u.l.bb_leftsib); in xfs_btree_readahead_lblock()
937 xfs_fsblock_t right = be64_to_cpu(block->bb_u.l.bb_rightsib); in xfs_btree_readahead_lblock()
940 xfs_btree_reada_bufl(cur->bc_mp, left, 1, in xfs_btree_readahead_lblock()
941 cur->bc_ops->buf_ops); in xfs_btree_readahead_lblock()
946 xfs_btree_reada_bufl(cur->bc_mp, right, 1, in xfs_btree_readahead_lblock()
947 cur->bc_ops->buf_ops); in xfs_btree_readahead_lblock()
961 xfs_agblock_t left = be32_to_cpu(block->bb_u.s.bb_leftsib); in xfs_btree_readahead_sblock()
962 xfs_agblock_t right = be32_to_cpu(block->bb_u.s.bb_rightsib); in xfs_btree_readahead_sblock()
966 xfs_btree_reada_bufs(cur->bc_mp, cur->bc_ag.pag->pag_agno, in xfs_btree_readahead_sblock()
967 left, 1, cur->bc_ops->buf_ops); in xfs_btree_readahead_sblock()
972 xfs_btree_reada_bufs(cur->bc_mp, cur->bc_ag.pag->pag_agno, in xfs_btree_readahead_sblock()
973 right, 1, cur->bc_ops->buf_ops); in xfs_btree_readahead_sblock()
981 * Read-ahead btree blocks, at the given level.
987 int lev, /* level in btree */ in xfs_btree_readahead()
993 * No readahead needed if we are at the root level and the in xfs_btree_readahead()
996 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_readahead()
997 (lev == cur->bc_nlevels - 1)) in xfs_btree_readahead()
1000 if ((cur->bc_levels[lev].ra | lr) == cur->bc_levels[lev].ra) in xfs_btree_readahead()
1003 cur->bc_levels[lev].ra |= lr; in xfs_btree_readahead()
1004 block = XFS_BUF_TO_BLOCK(cur->bc_levels[lev].bp); in xfs_btree_readahead()
1006 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_readahead()
1025 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_ptr_to_daddr()
1026 fsbno = be64_to_cpu(ptr->l); in xfs_btree_ptr_to_daddr()
1027 *daddr = XFS_FSB_TO_DADDR(cur->bc_mp, fsbno); in xfs_btree_ptr_to_daddr()
1029 agbno = be32_to_cpu(ptr->s); in xfs_btree_ptr_to_daddr()
1030 *daddr = XFS_AGB_TO_DADDR(cur->bc_mp, cur->bc_ag.pag->pag_agno, in xfs_btree_ptr_to_daddr()
1053 xfs_buf_readahead(cur->bc_mp->m_ddev_targp, daddr, in xfs_btree_readahead_ptr()
1054 cur->bc_mp->m_bsize * count, cur->bc_ops->buf_ops); in xfs_btree_readahead_ptr()
1058 * Set the buffer for level "lev" in the cursor to bp, releasing
1064 int lev, /* level in btree */ in xfs_btree_setbuf()
1069 if (cur->bc_levels[lev].bp) in xfs_btree_setbuf()
1070 xfs_trans_brelse(cur->bc_tp, cur->bc_levels[lev].bp); in xfs_btree_setbuf()
1071 cur->bc_levels[lev].bp = bp; in xfs_btree_setbuf()
1072 cur->bc_levels[lev].ra = 0; in xfs_btree_setbuf()
1075 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_setbuf()
1076 if (b->bb_u.l.bb_leftsib == cpu_to_be64(NULLFSBLOCK)) in xfs_btree_setbuf()
1077 cur->bc_levels[lev].ra |= XFS_BTCUR_LEFTRA; in xfs_btree_setbuf()
1078 if (b->bb_u.l.bb_rightsib == cpu_to_be64(NULLFSBLOCK)) in xfs_btree_setbuf()
1079 cur->bc_levels[lev].ra |= XFS_BTCUR_RIGHTRA; in xfs_btree_setbuf()
1081 if (b->bb_u.s.bb_leftsib == cpu_to_be32(NULLAGBLOCK)) in xfs_btree_setbuf()
1082 cur->bc_levels[lev].ra |= XFS_BTCUR_LEFTRA; in xfs_btree_setbuf()
1083 if (b->bb_u.s.bb_rightsib == cpu_to_be32(NULLAGBLOCK)) in xfs_btree_setbuf()
1084 cur->bc_levels[lev].ra |= XFS_BTCUR_RIGHTRA; in xfs_btree_setbuf()
1093 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_ptr_is_null()
1094 return ptr->l == cpu_to_be64(NULLFSBLOCK); in xfs_btree_ptr_is_null()
1096 return ptr->s == cpu_to_be32(NULLAGBLOCK); in xfs_btree_ptr_is_null()
1104 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_set_ptr_null()
1105 ptr->l = cpu_to_be64(NULLFSBLOCK); in xfs_btree_set_ptr_null()
1107 ptr->s = cpu_to_be32(NULLAGBLOCK); in xfs_btree_set_ptr_null()
1122 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_get_sibling()
1124 ptr->l = block->bb_u.l.bb_rightsib; in xfs_btree_get_sibling()
1126 ptr->l = block->bb_u.l.bb_leftsib; in xfs_btree_get_sibling()
1129 ptr->s = block->bb_u.s.bb_rightsib; in xfs_btree_get_sibling()
1131 ptr->s = block->bb_u.s.bb_leftsib; in xfs_btree_get_sibling()
1144 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_set_sibling()
1146 block->bb_u.l.bb_rightsib = ptr->l; in xfs_btree_set_sibling()
1148 block->bb_u.l.bb_leftsib = ptr->l; in xfs_btree_set_sibling()
1151 block->bb_u.s.bb_rightsib = ptr->s; in xfs_btree_set_sibling()
1153 block->bb_u.s.bb_leftsib = ptr->s; in xfs_btree_set_sibling()
1163 __u16 level, in xfs_btree_init_block_int() argument
1171 buf->bb_magic = cpu_to_be32(magic); in xfs_btree_init_block_int()
1172 buf->bb_level = cpu_to_be16(level); in xfs_btree_init_block_int()
1173 buf->bb_numrecs = cpu_to_be16(numrecs); in xfs_btree_init_block_int()
1176 buf->bb_u.l.bb_leftsib = cpu_to_be64(NULLFSBLOCK); in xfs_btree_init_block_int()
1177 buf->bb_u.l.bb_rightsib = cpu_to_be64(NULLFSBLOCK); in xfs_btree_init_block_int()
1179 buf->bb_u.l.bb_blkno = cpu_to_be64(blkno); in xfs_btree_init_block_int()
1180 buf->bb_u.l.bb_owner = cpu_to_be64(owner); in xfs_btree_init_block_int()
1181 uuid_copy(&buf->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid); in xfs_btree_init_block_int()
1182 buf->bb_u.l.bb_pad = 0; in xfs_btree_init_block_int()
1183 buf->bb_u.l.bb_lsn = 0; in xfs_btree_init_block_int()
1189 buf->bb_u.s.bb_leftsib = cpu_to_be32(NULLAGBLOCK); in xfs_btree_init_block_int()
1190 buf->bb_u.s.bb_rightsib = cpu_to_be32(NULLAGBLOCK); in xfs_btree_init_block_int()
1192 buf->bb_u.s.bb_blkno = cpu_to_be64(blkno); in xfs_btree_init_block_int()
1193 buf->bb_u.s.bb_owner = cpu_to_be32(__owner); in xfs_btree_init_block_int()
1194 uuid_copy(&buf->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid); in xfs_btree_init_block_int()
1195 buf->bb_u.s.bb_lsn = 0; in xfs_btree_init_block_int()
1205 __u16 level, in xfs_btree_init_block() argument
1210 btnum, level, numrecs, owner, 0); in xfs_btree_init_block()
1217 int level, in xfs_btree_init_block_cur() argument
1228 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_init_block_cur()
1229 owner = cur->bc_ino.ip->i_ino; in xfs_btree_init_block_cur()
1231 owner = cur->bc_ag.pag->pag_agno; in xfs_btree_init_block_cur()
1233 xfs_btree_init_block_int(cur->bc_mp, XFS_BUF_TO_BLOCK(bp), in xfs_btree_init_block_cur()
1234 xfs_buf_daddr(bp), cur->bc_btnum, level, in xfs_btree_init_block_cur()
1235 numrecs, owner, cur->bc_flags); in xfs_btree_init_block_cur()
1239 * Return true if ptr is the last record in the btree and
1247 int level) in xfs_btree_is_lastrec() argument
1251 if (level > 0) in xfs_btree_is_lastrec()
1253 if (!(cur->bc_flags & XFS_BTREE_LASTREC_UPDATE)) in xfs_btree_is_lastrec()
1268 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_buf_to_ptr()
1269 ptr->l = cpu_to_be64(XFS_DADDR_TO_FSB(cur->bc_mp, in xfs_btree_buf_to_ptr()
1272 ptr->s = cpu_to_be32(xfs_daddr_to_agbno(cur->bc_mp, in xfs_btree_buf_to_ptr()
1282 switch (cur->bc_btnum) { in xfs_btree_set_refs()
1312 struct xfs_mount *mp = cur->bc_mp; in xfs_btree_get_buf_block()
1319 error = xfs_trans_get_buf(cur->bc_tp, mp->m_ddev_targp, d, mp->m_bsize, in xfs_btree_get_buf_block()
1324 (*bpp)->b_ops = cur->bc_ops->buf_ops; in xfs_btree_get_buf_block()
1341 struct xfs_mount *mp = cur->bc_mp; in xfs_btree_read_buf_block()
1351 error = xfs_trans_read_buf(mp, cur->bc_tp, mp->m_ddev_targp, d, in xfs_btree_read_buf_block()
1352 mp->m_bsize, flags, bpp, in xfs_btree_read_buf_block()
1353 cur->bc_ops->buf_ops); in xfs_btree_read_buf_block()
1373 memcpy(dst_key, src_key, numkeys * cur->bc_ops->key_len); in xfs_btree_copy_keys()
1387 memcpy(dst_rec, src_rec, numrecs * cur->bc_ops->rec_len); in xfs_btree_copy_recs()
1417 ASSERT(dir == 1 || dir == -1); in xfs_btree_shift_keys()
1419 dst_key = (char *)key + (dir * cur->bc_ops->key_len); in xfs_btree_shift_keys()
1420 memmove(dst_key, key, numkeys * cur->bc_ops->key_len); in xfs_btree_shift_keys()
1436 ASSERT(dir == 1 || dir == -1); in xfs_btree_shift_recs()
1438 dst_rec = (char *)rec + (dir * cur->bc_ops->rec_len); in xfs_btree_shift_recs()
1439 memmove(dst_rec, rec, numrecs * cur->bc_ops->rec_len); in xfs_btree_shift_recs()
1455 ASSERT(dir == 1 || dir == -1); in xfs_btree_shift_ptrs()
1469 int last) in xfs_btree_log_keys() argument
1473 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF); in xfs_btree_log_keys()
1474 xfs_trans_log_buf(cur->bc_tp, bp, in xfs_btree_log_keys()
1476 xfs_btree_key_offset(cur, last + 1) - 1); in xfs_btree_log_keys()
1478 xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip, in xfs_btree_log_keys()
1479 xfs_ilog_fbroot(cur->bc_ino.whichfork)); in xfs_btree_log_keys()
1491 int last) in xfs_btree_log_recs() argument
1494 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF); in xfs_btree_log_recs()
1495 xfs_trans_log_buf(cur->bc_tp, bp, in xfs_btree_log_recs()
1497 xfs_btree_rec_offset(cur, last + 1) - 1); in xfs_btree_log_recs()
1509 int last) /* index of last pointer to log */ in xfs_btree_log_ptrs() argument
1514 int level = xfs_btree_get_level(block); in xfs_btree_log_ptrs() local
1516 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF); in xfs_btree_log_ptrs()
1517 xfs_trans_log_buf(cur->bc_tp, bp, in xfs_btree_log_ptrs()
1518 xfs_btree_ptr_offset(cur, first, level), in xfs_btree_log_ptrs()
1519 xfs_btree_ptr_offset(cur, last + 1, level) - 1); in xfs_btree_log_ptrs()
1521 xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip, in xfs_btree_log_ptrs()
1522 xfs_ilog_fbroot(cur->bc_ino.whichfork)); in xfs_btree_log_ptrs()
1537 int last; /* last byte offset logged */ in xfs_btree_log_block() local
1569 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) { in xfs_btree_log_block()
1584 (cur->bc_flags & XFS_BTREE_LONG_PTRS) ? in xfs_btree_log_block()
1586 nbits, &first, &last); in xfs_btree_log_block()
1587 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF); in xfs_btree_log_block()
1588 xfs_trans_log_buf(cur->bc_tp, bp, first, last); in xfs_btree_log_block()
1590 xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip, in xfs_btree_log_block()
1591 xfs_ilog_fbroot(cur->bc_ino.whichfork)); in xfs_btree_log_block()
1596 * Increment cursor by one record at the level.
1597 * For nonzero levels the leaf-ward information is untouched.
1602 int level, in xfs_btree_increment() argument
1611 ASSERT(level < cur->bc_nlevels); in xfs_btree_increment()
1613 /* Read-ahead to the right at this level. */ in xfs_btree_increment()
1614 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA); in xfs_btree_increment()
1617 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_increment()
1620 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_increment()
1626 if (++cur->bc_levels[level].ptr <= xfs_btree_get_numrecs(block)) in xfs_btree_increment()
1640 for (lev = level + 1; lev < cur->bc_nlevels; lev++) { in xfs_btree_increment()
1649 if (++cur->bc_levels[lev].ptr <= xfs_btree_get_numrecs(block)) in xfs_btree_increment()
1652 /* Read-ahead the right block for the next loop. */ in xfs_btree_increment()
1660 if (lev == cur->bc_nlevels) { in xfs_btree_increment()
1661 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) in xfs_btree_increment()
1664 error = -EFSCORRUPTED; in xfs_btree_increment()
1667 ASSERT(lev < cur->bc_nlevels); in xfs_btree_increment()
1673 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) { in xfs_btree_increment()
1676 ptrp = xfs_btree_ptr_addr(cur, cur->bc_levels[lev].ptr, block); in xfs_btree_increment()
1677 --lev; in xfs_btree_increment()
1683 cur->bc_levels[lev].ptr = 1; in xfs_btree_increment()
1698 * Decrement cursor by one record at the level.
1699 * For nonzero levels the leaf-ward information is untouched.
1704 int level, in xfs_btree_decrement() argument
1713 ASSERT(level < cur->bc_nlevels); in xfs_btree_decrement()
1715 /* Read-ahead to the left at this level. */ in xfs_btree_decrement()
1716 xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA); in xfs_btree_decrement()
1719 if (--cur->bc_levels[level].ptr > 0) in xfs_btree_decrement()
1723 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_decrement()
1726 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_decrement()
1742 for (lev = level + 1; lev < cur->bc_nlevels; lev++) { in xfs_btree_decrement()
1743 if (--cur->bc_levels[lev].ptr > 0) in xfs_btree_decrement()
1745 /* Read-ahead the left block for the next loop. */ in xfs_btree_decrement()
1753 if (lev == cur->bc_nlevels) { in xfs_btree_decrement()
1754 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) in xfs_btree_decrement()
1757 error = -EFSCORRUPTED; in xfs_btree_decrement()
1760 ASSERT(lev < cur->bc_nlevels); in xfs_btree_decrement()
1766 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) { in xfs_btree_decrement()
1769 ptrp = xfs_btree_ptr_addr(cur, cur->bc_levels[lev].ptr, block); in xfs_btree_decrement()
1770 --lev; in xfs_btree_decrement()
1775 cur->bc_levels[lev].ptr = xfs_btree_get_numrecs(block); in xfs_btree_decrement()
1792 int level, /* level in the btree */ in xfs_btree_lookup_get_block() argument
1801 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_lookup_get_block()
1802 (level == cur->bc_nlevels - 1)) { in xfs_btree_lookup_get_block()
1808 * If the old buffer at this level for the disk address we are in xfs_btree_lookup_get_block()
1809 * looking for re-use it. in xfs_btree_lookup_get_block()
1813 bp = cur->bc_levels[level].bp; in xfs_btree_lookup_get_block()
1827 if (xfs_has_crc(cur->bc_mp) && in xfs_btree_lookup_get_block()
1828 !(cur->bc_ino.flags & XFS_BTCUR_BMBT_INVALID_OWNER) && in xfs_btree_lookup_get_block()
1829 (cur->bc_flags & XFS_BTREE_LONG_PTRS) && in xfs_btree_lookup_get_block()
1830 be64_to_cpu((*blkp)->bb_u.l.bb_owner) != in xfs_btree_lookup_get_block()
1831 cur->bc_ino.ip->i_ino) in xfs_btree_lookup_get_block()
1834 /* Did we get the level we were looking for? */ in xfs_btree_lookup_get_block()
1835 if (be16_to_cpu((*blkp)->bb_level) != level) in xfs_btree_lookup_get_block()
1839 if (level != 0 && be16_to_cpu((*blkp)->bb_numrecs) == 0) in xfs_btree_lookup_get_block()
1842 xfs_btree_setbuf(cur, level, bp); in xfs_btree_lookup_get_block()
1848 xfs_trans_brelse(cur->bc_tp, bp); in xfs_btree_lookup_get_block()
1849 return -EFSCORRUPTED; in xfs_btree_lookup_get_block()
1853 * Get current search key. For level 0 we don't actually have a key
1860 int level, in xfs_lookup_get_search_key() argument
1865 if (level == 0) { in xfs_lookup_get_search_key()
1866 cur->bc_ops->init_key_from_rec(kp, in xfs_lookup_get_search_key()
1888 int level; /* level in the btree */ in xfs_btree_lookup() local
1894 /* No such thing as a zero-level tree. */ in xfs_btree_lookup()
1895 if (XFS_IS_CORRUPT(cur->bc_mp, cur->bc_nlevels == 0)) in xfs_btree_lookup()
1896 return -EFSCORRUPTED; in xfs_btree_lookup()
1902 cur->bc_ops->init_ptr_from_cur(cur, &ptr); in xfs_btree_lookup()
1906 * Iterate over each level in the btree, starting at the root. in xfs_btree_lookup()
1907 * For each level above the leaves, find the key we need, based in xfs_btree_lookup()
1909 * pointer down to the next level. in xfs_btree_lookup()
1911 for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) { in xfs_btree_lookup()
1913 error = xfs_btree_lookup_get_block(cur, level, pp, &block); in xfs_btree_lookup()
1919 * If we already had a key match at a higher level, we in xfs_btree_lookup()
1929 /* Set low and high entry numbers, 1-based. */ in xfs_btree_lookup()
1934 if (level != 0 || cur->bc_nlevels != 1) { in xfs_btree_lookup()
1937 cur->bc_mp, block, in xfs_btree_lookup()
1939 return -EFSCORRUPTED; in xfs_btree_lookup()
1942 cur->bc_levels[0].ptr = dir != XFS_LOOKUP_LE; in xfs_btree_lookup()
1958 kp = xfs_lookup_get_search_key(cur, level, in xfs_btree_lookup()
1963 * - less than, move right in xfs_btree_lookup()
1964 * - greater than, move left in xfs_btree_lookup()
1965 * - equal, we're done in xfs_btree_lookup()
1967 diff = cur->bc_ops->key_diff(cur, kp); in xfs_btree_lookup()
1971 high = keyno - 1; in xfs_btree_lookup()
1978 * If there are more levels, set up for the next level in xfs_btree_lookup()
1981 if (level > 0) { in xfs_btree_lookup()
1986 if (diff > 0 && --keyno < 1) in xfs_btree_lookup()
1990 error = xfs_btree_debug_check_ptr(cur, pp, 0, level); in xfs_btree_lookup()
1994 cur->bc_levels[level].ptr = keyno; in xfs_btree_lookup()
2003 * not the last block, we're in the wrong block. in xfs_btree_lookup()
2011 cur->bc_levels[0].ptr = keyno; in xfs_btree_lookup()
2015 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) in xfs_btree_lookup()
2016 return -EFSCORRUPTED; in xfs_btree_lookup()
2021 keyno--; in xfs_btree_lookup()
2022 cur->bc_levels[0].ptr = keyno; in xfs_btree_lookup()
2043 ASSERT(cur->bc_flags & XFS_BTREE_OVERLAPPING); in xfs_btree_high_key_from_key()
2045 (cur->bc_ops->key_len / 2)); in xfs_btree_high_key_from_key()
2062 cur->bc_ops->init_key_from_rec(key, rec); in xfs_btree_get_leaf_keys()
2064 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { in xfs_btree_get_leaf_keys()
2066 cur->bc_ops->init_high_key_from_rec(&max_hkey, rec); in xfs_btree_get_leaf_keys()
2069 cur->bc_ops->init_high_key_from_rec(&hkey, rec); in xfs_btree_get_leaf_keys()
2070 if (cur->bc_ops->diff_two_keys(cur, &hkey, &max_hkey) in xfs_btree_get_leaf_keys()
2076 memcpy(high, &max_hkey, cur->bc_ops->key_len / 2); in xfs_btree_get_leaf_keys()
2092 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { in xfs_btree_get_node_keys()
2094 cur->bc_ops->key_len / 2); in xfs_btree_get_node_keys()
2099 if (cur->bc_ops->diff_two_keys(cur, hkey, max_hkey) > 0) in xfs_btree_get_node_keys()
2104 memcpy(high, max_hkey, cur->bc_ops->key_len / 2); in xfs_btree_get_node_keys()
2107 cur->bc_ops->key_len); in xfs_btree_get_node_keys()
2118 if (be16_to_cpu(block->bb_level) == 0) in xfs_btree_get_keys()
2136 return (cur->bc_flags & XFS_BTREE_OVERLAPPING) || ptr == 1; in xfs_btree_needs_key_update()
2140 * Update the low and high parent keys of the given level, progressing
2142 * level do not need updating.
2147 int level, in __xfs_btree_updkeys() argument
2152 union xfs_btree_key key; /* keys from current level */ in __xfs_btree_updkeys()
2153 union xfs_btree_key *lkey; /* keys from the next level up */ in __xfs_btree_updkeys()
2155 union xfs_btree_key *nlkey; /* keys from the next level up */ in __xfs_btree_updkeys()
2160 ASSERT(cur->bc_flags & XFS_BTREE_OVERLAPPING); in __xfs_btree_updkeys()
2163 if (level + 1 >= cur->bc_nlevels) in __xfs_btree_updkeys()
2166 trace_xfs_btree_updkeys(cur, level, bp0); in __xfs_btree_updkeys()
2171 for (level++; level < cur->bc_nlevels; level++) { in __xfs_btree_updkeys()
2175 block = xfs_btree_get_block(cur, level, &bp); in __xfs_btree_updkeys()
2176 trace_xfs_btree_updkeys(cur, level, bp); in __xfs_btree_updkeys()
2178 error = xfs_btree_check_block(cur, block, level, bp); in __xfs_btree_updkeys()
2182 ptr = cur->bc_levels[level].ptr; in __xfs_btree_updkeys()
2186 !(cur->bc_ops->diff_two_keys(cur, nlkey, lkey) != 0 || in __xfs_btree_updkeys()
2187 cur->bc_ops->diff_two_keys(cur, nhkey, hkey) != 0)) in __xfs_btree_updkeys()
2191 if (level + 1 >= cur->bc_nlevels) in __xfs_btree_updkeys()
2199 /* Update all the keys from some level in cursor back to the root. */
2203 int level) in xfs_btree_updkeys_force() argument
2208 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_updkeys_force()
2209 return __xfs_btree_updkeys(cur, level, block, bp, true); in xfs_btree_updkeys_force()
2213 * Update the parent keys of the given level, progressing towards the root.
2218 int level) in xfs_btree_update_keys() argument
2226 ASSERT(level >= 0); in xfs_btree_update_keys()
2228 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_update_keys()
2229 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) in xfs_btree_update_keys()
2230 return __xfs_btree_updkeys(cur, level, block, bp, false); in xfs_btree_update_keys()
2233 * Go up the tree from this level toward the root. in xfs_btree_update_keys()
2234 * At each level, update the key value to the value input. in xfs_btree_update_keys()
2235 * Stop when we reach a level where the cursor isn't pointing in xfs_btree_update_keys()
2239 for (level++, ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) { in xfs_btree_update_keys()
2243 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_update_keys()
2245 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_update_keys()
2249 ptr = cur->bc_levels[level].ptr; in xfs_btree_update_keys()
2283 ptr = cur->bc_levels[0].ptr; in xfs_btree_update()
2291 * If we are tracking the last record in the tree and in xfs_btree_update()
2295 cur->bc_ops->update_lastrec(cur, block, rec, in xfs_btree_update()
2313 * Move 1 record left from cur/level if possible.
2319 int level, in xfs_btree_lshift() argument
2336 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_lshift()
2337 level == cur->bc_nlevels - 1) in xfs_btree_lshift()
2341 right = xfs_btree_get_block(cur, level, &rbp); in xfs_btree_lshift()
2344 error = xfs_btree_check_block(cur, right, level, rbp); in xfs_btree_lshift()
2358 if (cur->bc_levels[level].ptr <= 1) in xfs_btree_lshift()
2368 if (lrecs == cur->bc_ops->get_maxrecs(cur, level)) in xfs_btree_lshift()
2379 rrecs--; in xfs_btree_lshift()
2385 * If non-leaf, copy a key and a ptr to the left block. in xfs_btree_lshift()
2388 if (level > 0) { in xfs_btree_lshift()
2389 /* It's a non-leaf. Move keys and pointers. */ in xfs_btree_lshift()
2399 error = xfs_btree_debug_check_ptr(cur, rpp, 0, level); in xfs_btree_lshift()
2409 ASSERT(cur->bc_ops->keys_inorder(cur, in xfs_btree_lshift()
2410 xfs_btree_key_addr(cur, lrecs - 1, left), lkp)); in xfs_btree_lshift()
2421 ASSERT(cur->bc_ops->recs_inorder(cur, in xfs_btree_lshift()
2422 xfs_btree_rec_addr(cur, lrecs - 1, left), lrp)); in xfs_btree_lshift()
2434 XFS_BTREE_STATS_ADD(cur, moves, rrecs - 1); in xfs_btree_lshift()
2435 if (level > 0) { in xfs_btree_lshift()
2438 error = xfs_btree_debug_check_ptr(cur, rpp, i + 1, level); in xfs_btree_lshift()
2445 -1, rrecs); in xfs_btree_lshift()
2448 -1, rrecs); in xfs_btree_lshift()
2456 -1, rrecs); in xfs_btree_lshift()
2464 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { in xfs_btree_lshift()
2468 i = xfs_btree_firstrec(tcur, level); in xfs_btree_lshift()
2469 if (XFS_IS_CORRUPT(tcur->bc_mp, i != 1)) { in xfs_btree_lshift()
2470 error = -EFSCORRUPTED; in xfs_btree_lshift()
2474 error = xfs_btree_decrement(tcur, level, &i); in xfs_btree_lshift()
2479 error = xfs_btree_update_keys(tcur, level); in xfs_btree_lshift()
2487 error = xfs_btree_update_keys(cur, level); in xfs_btree_lshift()
2492 cur->bc_levels[level].ptr--; in xfs_btree_lshift()
2510 * Move 1 record right from cur/level if possible.
2516 int level, in xfs_btree_rshift() argument
2531 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_rshift()
2532 (level == cur->bc_nlevels - 1)) in xfs_btree_rshift()
2536 left = xfs_btree_get_block(cur, level, &lbp); in xfs_btree_rshift()
2539 error = xfs_btree_check_block(cur, left, level, lbp); in xfs_btree_rshift()
2554 if (cur->bc_levels[level].ptr >= lrecs) in xfs_btree_rshift()
2564 if (rrecs == cur->bc_ops->get_maxrecs(cur, level)) in xfs_btree_rshift()
2572 * copy the last left block entry to the hole. in xfs_btree_rshift()
2574 if (level > 0) { in xfs_btree_rshift()
2585 for (i = rrecs - 1; i >= 0; i--) { in xfs_btree_rshift()
2586 error = xfs_btree_debug_check_ptr(cur, rpp, i, level); in xfs_btree_rshift()
2594 error = xfs_btree_debug_check_ptr(cur, lpp, 0, level); in xfs_btree_rshift()
2605 ASSERT(cur->bc_ops->keys_inorder(cur, rkp, in xfs_btree_rshift()
2625 xfs_btree_set_numrecs(left, --lrecs); in xfs_btree_rshift()
2638 i = xfs_btree_lastrec(tcur, level); in xfs_btree_rshift()
2639 if (XFS_IS_CORRUPT(tcur->bc_mp, i != 1)) { in xfs_btree_rshift()
2640 error = -EFSCORRUPTED; in xfs_btree_rshift()
2644 error = xfs_btree_increment(tcur, level, &i); in xfs_btree_rshift()
2649 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { in xfs_btree_rshift()
2650 error = xfs_btree_update_keys(cur, level); in xfs_btree_rshift()
2656 error = xfs_btree_update_keys(tcur, level); in xfs_btree_rshift()
2678 * Split cur/level block in half.
2685 int level, in __xfs_btree_split() argument
2697 union xfs_btree_ptr rrptr; /* right-right sibling ptr */ in __xfs_btree_split()
2698 struct xfs_buf *rrbp; /* right-right buffer pointer */ in __xfs_btree_split()
2699 struct xfs_btree_block *rrblock; /* right-right btree block */ in __xfs_btree_split()
2709 left = xfs_btree_get_block(cur, level, &lbp); in __xfs_btree_split()
2712 error = xfs_btree_check_block(cur, left, level, lbp); in __xfs_btree_split()
2720 error = cur->bc_ops->alloc_block(cur, &lptr, &rptr, stat); in __xfs_btree_split()
2742 if ((lrecs & 1) && cur->bc_levels[level].ptr <= rrecs + 1) in __xfs_btree_split()
2744 src_index = (lrecs - rrecs + 1); in __xfs_btree_split()
2749 lrecs -= rrecs; in __xfs_btree_split()
2758 if (level > 0) { in __xfs_btree_split()
2759 /* It's a non-leaf. Move keys and pointers. */ in __xfs_btree_split()
2771 error = xfs_btree_debug_check_ptr(cur, lpp, i, level); in __xfs_btree_split()
2827 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) { in __xfs_btree_split()
2828 error = xfs_btree_update_keys(cur, level); in __xfs_btree_split()
2835 * If it's just pointing past the last entry in left, then we'll in __xfs_btree_split()
2838 if (cur->bc_levels[level].ptr > lrecs + 1) { in __xfs_btree_split()
2839 xfs_btree_setbuf(cur, level, rbp); in __xfs_btree_split()
2840 cur->bc_levels[level].ptr -= lrecs; in __xfs_btree_split()
2846 if (level + 1 < cur->bc_nlevels) { in __xfs_btree_split()
2850 (*curp)->bc_levels[level + 1].ptr++; in __xfs_btree_split()
2866 int level; member
2895 if (args->kswapd) in xfs_btree_split_worker()
2899 xfs_trans_set_context(args->cur->bc_tp); in xfs_btree_split_worker()
2901 args->result = __xfs_btree_split(args->cur, args->level, args->ptrp, in xfs_btree_split_worker()
2902 args->key, args->curp, args->stat); in xfs_btree_split_worker()
2904 xfs_trans_clear_context(args->cur->bc_tp); in xfs_btree_split_worker()
2911 complete(args->done); in xfs_btree_split_worker()
2923 int level, in xfs_btree_split() argument
2932 if (cur->bc_btnum != XFS_BTNUM_BMAP) in xfs_btree_split()
2933 return __xfs_btree_split(cur, level, ptrp, key, curp, stat); in xfs_btree_split()
2936 args.level = level; in xfs_btree_split()
2962 int *stat) /* return status - 0 fail */ in xfs_btree_new_iroot()
2972 int level; /* btree level */ in xfs_btree_new_iroot() local
2978 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE); in xfs_btree_new_iroot()
2980 level = cur->bc_nlevels - 1; in xfs_btree_new_iroot()
2986 error = cur->bc_ops->alloc_block(cur, pp, &nptr, stat); in xfs_btree_new_iroot()
3004 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) { in xfs_btree_new_iroot()
3006 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_new_iroot()
3007 cblock->bb_u.l.bb_blkno = bno; in xfs_btree_new_iroot()
3009 cblock->bb_u.s.bb_blkno = bno; in xfs_btree_new_iroot()
3012 be16_add_cpu(&block->bb_level, 1); in xfs_btree_new_iroot()
3014 cur->bc_nlevels++; in xfs_btree_new_iroot()
3015 ASSERT(cur->bc_nlevels <= cur->bc_maxlevels); in xfs_btree_new_iroot()
3016 cur->bc_levels[level + 1].ptr = 1; in xfs_btree_new_iroot()
3023 for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) { in xfs_btree_new_iroot()
3024 error = xfs_btree_debug_check_ptr(cur, pp, i, level); in xfs_btree_new_iroot()
3031 error = xfs_btree_debug_check_ptr(cur, &nptr, 0, level); in xfs_btree_new_iroot()
3037 xfs_iroot_realloc(cur->bc_ino.ip, in xfs_btree_new_iroot()
3038 1 - xfs_btree_get_numrecs(cblock), in xfs_btree_new_iroot()
3039 cur->bc_ino.whichfork); in xfs_btree_new_iroot()
3041 xfs_btree_setbuf(cur, level, cbp); in xfs_btree_new_iroot()
3045 * the root is at the right level. in xfs_btree_new_iroot()
3048 xfs_btree_log_keys(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs)); in xfs_btree_new_iroot()
3049 xfs_btree_log_ptrs(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs)); in xfs_btree_new_iroot()
3052 XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_ino.whichfork); in xfs_btree_new_iroot()
3083 cur->bc_ops->init_ptr_from_cur(cur, &rptr); in xfs_btree_new_root()
3086 error = cur->bc_ops->alloc_block(cur, &rptr, &lptr, stat); in xfs_btree_new_root()
3098 /* Set the root in the holding structure increasing the level by 1. */ in xfs_btree_new_root()
3099 cur->bc_ops->set_root(cur, &lptr, 1); in xfs_btree_new_root()
3102 * At the previous root level there are now two blocks: the old root, in xfs_btree_new_root()
3107 block = xfs_btree_get_block(cur, cur->bc_nlevels - 1, &bp); in xfs_btree_new_root()
3110 error = xfs_btree_check_block(cur, block, cur->bc_nlevels - 1, bp); in xfs_btree_new_root()
3140 xfs_btree_init_block_cur(cur, nbp, cur->bc_nlevels, 2); in xfs_btree_new_root()
3176 xfs_btree_setbuf(cur, cur->bc_nlevels, nbp); in xfs_btree_new_root()
3177 cur->bc_levels[cur->bc_nlevels].ptr = nptr; in xfs_btree_new_root()
3178 cur->bc_nlevels++; in xfs_btree_new_root()
3179 ASSERT(cur->bc_nlevels <= cur->bc_maxlevels); in xfs_btree_new_root()
3192 int level, /* btree level */ in xfs_btree_make_block_unfull() argument
3203 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_make_block_unfull()
3204 level == cur->bc_nlevels - 1) { in xfs_btree_make_block_unfull()
3205 struct xfs_inode *ip = cur->bc_ino.ip; in xfs_btree_make_block_unfull()
3207 if (numrecs < cur->bc_ops->get_dmaxrecs(cur, level)) { in xfs_btree_make_block_unfull()
3209 xfs_iroot_realloc(ip, 1, cur->bc_ino.whichfork); in xfs_btree_make_block_unfull()
3219 xfs_trans_log_inode(cur->bc_tp, ip, logflags); in xfs_btree_make_block_unfull()
3226 error = xfs_btree_rshift(cur, level, stat); in xfs_btree_make_block_unfull()
3231 error = xfs_btree_lshift(cur, level, stat); in xfs_btree_make_block_unfull()
3236 *oindex = *index = cur->bc_levels[level].ptr; in xfs_btree_make_block_unfull()
3243 * If this works we have to re-set our variables because we in xfs_btree_make_block_unfull()
3246 error = xfs_btree_split(cur, level, nptr, key, ncur, stat); in xfs_btree_make_block_unfull()
3251 *index = cur->bc_levels[level].ptr; in xfs_btree_make_block_unfull()
3256 * Insert one record/level. Return information to the caller
3257 * allowing the next level up to proceed if necessary.
3262 int level, /* level to insert record at */ in xfs_btree_insrec() argument
3287 * root level, allocate a new root block and we're done. in xfs_btree_insrec()
3289 if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) && in xfs_btree_insrec()
3290 (level >= cur->bc_nlevels)) { in xfs_btree_insrec()
3298 ptr = cur->bc_levels[level].ptr; in xfs_btree_insrec()
3309 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_insrec()
3314 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_insrec()
3320 if (level == 0) { in xfs_btree_insrec()
3321 ASSERT(cur->bc_ops->recs_inorder(cur, rec, in xfs_btree_insrec()
3324 ASSERT(cur->bc_ops->keys_inorder(cur, key, in xfs_btree_insrec()
3332 * make the block un-full. in xfs_btree_insrec()
3335 if (numrecs == cur->bc_ops->get_maxrecs(cur, level)) { in xfs_btree_insrec()
3336 error = xfs_btree_make_block_unfull(cur, level, numrecs, in xfs_btree_insrec()
3346 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_insrec()
3350 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_insrec()
3359 XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr + 1); in xfs_btree_insrec()
3361 if (level > 0) { in xfs_btree_insrec()
3369 for (i = numrecs - ptr; i >= 0; i--) { in xfs_btree_insrec()
3370 error = xfs_btree_debug_check_ptr(cur, pp, i, level); in xfs_btree_insrec()
3375 xfs_btree_shift_keys(cur, kp, 1, numrecs - ptr + 1); in xfs_btree_insrec()
3376 xfs_btree_shift_ptrs(cur, pp, 1, numrecs - ptr + 1); in xfs_btree_insrec()
3378 error = xfs_btree_debug_check_ptr(cur, ptrp, 0, level); in xfs_btree_insrec()
3391 ASSERT(cur->bc_ops->keys_inorder(cur, kp, in xfs_btree_insrec()
3401 xfs_btree_shift_recs(cur, rp, 1, numrecs - ptr + 1); in xfs_btree_insrec()
3409 ASSERT(cur->bc_ops->recs_inorder(cur, rp, in xfs_btree_insrec()
3429 error = xfs_btree_update_keys(cur, level); in xfs_btree_insrec()
3435 * If we are tracking the last record in the tree and in xfs_btree_insrec()
3438 if (xfs_btree_is_lastrec(cur, block, level)) { in xfs_btree_insrec()
3439 cur->bc_ops->update_lastrec(cur, block, rec, in xfs_btree_insrec()
3465 * A multi-level split of the tree on insert will invalidate the original
3476 int level; /* current level number in btree */ in xfs_btree_insert() local
3479 struct xfs_btree_cur *pcur; /* previous level's cursor */ in xfs_btree_insert()
3484 level = 0; in xfs_btree_insert()
3492 cur->bc_ops->init_rec_from_cur(cur, &rec); in xfs_btree_insert()
3493 cur->bc_ops->init_key_from_rec(key, &rec); in xfs_btree_insert()
3496 * Loop going up the tree, starting at the leaf level. in xfs_btree_insert()
3498 * the insert is finished with this level. in xfs_btree_insert()
3502 * Insert nrec/nptr into this level of the tree. in xfs_btree_insert()
3505 error = xfs_btree_insrec(pcur, level, &nptr, &rec, key, in xfs_btree_insert()
3513 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_insert()
3514 error = -EFSCORRUPTED; in xfs_btree_insert()
3517 level++; in xfs_btree_insert()
3527 if (cur->bc_ops->update_cursor) in xfs_btree_insert()
3528 cur->bc_ops->update_cursor(pcur, cur); in xfs_btree_insert()
3529 cur->bc_nlevels = pcur->bc_nlevels; in xfs_btree_insert()
3546 * Try to merge a non-leaf block back into the inode root.
3557 int whichfork = cur->bc_ino.whichfork; in xfs_btree_kill_iroot()
3558 struct xfs_inode *ip = cur->bc_ino.ip; in xfs_btree_kill_iroot()
3567 int level; in xfs_btree_kill_iroot() local
3576 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE); in xfs_btree_kill_iroot()
3577 ASSERT(cur->bc_nlevels > 1); in xfs_btree_kill_iroot()
3583 level = cur->bc_nlevels - 1; in xfs_btree_kill_iroot()
3584 if (level == 1) in xfs_btree_kill_iroot()
3594 cblock = xfs_btree_get_block(cur, level - 1, &cbp); in xfs_btree_kill_iroot()
3598 * Only do this if the next level will fit. in xfs_btree_kill_iroot()
3600 * instead of freeing the root you free the next level. in xfs_btree_kill_iroot()
3602 if (numrecs > cur->bc_ops->get_dmaxrecs(cur, level)) in xfs_btree_kill_iroot()
3614 index = numrecs - cur->bc_ops->get_maxrecs(cur, level); in xfs_btree_kill_iroot()
3616 xfs_iroot_realloc(cur->bc_ino.ip, index, in xfs_btree_kill_iroot()
3617 cur->bc_ino.whichfork); in xfs_btree_kill_iroot()
3618 block = ifp->if_broot; in xfs_btree_kill_iroot()
3621 be16_add_cpu(&block->bb_numrecs, index); in xfs_btree_kill_iroot()
3622 ASSERT(block->bb_numrecs == cblock->bb_numrecs); in xfs_btree_kill_iroot()
3632 error = xfs_btree_debug_check_ptr(cur, cpp, i, level - 1); in xfs_btree_kill_iroot()
3643 cur->bc_levels[level - 1].bp = NULL; in xfs_btree_kill_iroot()
3644 be16_add_cpu(&block->bb_level, -1); in xfs_btree_kill_iroot()
3645 xfs_trans_log_inode(cur->bc_tp, ip, in xfs_btree_kill_iroot()
3646 XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_ino.whichfork)); in xfs_btree_kill_iroot()
3647 cur->bc_nlevels--; in xfs_btree_kill_iroot()
3659 int level, in xfs_btree_kill_root() argument
3667 * Update the root pointer, decreasing the level by 1 and then in xfs_btree_kill_root()
3670 cur->bc_ops->set_root(cur, newroot, -1); in xfs_btree_kill_root()
3676 cur->bc_levels[level].bp = NULL; in xfs_btree_kill_root()
3677 cur->bc_levels[level].ra = 0; in xfs_btree_kill_root()
3678 cur->bc_nlevels--; in xfs_btree_kill_root()
3686 int level, in xfs_btree_dec_cursor() argument
3692 if (level > 0) { in xfs_btree_dec_cursor()
3693 error = xfs_btree_decrement(cur, level, &i); in xfs_btree_dec_cursor()
3703 * Single level of the btree record deletion routine.
3704 * Delete record pointed to by cur/level.
3706 * Return 0 for error, 1 for done, 2 to go on to the next level.
3711 int level, /* level removing record from */ in xfs_btree_delrec() argument
3712 int *stat) /* fail/done/go-on */ in xfs_btree_delrec()
3727 struct xfs_btree_block *rrblock; /* right-right btree block */ in xfs_btree_delrec()
3728 struct xfs_buf *rrbp; /* right-right buffer pointer */ in xfs_btree_delrec()
3736 ptr = cur->bc_levels[level].ptr; in xfs_btree_delrec()
3743 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_delrec()
3747 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_delrec()
3759 XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr); in xfs_btree_delrec()
3762 if (level > 0) { in xfs_btree_delrec()
3770 for (i = 0; i < numrecs - ptr; i++) { in xfs_btree_delrec()
3771 error = xfs_btree_debug_check_ptr(cur, lpp, i, level); in xfs_btree_delrec()
3777 xfs_btree_shift_keys(cur, lkp, -1, numrecs - ptr); in xfs_btree_delrec()
3778 xfs_btree_shift_ptrs(cur, lpp, -1, numrecs - ptr); in xfs_btree_delrec()
3779 xfs_btree_log_keys(cur, bp, ptr, numrecs - 1); in xfs_btree_delrec()
3780 xfs_btree_log_ptrs(cur, bp, ptr, numrecs - 1); in xfs_btree_delrec()
3787 -1, numrecs - ptr); in xfs_btree_delrec()
3788 xfs_btree_log_recs(cur, bp, ptr, numrecs - 1); in xfs_btree_delrec()
3795 xfs_btree_set_numrecs(block, --numrecs); in xfs_btree_delrec()
3799 * If we are tracking the last record in the tree and in xfs_btree_delrec()
3802 if (xfs_btree_is_lastrec(cur, block, level)) { in xfs_btree_delrec()
3803 cur->bc_ops->update_lastrec(cur, block, NULL, in xfs_btree_delrec()
3808 * We're at the root level. First, shrink the root block in-memory. in xfs_btree_delrec()
3809 * Try to get rid of the next level down. If we can't then there's in xfs_btree_delrec()
3812 if (level == cur->bc_nlevels - 1) { in xfs_btree_delrec()
3813 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) { in xfs_btree_delrec()
3814 xfs_iroot_realloc(cur->bc_ino.ip, -1, in xfs_btree_delrec()
3815 cur->bc_ino.whichfork); in xfs_btree_delrec()
3821 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
3829 * If this is the root level, and there's only one entry left, in xfs_btree_delrec()
3830 * and it's NOT the leaf level, then we can get rid of this in xfs_btree_delrec()
3831 * level. in xfs_btree_delrec()
3833 if (numrecs == 1 && level > 0) { in xfs_btree_delrec()
3840 error = xfs_btree_kill_root(cur, bp, level, pp); in xfs_btree_delrec()
3843 } else if (level > 0) { in xfs_btree_delrec()
3844 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
3857 error = xfs_btree_update_keys(cur, level); in xfs_btree_delrec()
3866 if (numrecs >= cur->bc_ops->get_minrecs(cur, level)) { in xfs_btree_delrec()
3867 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
3876 * see if we can re-balance by moving only one record. in xfs_btree_delrec()
3881 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) { in xfs_btree_delrec()
3884 * into the root and delete it. Can't go up to next level, in xfs_btree_delrec()
3889 level == cur->bc_nlevels - 2) { in xfs_btree_delrec()
3892 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
3904 * disrupt the next level up. in xfs_btree_delrec()
3916 * Move the temp cursor to the last entry in the next block. in xfs_btree_delrec()
3919 i = xfs_btree_lastrec(tcur, level); in xfs_btree_delrec()
3920 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3921 error = -EFSCORRUPTED; in xfs_btree_delrec()
3925 error = xfs_btree_increment(tcur, level, &i); in xfs_btree_delrec()
3928 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3929 error = -EFSCORRUPTED; in xfs_btree_delrec()
3933 i = xfs_btree_lastrec(tcur, level); in xfs_btree_delrec()
3934 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3935 error = -EFSCORRUPTED; in xfs_btree_delrec()
3940 right = xfs_btree_get_block(tcur, level, &rbp); in xfs_btree_delrec()
3942 error = xfs_btree_check_block(tcur, right, level, rbp); in xfs_btree_delrec()
3951 * won't make it too empty, and left-shifting an entry out in xfs_btree_delrec()
3954 if (xfs_btree_get_numrecs(right) - 1 >= in xfs_btree_delrec()
3955 cur->bc_ops->get_minrecs(tcur, level)) { in xfs_btree_delrec()
3956 error = xfs_btree_lshift(tcur, level, &i); in xfs_btree_delrec()
3961 cur->bc_ops->get_minrecs(tcur, level)); in xfs_btree_delrec()
3966 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
3976 * to our block again (last record). in xfs_btree_delrec()
3980 i = xfs_btree_firstrec(tcur, level); in xfs_btree_delrec()
3981 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3982 error = -EFSCORRUPTED; in xfs_btree_delrec()
3986 error = xfs_btree_decrement(tcur, level, &i); in xfs_btree_delrec()
3989 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
3990 error = -EFSCORRUPTED; in xfs_btree_delrec()
4005 i = xfs_btree_firstrec(tcur, level); in xfs_btree_delrec()
4006 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
4007 error = -EFSCORRUPTED; in xfs_btree_delrec()
4011 error = xfs_btree_decrement(tcur, level, &i); in xfs_btree_delrec()
4014 i = xfs_btree_firstrec(tcur, level); in xfs_btree_delrec()
4015 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { in xfs_btree_delrec()
4016 error = -EFSCORRUPTED; in xfs_btree_delrec()
4021 left = xfs_btree_get_block(tcur, level, &lbp); in xfs_btree_delrec()
4023 error = xfs_btree_check_block(cur, left, level, lbp); in xfs_btree_delrec()
4032 * won't make it too empty, and right-shifting an entry out in xfs_btree_delrec()
4035 if (xfs_btree_get_numrecs(left) - 1 >= in xfs_btree_delrec()
4036 cur->bc_ops->get_minrecs(tcur, level)) { in xfs_btree_delrec()
4037 error = xfs_btree_rshift(tcur, level, &i); in xfs_btree_delrec()
4042 cur->bc_ops->get_minrecs(tcur, level)); in xfs_btree_delrec()
4045 if (level == 0) in xfs_btree_delrec()
4046 cur->bc_levels[0].ptr++; in xfs_btree_delrec()
4069 cur->bc_ops->get_maxrecs(cur, level)) { in xfs_btree_delrec()
4086 cur->bc_ops->get_maxrecs(cur, level)) { in xfs_btree_delrec()
4103 error = xfs_btree_dec_cursor(cur, level, stat); in xfs_btree_delrec()
4117 if (level > 0) { in xfs_btree_delrec()
4118 /* It's a non-leaf. Move keys and pointers. */ in xfs_btree_delrec()
4130 error = xfs_btree_debug_check_ptr(cur, rpp, i, level); in xfs_btree_delrec()
4183 cur->bc_levels[level].bp = lbp; in xfs_btree_delrec()
4184 cur->bc_levels[level].ptr += lrecs; in xfs_btree_delrec()
4185 cur->bc_levels[level].ra = 0; in xfs_btree_delrec()
4188 * If we joined with the right neighbor and there's a level above in xfs_btree_delrec()
4189 * us, increment the cursor at that level. in xfs_btree_delrec()
4191 else if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) || in xfs_btree_delrec()
4192 (level + 1 < cur->bc_nlevels)) { in xfs_btree_delrec()
4193 error = xfs_btree_increment(cur, level + 1, &i); in xfs_btree_delrec()
4199 * Readjust the ptr at this level if it's not a leaf, since it's in xfs_btree_delrec()
4202 * We can't use decrement because it would change the next level up. in xfs_btree_delrec()
4204 if (level > 0) in xfs_btree_delrec()
4205 cur->bc_levels[level].ptr--; in xfs_btree_delrec()
4210 * bc_levels[level + 1].ptr points to the old block so that the caller in xfs_btree_delrec()
4217 /* Return value means the next level up has something to do. */ in xfs_btree_delrec()
4238 int level; in xfs_btree_delete() local
4243 * Go up the tree, starting at leaf level. in xfs_btree_delete()
4245 * If 2 is returned then a join was done; go to the next level. in xfs_btree_delete()
4248 for (level = 0, i = 2; i == 2; level++) { in xfs_btree_delete()
4249 error = xfs_btree_delrec(cur, level, &i); in xfs_btree_delete()
4260 if (joined && (cur->bc_flags & XFS_BTREE_OVERLAPPING)) { in xfs_btree_delete()
4267 for (level = 1; level < cur->bc_nlevels; level++) { in xfs_btree_delete()
4268 if (cur->bc_levels[level].ptr == 0) { in xfs_btree_delete()
4269 error = xfs_btree_decrement(cur, level, &i); in xfs_btree_delete()
4284 * Get the data from the pointed-to record.
4299 ptr = cur->bc_levels[0].ptr; in xfs_btree_get_rec()
4328 int level, in xfs_btree_visit_block() argument
4338 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA); in xfs_btree_visit_block()
4339 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_visit_block()
4342 error = fn(cur, level, data); in xfs_btree_visit_block()
4349 return -ENOENT; in xfs_btree_visit_block()
4357 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_visit_block()
4358 if (be64_to_cpu(rptr.l) == XFS_DADDR_TO_FSB(cur->bc_mp, in xfs_btree_visit_block()
4360 return -EFSCORRUPTED; in xfs_btree_visit_block()
4362 if (be32_to_cpu(rptr.s) == xfs_daddr_to_agbno(cur->bc_mp, in xfs_btree_visit_block()
4364 return -EFSCORRUPTED; in xfs_btree_visit_block()
4366 return xfs_btree_lookup_get_block(cur, level, &rptr, &block); in xfs_btree_visit_block()
4379 int level; in xfs_btree_visit_blocks() local
4383 cur->bc_ops->init_ptr_from_cur(cur, &lptr); in xfs_btree_visit_blocks()
4385 /* for each level */ in xfs_btree_visit_blocks()
4386 for (level = cur->bc_nlevels - 1; level >= 0; level--) { in xfs_btree_visit_blocks()
4388 error = xfs_btree_lookup_get_block(cur, level, &lptr, &block); in xfs_btree_visit_blocks()
4392 /* readahead the left most block for the next level down */ in xfs_btree_visit_blocks()
4393 if (level > 0) { in xfs_btree_visit_blocks()
4408 /* for each buffer in the level */ in xfs_btree_visit_blocks()
4410 error = xfs_btree_visit_block(cur, level, fn, data); in xfs_btree_visit_blocks()
4413 if (error != -ENOENT) in xfs_btree_visit_blocks()
4428 * We do the btree walk in the most optimal manner possible - we have sibling
4429 * pointers so we can just walk all the blocks on each level from left to right
4430 * in a single pass, and then move to the next level and do the same. We can
4452 int level, in xfs_btree_block_change_owner() argument
4460 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_block_change_owner()
4461 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) { in xfs_btree_block_change_owner()
4462 if (block->bb_u.l.bb_owner == cpu_to_be64(bbcoi->new_owner)) in xfs_btree_block_change_owner()
4464 block->bb_u.l.bb_owner = cpu_to_be64(bbcoi->new_owner); in xfs_btree_block_change_owner()
4466 if (block->bb_u.s.bb_owner == cpu_to_be32(bbcoi->new_owner)) in xfs_btree_block_change_owner()
4468 block->bb_u.s.bb_owner = cpu_to_be32(bbcoi->new_owner); in xfs_btree_block_change_owner()
4475 * block is formatted into the on-disk inode fork. We still change it, in xfs_btree_block_change_owner()
4479 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE); in xfs_btree_block_change_owner()
4480 ASSERT(level == cur->bc_nlevels - 1); in xfs_btree_block_change_owner()
4484 if (cur->bc_tp) { in xfs_btree_block_change_owner()
4485 if (!xfs_trans_ordered_buf(cur->bc_tp, bp)) { in xfs_btree_block_change_owner()
4487 return -EAGAIN; in xfs_btree_block_change_owner()
4490 xfs_buf_delwri_queue(bp, bbcoi->buffer_list); in xfs_btree_block_change_owner()
4511 /* Verify the v5 fields of a long-format btree block. */
4517 struct xfs_mount *mp = bp->b_mount; in xfs_btree_lblock_v5hdr_verify()
4522 if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid)) in xfs_btree_lblock_v5hdr_verify()
4524 if (block->bb_u.l.bb_blkno != cpu_to_be64(xfs_buf_daddr(bp))) in xfs_btree_lblock_v5hdr_verify()
4527 be64_to_cpu(block->bb_u.l.bb_owner) != owner) in xfs_btree_lblock_v5hdr_verify()
4532 /* Verify a long-format btree block. */
4538 struct xfs_mount *mp = bp->b_mount; in xfs_btree_lblock_verify()
4544 if (be16_to_cpu(block->bb_numrecs) > max_recs) in xfs_btree_lblock_verify()
4549 fa = xfs_btree_check_lblock_siblings(mp, NULL, -1, fsb, in xfs_btree_lblock_verify()
4550 block->bb_u.l.bb_leftsib); in xfs_btree_lblock_verify()
4552 fa = xfs_btree_check_lblock_siblings(mp, NULL, -1, fsb, in xfs_btree_lblock_verify()
4553 block->bb_u.l.bb_rightsib); in xfs_btree_lblock_verify()
4558 * xfs_btree_sblock_v5hdr_verify() -- verify the v5 fields of a short-format
4567 struct xfs_mount *mp = bp->b_mount; in xfs_btree_sblock_v5hdr_verify()
4569 struct xfs_perag *pag = bp->b_pag; in xfs_btree_sblock_v5hdr_verify()
4573 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid)) in xfs_btree_sblock_v5hdr_verify()
4575 if (block->bb_u.s.bb_blkno != cpu_to_be64(xfs_buf_daddr(bp))) in xfs_btree_sblock_v5hdr_verify()
4577 if (pag && be32_to_cpu(block->bb_u.s.bb_owner) != pag->pag_agno) in xfs_btree_sblock_v5hdr_verify()
4583 * xfs_btree_sblock_verify() -- verify a short-format btree block
4593 struct xfs_mount *mp = bp->b_mount; in xfs_btree_sblock_verify()
4599 if (be16_to_cpu(block->bb_numrecs) > max_recs) in xfs_btree_sblock_verify()
4604 fa = xfs_btree_check_sblock_siblings(bp->b_pag, NULL, -1, agbno, in xfs_btree_sblock_verify()
4605 block->bb_u.s.bb_leftsib); in xfs_btree_sblock_verify()
4607 fa = xfs_btree_check_sblock_siblings(bp->b_pag, NULL, -1, agbno, in xfs_btree_sblock_verify()
4608 block->bb_u.s.bb_rightsib); in xfs_btree_sblock_verify()
4658 * We start by assuming a single level tree consumes a single block, then track
4659 * the number of blocks each node level consumes until we no longer have space
4660 * to store the next node level. At this point, we are indexing all the leaf
4670 unsigned long long blocks_left = leaf_blocks - 1; in xfs_btree_space_to_height()
4677 blocks_left -= node_blocks; in xfs_btree_space_to_height()
4705 ASSERT(cur->bc_ops->init_high_key_from_rec); in xfs_btree_simple_query_range()
4706 ASSERT(cur->bc_ops->diff_two_keys); in xfs_btree_simple_query_range()
4732 cur->bc_ops->init_high_key_from_rec(&rec_key, recp); in xfs_btree_simple_query_range()
4734 diff = cur->bc_ops->diff_two_keys(cur, low_key, in xfs_btree_simple_query_range()
4741 cur->bc_ops->init_key_from_rec(&rec_key, recp); in xfs_btree_simple_query_range()
4742 diff = cur->bc_ops->diff_two_keys(cur, &rec_key, high_key); in xfs_btree_simple_query_range()
4799 int level; in xfs_btree_overlapped_query_range() local
4805 level = cur->bc_nlevels - 1; in xfs_btree_overlapped_query_range()
4806 cur->bc_ops->init_ptr_from_cur(cur, &ptr); in xfs_btree_overlapped_query_range()
4807 error = xfs_btree_lookup_get_block(cur, level, &ptr, &block); in xfs_btree_overlapped_query_range()
4810 xfs_btree_get_block(cur, level, &bp); in xfs_btree_overlapped_query_range()
4811 trace_xfs_btree_overlapped_query_range(cur, level, bp); in xfs_btree_overlapped_query_range()
4813 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_overlapped_query_range()
4817 cur->bc_levels[level].ptr = 1; in xfs_btree_overlapped_query_range()
4819 while (level < cur->bc_nlevels) { in xfs_btree_overlapped_query_range()
4820 block = xfs_btree_get_block(cur, level, &bp); in xfs_btree_overlapped_query_range()
4823 if (cur->bc_levels[level].ptr > in xfs_btree_overlapped_query_range()
4824 be16_to_cpu(block->bb_numrecs)) { in xfs_btree_overlapped_query_range()
4826 if (level < cur->bc_nlevels - 1) in xfs_btree_overlapped_query_range()
4827 cur->bc_levels[level + 1].ptr++; in xfs_btree_overlapped_query_range()
4828 level++; in xfs_btree_overlapped_query_range()
4832 if (level == 0) { in xfs_btree_overlapped_query_range()
4834 recp = xfs_btree_rec_addr(cur, cur->bc_levels[0].ptr, in xfs_btree_overlapped_query_range()
4837 cur->bc_ops->init_high_key_from_rec(&rec_hkey, recp); in xfs_btree_overlapped_query_range()
4838 ldiff = cur->bc_ops->diff_two_keys(cur, &rec_hkey, in xfs_btree_overlapped_query_range()
4841 cur->bc_ops->init_key_from_rec(&rec_key, recp); in xfs_btree_overlapped_query_range()
4842 hdiff = cur->bc_ops->diff_two_keys(cur, high_key, in xfs_btree_overlapped_query_range()
4858 cur->bc_levels[level].ptr++; in xfs_btree_overlapped_query_range()
4863 lkp = xfs_btree_key_addr(cur, cur->bc_levels[level].ptr, block); in xfs_btree_overlapped_query_range()
4864 hkp = xfs_btree_high_key_addr(cur, cur->bc_levels[level].ptr, in xfs_btree_overlapped_query_range()
4866 pp = xfs_btree_ptr_addr(cur, cur->bc_levels[level].ptr, block); in xfs_btree_overlapped_query_range()
4868 ldiff = cur->bc_ops->diff_two_keys(cur, hkp, low_key); in xfs_btree_overlapped_query_range()
4869 hdiff = cur->bc_ops->diff_two_keys(cur, high_key, lkp); in xfs_btree_overlapped_query_range()
4877 level--; in xfs_btree_overlapped_query_range()
4878 error = xfs_btree_lookup_get_block(cur, level, pp, in xfs_btree_overlapped_query_range()
4882 xfs_btree_get_block(cur, level, &bp); in xfs_btree_overlapped_query_range()
4883 trace_xfs_btree_overlapped_query_range(cur, level, bp); in xfs_btree_overlapped_query_range()
4885 error = xfs_btree_check_block(cur, block, level, bp); in xfs_btree_overlapped_query_range()
4889 cur->bc_levels[level].ptr = 1; in xfs_btree_overlapped_query_range()
4895 cur->bc_levels[level].ptr++; in xfs_btree_overlapped_query_range()
4901 * block, a subsequent non-error cursor deletion will not release in xfs_btree_overlapped_query_range()
4902 * node-level buffers, causing a buffer leak. This is quite possible in xfs_btree_overlapped_query_range()
4903 * with a zero-results range query, so release the buffers if we in xfs_btree_overlapped_query_range()
4906 if (cur->bc_levels[0].bp == NULL) { in xfs_btree_overlapped_query_range()
4907 for (i = 0; i < cur->bc_nlevels; i++) { in xfs_btree_overlapped_query_range()
4908 if (cur->bc_levels[i].bp) { in xfs_btree_overlapped_query_range()
4909 xfs_trans_brelse(cur->bc_tp, in xfs_btree_overlapped_query_range()
4910 cur->bc_levels[i].bp); in xfs_btree_overlapped_query_range()
4911 cur->bc_levels[i].bp = NULL; in xfs_btree_overlapped_query_range()
4912 cur->bc_levels[i].ptr = 0; in xfs_btree_overlapped_query_range()
4913 cur->bc_levels[i].ra = 0; in xfs_btree_overlapped_query_range()
4925 * code. This function returns -ECANCELED, zero, or a negative error code.
4940 cur->bc_rec = *high_rec; in xfs_btree_query_range()
4941 cur->bc_ops->init_rec_from_cur(cur, &rec); in xfs_btree_query_range()
4942 cur->bc_ops->init_key_from_rec(&high_key, &rec); in xfs_btree_query_range()
4944 cur->bc_rec = *low_rec; in xfs_btree_query_range()
4945 cur->bc_ops->init_rec_from_cur(cur, &rec); in xfs_btree_query_range()
4946 cur->bc_ops->init_key_from_rec(&low_key, &rec); in xfs_btree_query_range()
4949 if (cur->bc_ops->diff_two_keys(cur, &low_key, &high_key) > 0) in xfs_btree_query_range()
4950 return -EINVAL; in xfs_btree_query_range()
4952 if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING)) in xfs_btree_query_range()
4969 memset(&cur->bc_rec, 0, sizeof(cur->bc_rec)); in xfs_btree_query_all()
4979 int level, in xfs_btree_count_blocks_helper() argument
5006 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_diff_two_ptrs()
5007 return (int64_t)be64_to_cpu(a->l) - be64_to_cpu(b->l); in xfs_btree_diff_two_ptrs()
5008 return (int64_t)be32_to_cpu(a->s) - be32_to_cpu(b->s); in xfs_btree_diff_two_ptrs()
5018 return -ECANCELED; in xfs_btree_has_record_helper()
5033 if (error == -ECANCELED) { in xfs_btree_has_record()
5052 if (cur->bc_levels[0].ptr < xfs_btree_get_numrecs(block)) in xfs_btree_has_more_records()
5056 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) in xfs_btree_has_more_records()
5057 return block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK); in xfs_btree_has_more_records()
5059 return block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK); in xfs_btree_has_more_records()