Lines Matching refs:level
61 int level,
80 if (be16_to_cpu(block->bb_level) != level)
83 cur->bc_ops->get_maxrecs(cur, level))
87 level + 1))
91 level + 1))
102 int level,
108 fa = __xfs_btree_check_lblock(cur, block, level, bp);
126 int level,
143 if (be16_to_cpu(block->bb_level) != level)
146 cur->bc_ops->get_maxrecs(cur, level))
150 level + 1))
154 level + 1))
165 int level,
171 fa = __xfs_btree_check_sblock(cur, block, level, bp);
188 int level, /* level of the btree block */
192 return xfs_btree_check_lblock(cur, block, level, bp);
194 return xfs_btree_check_sblock(cur, block, level, bp);
202 int level)
204 if (level <= 0)
214 int level)
216 if (level <= 0)
222 * Check that a given (indexed) btree pointer at a certain level of a
230 int level)
234 level))
237 "Inode %llu fork %d: Corrupt btree %d pointer at level %d index %d.",
240 level, index);
243 level))
246 "AG %u: Corrupt btree %d pointer at level %d index %d.",
248 level, index);
359 int i; /* btree level */
365 * code works from level n down to 0, and if we get an error along the
399 int i; /* level number of btree block */
418 * For each level current, re-get the buffer and copy the ptr value.
449 * to the btree blocks at the previous level.
582 int level)
585 cur->bc_ops->get_maxrecs(cur, level) * cur->bc_ops->key_len +
637 int level = xfs_btree_get_level(block);
642 ((char *)block + xfs_btree_ptr_offset(cur, n, level));
672 * Retrieve the block pointer from the cursor at the given level.
678 int level, /* level in btree */
682 (level == cur->bc_nlevels - 1)) {
687 *bpp = cur->bc_bufs[level];
692 * Change the cursor to point to the first record at the given level.
698 int level) /* level to change */
704 * Get the block pointer for this level.
706 block = xfs_btree_get_block(cur, level, &bp);
707 if (xfs_btree_check_block(cur, block, level, bp))
717 cur->bc_ptrs[level] = 1;
723 * at the given level. Other levels are unaffected.
728 int level) /* level to change */
734 * Get the block pointer for this level.
736 block = xfs_btree_get_block(cur, level, &bp);
737 if (xfs_btree_check_block(cur, block, level, bp))
747 cur->bc_ptrs[level] = be16_to_cpu(block->bb_numrecs);
909 * Read-ahead btree blocks, at the given level.
915 int lev, /* level in btree */
921 * No readahead needed if we are at the root level and the
986 * Set the buffer for level "lev" in the cursor to bp, releasing
992 int lev, /* level in btree */
1091 __u16 level,
1100 buf->bb_level = cpu_to_be16(level);
1133 __u16 level,
1138 btnum, level, numrecs, owner, 0);
1145 int level,
1162 cur->bc_btnum, level, numrecs,
1175 int level)
1179 if (level > 0)
1442 int level = xfs_btree_get_level(block);
1446 xfs_btree_ptr_offset(cur, first, level),
1447 xfs_btree_ptr_offset(cur, last + 1, level) - 1);
1524 * Increment cursor by one record at the level.
1530 int level,
1539 ASSERT(level < cur->bc_nlevels);
1541 /* Read-ahead to the right at this level. */
1542 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
1545 block = xfs_btree_get_block(cur, level, &bp);
1548 error = xfs_btree_check_block(cur, block, level, bp);
1554 if (++cur->bc_ptrs[level] <= xfs_btree_get_numrecs(block))
1568 for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1601 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) {
1626 * Decrement cursor by one record at the level.
1632 int level,
1641 ASSERT(level < cur->bc_nlevels);
1643 /* Read-ahead to the left at this level. */
1644 xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA);
1647 if (--cur->bc_ptrs[level] > 0)
1651 block = xfs_btree_get_block(cur, level, &bp);
1654 error = xfs_btree_check_block(cur, block, level, bp);
1670 for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1694 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) {
1720 int level, /* level in the btree */
1730 (level == cur->bc_nlevels - 1)) {
1736 * If the old buffer at this level for the disk address we are
1741 bp = cur->bc_bufs[level];
1762 /* Did we get the level we were looking for? */
1763 if (be16_to_cpu((*blkp)->bb_level) != level)
1767 if (level != 0 && be16_to_cpu((*blkp)->bb_numrecs) == 0)
1770 xfs_btree_setbuf(cur, level, bp);
1781 * Get current search key. For level 0 we don't actually have a key
1788 int level,
1793 if (level == 0) {
1816 int level; /* level in the btree */
1822 /* No such thing as a zero-level tree. */
1834 * Iterate over each level in the btree, starting at the root.
1835 * For each level above the leaves, find the key we need, based
1837 * pointer down to the next level.
1839 for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {
1841 error = xfs_btree_lookup_get_block(cur, level, pp, &block);
1847 * If we already had a key match at a higher level, we
1862 if (level != 0 || cur->bc_nlevels != 1) {
1886 kp = xfs_lookup_get_search_key(cur, level,
1906 * If there are more levels, set up for the next level
1909 if (level > 0) {
1918 error = xfs_btree_debug_check_ptr(cur, pp, 0, level);
1922 cur->bc_ptrs[level] = keyno;
2068 * Update the low and high parent keys of the given level, progressing
2070 * level do not need updating.
2075 int level,
2080 union xfs_btree_key key; /* keys from current level */
2081 union xfs_btree_key *lkey; /* keys from the next level up */
2083 union xfs_btree_key *nlkey; /* keys from the next level up */
2091 if (level + 1 >= cur->bc_nlevels)
2094 trace_xfs_btree_updkeys(cur, level, bp0);
2099 for (level++; level < cur->bc_nlevels; level++) {
2103 block = xfs_btree_get_block(cur, level, &bp);
2104 trace_xfs_btree_updkeys(cur, level, bp);
2106 error = xfs_btree_check_block(cur, block, level, bp);
2110 ptr = cur->bc_ptrs[level];
2119 if (level + 1 >= cur->bc_nlevels)
2127 /* Update all the keys from some level in cursor back to the root. */
2131 int level)
2136 block = xfs_btree_get_block(cur, level, &bp);
2137 return __xfs_btree_updkeys(cur, level, block, bp, true);
2141 * Update the parent keys of the given level, progressing towards the root.
2146 int level)
2154 ASSERT(level >= 0);
2156 block = xfs_btree_get_block(cur, level, &bp);
2158 return __xfs_btree_updkeys(cur, level, block, bp, false);
2161 * Go up the tree from this level toward the root.
2162 * At each level, update the key value to the value input.
2163 * Stop when we reach a level where the cursor isn't pointing
2167 for (level++, ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) {
2171 block = xfs_btree_get_block(cur, level, &bp);
2173 error = xfs_btree_check_block(cur, block, level, bp);
2177 ptr = cur->bc_ptrs[level];
2241 * Move 1 record left from cur/level if possible.
2247 int level,
2265 level == cur->bc_nlevels - 1)
2269 right = xfs_btree_get_block(cur, level, &rbp);
2272 error = xfs_btree_check_block(cur, right, level, rbp);
2286 if (cur->bc_ptrs[level] <= 1)
2296 if (lrecs == cur->bc_ops->get_maxrecs(cur, level))
2316 if (level > 0) {
2327 error = xfs_btree_debug_check_ptr(cur, rpp, 0, level);
2363 if (level > 0) {
2366 error = xfs_btree_debug_check_ptr(cur, rpp, i + 1, level);
2396 i = xfs_btree_firstrec(tcur, level);
2402 error = xfs_btree_decrement(tcur, level, &i);
2407 error = xfs_btree_update_keys(tcur, level);
2415 error = xfs_btree_update_keys(cur, level);
2420 cur->bc_ptrs[level]--;
2438 * Move 1 record right from cur/level if possible.
2444 int level,
2460 (level == cur->bc_nlevels - 1))
2464 left = xfs_btree_get_block(cur, level, &lbp);
2467 error = xfs_btree_check_block(cur, left, level, lbp);
2482 if (cur->bc_ptrs[level] >= lrecs)
2492 if (rrecs == cur->bc_ops->get_maxrecs(cur, level))
2502 if (level > 0) {
2514 error = xfs_btree_debug_check_ptr(cur, rpp, i, level);
2522 error = xfs_btree_debug_check_ptr(cur, lpp, 0, level);
2566 i = xfs_btree_lastrec(tcur, level);
2572 error = xfs_btree_increment(tcur, level, &i);
2578 error = xfs_btree_update_keys(cur, level);
2584 error = xfs_btree_update_keys(tcur, level);
2606 * Split cur/level block in half.
2613 int level,
2637 left = xfs_btree_get_block(cur, level, &lbp);
2640 error = xfs_btree_check_block(cur, left, level, lbp);
2670 if ((lrecs & 1) && cur->bc_ptrs[level] <= rrecs + 1)
2686 if (level > 0) {
2699 error = xfs_btree_debug_check_ptr(cur, lpp, i, level);
2756 error = xfs_btree_update_keys(cur, level);
2766 if (cur->bc_ptrs[level] > lrecs + 1) {
2767 xfs_btree_setbuf(cur, level, rbp);
2768 cur->bc_ptrs[level] -= lrecs;
2774 if (level + 1 < cur->bc_nlevels) {
2778 (*curp)->bc_ptrs[level + 1]++;
2793 int level;
2828 args->result = __xfs_btree_split(args->cur, args->level, args->ptrp,
2850 int level,
2860 return __xfs_btree_split(cur, level, ptrp, key, curp, stat);
2863 args.level = level;
2896 int level; /* btree level */
2904 level = cur->bc_nlevels - 1;
2938 cur->bc_ptrs[level + 1] = 1;
2946 error = xfs_btree_debug_check_ptr(cur, pp, i, level);
2953 error = xfs_btree_debug_check_ptr(cur, &nptr, 0, level);
2963 xfs_btree_setbuf(cur, level, cbp);
2967 * the root is at the right level.
3020 /* Set the root in the holding structure increasing the level by 1. */
3024 * At the previous root level there are now two blocks: the old root,
3113 int level, /* btree level */
3125 level == cur->bc_nlevels - 1) {
3128 if (numrecs < cur->bc_ops->get_dmaxrecs(cur, level)) {
3147 error = xfs_btree_rshift(cur, level, stat);
3152 error = xfs_btree_lshift(cur, level, stat);
3157 *oindex = *index = cur->bc_ptrs[level];
3167 error = xfs_btree_split(cur, level, nptr, key, ncur, stat);
3172 *index = cur->bc_ptrs[level];
3177 * Insert one record/level. Return information to the caller
3178 * allowing the next level up to proceed if necessary.
3183 int level, /* level to insert record at */
3208 * root level, allocate a new root block and we're done.
3211 (level >= cur->bc_nlevels)) {
3219 ptr = cur->bc_ptrs[level];
3230 block = xfs_btree_get_block(cur, level, &bp);
3235 error = xfs_btree_check_block(cur, block, level, bp);
3241 if (level == 0) {
3256 if (numrecs == cur->bc_ops->get_maxrecs(cur, level)) {
3257 error = xfs_btree_make_block_unfull(cur, level, numrecs,
3267 block = xfs_btree_get_block(cur, level, &bp);
3271 error = xfs_btree_check_block(cur, block, level, bp);
3282 if (level > 0) {
3291 error = xfs_btree_debug_check_ptr(cur, pp, i, level);
3299 error = xfs_btree_debug_check_ptr(cur, ptrp, 0, level);
3350 error = xfs_btree_update_keys(cur, level);
3359 if (xfs_btree_is_lastrec(cur, block, level)) {
3386 * A multi-level split of the tree on insert will invalidate the original
3397 int level; /* current level number in btree */
3400 struct xfs_btree_cur *pcur; /* previous level's cursor */
3405 level = 0;
3417 * Loop going up the tree, starting at the leaf level.
3419 * the insert is finished with this level.
3423 * Insert nrec/nptr into this level of the tree.
3426 error = xfs_btree_insrec(pcur, level, &nptr, &rec, key,
3438 level++;
3488 int level;
3504 level = cur->bc_nlevels - 1;
3505 if (level == 1)
3515 cblock = xfs_btree_get_block(cur, level - 1, &cbp);
3519 * Only do this if the next level will fit.
3521 * instead of freeing the root you free the next level.
3523 if (numrecs > cur->bc_ops->get_dmaxrecs(cur, level))
3535 index = numrecs - cur->bc_ops->get_maxrecs(cur, level);
3553 error = xfs_btree_debug_check_ptr(cur, cpp, i, level - 1);
3564 cur->bc_bufs[level - 1] = NULL;
3580 int level,
3588 * Update the root pointer, decreasing the level by 1 and then
3597 cur->bc_bufs[level] = NULL;
3598 cur->bc_ra[level] = 0;
3607 int level,
3613 if (level > 0) {
3614 error = xfs_btree_decrement(cur, level, &i);
3624 * Single level of the btree record deletion routine.
3625 * Delete record pointed to by cur/level.
3627 * Return 0 for error, 1 for done, 2 to go on to the next level.
3632 int level, /* level removing record from */
3657 ptr = cur->bc_ptrs[level];
3664 block = xfs_btree_get_block(cur, level, &bp);
3668 error = xfs_btree_check_block(cur, block, level, bp);
3683 if (level > 0) {
3692 error = xfs_btree_debug_check_ptr(cur, lpp, i, level);
3723 if (xfs_btree_is_lastrec(cur, block, level)) {
3729 * We're at the root level. First, shrink the root block in-memory.
3730 * Try to get rid of the next level down. If we can't then there's
3733 if (level == cur->bc_nlevels - 1) {
3742 error = xfs_btree_dec_cursor(cur, level, stat);
3750 * If this is the root level, and there's only one entry left,
3751 * and it's NOT the leaf level, then we can get rid of this
3752 * level.
3754 if (numrecs == 1 && level > 0) {
3761 error = xfs_btree_kill_root(cur, bp, level, pp);
3764 } else if (level > 0) {
3765 error = xfs_btree_dec_cursor(cur, level, stat);
3778 error = xfs_btree_update_keys(cur, level);
3787 if (numrecs >= cur->bc_ops->get_minrecs(cur, level)) {
3788 error = xfs_btree_dec_cursor(cur, level, stat);
3805 * into the root and delete it. Can't go up to next level,
3810 level == cur->bc_nlevels - 2) {
3813 error = xfs_btree_dec_cursor(cur, level, stat);
3825 * disrupt the next level up.
3840 i = xfs_btree_lastrec(tcur, level);
3846 error = xfs_btree_increment(tcur, level, &i);
3854 i = xfs_btree_lastrec(tcur, level);
3861 right = xfs_btree_get_block(tcur, level, &rbp);
3863 error = xfs_btree_check_block(tcur, right, level, rbp);
3876 cur->bc_ops->get_minrecs(tcur, level)) {
3877 error = xfs_btree_lshift(tcur, level, &i);
3882 cur->bc_ops->get_minrecs(tcur, level));
3887 error = xfs_btree_dec_cursor(cur, level, stat);
3901 i = xfs_btree_firstrec(tcur, level);
3907 error = xfs_btree_decrement(tcur, level, &i);
3926 i = xfs_btree_firstrec(tcur, level);
3932 error = xfs_btree_decrement(tcur, level, &i);
3935 i = xfs_btree_firstrec(tcur, level);
3942 left = xfs_btree_get_block(tcur, level, &lbp);
3944 error = xfs_btree_check_block(cur, left, level, lbp);
3957 cur->bc_ops->get_minrecs(tcur, level)) {
3958 error = xfs_btree_rshift(tcur, level, &i);
3963 cur->bc_ops->get_minrecs(tcur, level));
3966 if (level == 0)
3990 cur->bc_ops->get_maxrecs(cur, level)) {
4007 cur->bc_ops->get_maxrecs(cur, level)) {
4024 error = xfs_btree_dec_cursor(cur, level, stat);
4038 if (level > 0) {
4051 error = xfs_btree_debug_check_ptr(cur, rpp, i, level);
4104 cur->bc_bufs[level] = lbp;
4105 cur->bc_ptrs[level] += lrecs;
4106 cur->bc_ra[level] = 0;
4109 * If we joined with the right neighbor and there's a level above
4110 * us, increment the cursor at that level.
4113 (level + 1 < cur->bc_nlevels)) {
4114 error = xfs_btree_increment(cur, level + 1, &i);
4120 * Readjust the ptr at this level if it's not a leaf, since it's
4123 * We can't use decrement because it would change the next level up.
4125 if (level > 0)
4126 cur->bc_ptrs[level]--;
4130 * btree supports overlapped intervals. However, bc_ptrs[level + 1]
4138 /* Return value means the next level up has something to do. */
4159 int level;
4164 * Go up the tree, starting at leaf level.
4166 * If 2 is returned then a join was done; go to the next level.
4169 for (level = 0, i = 2; i == 2; level++) {
4170 error = xfs_btree_delrec(cur, level, &i);
4188 for (level = 1; level < cur->bc_nlevels; level++) {
4189 if (cur->bc_ptrs[level] == 0) {
4190 error = xfs_btree_decrement(cur, level, &i);
4249 int level,
4259 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
4260 block = xfs_btree_get_block(cur, level, &bp);
4263 error = fn(cur, level, data);
4272 return xfs_btree_lookup_get_block(cur, level, &rptr, &block);
4285 int level;
4291 /* for each level */
4292 for (level = cur->bc_nlevels - 1; level >= 0; level--) {
4294 error = xfs_btree_lookup_get_block(cur, level, &lptr, &block);
4298 /* readahead the left most block for the next level down */
4299 if (level > 0) {
4314 /* for each buffer in the level */
4316 error = xfs_btree_visit_block(cur, level, fn, data);
4335 * pointers so we can just walk all the blocks on each level from left to right
4336 * in a single pass, and then move to the next level and do the same. We can
4358 int level,
4366 block = xfs_btree_get_block(cur, level, &bp);
4386 ASSERT(level == cur->bc_nlevels - 1);
4527 uint level;
4531 for (level = 1; maxblocks > 1; level++)
4533 return level;
4650 int level;
4656 level = cur->bc_nlevels - 1;
4658 error = xfs_btree_lookup_get_block(cur, level, &ptr, &block);
4661 xfs_btree_get_block(cur, level, &bp);
4662 trace_xfs_btree_overlapped_query_range(cur, level, bp);
4664 error = xfs_btree_check_block(cur, block, level, bp);
4668 cur->bc_ptrs[level] = 1;
4670 while (level < cur->bc_nlevels) {
4671 block = xfs_btree_get_block(cur, level, &bp);
4674 if (cur->bc_ptrs[level] > be16_to_cpu(block->bb_numrecs)) {
4676 if (level < cur->bc_nlevels - 1)
4677 cur->bc_ptrs[level + 1]++;
4678 level++;
4682 if (level == 0) {
4707 cur->bc_ptrs[level]++;
4712 lkp = xfs_btree_key_addr(cur, cur->bc_ptrs[level], block);
4713 hkp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level], block);
4714 pp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[level], block);
4725 level--;
4726 error = xfs_btree_lookup_get_block(cur, level, pp,
4730 xfs_btree_get_block(cur, level, &bp);
4731 trace_xfs_btree_overlapped_query_range(cur, level, bp);
4733 error = xfs_btree_check_block(cur, block, level, bp);
4737 cur->bc_ptrs[level] = 1;
4743 cur->bc_ptrs[level]++;
4750 * node-level buffers, causing a buffer leak. This is quite possible
4832 int level;
4837 for (level = 0, rval = 0; len > 1; level++) {
4849 int level,