1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
6 #include "libxfs_priv.h"
8 #include "xfs_shared.h"
9 #include "xfs_format.h"
10 #include "xfs_log_format.h"
11 #include "xfs_trans_resv.h"
13 #include "xfs_mount.h"
14 #include "xfs_inode.h"
15 #include "xfs_trans.h"
16 #include "xfs_btree.h"
17 #include "xfs_errortag.h"
18 #include "xfs_trace.h"
19 #include "xfs_alloc.h"
20 #include "xfs_btree_staging.h"
24 * Cursor allocation zone.
26 kmem_zone_t
*xfs_btree_cur_zone
;
29 * Btree magic numbers.
31 static const uint32_t xfs_magics
[2][XFS_BTNUM_MAX
] = {
32 { XFS_ABTB_MAGIC
, XFS_ABTC_MAGIC
, 0, XFS_BMAP_MAGIC
, XFS_IBT_MAGIC
,
34 { XFS_ABTB_CRC_MAGIC
, XFS_ABTC_CRC_MAGIC
, XFS_RMAP_CRC_MAGIC
,
35 XFS_BMAP_CRC_MAGIC
, XFS_IBT_CRC_MAGIC
, XFS_FIBT_CRC_MAGIC
,
44 uint32_t magic
= xfs_magics
[crc
][btnum
];
46 /* Ensure we asked for crc for crc-only magics. */
52 * Check a long btree block header. Return the address of the failing check,
53 * or NULL if everything is ok.
56 __xfs_btree_check_lblock(
57 struct xfs_btree_cur
*cur
,
58 struct xfs_btree_block
*block
,
62 struct xfs_mount
*mp
= cur
->bc_mp
;
63 xfs_btnum_t btnum
= cur
->bc_btnum
;
64 int crc
= xfs_sb_version_hascrc(&mp
->m_sb
);
67 if (!uuid_equal(&block
->bb_u
.l
.bb_uuid
, &mp
->m_sb
.sb_meta_uuid
))
68 return __this_address
;
69 if (block
->bb_u
.l
.bb_blkno
!=
70 cpu_to_be64(bp
? bp
->b_bn
: XFS_BUF_DADDR_NULL
))
71 return __this_address
;
72 if (block
->bb_u
.l
.bb_pad
!= cpu_to_be32(0))
73 return __this_address
;
76 if (be32_to_cpu(block
->bb_magic
) != xfs_btree_magic(crc
, btnum
))
77 return __this_address
;
78 if (be16_to_cpu(block
->bb_level
) != level
)
79 return __this_address
;
80 if (be16_to_cpu(block
->bb_numrecs
) >
81 cur
->bc_ops
->get_maxrecs(cur
, level
))
82 return __this_address
;
83 if (block
->bb_u
.l
.bb_leftsib
!= cpu_to_be64(NULLFSBLOCK
) &&
84 !xfs_btree_check_lptr(cur
, be64_to_cpu(block
->bb_u
.l
.bb_leftsib
),
86 return __this_address
;
87 if (block
->bb_u
.l
.bb_rightsib
!= cpu_to_be64(NULLFSBLOCK
) &&
88 !xfs_btree_check_lptr(cur
, be64_to_cpu(block
->bb_u
.l
.bb_rightsib
),
90 return __this_address
;
95 /* Check a long btree block header. */
97 xfs_btree_check_lblock(
98 struct xfs_btree_cur
*cur
,
99 struct xfs_btree_block
*block
,
103 struct xfs_mount
*mp
= cur
->bc_mp
;
106 fa
= __xfs_btree_check_lblock(cur
, block
, level
, bp
);
107 if (XFS_IS_CORRUPT(mp
, fa
!= NULL
) ||
108 XFS_TEST_ERROR(false, mp
, XFS_ERRTAG_BTREE_CHECK_LBLOCK
)) {
110 trace_xfs_btree_corrupt(bp
, _RET_IP_
);
111 return -EFSCORRUPTED
;
117 * Check a short btree block header. Return the address of the failing check,
118 * or NULL if everything is ok.
121 __xfs_btree_check_sblock(
122 struct xfs_btree_cur
*cur
,
123 struct xfs_btree_block
*block
,
127 struct xfs_mount
*mp
= cur
->bc_mp
;
128 xfs_btnum_t btnum
= cur
->bc_btnum
;
129 int crc
= xfs_sb_version_hascrc(&mp
->m_sb
);
132 if (!uuid_equal(&block
->bb_u
.s
.bb_uuid
, &mp
->m_sb
.sb_meta_uuid
))
133 return __this_address
;
134 if (block
->bb_u
.s
.bb_blkno
!=
135 cpu_to_be64(bp
? bp
->b_bn
: XFS_BUF_DADDR_NULL
))
136 return __this_address
;
139 if (be32_to_cpu(block
->bb_magic
) != xfs_btree_magic(crc
, btnum
))
140 return __this_address
;
141 if (be16_to_cpu(block
->bb_level
) != level
)
142 return __this_address
;
143 if (be16_to_cpu(block
->bb_numrecs
) >
144 cur
->bc_ops
->get_maxrecs(cur
, level
))
145 return __this_address
;
146 if (block
->bb_u
.s
.bb_leftsib
!= cpu_to_be32(NULLAGBLOCK
) &&
147 !xfs_btree_check_sptr(cur
, be32_to_cpu(block
->bb_u
.s
.bb_leftsib
),
149 return __this_address
;
150 if (block
->bb_u
.s
.bb_rightsib
!= cpu_to_be32(NULLAGBLOCK
) &&
151 !xfs_btree_check_sptr(cur
, be32_to_cpu(block
->bb_u
.s
.bb_rightsib
),
153 return __this_address
;
158 /* Check a short btree block header. */
160 xfs_btree_check_sblock(
161 struct xfs_btree_cur
*cur
,
162 struct xfs_btree_block
*block
,
166 struct xfs_mount
*mp
= cur
->bc_mp
;
169 fa
= __xfs_btree_check_sblock(cur
, block
, level
, bp
);
170 if (XFS_IS_CORRUPT(mp
, fa
!= NULL
) ||
171 XFS_TEST_ERROR(false, mp
, XFS_ERRTAG_BTREE_CHECK_SBLOCK
)) {
173 trace_xfs_btree_corrupt(bp
, _RET_IP_
);
174 return -EFSCORRUPTED
;
180 * Debug routine: check that block header is ok.
183 xfs_btree_check_block(
184 struct xfs_btree_cur
*cur
, /* btree cursor */
185 struct xfs_btree_block
*block
, /* generic btree block pointer */
186 int level
, /* level of the btree block */
187 struct xfs_buf
*bp
) /* buffer containing block, if any */
189 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
)
190 return xfs_btree_check_lblock(cur
, block
, level
, bp
);
192 return xfs_btree_check_sblock(cur
, block
, level
, bp
);
195 /* Check that this long pointer is valid and points within the fs. */
197 xfs_btree_check_lptr(
198 struct xfs_btree_cur
*cur
,
204 return xfs_verify_fsbno(cur
->bc_mp
, fsbno
);
207 /* Check that this short pointer is valid and points within the AG. */
209 xfs_btree_check_sptr(
210 struct xfs_btree_cur
*cur
,
216 return xfs_verify_agbno(cur
->bc_mp
, cur
->bc_ag
.agno
, agbno
);
220 * Check that a given (indexed) btree pointer at a certain level of a
221 * btree is valid and doesn't point past where it should.
225 struct xfs_btree_cur
*cur
,
226 union xfs_btree_ptr
*ptr
,
230 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
) {
231 if (xfs_btree_check_lptr(cur
, be64_to_cpu((&ptr
->l
)[index
]),
235 "Inode %llu fork %d: Corrupt btree %d pointer at level %d index %d.",
236 cur
->bc_ino
.ip
->i_ino
,
237 cur
->bc_ino
.whichfork
, cur
->bc_btnum
,
240 if (xfs_btree_check_sptr(cur
, be32_to_cpu((&ptr
->s
)[index
]),
244 "AG %u: Corrupt btree %d pointer at level %d index %d.",
245 cur
->bc_ag
.agno
, cur
->bc_btnum
,
249 return -EFSCORRUPTED
;
253 # define xfs_btree_debug_check_ptr xfs_btree_check_ptr
255 # define xfs_btree_debug_check_ptr(...) (0)
259 * Calculate CRC on the whole btree block and stuff it into the
260 * long-form btree header.
262 * Prior to calculting the CRC, pull the LSN out of the buffer log item and put
263 * it into the buffer so recovery knows what the last modification was that made
267 xfs_btree_lblock_calc_crc(
270 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
271 struct xfs_buf_log_item
*bip
= bp
->b_log_item
;
273 if (!xfs_sb_version_hascrc(&bp
->b_mount
->m_sb
))
276 block
->bb_u
.l
.bb_lsn
= cpu_to_be64(bip
->bli_item
.li_lsn
);
277 xfs_buf_update_cksum(bp
, XFS_BTREE_LBLOCK_CRC_OFF
);
281 xfs_btree_lblock_verify_crc(
284 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
285 struct xfs_mount
*mp
= bp
->b_mount
;
287 if (xfs_sb_version_hascrc(&mp
->m_sb
)) {
288 if (!xfs_log_check_lsn(mp
, be64_to_cpu(block
->bb_u
.l
.bb_lsn
)))
290 return xfs_buf_verify_cksum(bp
, XFS_BTREE_LBLOCK_CRC_OFF
);
297 * Calculate CRC on the whole btree block and stuff it into the
298 * short-form btree header.
300 * Prior to calculting the CRC, pull the LSN out of the buffer log item and put
301 * it into the buffer so recovery knows what the last modification was that made
305 xfs_btree_sblock_calc_crc(
308 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
309 struct xfs_buf_log_item
*bip
= bp
->b_log_item
;
311 if (!xfs_sb_version_hascrc(&bp
->b_mount
->m_sb
))
314 block
->bb_u
.s
.bb_lsn
= cpu_to_be64(bip
->bli_item
.li_lsn
);
315 xfs_buf_update_cksum(bp
, XFS_BTREE_SBLOCK_CRC_OFF
);
319 xfs_btree_sblock_verify_crc(
322 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
323 struct xfs_mount
*mp
= bp
->b_mount
;
325 if (xfs_sb_version_hascrc(&mp
->m_sb
)) {
326 if (!xfs_log_check_lsn(mp
, be64_to_cpu(block
->bb_u
.s
.bb_lsn
)))
328 return xfs_buf_verify_cksum(bp
, XFS_BTREE_SBLOCK_CRC_OFF
);
335 xfs_btree_free_block(
336 struct xfs_btree_cur
*cur
,
341 error
= cur
->bc_ops
->free_block(cur
, bp
);
343 xfs_trans_binval(cur
->bc_tp
, bp
);
344 XFS_BTREE_STATS_INC(cur
, free
);
350 * Delete the btree cursor.
353 xfs_btree_del_cursor(
354 struct xfs_btree_cur
*cur
, /* btree cursor */
355 int error
) /* del because of error */
357 int i
; /* btree level */
360 * Clear the buffer pointers and release the buffers. If we're doing
361 * this because of an error, inspect all of the entries in the bc_bufs
362 * array for buffers to be unlocked. This is because some of the btree
363 * code works from level n down to 0, and if we get an error along the
364 * way we won't have initialized all the entries down to 0.
366 for (i
= 0; i
< cur
->bc_nlevels
; i
++) {
368 xfs_trans_brelse(cur
->bc_tp
, cur
->bc_bufs
[i
]);
373 ASSERT(cur
->bc_btnum
!= XFS_BTNUM_BMAP
|| cur
->bc_ino
.allocated
== 0 ||
374 XFS_FORCED_SHUTDOWN(cur
->bc_mp
));
375 if (unlikely(cur
->bc_flags
& XFS_BTREE_STAGING
))
376 kmem_free(cur
->bc_ops
);
377 kmem_cache_free(xfs_btree_cur_zone
, cur
);
381 * Duplicate the btree cursor.
382 * Allocate a new one, copy the record, re-get the buffers.
385 xfs_btree_dup_cursor(
386 xfs_btree_cur_t
*cur
, /* input cursor */
387 xfs_btree_cur_t
**ncur
) /* output cursor */
389 struct xfs_buf
*bp
; /* btree block's buffer pointer */
390 int error
; /* error return value */
391 int i
; /* level number of btree block */
392 xfs_mount_t
*mp
; /* mount structure for filesystem */
393 xfs_btree_cur_t
*new; /* new cursor value */
394 xfs_trans_t
*tp
; /* transaction pointer, can be NULL */
400 * Allocate a new cursor like the old one.
402 new = cur
->bc_ops
->dup_cursor(cur
);
405 * Copy the record currently in the cursor.
407 new->bc_rec
= cur
->bc_rec
;
410 * For each level current, re-get the buffer and copy the ptr value.
412 for (i
= 0; i
< new->bc_nlevels
; i
++) {
413 new->bc_ptrs
[i
] = cur
->bc_ptrs
[i
];
414 new->bc_ra
[i
] = cur
->bc_ra
[i
];
415 bp
= cur
->bc_bufs
[i
];
417 error
= xfs_trans_read_buf(mp
, tp
, mp
->m_ddev_targp
,
418 XFS_BUF_ADDR(bp
), mp
->m_bsize
,
420 cur
->bc_ops
->buf_ops
);
422 xfs_btree_del_cursor(new, error
);
427 new->bc_bufs
[i
] = bp
;
434 * XFS btree block layout and addressing:
436 * There are two types of blocks in the btree: leaf and non-leaf blocks.
438 * The leaf record start with a header then followed by records containing
439 * the values. A non-leaf block also starts with the same header, and
440 * then first contains lookup keys followed by an equal number of pointers
441 * to the btree blocks at the previous level.
443 * +--------+-------+-------+-------+-------+-------+-------+
444 * Leaf: | header | rec 1 | rec 2 | rec 3 | rec 4 | rec 5 | rec N |
445 * +--------+-------+-------+-------+-------+-------+-------+
447 * +--------+-------+-------+-------+-------+-------+-------+
448 * Non-Leaf: | header | key 1 | key 2 | key N | ptr 1 | ptr 2 | ptr N |
449 * +--------+-------+-------+-------+-------+-------+-------+
451 * The header is called struct xfs_btree_block for reasons better left unknown
452 * and comes in different versions for short (32bit) and long (64bit) block
453 * pointers. The record and key structures are defined by the btree instances
454 * and opaque to the btree core. The block pointers are simple disk endian
455 * integers, available in a short (32bit) and long (64bit) variant.
457 * The helpers below calculate the offset of a given record, key or pointer
458 * into a btree block (xfs_btree_*_offset) or return a pointer to the given
459 * record, key or pointer (xfs_btree_*_addr). Note that all addressing
460 * inside the btree block is done using indices starting at one, not zero!
462 * If XFS_BTREE_OVERLAPPING is set, then this btree supports keys containing
463 * overlapping intervals. In such a tree, records are still sorted lowest to
464 * highest and indexed by the smallest key value that refers to the record.
465 * However, nodes are different: each pointer has two associated keys -- one
466 * indexing the lowest key available in the block(s) below (the same behavior
467 * as the key in a regular btree) and another indexing the highest key
468 * available in the block(s) below. Because records are /not/ sorted by the
469 * highest key, all leaf block updates require us to compute the highest key
470 * that matches any record in the leaf and to recursively update the high keys
471 * in the nodes going further up in the tree, if necessary. Nodes look like
474 * +--------+-----+-----+-----+-----+-----+-------+-------+-----+
475 * Non-Leaf: | header | lo1 | hi1 | lo2 | hi2 | ... | ptr 1 | ptr 2 | ... |
476 * +--------+-----+-----+-----+-----+-----+-------+-------+-----+
478 * To perform an interval query on an overlapped tree, perform the usual
479 * depth-first search and use the low and high keys to decide if we can skip
480 * that particular node. If a leaf node is reached, return the records that
481 * intersect the interval. Note that an interval query may return numerous
482 * entries. For a non-overlapped tree, simply search for the record associated
483 * with the lowest key and iterate forward until a non-matching record is
484 * found. Section 14.3 ("Interval Trees") of _Introduction to Algorithms_ by
485 * Cormen, Leiserson, Rivest, and Stein (2nd or 3rd ed. only) discuss this in
488 * Why do we care about overlapping intervals? Let's say you have a bunch of
489 * reverse mapping records on a reflink filesystem:
491 * 1: +- file A startblock B offset C length D -----------+
492 * 2: +- file E startblock F offset G length H --------------+
493 * 3: +- file I startblock F offset J length K --+
494 * 4: +- file L... --+
496 * Now say we want to map block (B+D) into file A at offset (C+D). Ideally,
497 * we'd simply increment the length of record 1. But how do we find the record
498 * that ends at (B+D-1) (i.e. record 1)? A LE lookup of (B+D-1) would return
499 * record 3 because the keys are ordered first by startblock. An interval
500 * query would return records 1 and 2 because they both overlap (B+D-1), and
501 * from that we can pick out record 1 as the appropriate left neighbor.
503 * In the non-overlapped case you can do a LE lookup and decrement the cursor
504 * because a record's interval must end before the next record.
508 * Return size of the btree block header for this btree instance.
510 static inline size_t xfs_btree_block_len(struct xfs_btree_cur
*cur
)
512 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
) {
513 if (cur
->bc_flags
& XFS_BTREE_CRC_BLOCKS
)
514 return XFS_BTREE_LBLOCK_CRC_LEN
;
515 return XFS_BTREE_LBLOCK_LEN
;
517 if (cur
->bc_flags
& XFS_BTREE_CRC_BLOCKS
)
518 return XFS_BTREE_SBLOCK_CRC_LEN
;
519 return XFS_BTREE_SBLOCK_LEN
;
523 * Return size of btree block pointers for this btree instance.
525 static inline size_t xfs_btree_ptr_len(struct xfs_btree_cur
*cur
)
527 return (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
) ?
528 sizeof(__be64
) : sizeof(__be32
);
532 * Calculate offset of the n-th record in a btree block.
535 xfs_btree_rec_offset(
536 struct xfs_btree_cur
*cur
,
539 return xfs_btree_block_len(cur
) +
540 (n
- 1) * cur
->bc_ops
->rec_len
;
544 * Calculate offset of the n-th key in a btree block.
547 xfs_btree_key_offset(
548 struct xfs_btree_cur
*cur
,
551 return xfs_btree_block_len(cur
) +
552 (n
- 1) * cur
->bc_ops
->key_len
;
556 * Calculate offset of the n-th high key in a btree block.
559 xfs_btree_high_key_offset(
560 struct xfs_btree_cur
*cur
,
563 return xfs_btree_block_len(cur
) +
564 (n
- 1) * cur
->bc_ops
->key_len
+ (cur
->bc_ops
->key_len
/ 2);
568 * Calculate offset of the n-th block pointer in a btree block.
571 xfs_btree_ptr_offset(
572 struct xfs_btree_cur
*cur
,
576 return xfs_btree_block_len(cur
) +
577 cur
->bc_ops
->get_maxrecs(cur
, level
) * cur
->bc_ops
->key_len
+
578 (n
- 1) * xfs_btree_ptr_len(cur
);
582 * Return a pointer to the n-th record in the btree block.
584 union xfs_btree_rec
*
586 struct xfs_btree_cur
*cur
,
588 struct xfs_btree_block
*block
)
590 return (union xfs_btree_rec
*)
591 ((char *)block
+ xfs_btree_rec_offset(cur
, n
));
595 * Return a pointer to the n-th key in the btree block.
597 union xfs_btree_key
*
599 struct xfs_btree_cur
*cur
,
601 struct xfs_btree_block
*block
)
603 return (union xfs_btree_key
*)
604 ((char *)block
+ xfs_btree_key_offset(cur
, n
));
608 * Return a pointer to the n-th high key in the btree block.
610 union xfs_btree_key
*
611 xfs_btree_high_key_addr(
612 struct xfs_btree_cur
*cur
,
614 struct xfs_btree_block
*block
)
616 return (union xfs_btree_key
*)
617 ((char *)block
+ xfs_btree_high_key_offset(cur
, n
));
621 * Return a pointer to the n-th block pointer in the btree block.
623 union xfs_btree_ptr
*
625 struct xfs_btree_cur
*cur
,
627 struct xfs_btree_block
*block
)
629 int level
= xfs_btree_get_level(block
);
631 ASSERT(block
->bb_level
!= 0);
633 return (union xfs_btree_ptr
*)
634 ((char *)block
+ xfs_btree_ptr_offset(cur
, n
, level
));
639 struct xfs_btree_cur
*cur
)
641 ASSERT(cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
);
643 if (cur
->bc_flags
& XFS_BTREE_STAGING
)
644 return cur
->bc_ino
.ifake
->if_fork
;
645 return XFS_IFORK_PTR(cur
->bc_ino
.ip
, cur
->bc_ino
.whichfork
);
649 * Get the root block which is stored in the inode.
651 * For now this btree implementation assumes the btree root is always
652 * stored in the if_broot field of an inode fork.
654 STATIC
struct xfs_btree_block
*
656 struct xfs_btree_cur
*cur
)
658 struct xfs_ifork
*ifp
= xfs_btree_ifork_ptr(cur
);
660 return (struct xfs_btree_block
*)ifp
->if_broot
;
664 * Retrieve the block pointer from the cursor at the given level.
665 * This may be an inode btree root or from a buffer.
667 struct xfs_btree_block
* /* generic btree block pointer */
669 struct xfs_btree_cur
*cur
, /* btree cursor */
670 int level
, /* level in btree */
671 struct xfs_buf
**bpp
) /* buffer containing the block */
673 if ((cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
) &&
674 (level
== cur
->bc_nlevels
- 1)) {
676 return xfs_btree_get_iroot(cur
);
679 *bpp
= cur
->bc_bufs
[level
];
680 return XFS_BUF_TO_BLOCK(*bpp
);
684 * Change the cursor to point to the first record at the given level.
685 * Other levels are unaffected.
687 STATIC
int /* success=1, failure=0 */
689 xfs_btree_cur_t
*cur
, /* btree cursor */
690 int level
) /* level to change */
692 struct xfs_btree_block
*block
; /* generic btree block pointer */
693 struct xfs_buf
*bp
; /* buffer containing block */
696 * Get the block pointer for this level.
698 block
= xfs_btree_get_block(cur
, level
, &bp
);
699 if (xfs_btree_check_block(cur
, block
, level
, bp
))
702 * It's empty, there is no such record.
704 if (!block
->bb_numrecs
)
707 * Set the ptr value to 1, that's the first record/key.
709 cur
->bc_ptrs
[level
] = 1;
714 * Change the cursor to point to the last record in the current block
715 * at the given level. Other levels are unaffected.
717 STATIC
int /* success=1, failure=0 */
719 xfs_btree_cur_t
*cur
, /* btree cursor */
720 int level
) /* level to change */
722 struct xfs_btree_block
*block
; /* generic btree block pointer */
723 struct xfs_buf
*bp
; /* buffer containing block */
726 * Get the block pointer for this level.
728 block
= xfs_btree_get_block(cur
, level
, &bp
);
729 if (xfs_btree_check_block(cur
, block
, level
, bp
))
732 * It's empty, there is no such record.
734 if (!block
->bb_numrecs
)
737 * Set the ptr value to numrecs, that's the last record/key.
739 cur
->bc_ptrs
[level
] = be16_to_cpu(block
->bb_numrecs
);
744 * Compute first and last byte offsets for the fields given.
745 * Interprets the offsets table, which contains struct field offsets.
749 int64_t fields
, /* bitmask of fields */
750 const short *offsets
, /* table of field offsets */
751 int nbits
, /* number of bits to inspect */
752 int *first
, /* output: first byte offset */
753 int *last
) /* output: last byte offset */
755 int i
; /* current bit number */
756 int64_t imask
; /* mask for current bit number */
760 * Find the lowest bit, so the first byte offset.
762 for (i
= 0, imask
= 1LL; ; i
++, imask
<<= 1) {
763 if (imask
& fields
) {
769 * Find the highest bit, so the last byte offset.
771 for (i
= nbits
- 1, imask
= 1LL << i
; ; i
--, imask
>>= 1) {
772 if (imask
& fields
) {
773 *last
= offsets
[i
+ 1] - 1;
780 * Get a buffer for the block, return it read in.
781 * Long-form addressing.
785 struct xfs_mount
*mp
, /* file system mount point */
786 struct xfs_trans
*tp
, /* transaction pointer */
787 xfs_fsblock_t fsbno
, /* file system block number */
788 struct xfs_buf
**bpp
, /* buffer for fsbno */
789 int refval
, /* ref count value for buffer */
790 const struct xfs_buf_ops
*ops
)
792 struct xfs_buf
*bp
; /* return value */
793 xfs_daddr_t d
; /* real disk block address */
796 if (!xfs_verify_fsbno(mp
, fsbno
))
797 return -EFSCORRUPTED
;
798 d
= XFS_FSB_TO_DADDR(mp
, fsbno
);
799 error
= xfs_trans_read_buf(mp
, tp
, mp
->m_ddev_targp
, d
,
800 mp
->m_bsize
, 0, &bp
, ops
);
804 xfs_buf_set_ref(bp
, refval
);
810 * Read-ahead the block, don't wait for it, don't return a buffer.
811 * Long-form addressing.
815 xfs_btree_reada_bufl(
816 struct xfs_mount
*mp
, /* file system mount point */
817 xfs_fsblock_t fsbno
, /* file system block number */
818 xfs_extlen_t count
, /* count of filesystem blocks */
819 const struct xfs_buf_ops
*ops
)
823 ASSERT(fsbno
!= NULLFSBLOCK
);
824 d
= XFS_FSB_TO_DADDR(mp
, fsbno
);
825 xfs_buf_readahead(mp
->m_ddev_targp
, d
, mp
->m_bsize
* count
, ops
);
829 * Read-ahead the block, don't wait for it, don't return a buffer.
830 * Short-form addressing.
834 xfs_btree_reada_bufs(
835 struct xfs_mount
*mp
, /* file system mount point */
836 xfs_agnumber_t agno
, /* allocation group number */
837 xfs_agblock_t agbno
, /* allocation group block number */
838 xfs_extlen_t count
, /* count of filesystem blocks */
839 const struct xfs_buf_ops
*ops
)
843 ASSERT(agno
!= NULLAGNUMBER
);
844 ASSERT(agbno
!= NULLAGBLOCK
);
845 d
= XFS_AGB_TO_DADDR(mp
, agno
, agbno
);
846 xfs_buf_readahead(mp
->m_ddev_targp
, d
, mp
->m_bsize
* count
, ops
);
850 xfs_btree_readahead_lblock(
851 struct xfs_btree_cur
*cur
,
853 struct xfs_btree_block
*block
)
856 xfs_fsblock_t left
= be64_to_cpu(block
->bb_u
.l
.bb_leftsib
);
857 xfs_fsblock_t right
= be64_to_cpu(block
->bb_u
.l
.bb_rightsib
);
859 if ((lr
& XFS_BTCUR_LEFTRA
) && left
!= NULLFSBLOCK
) {
860 xfs_btree_reada_bufl(cur
->bc_mp
, left
, 1,
861 cur
->bc_ops
->buf_ops
);
865 if ((lr
& XFS_BTCUR_RIGHTRA
) && right
!= NULLFSBLOCK
) {
866 xfs_btree_reada_bufl(cur
->bc_mp
, right
, 1,
867 cur
->bc_ops
->buf_ops
);
875 xfs_btree_readahead_sblock(
876 struct xfs_btree_cur
*cur
,
878 struct xfs_btree_block
*block
)
881 xfs_agblock_t left
= be32_to_cpu(block
->bb_u
.s
.bb_leftsib
);
882 xfs_agblock_t right
= be32_to_cpu(block
->bb_u
.s
.bb_rightsib
);
885 if ((lr
& XFS_BTCUR_LEFTRA
) && left
!= NULLAGBLOCK
) {
886 xfs_btree_reada_bufs(cur
->bc_mp
, cur
->bc_ag
.agno
,
887 left
, 1, cur
->bc_ops
->buf_ops
);
891 if ((lr
& XFS_BTCUR_RIGHTRA
) && right
!= NULLAGBLOCK
) {
892 xfs_btree_reada_bufs(cur
->bc_mp
, cur
->bc_ag
.agno
,
893 right
, 1, cur
->bc_ops
->buf_ops
);
901 * Read-ahead btree blocks, at the given level.
902 * Bits in lr are set from XFS_BTCUR_{LEFT,RIGHT}RA.
906 struct xfs_btree_cur
*cur
, /* btree cursor */
907 int lev
, /* level in btree */
908 int lr
) /* left/right bits */
910 struct xfs_btree_block
*block
;
913 * No readahead needed if we are at the root level and the
914 * btree root is stored in the inode.
916 if ((cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
) &&
917 (lev
== cur
->bc_nlevels
- 1))
920 if ((cur
->bc_ra
[lev
] | lr
) == cur
->bc_ra
[lev
])
923 cur
->bc_ra
[lev
] |= lr
;
924 block
= XFS_BUF_TO_BLOCK(cur
->bc_bufs
[lev
]);
926 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
)
927 return xfs_btree_readahead_lblock(cur
, lr
, block
);
928 return xfs_btree_readahead_sblock(cur
, lr
, block
);
932 xfs_btree_ptr_to_daddr(
933 struct xfs_btree_cur
*cur
,
934 union xfs_btree_ptr
*ptr
,
941 error
= xfs_btree_check_ptr(cur
, ptr
, 0, 1);
945 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
) {
946 fsbno
= be64_to_cpu(ptr
->l
);
947 *daddr
= XFS_FSB_TO_DADDR(cur
->bc_mp
, fsbno
);
949 agbno
= be32_to_cpu(ptr
->s
);
950 *daddr
= XFS_AGB_TO_DADDR(cur
->bc_mp
, cur
->bc_ag
.agno
,
958 * Readahead @count btree blocks at the given @ptr location.
960 * We don't need to care about long or short form btrees here as we have a
961 * method of converting the ptr directly to a daddr available to us.
964 xfs_btree_readahead_ptr(
965 struct xfs_btree_cur
*cur
,
966 union xfs_btree_ptr
*ptr
,
971 if (xfs_btree_ptr_to_daddr(cur
, ptr
, &daddr
))
973 xfs_buf_readahead(cur
->bc_mp
->m_ddev_targp
, daddr
,
974 cur
->bc_mp
->m_bsize
* count
, cur
->bc_ops
->buf_ops
);
978 * Set the buffer for level "lev" in the cursor to bp, releasing
979 * any previous buffer.
983 xfs_btree_cur_t
*cur
, /* btree cursor */
984 int lev
, /* level in btree */
985 struct xfs_buf
*bp
) /* new buffer to set */
987 struct xfs_btree_block
*b
; /* btree block */
989 if (cur
->bc_bufs
[lev
])
990 xfs_trans_brelse(cur
->bc_tp
, cur
->bc_bufs
[lev
]);
991 cur
->bc_bufs
[lev
] = bp
;
994 b
= XFS_BUF_TO_BLOCK(bp
);
995 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
) {
996 if (b
->bb_u
.l
.bb_leftsib
== cpu_to_be64(NULLFSBLOCK
))
997 cur
->bc_ra
[lev
] |= XFS_BTCUR_LEFTRA
;
998 if (b
->bb_u
.l
.bb_rightsib
== cpu_to_be64(NULLFSBLOCK
))
999 cur
->bc_ra
[lev
] |= XFS_BTCUR_RIGHTRA
;
1001 if (b
->bb_u
.s
.bb_leftsib
== cpu_to_be32(NULLAGBLOCK
))
1002 cur
->bc_ra
[lev
] |= XFS_BTCUR_LEFTRA
;
1003 if (b
->bb_u
.s
.bb_rightsib
== cpu_to_be32(NULLAGBLOCK
))
1004 cur
->bc_ra
[lev
] |= XFS_BTCUR_RIGHTRA
;
1009 xfs_btree_ptr_is_null(
1010 struct xfs_btree_cur
*cur
,
1011 union xfs_btree_ptr
*ptr
)
1013 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
)
1014 return ptr
->l
== cpu_to_be64(NULLFSBLOCK
);
1016 return ptr
->s
== cpu_to_be32(NULLAGBLOCK
);
1020 xfs_btree_set_ptr_null(
1021 struct xfs_btree_cur
*cur
,
1022 union xfs_btree_ptr
*ptr
)
1024 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
)
1025 ptr
->l
= cpu_to_be64(NULLFSBLOCK
);
1027 ptr
->s
= cpu_to_be32(NULLAGBLOCK
);
1031 * Get/set/init sibling pointers
1034 xfs_btree_get_sibling(
1035 struct xfs_btree_cur
*cur
,
1036 struct xfs_btree_block
*block
,
1037 union xfs_btree_ptr
*ptr
,
1040 ASSERT(lr
== XFS_BB_LEFTSIB
|| lr
== XFS_BB_RIGHTSIB
);
1042 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
) {
1043 if (lr
== XFS_BB_RIGHTSIB
)
1044 ptr
->l
= block
->bb_u
.l
.bb_rightsib
;
1046 ptr
->l
= block
->bb_u
.l
.bb_leftsib
;
1048 if (lr
== XFS_BB_RIGHTSIB
)
1049 ptr
->s
= block
->bb_u
.s
.bb_rightsib
;
1051 ptr
->s
= block
->bb_u
.s
.bb_leftsib
;
1056 xfs_btree_set_sibling(
1057 struct xfs_btree_cur
*cur
,
1058 struct xfs_btree_block
*block
,
1059 union xfs_btree_ptr
*ptr
,
1062 ASSERT(lr
== XFS_BB_LEFTSIB
|| lr
== XFS_BB_RIGHTSIB
);
1064 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
) {
1065 if (lr
== XFS_BB_RIGHTSIB
)
1066 block
->bb_u
.l
.bb_rightsib
= ptr
->l
;
1068 block
->bb_u
.l
.bb_leftsib
= ptr
->l
;
1070 if (lr
== XFS_BB_RIGHTSIB
)
1071 block
->bb_u
.s
.bb_rightsib
= ptr
->s
;
1073 block
->bb_u
.s
.bb_leftsib
= ptr
->s
;
1078 xfs_btree_init_block_int(
1079 struct xfs_mount
*mp
,
1080 struct xfs_btree_block
*buf
,
1088 int crc
= xfs_sb_version_hascrc(&mp
->m_sb
);
1089 __u32 magic
= xfs_btree_magic(crc
, btnum
);
1091 buf
->bb_magic
= cpu_to_be32(magic
);
1092 buf
->bb_level
= cpu_to_be16(level
);
1093 buf
->bb_numrecs
= cpu_to_be16(numrecs
);
1095 if (flags
& XFS_BTREE_LONG_PTRS
) {
1096 buf
->bb_u
.l
.bb_leftsib
= cpu_to_be64(NULLFSBLOCK
);
1097 buf
->bb_u
.l
.bb_rightsib
= cpu_to_be64(NULLFSBLOCK
);
1099 buf
->bb_u
.l
.bb_blkno
= cpu_to_be64(blkno
);
1100 buf
->bb_u
.l
.bb_owner
= cpu_to_be64(owner
);
1101 uuid_copy(&buf
->bb_u
.l
.bb_uuid
, &mp
->m_sb
.sb_meta_uuid
);
1102 buf
->bb_u
.l
.bb_pad
= 0;
1103 buf
->bb_u
.l
.bb_lsn
= 0;
1106 /* owner is a 32 bit value on short blocks */
1107 __u32 __owner
= (__u32
)owner
;
1109 buf
->bb_u
.s
.bb_leftsib
= cpu_to_be32(NULLAGBLOCK
);
1110 buf
->bb_u
.s
.bb_rightsib
= cpu_to_be32(NULLAGBLOCK
);
1112 buf
->bb_u
.s
.bb_blkno
= cpu_to_be64(blkno
);
1113 buf
->bb_u
.s
.bb_owner
= cpu_to_be32(__owner
);
1114 uuid_copy(&buf
->bb_u
.s
.bb_uuid
, &mp
->m_sb
.sb_meta_uuid
);
1115 buf
->bb_u
.s
.bb_lsn
= 0;
1121 xfs_btree_init_block(
1122 struct xfs_mount
*mp
,
1129 xfs_btree_init_block_int(mp
, XFS_BUF_TO_BLOCK(bp
), bp
->b_bn
,
1130 btnum
, level
, numrecs
, owner
, 0);
1134 xfs_btree_init_block_cur(
1135 struct xfs_btree_cur
*cur
,
1143 * we can pull the owner from the cursor right now as the different
1144 * owners align directly with the pointer size of the btree. This may
1145 * change in future, but is safe for current users of the generic btree
1148 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
)
1149 owner
= cur
->bc_ino
.ip
->i_ino
;
1151 owner
= cur
->bc_ag
.agno
;
1153 xfs_btree_init_block_int(cur
->bc_mp
, XFS_BUF_TO_BLOCK(bp
), bp
->b_bn
,
1154 cur
->bc_btnum
, level
, numrecs
,
1155 owner
, cur
->bc_flags
);
1159 * Return true if ptr is the last record in the btree and
1160 * we need to track updates to this record. The decision
1161 * will be further refined in the update_lastrec method.
1164 xfs_btree_is_lastrec(
1165 struct xfs_btree_cur
*cur
,
1166 struct xfs_btree_block
*block
,
1169 union xfs_btree_ptr ptr
;
1173 if (!(cur
->bc_flags
& XFS_BTREE_LASTREC_UPDATE
))
1176 xfs_btree_get_sibling(cur
, block
, &ptr
, XFS_BB_RIGHTSIB
);
1177 if (!xfs_btree_ptr_is_null(cur
, &ptr
))
1183 xfs_btree_buf_to_ptr(
1184 struct xfs_btree_cur
*cur
,
1186 union xfs_btree_ptr
*ptr
)
1188 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
)
1189 ptr
->l
= cpu_to_be64(XFS_DADDR_TO_FSB(cur
->bc_mp
,
1192 ptr
->s
= cpu_to_be32(xfs_daddr_to_agbno(cur
->bc_mp
,
1199 struct xfs_btree_cur
*cur
,
1202 switch (cur
->bc_btnum
) {
1205 xfs_buf_set_ref(bp
, XFS_ALLOC_BTREE_REF
);
1208 case XFS_BTNUM_FINO
:
1209 xfs_buf_set_ref(bp
, XFS_INO_BTREE_REF
);
1211 case XFS_BTNUM_BMAP
:
1212 xfs_buf_set_ref(bp
, XFS_BMAP_BTREE_REF
);
1214 case XFS_BTNUM_RMAP
:
1215 xfs_buf_set_ref(bp
, XFS_RMAP_BTREE_REF
);
1217 case XFS_BTNUM_REFC
:
1218 xfs_buf_set_ref(bp
, XFS_REFC_BTREE_REF
);
1226 xfs_btree_get_buf_block(
1227 struct xfs_btree_cur
*cur
,
1228 union xfs_btree_ptr
*ptr
,
1229 struct xfs_btree_block
**block
,
1230 struct xfs_buf
**bpp
)
1232 struct xfs_mount
*mp
= cur
->bc_mp
;
1236 error
= xfs_btree_ptr_to_daddr(cur
, ptr
, &d
);
1239 error
= xfs_trans_get_buf(cur
->bc_tp
, mp
->m_ddev_targp
, d
, mp
->m_bsize
,
1244 (*bpp
)->b_ops
= cur
->bc_ops
->buf_ops
;
1245 *block
= XFS_BUF_TO_BLOCK(*bpp
);
1250 * Read in the buffer at the given ptr and return the buffer and
1251 * the block pointer within the buffer.
1254 xfs_btree_read_buf_block(
1255 struct xfs_btree_cur
*cur
,
1256 union xfs_btree_ptr
*ptr
,
1258 struct xfs_btree_block
**block
,
1259 struct xfs_buf
**bpp
)
1261 struct xfs_mount
*mp
= cur
->bc_mp
;
1265 /* need to sort out how callers deal with failures first */
1266 ASSERT(!(flags
& XBF_TRYLOCK
));
1268 error
= xfs_btree_ptr_to_daddr(cur
, ptr
, &d
);
1271 error
= xfs_trans_read_buf(mp
, cur
->bc_tp
, mp
->m_ddev_targp
, d
,
1272 mp
->m_bsize
, flags
, bpp
,
1273 cur
->bc_ops
->buf_ops
);
1277 xfs_btree_set_refs(cur
, *bpp
);
1278 *block
= XFS_BUF_TO_BLOCK(*bpp
);
1283 * Copy keys from one btree block to another.
1286 xfs_btree_copy_keys(
1287 struct xfs_btree_cur
*cur
,
1288 union xfs_btree_key
*dst_key
,
1289 union xfs_btree_key
*src_key
,
1292 ASSERT(numkeys
>= 0);
1293 memcpy(dst_key
, src_key
, numkeys
* cur
->bc_ops
->key_len
);
1297 * Copy records from one btree block to another.
1300 xfs_btree_copy_recs(
1301 struct xfs_btree_cur
*cur
,
1302 union xfs_btree_rec
*dst_rec
,
1303 union xfs_btree_rec
*src_rec
,
1306 ASSERT(numrecs
>= 0);
1307 memcpy(dst_rec
, src_rec
, numrecs
* cur
->bc_ops
->rec_len
);
1311 * Copy block pointers from one btree block to another.
1314 xfs_btree_copy_ptrs(
1315 struct xfs_btree_cur
*cur
,
1316 union xfs_btree_ptr
*dst_ptr
,
1317 const union xfs_btree_ptr
*src_ptr
,
1320 ASSERT(numptrs
>= 0);
1321 memcpy(dst_ptr
, src_ptr
, numptrs
* xfs_btree_ptr_len(cur
));
1325 * Shift keys one index left/right inside a single btree block.
1328 xfs_btree_shift_keys(
1329 struct xfs_btree_cur
*cur
,
1330 union xfs_btree_key
*key
,
1336 ASSERT(numkeys
>= 0);
1337 ASSERT(dir
== 1 || dir
== -1);
1339 dst_key
= (char *)key
+ (dir
* cur
->bc_ops
->key_len
);
1340 memmove(dst_key
, key
, numkeys
* cur
->bc_ops
->key_len
);
1344 * Shift records one index left/right inside a single btree block.
1347 xfs_btree_shift_recs(
1348 struct xfs_btree_cur
*cur
,
1349 union xfs_btree_rec
*rec
,
1355 ASSERT(numrecs
>= 0);
1356 ASSERT(dir
== 1 || dir
== -1);
1358 dst_rec
= (char *)rec
+ (dir
* cur
->bc_ops
->rec_len
);
1359 memmove(dst_rec
, rec
, numrecs
* cur
->bc_ops
->rec_len
);
1363 * Shift block pointers one index left/right inside a single btree block.
1366 xfs_btree_shift_ptrs(
1367 struct xfs_btree_cur
*cur
,
1368 union xfs_btree_ptr
*ptr
,
1374 ASSERT(numptrs
>= 0);
1375 ASSERT(dir
== 1 || dir
== -1);
1377 dst_ptr
= (char *)ptr
+ (dir
* xfs_btree_ptr_len(cur
));
1378 memmove(dst_ptr
, ptr
, numptrs
* xfs_btree_ptr_len(cur
));
1382 * Log key values from the btree block.
1386 struct xfs_btree_cur
*cur
,
1393 xfs_trans_buf_set_type(cur
->bc_tp
, bp
, XFS_BLFT_BTREE_BUF
);
1394 xfs_trans_log_buf(cur
->bc_tp
, bp
,
1395 xfs_btree_key_offset(cur
, first
),
1396 xfs_btree_key_offset(cur
, last
+ 1) - 1);
1398 xfs_trans_log_inode(cur
->bc_tp
, cur
->bc_ino
.ip
,
1399 xfs_ilog_fbroot(cur
->bc_ino
.whichfork
));
1404 * Log record values from the btree block.
1408 struct xfs_btree_cur
*cur
,
1414 xfs_trans_buf_set_type(cur
->bc_tp
, bp
, XFS_BLFT_BTREE_BUF
);
1415 xfs_trans_log_buf(cur
->bc_tp
, bp
,
1416 xfs_btree_rec_offset(cur
, first
),
1417 xfs_btree_rec_offset(cur
, last
+ 1) - 1);
1422 * Log block pointer fields from a btree block (nonleaf).
1426 struct xfs_btree_cur
*cur
, /* btree cursor */
1427 struct xfs_buf
*bp
, /* buffer containing btree block */
1428 int first
, /* index of first pointer to log */
1429 int last
) /* index of last pointer to log */
1433 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
1434 int level
= xfs_btree_get_level(block
);
1436 xfs_trans_buf_set_type(cur
->bc_tp
, bp
, XFS_BLFT_BTREE_BUF
);
1437 xfs_trans_log_buf(cur
->bc_tp
, bp
,
1438 xfs_btree_ptr_offset(cur
, first
, level
),
1439 xfs_btree_ptr_offset(cur
, last
+ 1, level
) - 1);
1441 xfs_trans_log_inode(cur
->bc_tp
, cur
->bc_ino
.ip
,
1442 xfs_ilog_fbroot(cur
->bc_ino
.whichfork
));
1448 * Log fields from a btree block header.
1451 xfs_btree_log_block(
1452 struct xfs_btree_cur
*cur
, /* btree cursor */
1453 struct xfs_buf
*bp
, /* buffer containing btree block */
1454 int fields
) /* mask of fields: XFS_BB_... */
1456 int first
; /* first byte offset logged */
1457 int last
; /* last byte offset logged */
1458 static const short soffsets
[] = { /* table of offsets (short) */
1459 offsetof(struct xfs_btree_block
, bb_magic
),
1460 offsetof(struct xfs_btree_block
, bb_level
),
1461 offsetof(struct xfs_btree_block
, bb_numrecs
),
1462 offsetof(struct xfs_btree_block
, bb_u
.s
.bb_leftsib
),
1463 offsetof(struct xfs_btree_block
, bb_u
.s
.bb_rightsib
),
1464 offsetof(struct xfs_btree_block
, bb_u
.s
.bb_blkno
),
1465 offsetof(struct xfs_btree_block
, bb_u
.s
.bb_lsn
),
1466 offsetof(struct xfs_btree_block
, bb_u
.s
.bb_uuid
),
1467 offsetof(struct xfs_btree_block
, bb_u
.s
.bb_owner
),
1468 offsetof(struct xfs_btree_block
, bb_u
.s
.bb_crc
),
1469 XFS_BTREE_SBLOCK_CRC_LEN
1471 static const short loffsets
[] = { /* table of offsets (long) */
1472 offsetof(struct xfs_btree_block
, bb_magic
),
1473 offsetof(struct xfs_btree_block
, bb_level
),
1474 offsetof(struct xfs_btree_block
, bb_numrecs
),
1475 offsetof(struct xfs_btree_block
, bb_u
.l
.bb_leftsib
),
1476 offsetof(struct xfs_btree_block
, bb_u
.l
.bb_rightsib
),
1477 offsetof(struct xfs_btree_block
, bb_u
.l
.bb_blkno
),
1478 offsetof(struct xfs_btree_block
, bb_u
.l
.bb_lsn
),
1479 offsetof(struct xfs_btree_block
, bb_u
.l
.bb_uuid
),
1480 offsetof(struct xfs_btree_block
, bb_u
.l
.bb_owner
),
1481 offsetof(struct xfs_btree_block
, bb_u
.l
.bb_crc
),
1482 offsetof(struct xfs_btree_block
, bb_u
.l
.bb_pad
),
1483 XFS_BTREE_LBLOCK_CRC_LEN
1489 if (cur
->bc_flags
& XFS_BTREE_CRC_BLOCKS
) {
1491 * We don't log the CRC when updating a btree
1492 * block but instead recreate it during log
1493 * recovery. As the log buffers have checksums
1494 * of their own this is safe and avoids logging a crc
1495 * update in a lot of places.
1497 if (fields
== XFS_BB_ALL_BITS
)
1498 fields
= XFS_BB_ALL_BITS_CRC
;
1499 nbits
= XFS_BB_NUM_BITS_CRC
;
1501 nbits
= XFS_BB_NUM_BITS
;
1503 xfs_btree_offsets(fields
,
1504 (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
) ?
1505 loffsets
: soffsets
,
1506 nbits
, &first
, &last
);
1507 xfs_trans_buf_set_type(cur
->bc_tp
, bp
, XFS_BLFT_BTREE_BUF
);
1508 xfs_trans_log_buf(cur
->bc_tp
, bp
, first
, last
);
1510 xfs_trans_log_inode(cur
->bc_tp
, cur
->bc_ino
.ip
,
1511 xfs_ilog_fbroot(cur
->bc_ino
.whichfork
));
1516 * Increment cursor by one record at the level.
1517 * For nonzero levels the leaf-ward information is untouched.
1520 xfs_btree_increment(
1521 struct xfs_btree_cur
*cur
,
1523 int *stat
) /* success/failure */
1525 struct xfs_btree_block
*block
;
1526 union xfs_btree_ptr ptr
;
1528 int error
; /* error return value */
1531 ASSERT(level
< cur
->bc_nlevels
);
1533 /* Read-ahead to the right at this level. */
1534 xfs_btree_readahead(cur
, level
, XFS_BTCUR_RIGHTRA
);
1536 /* Get a pointer to the btree block. */
1537 block
= xfs_btree_get_block(cur
, level
, &bp
);
1540 error
= xfs_btree_check_block(cur
, block
, level
, bp
);
1545 /* We're done if we remain in the block after the increment. */
1546 if (++cur
->bc_ptrs
[level
] <= xfs_btree_get_numrecs(block
))
1549 /* Fail if we just went off the right edge of the tree. */
1550 xfs_btree_get_sibling(cur
, block
, &ptr
, XFS_BB_RIGHTSIB
);
1551 if (xfs_btree_ptr_is_null(cur
, &ptr
))
1554 XFS_BTREE_STATS_INC(cur
, increment
);
1557 * March up the tree incrementing pointers.
1558 * Stop when we don't go off the right edge of a block.
1560 for (lev
= level
+ 1; lev
< cur
->bc_nlevels
; lev
++) {
1561 block
= xfs_btree_get_block(cur
, lev
, &bp
);
1564 error
= xfs_btree_check_block(cur
, block
, lev
, bp
);
1569 if (++cur
->bc_ptrs
[lev
] <= xfs_btree_get_numrecs(block
))
1572 /* Read-ahead the right block for the next loop. */
1573 xfs_btree_readahead(cur
, lev
, XFS_BTCUR_RIGHTRA
);
1577 * If we went off the root then we are either seriously
1578 * confused or have the tree root in an inode.
1580 if (lev
== cur
->bc_nlevels
) {
1581 if (cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
)
1584 error
= -EFSCORRUPTED
;
1587 ASSERT(lev
< cur
->bc_nlevels
);
1590 * Now walk back down the tree, fixing up the cursor's buffer
1591 * pointers and key numbers.
1593 for (block
= xfs_btree_get_block(cur
, lev
, &bp
); lev
> level
; ) {
1594 union xfs_btree_ptr
*ptrp
;
1596 ptrp
= xfs_btree_ptr_addr(cur
, cur
->bc_ptrs
[lev
], block
);
1598 error
= xfs_btree_read_buf_block(cur
, ptrp
, 0, &block
, &bp
);
1602 xfs_btree_setbuf(cur
, lev
, bp
);
1603 cur
->bc_ptrs
[lev
] = 1;
1618 * Decrement cursor by one record at the level.
1619 * For nonzero levels the leaf-ward information is untouched.
1622 xfs_btree_decrement(
1623 struct xfs_btree_cur
*cur
,
1625 int *stat
) /* success/failure */
1627 struct xfs_btree_block
*block
;
1629 int error
; /* error return value */
1631 union xfs_btree_ptr ptr
;
1633 ASSERT(level
< cur
->bc_nlevels
);
1635 /* Read-ahead to the left at this level. */
1636 xfs_btree_readahead(cur
, level
, XFS_BTCUR_LEFTRA
);
1638 /* We're done if we remain in the block after the decrement. */
1639 if (--cur
->bc_ptrs
[level
] > 0)
1642 /* Get a pointer to the btree block. */
1643 block
= xfs_btree_get_block(cur
, level
, &bp
);
1646 error
= xfs_btree_check_block(cur
, block
, level
, bp
);
1651 /* Fail if we just went off the left edge of the tree. */
1652 xfs_btree_get_sibling(cur
, block
, &ptr
, XFS_BB_LEFTSIB
);
1653 if (xfs_btree_ptr_is_null(cur
, &ptr
))
1656 XFS_BTREE_STATS_INC(cur
, decrement
);
1659 * March up the tree decrementing pointers.
1660 * Stop when we don't go off the left edge of a block.
1662 for (lev
= level
+ 1; lev
< cur
->bc_nlevels
; lev
++) {
1663 if (--cur
->bc_ptrs
[lev
] > 0)
1665 /* Read-ahead the left block for the next loop. */
1666 xfs_btree_readahead(cur
, lev
, XFS_BTCUR_LEFTRA
);
1670 * If we went off the root then we are seriously confused.
1671 * or the root of the tree is in an inode.
1673 if (lev
== cur
->bc_nlevels
) {
1674 if (cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
)
1677 error
= -EFSCORRUPTED
;
1680 ASSERT(lev
< cur
->bc_nlevels
);
1683 * Now walk back down the tree, fixing up the cursor's buffer
1684 * pointers and key numbers.
1686 for (block
= xfs_btree_get_block(cur
, lev
, &bp
); lev
> level
; ) {
1687 union xfs_btree_ptr
*ptrp
;
1689 ptrp
= xfs_btree_ptr_addr(cur
, cur
->bc_ptrs
[lev
], block
);
1691 error
= xfs_btree_read_buf_block(cur
, ptrp
, 0, &block
, &bp
);
1694 xfs_btree_setbuf(cur
, lev
, bp
);
1695 cur
->bc_ptrs
[lev
] = xfs_btree_get_numrecs(block
);
1710 xfs_btree_lookup_get_block(
1711 struct xfs_btree_cur
*cur
, /* btree cursor */
1712 int level
, /* level in the btree */
1713 union xfs_btree_ptr
*pp
, /* ptr to btree block */
1714 struct xfs_btree_block
**blkp
) /* return btree block */
1716 struct xfs_buf
*bp
; /* buffer pointer for btree block */
1720 /* special case the root block if in an inode */
1721 if ((cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
) &&
1722 (level
== cur
->bc_nlevels
- 1)) {
1723 *blkp
= xfs_btree_get_iroot(cur
);
1728 * If the old buffer at this level for the disk address we are
1729 * looking for re-use it.
1731 * Otherwise throw it away and get a new one.
1733 bp
= cur
->bc_bufs
[level
];
1734 error
= xfs_btree_ptr_to_daddr(cur
, pp
, &daddr
);
1737 if (bp
&& XFS_BUF_ADDR(bp
) == daddr
) {
1738 *blkp
= XFS_BUF_TO_BLOCK(bp
);
1742 error
= xfs_btree_read_buf_block(cur
, pp
, 0, blkp
, &bp
);
1746 /* Check the inode owner since the verifiers don't. */
1747 if (xfs_sb_version_hascrc(&cur
->bc_mp
->m_sb
) &&
1748 !(cur
->bc_ino
.flags
& XFS_BTCUR_BMBT_INVALID_OWNER
) &&
1749 (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
) &&
1750 be64_to_cpu((*blkp
)->bb_u
.l
.bb_owner
) !=
1751 cur
->bc_ino
.ip
->i_ino
)
1754 /* Did we get the level we were looking for? */
1755 if (be16_to_cpu((*blkp
)->bb_level
) != level
)
1758 /* Check that internal nodes have at least one record. */
1759 if (level
!= 0 && be16_to_cpu((*blkp
)->bb_numrecs
) == 0)
1762 xfs_btree_setbuf(cur
, level
, bp
);
1767 xfs_buf_mark_corrupt(bp
);
1768 xfs_trans_brelse(cur
->bc_tp
, bp
);
1769 return -EFSCORRUPTED
;
1773 * Get current search key. For level 0 we don't actually have a key
1774 * structure so we make one up from the record. For all other levels
1775 * we just return the right key.
1777 STATIC
union xfs_btree_key
*
1778 xfs_lookup_get_search_key(
1779 struct xfs_btree_cur
*cur
,
1782 struct xfs_btree_block
*block
,
1783 union xfs_btree_key
*kp
)
1786 cur
->bc_ops
->init_key_from_rec(kp
,
1787 xfs_btree_rec_addr(cur
, keyno
, block
));
1791 return xfs_btree_key_addr(cur
, keyno
, block
);
1795 * Lookup the record. The cursor is made to point to it, based on dir.
1796 * stat is set to 0 if can't find any such record, 1 for success.
1800 struct xfs_btree_cur
*cur
, /* btree cursor */
1801 xfs_lookup_t dir
, /* <=, ==, or >= */
1802 int *stat
) /* success/failure */
1804 struct xfs_btree_block
*block
; /* current btree block */
1805 int64_t diff
; /* difference for the current key */
1806 int error
; /* error return value */
1807 int keyno
; /* current key number */
1808 int level
; /* level in the btree */
1809 union xfs_btree_ptr
*pp
; /* ptr to btree block */
1810 union xfs_btree_ptr ptr
; /* ptr to btree block */
1812 XFS_BTREE_STATS_INC(cur
, lookup
);
1814 /* No such thing as a zero-level tree. */
1815 if (XFS_IS_CORRUPT(cur
->bc_mp
, cur
->bc_nlevels
== 0))
1816 return -EFSCORRUPTED
;
1821 /* initialise start pointer from cursor */
1822 cur
->bc_ops
->init_ptr_from_cur(cur
, &ptr
);
1826 * Iterate over each level in the btree, starting at the root.
1827 * For each level above the leaves, find the key we need, based
1828 * on the lookup record, then follow the corresponding block
1829 * pointer down to the next level.
1831 for (level
= cur
->bc_nlevels
- 1, diff
= 1; level
>= 0; level
--) {
1832 /* Get the block we need to do the lookup on. */
1833 error
= xfs_btree_lookup_get_block(cur
, level
, pp
, &block
);
1839 * If we already had a key match at a higher level, we
1840 * know we need to use the first entry in this block.
1844 /* Otherwise search this block. Do a binary search. */
1846 int high
; /* high entry number */
1847 int low
; /* low entry number */
1849 /* Set low and high entry numbers, 1-based. */
1851 high
= xfs_btree_get_numrecs(block
);
1853 /* Block is empty, must be an empty leaf. */
1854 if (level
!= 0 || cur
->bc_nlevels
!= 1) {
1855 XFS_CORRUPTION_ERROR(__func__
,
1859 return -EFSCORRUPTED
;
1862 cur
->bc_ptrs
[0] = dir
!= XFS_LOOKUP_LE
;
1867 /* Binary search the block. */
1868 while (low
<= high
) {
1869 union xfs_btree_key key
;
1870 union xfs_btree_key
*kp
;
1872 XFS_BTREE_STATS_INC(cur
, compare
);
1874 /* keyno is average of low and high. */
1875 keyno
= (low
+ high
) >> 1;
1877 /* Get current search key */
1878 kp
= xfs_lookup_get_search_key(cur
, level
,
1879 keyno
, block
, &key
);
1882 * Compute difference to get next direction:
1883 * - less than, move right
1884 * - greater than, move left
1885 * - equal, we're done
1887 diff
= cur
->bc_ops
->key_diff(cur
, kp
);
1898 * If there are more levels, set up for the next level
1899 * by getting the block number and filling in the cursor.
1903 * If we moved left, need the previous key number,
1904 * unless there isn't one.
1906 if (diff
> 0 && --keyno
< 1)
1908 pp
= xfs_btree_ptr_addr(cur
, keyno
, block
);
1910 error
= xfs_btree_debug_check_ptr(cur
, pp
, 0, level
);
1914 cur
->bc_ptrs
[level
] = keyno
;
1918 /* Done with the search. See if we need to adjust the results. */
1919 if (dir
!= XFS_LOOKUP_LE
&& diff
< 0) {
1922 * If ge search and we went off the end of the block, but it's
1923 * not the last block, we're in the wrong block.
1925 xfs_btree_get_sibling(cur
, block
, &ptr
, XFS_BB_RIGHTSIB
);
1926 if (dir
== XFS_LOOKUP_GE
&&
1927 keyno
> xfs_btree_get_numrecs(block
) &&
1928 !xfs_btree_ptr_is_null(cur
, &ptr
)) {
1931 cur
->bc_ptrs
[0] = keyno
;
1932 error
= xfs_btree_increment(cur
, 0, &i
);
1935 if (XFS_IS_CORRUPT(cur
->bc_mp
, i
!= 1))
1936 return -EFSCORRUPTED
;
1940 } else if (dir
== XFS_LOOKUP_LE
&& diff
> 0)
1942 cur
->bc_ptrs
[0] = keyno
;
1944 /* Return if we succeeded or not. */
1945 if (keyno
== 0 || keyno
> xfs_btree_get_numrecs(block
))
1947 else if (dir
!= XFS_LOOKUP_EQ
|| diff
== 0)
1957 /* Find the high key storage area from a regular key. */
1958 union xfs_btree_key
*
1959 xfs_btree_high_key_from_key(
1960 struct xfs_btree_cur
*cur
,
1961 union xfs_btree_key
*key
)
1963 ASSERT(cur
->bc_flags
& XFS_BTREE_OVERLAPPING
);
1964 return (union xfs_btree_key
*)((char *)key
+
1965 (cur
->bc_ops
->key_len
/ 2));
1968 /* Determine the low (and high if overlapped) keys of a leaf block */
1970 xfs_btree_get_leaf_keys(
1971 struct xfs_btree_cur
*cur
,
1972 struct xfs_btree_block
*block
,
1973 union xfs_btree_key
*key
)
1975 union xfs_btree_key max_hkey
;
1976 union xfs_btree_key hkey
;
1977 union xfs_btree_rec
*rec
;
1978 union xfs_btree_key
*high
;
1981 rec
= xfs_btree_rec_addr(cur
, 1, block
);
1982 cur
->bc_ops
->init_key_from_rec(key
, rec
);
1984 if (cur
->bc_flags
& XFS_BTREE_OVERLAPPING
) {
1986 cur
->bc_ops
->init_high_key_from_rec(&max_hkey
, rec
);
1987 for (n
= 2; n
<= xfs_btree_get_numrecs(block
); n
++) {
1988 rec
= xfs_btree_rec_addr(cur
, n
, block
);
1989 cur
->bc_ops
->init_high_key_from_rec(&hkey
, rec
);
1990 if (cur
->bc_ops
->diff_two_keys(cur
, &hkey
, &max_hkey
)
1995 high
= xfs_btree_high_key_from_key(cur
, key
);
1996 memcpy(high
, &max_hkey
, cur
->bc_ops
->key_len
/ 2);
2000 /* Determine the low (and high if overlapped) keys of a node block */
2002 xfs_btree_get_node_keys(
2003 struct xfs_btree_cur
*cur
,
2004 struct xfs_btree_block
*block
,
2005 union xfs_btree_key
*key
)
2007 union xfs_btree_key
*hkey
;
2008 union xfs_btree_key
*max_hkey
;
2009 union xfs_btree_key
*high
;
2012 if (cur
->bc_flags
& XFS_BTREE_OVERLAPPING
) {
2013 memcpy(key
, xfs_btree_key_addr(cur
, 1, block
),
2014 cur
->bc_ops
->key_len
/ 2);
2016 max_hkey
= xfs_btree_high_key_addr(cur
, 1, block
);
2017 for (n
= 2; n
<= xfs_btree_get_numrecs(block
); n
++) {
2018 hkey
= xfs_btree_high_key_addr(cur
, n
, block
);
2019 if (cur
->bc_ops
->diff_two_keys(cur
, hkey
, max_hkey
) > 0)
2023 high
= xfs_btree_high_key_from_key(cur
, key
);
2024 memcpy(high
, max_hkey
, cur
->bc_ops
->key_len
/ 2);
2026 memcpy(key
, xfs_btree_key_addr(cur
, 1, block
),
2027 cur
->bc_ops
->key_len
);
2031 /* Derive the keys for any btree block. */
2034 struct xfs_btree_cur
*cur
,
2035 struct xfs_btree_block
*block
,
2036 union xfs_btree_key
*key
)
2038 if (be16_to_cpu(block
->bb_level
) == 0)
2039 xfs_btree_get_leaf_keys(cur
, block
, key
);
2041 xfs_btree_get_node_keys(cur
, block
, key
);
2045 * Decide if we need to update the parent keys of a btree block. For
2046 * a standard btree this is only necessary if we're updating the first
2047 * record/key. For an overlapping btree, we must always update the
2048 * keys because the highest key can be in any of the records or keys
2052 xfs_btree_needs_key_update(
2053 struct xfs_btree_cur
*cur
,
2056 return (cur
->bc_flags
& XFS_BTREE_OVERLAPPING
) || ptr
== 1;
2060 * Update the low and high parent keys of the given level, progressing
2061 * towards the root. If force_all is false, stop if the keys for a given
2062 * level do not need updating.
2065 __xfs_btree_updkeys(
2066 struct xfs_btree_cur
*cur
,
2068 struct xfs_btree_block
*block
,
2069 struct xfs_buf
*bp0
,
2072 union xfs_btree_key key
; /* keys from current level */
2073 union xfs_btree_key
*lkey
; /* keys from the next level up */
2074 union xfs_btree_key
*hkey
;
2075 union xfs_btree_key
*nlkey
; /* keys from the next level up */
2076 union xfs_btree_key
*nhkey
;
2080 ASSERT(cur
->bc_flags
& XFS_BTREE_OVERLAPPING
);
2082 /* Exit if there aren't any parent levels to update. */
2083 if (level
+ 1 >= cur
->bc_nlevels
)
2086 trace_xfs_btree_updkeys(cur
, level
, bp0
);
2089 hkey
= xfs_btree_high_key_from_key(cur
, lkey
);
2090 xfs_btree_get_keys(cur
, block
, lkey
);
2091 for (level
++; level
< cur
->bc_nlevels
; level
++) {
2095 block
= xfs_btree_get_block(cur
, level
, &bp
);
2096 trace_xfs_btree_updkeys(cur
, level
, bp
);
2098 error
= xfs_btree_check_block(cur
, block
, level
, bp
);
2102 ptr
= cur
->bc_ptrs
[level
];
2103 nlkey
= xfs_btree_key_addr(cur
, ptr
, block
);
2104 nhkey
= xfs_btree_high_key_addr(cur
, ptr
, block
);
2106 !(cur
->bc_ops
->diff_two_keys(cur
, nlkey
, lkey
) != 0 ||
2107 cur
->bc_ops
->diff_two_keys(cur
, nhkey
, hkey
) != 0))
2109 xfs_btree_copy_keys(cur
, nlkey
, lkey
, 1);
2110 xfs_btree_log_keys(cur
, bp
, ptr
, ptr
);
2111 if (level
+ 1 >= cur
->bc_nlevels
)
2113 xfs_btree_get_node_keys(cur
, block
, lkey
);
2119 /* Update all the keys from some level in cursor back to the root. */
2121 xfs_btree_updkeys_force(
2122 struct xfs_btree_cur
*cur
,
2126 struct xfs_btree_block
*block
;
2128 block
= xfs_btree_get_block(cur
, level
, &bp
);
2129 return __xfs_btree_updkeys(cur
, level
, block
, bp
, true);
2133 * Update the parent keys of the given level, progressing towards the root.
2136 xfs_btree_update_keys(
2137 struct xfs_btree_cur
*cur
,
2140 struct xfs_btree_block
*block
;
2142 union xfs_btree_key
*kp
;
2143 union xfs_btree_key key
;
2148 block
= xfs_btree_get_block(cur
, level
, &bp
);
2149 if (cur
->bc_flags
& XFS_BTREE_OVERLAPPING
)
2150 return __xfs_btree_updkeys(cur
, level
, block
, bp
, false);
2153 * Go up the tree from this level toward the root.
2154 * At each level, update the key value to the value input.
2155 * Stop when we reach a level where the cursor isn't pointing
2156 * at the first entry in the block.
2158 xfs_btree_get_keys(cur
, block
, &key
);
2159 for (level
++, ptr
= 1; ptr
== 1 && level
< cur
->bc_nlevels
; level
++) {
2163 block
= xfs_btree_get_block(cur
, level
, &bp
);
2165 error
= xfs_btree_check_block(cur
, block
, level
, bp
);
2169 ptr
= cur
->bc_ptrs
[level
];
2170 kp
= xfs_btree_key_addr(cur
, ptr
, block
);
2171 xfs_btree_copy_keys(cur
, kp
, &key
, 1);
2172 xfs_btree_log_keys(cur
, bp
, ptr
, ptr
);
2179 * Update the record referred to by cur to the value in the
2180 * given record. This either works (return 0) or gets an
2181 * EFSCORRUPTED error.
2185 struct xfs_btree_cur
*cur
,
2186 union xfs_btree_rec
*rec
)
2188 struct xfs_btree_block
*block
;
2192 union xfs_btree_rec
*rp
;
2194 /* Pick up the current block. */
2195 block
= xfs_btree_get_block(cur
, 0, &bp
);
2198 error
= xfs_btree_check_block(cur
, block
, 0, bp
);
2202 /* Get the address of the rec to be updated. */
2203 ptr
= cur
->bc_ptrs
[0];
2204 rp
= xfs_btree_rec_addr(cur
, ptr
, block
);
2206 /* Fill in the new contents and log them. */
2207 xfs_btree_copy_recs(cur
, rp
, rec
, 1);
2208 xfs_btree_log_recs(cur
, bp
, ptr
, ptr
);
2211 * If we are tracking the last record in the tree and
2212 * we are at the far right edge of the tree, update it.
2214 if (xfs_btree_is_lastrec(cur
, block
, 0)) {
2215 cur
->bc_ops
->update_lastrec(cur
, block
, rec
,
2216 ptr
, LASTREC_UPDATE
);
2219 /* Pass new key value up to our parent. */
2220 if (xfs_btree_needs_key_update(cur
, ptr
)) {
2221 error
= xfs_btree_update_keys(cur
, 0);
2233 * Move 1 record left from cur/level if possible.
2234 * Update cur to reflect the new path.
2236 STATIC
int /* error */
2238 struct xfs_btree_cur
*cur
,
2240 int *stat
) /* success/failure */
2242 struct xfs_buf
*lbp
; /* left buffer pointer */
2243 struct xfs_btree_block
*left
; /* left btree block */
2244 int lrecs
; /* left record count */
2245 struct xfs_buf
*rbp
; /* right buffer pointer */
2246 struct xfs_btree_block
*right
; /* right btree block */
2247 struct xfs_btree_cur
*tcur
; /* temporary btree cursor */
2248 int rrecs
; /* right record count */
2249 union xfs_btree_ptr lptr
; /* left btree pointer */
2250 union xfs_btree_key
*rkp
= NULL
; /* right btree key */
2251 union xfs_btree_ptr
*rpp
= NULL
; /* right address pointer */
2252 union xfs_btree_rec
*rrp
= NULL
; /* right record pointer */
2253 int error
; /* error return value */
2256 if ((cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
) &&
2257 level
== cur
->bc_nlevels
- 1)
2260 /* Set up variables for this block as "right". */
2261 right
= xfs_btree_get_block(cur
, level
, &rbp
);
2264 error
= xfs_btree_check_block(cur
, right
, level
, rbp
);
2269 /* If we've got no left sibling then we can't shift an entry left. */
2270 xfs_btree_get_sibling(cur
, right
, &lptr
, XFS_BB_LEFTSIB
);
2271 if (xfs_btree_ptr_is_null(cur
, &lptr
))
2275 * If the cursor entry is the one that would be moved, don't
2276 * do it... it's too complicated.
2278 if (cur
->bc_ptrs
[level
] <= 1)
2281 /* Set up the left neighbor as "left". */
2282 error
= xfs_btree_read_buf_block(cur
, &lptr
, 0, &left
, &lbp
);
2286 /* If it's full, it can't take another entry. */
2287 lrecs
= xfs_btree_get_numrecs(left
);
2288 if (lrecs
== cur
->bc_ops
->get_maxrecs(cur
, level
))
2291 rrecs
= xfs_btree_get_numrecs(right
);
2294 * We add one entry to the left side and remove one for the right side.
2295 * Account for it here, the changes will be updated on disk and logged
2301 XFS_BTREE_STATS_INC(cur
, lshift
);
2302 XFS_BTREE_STATS_ADD(cur
, moves
, 1);
2305 * If non-leaf, copy a key and a ptr to the left block.
2306 * Log the changes to the left block.
2309 /* It's a non-leaf. Move keys and pointers. */
2310 union xfs_btree_key
*lkp
; /* left btree key */
2311 union xfs_btree_ptr
*lpp
; /* left address pointer */
2313 lkp
= xfs_btree_key_addr(cur
, lrecs
, left
);
2314 rkp
= xfs_btree_key_addr(cur
, 1, right
);
2316 lpp
= xfs_btree_ptr_addr(cur
, lrecs
, left
);
2317 rpp
= xfs_btree_ptr_addr(cur
, 1, right
);
2319 error
= xfs_btree_debug_check_ptr(cur
, rpp
, 0, level
);
2323 xfs_btree_copy_keys(cur
, lkp
, rkp
, 1);
2324 xfs_btree_copy_ptrs(cur
, lpp
, rpp
, 1);
2326 xfs_btree_log_keys(cur
, lbp
, lrecs
, lrecs
);
2327 xfs_btree_log_ptrs(cur
, lbp
, lrecs
, lrecs
);
2329 ASSERT(cur
->bc_ops
->keys_inorder(cur
,
2330 xfs_btree_key_addr(cur
, lrecs
- 1, left
), lkp
));
2332 /* It's a leaf. Move records. */
2333 union xfs_btree_rec
*lrp
; /* left record pointer */
2335 lrp
= xfs_btree_rec_addr(cur
, lrecs
, left
);
2336 rrp
= xfs_btree_rec_addr(cur
, 1, right
);
2338 xfs_btree_copy_recs(cur
, lrp
, rrp
, 1);
2339 xfs_btree_log_recs(cur
, lbp
, lrecs
, lrecs
);
2341 ASSERT(cur
->bc_ops
->recs_inorder(cur
,
2342 xfs_btree_rec_addr(cur
, lrecs
- 1, left
), lrp
));
2345 xfs_btree_set_numrecs(left
, lrecs
);
2346 xfs_btree_log_block(cur
, lbp
, XFS_BB_NUMRECS
);
2348 xfs_btree_set_numrecs(right
, rrecs
);
2349 xfs_btree_log_block(cur
, rbp
, XFS_BB_NUMRECS
);
2352 * Slide the contents of right down one entry.
2354 XFS_BTREE_STATS_ADD(cur
, moves
, rrecs
- 1);
2356 /* It's a nonleaf. operate on keys and ptrs */
2357 for (i
= 0; i
< rrecs
; i
++) {
2358 error
= xfs_btree_debug_check_ptr(cur
, rpp
, i
+ 1, level
);
2363 xfs_btree_shift_keys(cur
,
2364 xfs_btree_key_addr(cur
, 2, right
),
2366 xfs_btree_shift_ptrs(cur
,
2367 xfs_btree_ptr_addr(cur
, 2, right
),
2370 xfs_btree_log_keys(cur
, rbp
, 1, rrecs
);
2371 xfs_btree_log_ptrs(cur
, rbp
, 1, rrecs
);
2373 /* It's a leaf. operate on records */
2374 xfs_btree_shift_recs(cur
,
2375 xfs_btree_rec_addr(cur
, 2, right
),
2377 xfs_btree_log_recs(cur
, rbp
, 1, rrecs
);
2381 * Using a temporary cursor, update the parent key values of the
2382 * block on the left.
2384 if (cur
->bc_flags
& XFS_BTREE_OVERLAPPING
) {
2385 error
= xfs_btree_dup_cursor(cur
, &tcur
);
2388 i
= xfs_btree_firstrec(tcur
, level
);
2389 if (XFS_IS_CORRUPT(tcur
->bc_mp
, i
!= 1)) {
2390 error
= -EFSCORRUPTED
;
2394 error
= xfs_btree_decrement(tcur
, level
, &i
);
2398 /* Update the parent high keys of the left block, if needed. */
2399 error
= xfs_btree_update_keys(tcur
, level
);
2403 xfs_btree_del_cursor(tcur
, XFS_BTREE_NOERROR
);
2406 /* Update the parent keys of the right block. */
2407 error
= xfs_btree_update_keys(cur
, level
);
2411 /* Slide the cursor value left one. */
2412 cur
->bc_ptrs
[level
]--;
2425 xfs_btree_del_cursor(tcur
, XFS_BTREE_ERROR
);
2430 * Move 1 record right from cur/level if possible.
2431 * Update cur to reflect the new path.
2433 STATIC
int /* error */
2435 struct xfs_btree_cur
*cur
,
2437 int *stat
) /* success/failure */
2439 struct xfs_buf
*lbp
; /* left buffer pointer */
2440 struct xfs_btree_block
*left
; /* left btree block */
2441 struct xfs_buf
*rbp
; /* right buffer pointer */
2442 struct xfs_btree_block
*right
; /* right btree block */
2443 struct xfs_btree_cur
*tcur
; /* temporary btree cursor */
2444 union xfs_btree_ptr rptr
; /* right block pointer */
2445 union xfs_btree_key
*rkp
; /* right btree key */
2446 int rrecs
; /* right record count */
2447 int lrecs
; /* left record count */
2448 int error
; /* error return value */
2449 int i
; /* loop counter */
2451 if ((cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
) &&
2452 (level
== cur
->bc_nlevels
- 1))
2455 /* Set up variables for this block as "left". */
2456 left
= xfs_btree_get_block(cur
, level
, &lbp
);
2459 error
= xfs_btree_check_block(cur
, left
, level
, lbp
);
2464 /* If we've got no right sibling then we can't shift an entry right. */
2465 xfs_btree_get_sibling(cur
, left
, &rptr
, XFS_BB_RIGHTSIB
);
2466 if (xfs_btree_ptr_is_null(cur
, &rptr
))
2470 * If the cursor entry is the one that would be moved, don't
2471 * do it... it's too complicated.
2473 lrecs
= xfs_btree_get_numrecs(left
);
2474 if (cur
->bc_ptrs
[level
] >= lrecs
)
2477 /* Set up the right neighbor as "right". */
2478 error
= xfs_btree_read_buf_block(cur
, &rptr
, 0, &right
, &rbp
);
2482 /* If it's full, it can't take another entry. */
2483 rrecs
= xfs_btree_get_numrecs(right
);
2484 if (rrecs
== cur
->bc_ops
->get_maxrecs(cur
, level
))
2487 XFS_BTREE_STATS_INC(cur
, rshift
);
2488 XFS_BTREE_STATS_ADD(cur
, moves
, rrecs
);
2491 * Make a hole at the start of the right neighbor block, then
2492 * copy the last left block entry to the hole.
2495 /* It's a nonleaf. make a hole in the keys and ptrs */
2496 union xfs_btree_key
*lkp
;
2497 union xfs_btree_ptr
*lpp
;
2498 union xfs_btree_ptr
*rpp
;
2500 lkp
= xfs_btree_key_addr(cur
, lrecs
, left
);
2501 lpp
= xfs_btree_ptr_addr(cur
, lrecs
, left
);
2502 rkp
= xfs_btree_key_addr(cur
, 1, right
);
2503 rpp
= xfs_btree_ptr_addr(cur
, 1, right
);
2505 for (i
= rrecs
- 1; i
>= 0; i
--) {
2506 error
= xfs_btree_debug_check_ptr(cur
, rpp
, i
, level
);
2511 xfs_btree_shift_keys(cur
, rkp
, 1, rrecs
);
2512 xfs_btree_shift_ptrs(cur
, rpp
, 1, rrecs
);
2514 error
= xfs_btree_debug_check_ptr(cur
, lpp
, 0, level
);
2518 /* Now put the new data in, and log it. */
2519 xfs_btree_copy_keys(cur
, rkp
, lkp
, 1);
2520 xfs_btree_copy_ptrs(cur
, rpp
, lpp
, 1);
2522 xfs_btree_log_keys(cur
, rbp
, 1, rrecs
+ 1);
2523 xfs_btree_log_ptrs(cur
, rbp
, 1, rrecs
+ 1);
2525 ASSERT(cur
->bc_ops
->keys_inorder(cur
, rkp
,
2526 xfs_btree_key_addr(cur
, 2, right
)));
2528 /* It's a leaf. make a hole in the records */
2529 union xfs_btree_rec
*lrp
;
2530 union xfs_btree_rec
*rrp
;
2532 lrp
= xfs_btree_rec_addr(cur
, lrecs
, left
);
2533 rrp
= xfs_btree_rec_addr(cur
, 1, right
);
2535 xfs_btree_shift_recs(cur
, rrp
, 1, rrecs
);
2537 /* Now put the new data in, and log it. */
2538 xfs_btree_copy_recs(cur
, rrp
, lrp
, 1);
2539 xfs_btree_log_recs(cur
, rbp
, 1, rrecs
+ 1);
2543 * Decrement and log left's numrecs, bump and log right's numrecs.
2545 xfs_btree_set_numrecs(left
, --lrecs
);
2546 xfs_btree_log_block(cur
, lbp
, XFS_BB_NUMRECS
);
2548 xfs_btree_set_numrecs(right
, ++rrecs
);
2549 xfs_btree_log_block(cur
, rbp
, XFS_BB_NUMRECS
);
2552 * Using a temporary cursor, update the parent key values of the
2553 * block on the right.
2555 error
= xfs_btree_dup_cursor(cur
, &tcur
);
2558 i
= xfs_btree_lastrec(tcur
, level
);
2559 if (XFS_IS_CORRUPT(tcur
->bc_mp
, i
!= 1)) {
2560 error
= -EFSCORRUPTED
;
2564 error
= xfs_btree_increment(tcur
, level
, &i
);
2568 /* Update the parent high keys of the left block, if needed. */
2569 if (cur
->bc_flags
& XFS_BTREE_OVERLAPPING
) {
2570 error
= xfs_btree_update_keys(cur
, level
);
2575 /* Update the parent keys of the right block. */
2576 error
= xfs_btree_update_keys(tcur
, level
);
2580 xfs_btree_del_cursor(tcur
, XFS_BTREE_NOERROR
);
2593 xfs_btree_del_cursor(tcur
, XFS_BTREE_ERROR
);
2598 * Split cur/level block in half.
2599 * Return new block number and the key to its first
2600 * record (to be inserted into parent).
2602 STATIC
int /* error */
2604 struct xfs_btree_cur
*cur
,
2606 union xfs_btree_ptr
*ptrp
,
2607 union xfs_btree_key
*key
,
2608 struct xfs_btree_cur
**curp
,
2609 int *stat
) /* success/failure */
2611 union xfs_btree_ptr lptr
; /* left sibling block ptr */
2612 struct xfs_buf
*lbp
; /* left buffer pointer */
2613 struct xfs_btree_block
*left
; /* left btree block */
2614 union xfs_btree_ptr rptr
; /* right sibling block ptr */
2615 struct xfs_buf
*rbp
; /* right buffer pointer */
2616 struct xfs_btree_block
*right
; /* right btree block */
2617 union xfs_btree_ptr rrptr
; /* right-right sibling ptr */
2618 struct xfs_buf
*rrbp
; /* right-right buffer pointer */
2619 struct xfs_btree_block
*rrblock
; /* right-right btree block */
2623 int error
; /* error return value */
2626 XFS_BTREE_STATS_INC(cur
, split
);
2628 /* Set up left block (current one). */
2629 left
= xfs_btree_get_block(cur
, level
, &lbp
);
2632 error
= xfs_btree_check_block(cur
, left
, level
, lbp
);
2637 xfs_btree_buf_to_ptr(cur
, lbp
, &lptr
);
2639 /* Allocate the new block. If we can't do it, we're toast. Give up. */
2640 error
= cur
->bc_ops
->alloc_block(cur
, &lptr
, &rptr
, stat
);
2645 XFS_BTREE_STATS_INC(cur
, alloc
);
2647 /* Set up the new block as "right". */
2648 error
= xfs_btree_get_buf_block(cur
, &rptr
, &right
, &rbp
);
2652 /* Fill in the btree header for the new right block. */
2653 xfs_btree_init_block_cur(cur
, rbp
, xfs_btree_get_level(left
), 0);
2656 * Split the entries between the old and the new block evenly.
2657 * Make sure that if there's an odd number of entries now, that
2658 * each new block will have the same number of entries.
2660 lrecs
= xfs_btree_get_numrecs(left
);
2662 if ((lrecs
& 1) && cur
->bc_ptrs
[level
] <= rrecs
+ 1)
2664 src_index
= (lrecs
- rrecs
+ 1);
2666 XFS_BTREE_STATS_ADD(cur
, moves
, rrecs
);
2668 /* Adjust numrecs for the later get_*_keys() calls. */
2670 xfs_btree_set_numrecs(left
, lrecs
);
2671 xfs_btree_set_numrecs(right
, xfs_btree_get_numrecs(right
) + rrecs
);
2674 * Copy btree block entries from the left block over to the
2675 * new block, the right. Update the right block and log the
2679 /* It's a non-leaf. Move keys and pointers. */
2680 union xfs_btree_key
*lkp
; /* left btree key */
2681 union xfs_btree_ptr
*lpp
; /* left address pointer */
2682 union xfs_btree_key
*rkp
; /* right btree key */
2683 union xfs_btree_ptr
*rpp
; /* right address pointer */
2685 lkp
= xfs_btree_key_addr(cur
, src_index
, left
);
2686 lpp
= xfs_btree_ptr_addr(cur
, src_index
, left
);
2687 rkp
= xfs_btree_key_addr(cur
, 1, right
);
2688 rpp
= xfs_btree_ptr_addr(cur
, 1, right
);
2690 for (i
= src_index
; i
< rrecs
; i
++) {
2691 error
= xfs_btree_debug_check_ptr(cur
, lpp
, i
, level
);
2696 /* Copy the keys & pointers to the new block. */
2697 xfs_btree_copy_keys(cur
, rkp
, lkp
, rrecs
);
2698 xfs_btree_copy_ptrs(cur
, rpp
, lpp
, rrecs
);
2700 xfs_btree_log_keys(cur
, rbp
, 1, rrecs
);
2701 xfs_btree_log_ptrs(cur
, rbp
, 1, rrecs
);
2703 /* Stash the keys of the new block for later insertion. */
2704 xfs_btree_get_node_keys(cur
, right
, key
);
2706 /* It's a leaf. Move records. */
2707 union xfs_btree_rec
*lrp
; /* left record pointer */
2708 union xfs_btree_rec
*rrp
; /* right record pointer */
2710 lrp
= xfs_btree_rec_addr(cur
, src_index
, left
);
2711 rrp
= xfs_btree_rec_addr(cur
, 1, right
);
2713 /* Copy records to the new block. */
2714 xfs_btree_copy_recs(cur
, rrp
, lrp
, rrecs
);
2715 xfs_btree_log_recs(cur
, rbp
, 1, rrecs
);
2717 /* Stash the keys of the new block for later insertion. */
2718 xfs_btree_get_leaf_keys(cur
, right
, key
);
2722 * Find the left block number by looking in the buffer.
2723 * Adjust sibling pointers.
2725 xfs_btree_get_sibling(cur
, left
, &rrptr
, XFS_BB_RIGHTSIB
);
2726 xfs_btree_set_sibling(cur
, right
, &rrptr
, XFS_BB_RIGHTSIB
);
2727 xfs_btree_set_sibling(cur
, right
, &lptr
, XFS_BB_LEFTSIB
);
2728 xfs_btree_set_sibling(cur
, left
, &rptr
, XFS_BB_RIGHTSIB
);
2730 xfs_btree_log_block(cur
, rbp
, XFS_BB_ALL_BITS
);
2731 xfs_btree_log_block(cur
, lbp
, XFS_BB_NUMRECS
| XFS_BB_RIGHTSIB
);
2734 * If there's a block to the new block's right, make that block
2735 * point back to right instead of to left.
2737 if (!xfs_btree_ptr_is_null(cur
, &rrptr
)) {
2738 error
= xfs_btree_read_buf_block(cur
, &rrptr
,
2739 0, &rrblock
, &rrbp
);
2742 xfs_btree_set_sibling(cur
, rrblock
, &rptr
, XFS_BB_LEFTSIB
);
2743 xfs_btree_log_block(cur
, rrbp
, XFS_BB_LEFTSIB
);
2746 /* Update the parent high keys of the left block, if needed. */
2747 if (cur
->bc_flags
& XFS_BTREE_OVERLAPPING
) {
2748 error
= xfs_btree_update_keys(cur
, level
);
2754 * If the cursor is really in the right block, move it there.
2755 * If it's just pointing past the last entry in left, then we'll
2756 * insert there, so don't change anything in that case.
2758 if (cur
->bc_ptrs
[level
] > lrecs
+ 1) {
2759 xfs_btree_setbuf(cur
, level
, rbp
);
2760 cur
->bc_ptrs
[level
] -= lrecs
;
2763 * If there are more levels, we'll need another cursor which refers
2764 * the right block, no matter where this cursor was.
2766 if (level
+ 1 < cur
->bc_nlevels
) {
2767 error
= xfs_btree_dup_cursor(cur
, curp
);
2770 (*curp
)->bc_ptrs
[level
+ 1]++;
2784 struct xfs_btree_split_args
{
2785 struct xfs_btree_cur
*cur
;
2787 union xfs_btree_ptr
*ptrp
;
2788 union xfs_btree_key
*key
;
2789 struct xfs_btree_cur
**curp
;
2790 int *stat
; /* success/failure */
2792 bool kswapd
; /* allocation in kswapd context */
2793 struct completion
*done
;
2794 struct work_struct work
;
2798 * Stack switching interfaces for allocation
2801 xfs_btree_split_worker(
2802 struct work_struct
*work
)
2804 struct xfs_btree_split_args
*args
= container_of(work
,
2805 struct xfs_btree_split_args
, work
);
2806 unsigned long pflags
;
2807 unsigned long new_pflags
= 0;
2810 * we are in a transaction context here, but may also be doing work
2811 * in kswapd context, and hence we may need to inherit that state
2812 * temporarily to ensure that we don't block waiting for memory reclaim
2816 new_pflags
|= PF_MEMALLOC
| PF_SWAPWRITE
| PF_KSWAPD
;
2818 current_set_flags_nested(&pflags
, new_pflags
);
2819 xfs_trans_set_context(args
->cur
->bc_tp
);
2821 args
->result
= __xfs_btree_split(args
->cur
, args
->level
, args
->ptrp
,
2822 args
->key
, args
->curp
, args
->stat
);
2824 xfs_trans_clear_context(args
->cur
->bc_tp
);
2825 current_restore_flags_nested(&pflags
, new_pflags
);
2828 * Do not access args after complete() has run here. We don't own args
2829 * and the owner may run and free args before we return here.
2831 complete(args
->done
);
2836 * BMBT split requests often come in with little stack to work on. Push
2837 * them off to a worker thread so there is lots of stack to use. For the other
2838 * btree types, just call directly to avoid the context switch overhead here.
2840 STATIC
int /* error */
2842 struct xfs_btree_cur
*cur
,
2844 union xfs_btree_ptr
*ptrp
,
2845 union xfs_btree_key
*key
,
2846 struct xfs_btree_cur
**curp
,
2847 int *stat
) /* success/failure */
2849 struct xfs_btree_split_args args
;
2850 DECLARE_COMPLETION_ONSTACK(done
);
2852 if (cur
->bc_btnum
!= XFS_BTNUM_BMAP
)
2853 return __xfs_btree_split(cur
, level
, ptrp
, key
, curp
, stat
);
2862 args
.kswapd
= current_is_kswapd();
2863 INIT_WORK_ONSTACK(&args
.work
, xfs_btree_split_worker
);
2864 queue_work(xfs_alloc_wq
, &args
.work
);
2865 wait_for_completion(&done
);
2866 destroy_work_on_stack(&args
.work
);
2870 #define xfs_btree_split __xfs_btree_split
2875 * Copy the old inode root contents into a real block and make the
2876 * broot point to it.
2879 xfs_btree_new_iroot(
2880 struct xfs_btree_cur
*cur
, /* btree cursor */
2881 int *logflags
, /* logging flags for inode */
2882 int *stat
) /* return status - 0 fail */
2884 struct xfs_buf
*cbp
; /* buffer for cblock */
2885 struct xfs_btree_block
*block
; /* btree block */
2886 struct xfs_btree_block
*cblock
; /* child btree block */
2887 union xfs_btree_key
*ckp
; /* child key pointer */
2888 union xfs_btree_ptr
*cpp
; /* child ptr pointer */
2889 union xfs_btree_key
*kp
; /* pointer to btree key */
2890 union xfs_btree_ptr
*pp
; /* pointer to block addr */
2891 union xfs_btree_ptr nptr
; /* new block addr */
2892 int level
; /* btree level */
2893 int error
; /* error return code */
2894 int i
; /* loop counter */
2896 XFS_BTREE_STATS_INC(cur
, newroot
);
2898 ASSERT(cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
);
2900 level
= cur
->bc_nlevels
- 1;
2902 block
= xfs_btree_get_iroot(cur
);
2903 pp
= xfs_btree_ptr_addr(cur
, 1, block
);
2905 /* Allocate the new block. If we can't do it, we're toast. Give up. */
2906 error
= cur
->bc_ops
->alloc_block(cur
, pp
, &nptr
, stat
);
2912 XFS_BTREE_STATS_INC(cur
, alloc
);
2914 /* Copy the root into a real block. */
2915 error
= xfs_btree_get_buf_block(cur
, &nptr
, &cblock
, &cbp
);
2920 * we can't just memcpy() the root in for CRC enabled btree blocks.
2921 * In that case have to also ensure the blkno remains correct
2923 memcpy(cblock
, block
, xfs_btree_block_len(cur
));
2924 if (cur
->bc_flags
& XFS_BTREE_CRC_BLOCKS
) {
2925 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
)
2926 cblock
->bb_u
.l
.bb_blkno
= cpu_to_be64(cbp
->b_bn
);
2928 cblock
->bb_u
.s
.bb_blkno
= cpu_to_be64(cbp
->b_bn
);
2931 be16_add_cpu(&block
->bb_level
, 1);
2932 xfs_btree_set_numrecs(block
, 1);
2934 cur
->bc_ptrs
[level
+ 1] = 1;
2936 kp
= xfs_btree_key_addr(cur
, 1, block
);
2937 ckp
= xfs_btree_key_addr(cur
, 1, cblock
);
2938 xfs_btree_copy_keys(cur
, ckp
, kp
, xfs_btree_get_numrecs(cblock
));
2940 cpp
= xfs_btree_ptr_addr(cur
, 1, cblock
);
2941 for (i
= 0; i
< be16_to_cpu(cblock
->bb_numrecs
); i
++) {
2942 error
= xfs_btree_debug_check_ptr(cur
, pp
, i
, level
);
2947 xfs_btree_copy_ptrs(cur
, cpp
, pp
, xfs_btree_get_numrecs(cblock
));
2949 error
= xfs_btree_debug_check_ptr(cur
, &nptr
, 0, level
);
2953 xfs_btree_copy_ptrs(cur
, pp
, &nptr
, 1);
2955 xfs_iroot_realloc(cur
->bc_ino
.ip
,
2956 1 - xfs_btree_get_numrecs(cblock
),
2957 cur
->bc_ino
.whichfork
);
2959 xfs_btree_setbuf(cur
, level
, cbp
);
2962 * Do all this logging at the end so that
2963 * the root is at the right level.
2965 xfs_btree_log_block(cur
, cbp
, XFS_BB_ALL_BITS
);
2966 xfs_btree_log_keys(cur
, cbp
, 1, be16_to_cpu(cblock
->bb_numrecs
));
2967 xfs_btree_log_ptrs(cur
, cbp
, 1, be16_to_cpu(cblock
->bb_numrecs
));
2970 XFS_ILOG_CORE
| xfs_ilog_fbroot(cur
->bc_ino
.whichfork
);
2978 * Allocate a new root block, fill it in.
2980 STATIC
int /* error */
2982 struct xfs_btree_cur
*cur
, /* btree cursor */
2983 int *stat
) /* success/failure */
2985 struct xfs_btree_block
*block
; /* one half of the old root block */
2986 struct xfs_buf
*bp
; /* buffer containing block */
2987 int error
; /* error return value */
2988 struct xfs_buf
*lbp
; /* left buffer pointer */
2989 struct xfs_btree_block
*left
; /* left btree block */
2990 struct xfs_buf
*nbp
; /* new (root) buffer */
2991 struct xfs_btree_block
*new; /* new (root) btree block */
2992 int nptr
; /* new value for key index, 1 or 2 */
2993 struct xfs_buf
*rbp
; /* right buffer pointer */
2994 struct xfs_btree_block
*right
; /* right btree block */
2995 union xfs_btree_ptr rptr
;
2996 union xfs_btree_ptr lptr
;
2998 XFS_BTREE_STATS_INC(cur
, newroot
);
3000 /* initialise our start point from the cursor */
3001 cur
->bc_ops
->init_ptr_from_cur(cur
, &rptr
);
3003 /* Allocate the new block. If we can't do it, we're toast. Give up. */
3004 error
= cur
->bc_ops
->alloc_block(cur
, &rptr
, &lptr
, stat
);
3009 XFS_BTREE_STATS_INC(cur
, alloc
);
3011 /* Set up the new block. */
3012 error
= xfs_btree_get_buf_block(cur
, &lptr
, &new, &nbp
);
3016 /* Set the root in the holding structure increasing the level by 1. */
3017 cur
->bc_ops
->set_root(cur
, &lptr
, 1);
3020 * At the previous root level there are now two blocks: the old root,
3021 * and the new block generated when it was split. We don't know which
3022 * one the cursor is pointing at, so we set up variables "left" and
3023 * "right" for each case.
3025 block
= xfs_btree_get_block(cur
, cur
->bc_nlevels
- 1, &bp
);
3028 error
= xfs_btree_check_block(cur
, block
, cur
->bc_nlevels
- 1, bp
);
3033 xfs_btree_get_sibling(cur
, block
, &rptr
, XFS_BB_RIGHTSIB
);
3034 if (!xfs_btree_ptr_is_null(cur
, &rptr
)) {
3035 /* Our block is left, pick up the right block. */
3037 xfs_btree_buf_to_ptr(cur
, lbp
, &lptr
);
3039 error
= xfs_btree_read_buf_block(cur
, &rptr
, 0, &right
, &rbp
);
3045 /* Our block is right, pick up the left block. */
3047 xfs_btree_buf_to_ptr(cur
, rbp
, &rptr
);
3049 xfs_btree_get_sibling(cur
, right
, &lptr
, XFS_BB_LEFTSIB
);
3050 error
= xfs_btree_read_buf_block(cur
, &lptr
, 0, &left
, &lbp
);
3057 /* Fill in the new block's btree header and log it. */
3058 xfs_btree_init_block_cur(cur
, nbp
, cur
->bc_nlevels
, 2);
3059 xfs_btree_log_block(cur
, nbp
, XFS_BB_ALL_BITS
);
3060 ASSERT(!xfs_btree_ptr_is_null(cur
, &lptr
) &&
3061 !xfs_btree_ptr_is_null(cur
, &rptr
));
3063 /* Fill in the key data in the new root. */
3064 if (xfs_btree_get_level(left
) > 0) {
3066 * Get the keys for the left block's keys and put them directly
3067 * in the parent block. Do the same for the right block.
3069 xfs_btree_get_node_keys(cur
, left
,
3070 xfs_btree_key_addr(cur
, 1, new));
3071 xfs_btree_get_node_keys(cur
, right
,
3072 xfs_btree_key_addr(cur
, 2, new));
3075 * Get the keys for the left block's records and put them
3076 * directly in the parent block. Do the same for the right
3079 xfs_btree_get_leaf_keys(cur
, left
,
3080 xfs_btree_key_addr(cur
, 1, new));
3081 xfs_btree_get_leaf_keys(cur
, right
,
3082 xfs_btree_key_addr(cur
, 2, new));
3084 xfs_btree_log_keys(cur
, nbp
, 1, 2);
3086 /* Fill in the pointer data in the new root. */
3087 xfs_btree_copy_ptrs(cur
,
3088 xfs_btree_ptr_addr(cur
, 1, new), &lptr
, 1);
3089 xfs_btree_copy_ptrs(cur
,
3090 xfs_btree_ptr_addr(cur
, 2, new), &rptr
, 1);
3091 xfs_btree_log_ptrs(cur
, nbp
, 1, 2);
3093 /* Fix up the cursor. */
3094 xfs_btree_setbuf(cur
, cur
->bc_nlevels
, nbp
);
3095 cur
->bc_ptrs
[cur
->bc_nlevels
] = nptr
;
3107 xfs_btree_make_block_unfull(
3108 struct xfs_btree_cur
*cur
, /* btree cursor */
3109 int level
, /* btree level */
3110 int numrecs
,/* # of recs in block */
3111 int *oindex
,/* old tree index */
3112 int *index
, /* new tree index */
3113 union xfs_btree_ptr
*nptr
, /* new btree ptr */
3114 struct xfs_btree_cur
**ncur
, /* new btree cursor */
3115 union xfs_btree_key
*key
, /* key of new block */
3120 if ((cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
) &&
3121 level
== cur
->bc_nlevels
- 1) {
3122 struct xfs_inode
*ip
= cur
->bc_ino
.ip
;
3124 if (numrecs
< cur
->bc_ops
->get_dmaxrecs(cur
, level
)) {
3125 /* A root block that can be made bigger. */
3126 xfs_iroot_realloc(ip
, 1, cur
->bc_ino
.whichfork
);
3129 /* A root block that needs replacing */
3132 error
= xfs_btree_new_iroot(cur
, &logflags
, stat
);
3133 if (error
|| *stat
== 0)
3136 xfs_trans_log_inode(cur
->bc_tp
, ip
, logflags
);
3142 /* First, try shifting an entry to the right neighbor. */
3143 error
= xfs_btree_rshift(cur
, level
, stat
);
3147 /* Next, try shifting an entry to the left neighbor. */
3148 error
= xfs_btree_lshift(cur
, level
, stat
);
3153 *oindex
= *index
= cur
->bc_ptrs
[level
];
3158 * Next, try splitting the current block in half.
3160 * If this works we have to re-set our variables because we
3161 * could be in a different block now.
3163 error
= xfs_btree_split(cur
, level
, nptr
, key
, ncur
, stat
);
3164 if (error
|| *stat
== 0)
3168 *index
= cur
->bc_ptrs
[level
];
3173 * Insert one record/level. Return information to the caller
3174 * allowing the next level up to proceed if necessary.
3178 struct xfs_btree_cur
*cur
, /* btree cursor */
3179 int level
, /* level to insert record at */
3180 union xfs_btree_ptr
*ptrp
, /* i/o: block number inserted */
3181 union xfs_btree_rec
*rec
, /* record to insert */
3182 union xfs_btree_key
*key
, /* i/o: block key for ptrp */
3183 struct xfs_btree_cur
**curp
, /* output: new cursor replacing cur */
3184 int *stat
) /* success/failure */
3186 struct xfs_btree_block
*block
; /* btree block */
3187 struct xfs_buf
*bp
; /* buffer for block */
3188 union xfs_btree_ptr nptr
; /* new block ptr */
3189 struct xfs_btree_cur
*ncur
; /* new btree cursor */
3190 union xfs_btree_key nkey
; /* new block key */
3191 union xfs_btree_key
*lkey
;
3192 int optr
; /* old key/record index */
3193 int ptr
; /* key/record index */
3194 int numrecs
;/* number of records */
3195 int error
; /* error return value */
3203 * If we have an external root pointer, and we've made it to the
3204 * root level, allocate a new root block and we're done.
3206 if (!(cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
) &&
3207 (level
>= cur
->bc_nlevels
)) {
3208 error
= xfs_btree_new_root(cur
, stat
);
3209 xfs_btree_set_ptr_null(cur
, ptrp
);
3214 /* If we're off the left edge, return failure. */
3215 ptr
= cur
->bc_ptrs
[level
];
3223 XFS_BTREE_STATS_INC(cur
, insrec
);
3225 /* Get pointers to the btree buffer and block. */
3226 block
= xfs_btree_get_block(cur
, level
, &bp
);
3227 old_bn
= bp
? bp
->b_bn
: XFS_BUF_DADDR_NULL
;
3228 numrecs
= xfs_btree_get_numrecs(block
);
3231 error
= xfs_btree_check_block(cur
, block
, level
, bp
);
3235 /* Check that the new entry is being inserted in the right place. */
3236 if (ptr
<= numrecs
) {
3238 ASSERT(cur
->bc_ops
->recs_inorder(cur
, rec
,
3239 xfs_btree_rec_addr(cur
, ptr
, block
)));
3241 ASSERT(cur
->bc_ops
->keys_inorder(cur
, key
,
3242 xfs_btree_key_addr(cur
, ptr
, block
)));
3248 * If the block is full, we can't insert the new entry until we
3249 * make the block un-full.
3251 xfs_btree_set_ptr_null(cur
, &nptr
);
3252 if (numrecs
== cur
->bc_ops
->get_maxrecs(cur
, level
)) {
3253 error
= xfs_btree_make_block_unfull(cur
, level
, numrecs
,
3254 &optr
, &ptr
, &nptr
, &ncur
, lkey
, stat
);
3255 if (error
|| *stat
== 0)
3260 * The current block may have changed if the block was
3261 * previously full and we have just made space in it.
3263 block
= xfs_btree_get_block(cur
, level
, &bp
);
3264 numrecs
= xfs_btree_get_numrecs(block
);
3267 error
= xfs_btree_check_block(cur
, block
, level
, bp
);
3273 * At this point we know there's room for our new entry in the block
3274 * we're pointing at.
3276 XFS_BTREE_STATS_ADD(cur
, moves
, numrecs
- ptr
+ 1);
3279 /* It's a nonleaf. make a hole in the keys and ptrs */
3280 union xfs_btree_key
*kp
;
3281 union xfs_btree_ptr
*pp
;
3283 kp
= xfs_btree_key_addr(cur
, ptr
, block
);
3284 pp
= xfs_btree_ptr_addr(cur
, ptr
, block
);
3286 for (i
= numrecs
- ptr
; i
>= 0; i
--) {
3287 error
= xfs_btree_debug_check_ptr(cur
, pp
, i
, level
);
3292 xfs_btree_shift_keys(cur
, kp
, 1, numrecs
- ptr
+ 1);
3293 xfs_btree_shift_ptrs(cur
, pp
, 1, numrecs
- ptr
+ 1);
3295 error
= xfs_btree_debug_check_ptr(cur
, ptrp
, 0, level
);
3299 /* Now put the new data in, bump numrecs and log it. */
3300 xfs_btree_copy_keys(cur
, kp
, key
, 1);
3301 xfs_btree_copy_ptrs(cur
, pp
, ptrp
, 1);
3303 xfs_btree_set_numrecs(block
, numrecs
);
3304 xfs_btree_log_ptrs(cur
, bp
, ptr
, numrecs
);
3305 xfs_btree_log_keys(cur
, bp
, ptr
, numrecs
);
3307 if (ptr
< numrecs
) {
3308 ASSERT(cur
->bc_ops
->keys_inorder(cur
, kp
,
3309 xfs_btree_key_addr(cur
, ptr
+ 1, block
)));
3313 /* It's a leaf. make a hole in the records */
3314 union xfs_btree_rec
*rp
;
3316 rp
= xfs_btree_rec_addr(cur
, ptr
, block
);
3318 xfs_btree_shift_recs(cur
, rp
, 1, numrecs
- ptr
+ 1);
3320 /* Now put the new data in, bump numrecs and log it. */
3321 xfs_btree_copy_recs(cur
, rp
, rec
, 1);
3322 xfs_btree_set_numrecs(block
, ++numrecs
);
3323 xfs_btree_log_recs(cur
, bp
, ptr
, numrecs
);
3325 if (ptr
< numrecs
) {
3326 ASSERT(cur
->bc_ops
->recs_inorder(cur
, rp
,
3327 xfs_btree_rec_addr(cur
, ptr
+ 1, block
)));
3332 /* Log the new number of records in the btree header. */
3333 xfs_btree_log_block(cur
, bp
, XFS_BB_NUMRECS
);
3336 * If we just inserted into a new tree block, we have to
3337 * recalculate nkey here because nkey is out of date.
3339 * Otherwise we're just updating an existing block (having shoved
3340 * some records into the new tree block), so use the regular key
3343 if (bp
&& bp
->b_bn
!= old_bn
) {
3344 xfs_btree_get_keys(cur
, block
, lkey
);
3345 } else if (xfs_btree_needs_key_update(cur
, optr
)) {
3346 error
= xfs_btree_update_keys(cur
, level
);
3352 * If we are tracking the last record in the tree and
3353 * we are at the far right edge of the tree, update it.
3355 if (xfs_btree_is_lastrec(cur
, block
, level
)) {
3356 cur
->bc_ops
->update_lastrec(cur
, block
, rec
,
3357 ptr
, LASTREC_INSREC
);
3361 * Return the new block number, if any.
3362 * If there is one, give back a record value and a cursor too.
3365 if (!xfs_btree_ptr_is_null(cur
, &nptr
)) {
3366 xfs_btree_copy_keys(cur
, key
, lkey
, 1);
3378 * Insert the record at the point referenced by cur.
3380 * A multi-level split of the tree on insert will invalidate the original
3381 * cursor. All callers of this function should assume that the cursor is
3382 * no longer valid and revalidate it.
3386 struct xfs_btree_cur
*cur
,
3389 int error
; /* error return value */
3390 int i
; /* result value, 0 for failure */
3391 int level
; /* current level number in btree */
3392 union xfs_btree_ptr nptr
; /* new block number (split result) */
3393 struct xfs_btree_cur
*ncur
; /* new cursor (split result) */
3394 struct xfs_btree_cur
*pcur
; /* previous level's cursor */
3395 union xfs_btree_key bkey
; /* key of block to insert */
3396 union xfs_btree_key
*key
;
3397 union xfs_btree_rec rec
; /* record to insert */
3404 xfs_btree_set_ptr_null(cur
, &nptr
);
3406 /* Make a key out of the record data to be inserted, and save it. */
3407 cur
->bc_ops
->init_rec_from_cur(cur
, &rec
);
3408 cur
->bc_ops
->init_key_from_rec(key
, &rec
);
3411 * Loop going up the tree, starting at the leaf level.
3412 * Stop when we don't get a split block, that must mean that
3413 * the insert is finished with this level.
3417 * Insert nrec/nptr into this level of the tree.
3418 * Note if we fail, nptr will be null.
3420 error
= xfs_btree_insrec(pcur
, level
, &nptr
, &rec
, key
,
3424 xfs_btree_del_cursor(pcur
, XFS_BTREE_ERROR
);
3428 if (XFS_IS_CORRUPT(cur
->bc_mp
, i
!= 1)) {
3429 error
= -EFSCORRUPTED
;
3435 * See if the cursor we just used is trash.
3436 * Can't trash the caller's cursor, but otherwise we should
3437 * if ncur is a new cursor or we're about to be done.
3440 (ncur
|| xfs_btree_ptr_is_null(cur
, &nptr
))) {
3441 /* Save the state from the cursor before we trash it */
3442 if (cur
->bc_ops
->update_cursor
)
3443 cur
->bc_ops
->update_cursor(pcur
, cur
);
3444 cur
->bc_nlevels
= pcur
->bc_nlevels
;
3445 xfs_btree_del_cursor(pcur
, XFS_BTREE_NOERROR
);
3447 /* If we got a new cursor, switch to it. */
3452 } while (!xfs_btree_ptr_is_null(cur
, &nptr
));
3461 * Try to merge a non-leaf block back into the inode root.
3463 * Note: the killroot names comes from the fact that we're effectively
3464 * killing the old root block. But because we can't just delete the
3465 * inode we have to copy the single block it was pointing to into the
3469 xfs_btree_kill_iroot(
3470 struct xfs_btree_cur
*cur
)
3472 int whichfork
= cur
->bc_ino
.whichfork
;
3473 struct xfs_inode
*ip
= cur
->bc_ino
.ip
;
3474 struct xfs_ifork
*ifp
= XFS_IFORK_PTR(ip
, whichfork
);
3475 struct xfs_btree_block
*block
;
3476 struct xfs_btree_block
*cblock
;
3477 union xfs_btree_key
*kp
;
3478 union xfs_btree_key
*ckp
;
3479 union xfs_btree_ptr
*pp
;
3480 union xfs_btree_ptr
*cpp
;
3481 struct xfs_buf
*cbp
;
3487 union xfs_btree_ptr ptr
;
3491 ASSERT(cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
);
3492 ASSERT(cur
->bc_nlevels
> 1);
3495 * Don't deal with the root block needs to be a leaf case.
3496 * We're just going to turn the thing back into extents anyway.
3498 level
= cur
->bc_nlevels
- 1;
3503 * Give up if the root has multiple children.
3505 block
= xfs_btree_get_iroot(cur
);
3506 if (xfs_btree_get_numrecs(block
) != 1)
3509 cblock
= xfs_btree_get_block(cur
, level
- 1, &cbp
);
3510 numrecs
= xfs_btree_get_numrecs(cblock
);
3513 * Only do this if the next level will fit.
3514 * Then the data must be copied up to the inode,
3515 * instead of freeing the root you free the next level.
3517 if (numrecs
> cur
->bc_ops
->get_dmaxrecs(cur
, level
))
3520 XFS_BTREE_STATS_INC(cur
, killroot
);
3523 xfs_btree_get_sibling(cur
, block
, &ptr
, XFS_BB_LEFTSIB
);
3524 ASSERT(xfs_btree_ptr_is_null(cur
, &ptr
));
3525 xfs_btree_get_sibling(cur
, block
, &ptr
, XFS_BB_RIGHTSIB
);
3526 ASSERT(xfs_btree_ptr_is_null(cur
, &ptr
));
3529 index
= numrecs
- cur
->bc_ops
->get_maxrecs(cur
, level
);
3531 xfs_iroot_realloc(cur
->bc_ino
.ip
, index
,
3532 cur
->bc_ino
.whichfork
);
3533 block
= ifp
->if_broot
;
3536 be16_add_cpu(&block
->bb_numrecs
, index
);
3537 ASSERT(block
->bb_numrecs
== cblock
->bb_numrecs
);
3539 kp
= xfs_btree_key_addr(cur
, 1, block
);
3540 ckp
= xfs_btree_key_addr(cur
, 1, cblock
);
3541 xfs_btree_copy_keys(cur
, kp
, ckp
, numrecs
);
3543 pp
= xfs_btree_ptr_addr(cur
, 1, block
);
3544 cpp
= xfs_btree_ptr_addr(cur
, 1, cblock
);
3546 for (i
= 0; i
< numrecs
; i
++) {
3547 error
= xfs_btree_debug_check_ptr(cur
, cpp
, i
, level
- 1);
3552 xfs_btree_copy_ptrs(cur
, pp
, cpp
, numrecs
);
3554 error
= xfs_btree_free_block(cur
, cbp
);
3558 cur
->bc_bufs
[level
- 1] = NULL
;
3559 be16_add_cpu(&block
->bb_level
, -1);
3560 xfs_trans_log_inode(cur
->bc_tp
, ip
,
3561 XFS_ILOG_CORE
| xfs_ilog_fbroot(cur
->bc_ino
.whichfork
));
3568 * Kill the current root node, and replace it with it's only child node.
3571 xfs_btree_kill_root(
3572 struct xfs_btree_cur
*cur
,
3575 union xfs_btree_ptr
*newroot
)
3579 XFS_BTREE_STATS_INC(cur
, killroot
);
3582 * Update the root pointer, decreasing the level by 1 and then
3583 * free the old root.
3585 cur
->bc_ops
->set_root(cur
, newroot
, -1);
3587 error
= xfs_btree_free_block(cur
, bp
);
3591 cur
->bc_bufs
[level
] = NULL
;
3592 cur
->bc_ra
[level
] = 0;
3599 xfs_btree_dec_cursor(
3600 struct xfs_btree_cur
*cur
,
3608 error
= xfs_btree_decrement(cur
, level
, &i
);
3618 * Single level of the btree record deletion routine.
3619 * Delete record pointed to by cur/level.
3620 * Remove the record from its block then rebalance the tree.
3621 * Return 0 for error, 1 for done, 2 to go on to the next level.
3623 STATIC
int /* error */
3625 struct xfs_btree_cur
*cur
, /* btree cursor */
3626 int level
, /* level removing record from */
3627 int *stat
) /* fail/done/go-on */
3629 struct xfs_btree_block
*block
; /* btree block */
3630 union xfs_btree_ptr cptr
; /* current block ptr */
3631 struct xfs_buf
*bp
; /* buffer for block */
3632 int error
; /* error return value */
3633 int i
; /* loop counter */
3634 union xfs_btree_ptr lptr
; /* left sibling block ptr */
3635 struct xfs_buf
*lbp
; /* left buffer pointer */
3636 struct xfs_btree_block
*left
; /* left btree block */
3637 int lrecs
= 0; /* left record count */
3638 int ptr
; /* key/record index */
3639 union xfs_btree_ptr rptr
; /* right sibling block ptr */
3640 struct xfs_buf
*rbp
; /* right buffer pointer */
3641 struct xfs_btree_block
*right
; /* right btree block */
3642 struct xfs_btree_block
*rrblock
; /* right-right btree block */
3643 struct xfs_buf
*rrbp
; /* right-right buffer pointer */
3644 int rrecs
= 0; /* right record count */
3645 struct xfs_btree_cur
*tcur
; /* temporary btree cursor */
3646 int numrecs
; /* temporary numrec count */
3650 /* Get the index of the entry being deleted, check for nothing there. */
3651 ptr
= cur
->bc_ptrs
[level
];
3657 /* Get the buffer & block containing the record or key/ptr. */
3658 block
= xfs_btree_get_block(cur
, level
, &bp
);
3659 numrecs
= xfs_btree_get_numrecs(block
);
3662 error
= xfs_btree_check_block(cur
, block
, level
, bp
);
3667 /* Fail if we're off the end of the block. */
3668 if (ptr
> numrecs
) {
3673 XFS_BTREE_STATS_INC(cur
, delrec
);
3674 XFS_BTREE_STATS_ADD(cur
, moves
, numrecs
- ptr
);
3676 /* Excise the entries being deleted. */
3678 /* It's a nonleaf. operate on keys and ptrs */
3679 union xfs_btree_key
*lkp
;
3680 union xfs_btree_ptr
*lpp
;
3682 lkp
= xfs_btree_key_addr(cur
, ptr
+ 1, block
);
3683 lpp
= xfs_btree_ptr_addr(cur
, ptr
+ 1, block
);
3685 for (i
= 0; i
< numrecs
- ptr
; i
++) {
3686 error
= xfs_btree_debug_check_ptr(cur
, lpp
, i
, level
);
3691 if (ptr
< numrecs
) {
3692 xfs_btree_shift_keys(cur
, lkp
, -1, numrecs
- ptr
);
3693 xfs_btree_shift_ptrs(cur
, lpp
, -1, numrecs
- ptr
);
3694 xfs_btree_log_keys(cur
, bp
, ptr
, numrecs
- 1);
3695 xfs_btree_log_ptrs(cur
, bp
, ptr
, numrecs
- 1);
3698 /* It's a leaf. operate on records */
3699 if (ptr
< numrecs
) {
3700 xfs_btree_shift_recs(cur
,
3701 xfs_btree_rec_addr(cur
, ptr
+ 1, block
),
3703 xfs_btree_log_recs(cur
, bp
, ptr
, numrecs
- 1);
3708 * Decrement and log the number of entries in the block.
3710 xfs_btree_set_numrecs(block
, --numrecs
);
3711 xfs_btree_log_block(cur
, bp
, XFS_BB_NUMRECS
);
3714 * If we are tracking the last record in the tree and
3715 * we are at the far right edge of the tree, update it.
3717 if (xfs_btree_is_lastrec(cur
, block
, level
)) {
3718 cur
->bc_ops
->update_lastrec(cur
, block
, NULL
,
3719 ptr
, LASTREC_DELREC
);
3723 * We're at the root level. First, shrink the root block in-memory.
3724 * Try to get rid of the next level down. If we can't then there's
3725 * nothing left to do.
3727 if (level
== cur
->bc_nlevels
- 1) {
3728 if (cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
) {
3729 xfs_iroot_realloc(cur
->bc_ino
.ip
, -1,
3730 cur
->bc_ino
.whichfork
);
3732 error
= xfs_btree_kill_iroot(cur
);
3736 error
= xfs_btree_dec_cursor(cur
, level
, stat
);
3744 * If this is the root level, and there's only one entry left,
3745 * and it's NOT the leaf level, then we can get rid of this
3748 if (numrecs
== 1 && level
> 0) {
3749 union xfs_btree_ptr
*pp
;
3751 * pp is still set to the first pointer in the block.
3752 * Make it the new root of the btree.
3754 pp
= xfs_btree_ptr_addr(cur
, 1, block
);
3755 error
= xfs_btree_kill_root(cur
, bp
, level
, pp
);
3758 } else if (level
> 0) {
3759 error
= xfs_btree_dec_cursor(cur
, level
, stat
);
3768 * If we deleted the leftmost entry in the block, update the
3769 * key values above us in the tree.
3771 if (xfs_btree_needs_key_update(cur
, ptr
)) {
3772 error
= xfs_btree_update_keys(cur
, level
);
3778 * If the number of records remaining in the block is at least
3779 * the minimum, we're done.
3781 if (numrecs
>= cur
->bc_ops
->get_minrecs(cur
, level
)) {
3782 error
= xfs_btree_dec_cursor(cur
, level
, stat
);
3789 * Otherwise, we have to move some records around to keep the
3790 * tree balanced. Look at the left and right sibling blocks to
3791 * see if we can re-balance by moving only one record.
3793 xfs_btree_get_sibling(cur
, block
, &rptr
, XFS_BB_RIGHTSIB
);
3794 xfs_btree_get_sibling(cur
, block
, &lptr
, XFS_BB_LEFTSIB
);
3796 if (cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
) {
3798 * One child of root, need to get a chance to copy its contents
3799 * into the root and delete it. Can't go up to next level,
3800 * there's nothing to delete there.
3802 if (xfs_btree_ptr_is_null(cur
, &rptr
) &&
3803 xfs_btree_ptr_is_null(cur
, &lptr
) &&
3804 level
== cur
->bc_nlevels
- 2) {
3805 error
= xfs_btree_kill_iroot(cur
);
3807 error
= xfs_btree_dec_cursor(cur
, level
, stat
);
3814 ASSERT(!xfs_btree_ptr_is_null(cur
, &rptr
) ||
3815 !xfs_btree_ptr_is_null(cur
, &lptr
));
3818 * Duplicate the cursor so our btree manipulations here won't
3819 * disrupt the next level up.
3821 error
= xfs_btree_dup_cursor(cur
, &tcur
);
3826 * If there's a right sibling, see if it's ok to shift an entry
3829 if (!xfs_btree_ptr_is_null(cur
, &rptr
)) {
3831 * Move the temp cursor to the last entry in the next block.
3832 * Actually any entry but the first would suffice.
3834 i
= xfs_btree_lastrec(tcur
, level
);
3835 if (XFS_IS_CORRUPT(cur
->bc_mp
, i
!= 1)) {
3836 error
= -EFSCORRUPTED
;
3840 error
= xfs_btree_increment(tcur
, level
, &i
);
3843 if (XFS_IS_CORRUPT(cur
->bc_mp
, i
!= 1)) {
3844 error
= -EFSCORRUPTED
;
3848 i
= xfs_btree_lastrec(tcur
, level
);
3849 if (XFS_IS_CORRUPT(cur
->bc_mp
, i
!= 1)) {
3850 error
= -EFSCORRUPTED
;
3854 /* Grab a pointer to the block. */
3855 right
= xfs_btree_get_block(tcur
, level
, &rbp
);
3857 error
= xfs_btree_check_block(tcur
, right
, level
, rbp
);
3861 /* Grab the current block number, for future use. */
3862 xfs_btree_get_sibling(tcur
, right
, &cptr
, XFS_BB_LEFTSIB
);
3865 * If right block is full enough so that removing one entry
3866 * won't make it too empty, and left-shifting an entry out
3867 * of right to us works, we're done.
3869 if (xfs_btree_get_numrecs(right
) - 1 >=
3870 cur
->bc_ops
->get_minrecs(tcur
, level
)) {
3871 error
= xfs_btree_lshift(tcur
, level
, &i
);
3875 ASSERT(xfs_btree_get_numrecs(block
) >=
3876 cur
->bc_ops
->get_minrecs(tcur
, level
));
3878 xfs_btree_del_cursor(tcur
, XFS_BTREE_NOERROR
);
3881 error
= xfs_btree_dec_cursor(cur
, level
, stat
);
3889 * Otherwise, grab the number of records in right for
3890 * future reference, and fix up the temp cursor to point
3891 * to our block again (last record).
3893 rrecs
= xfs_btree_get_numrecs(right
);
3894 if (!xfs_btree_ptr_is_null(cur
, &lptr
)) {
3895 i
= xfs_btree_firstrec(tcur
, level
);
3896 if (XFS_IS_CORRUPT(cur
->bc_mp
, i
!= 1)) {
3897 error
= -EFSCORRUPTED
;
3901 error
= xfs_btree_decrement(tcur
, level
, &i
);
3904 if (XFS_IS_CORRUPT(cur
->bc_mp
, i
!= 1)) {
3905 error
= -EFSCORRUPTED
;
3912 * If there's a left sibling, see if it's ok to shift an entry
3915 if (!xfs_btree_ptr_is_null(cur
, &lptr
)) {
3917 * Move the temp cursor to the first entry in the
3920 i
= xfs_btree_firstrec(tcur
, level
);
3921 if (XFS_IS_CORRUPT(cur
->bc_mp
, i
!= 1)) {
3922 error
= -EFSCORRUPTED
;
3926 error
= xfs_btree_decrement(tcur
, level
, &i
);
3929 i
= xfs_btree_firstrec(tcur
, level
);
3930 if (XFS_IS_CORRUPT(cur
->bc_mp
, i
!= 1)) {
3931 error
= -EFSCORRUPTED
;
3935 /* Grab a pointer to the block. */
3936 left
= xfs_btree_get_block(tcur
, level
, &lbp
);
3938 error
= xfs_btree_check_block(cur
, left
, level
, lbp
);
3942 /* Grab the current block number, for future use. */
3943 xfs_btree_get_sibling(tcur
, left
, &cptr
, XFS_BB_RIGHTSIB
);
3946 * If left block is full enough so that removing one entry
3947 * won't make it too empty, and right-shifting an entry out
3948 * of left to us works, we're done.
3950 if (xfs_btree_get_numrecs(left
) - 1 >=
3951 cur
->bc_ops
->get_minrecs(tcur
, level
)) {
3952 error
= xfs_btree_rshift(tcur
, level
, &i
);
3956 ASSERT(xfs_btree_get_numrecs(block
) >=
3957 cur
->bc_ops
->get_minrecs(tcur
, level
));
3958 xfs_btree_del_cursor(tcur
, XFS_BTREE_NOERROR
);
3969 * Otherwise, grab the number of records in right for
3972 lrecs
= xfs_btree_get_numrecs(left
);
3975 /* Delete the temp cursor, we're done with it. */
3976 xfs_btree_del_cursor(tcur
, XFS_BTREE_NOERROR
);
3979 /* If here, we need to do a join to keep the tree balanced. */
3980 ASSERT(!xfs_btree_ptr_is_null(cur
, &cptr
));
3982 if (!xfs_btree_ptr_is_null(cur
, &lptr
) &&
3983 lrecs
+ xfs_btree_get_numrecs(block
) <=
3984 cur
->bc_ops
->get_maxrecs(cur
, level
)) {
3986 * Set "right" to be the starting block,
3987 * "left" to be the left neighbor.
3992 error
= xfs_btree_read_buf_block(cur
, &lptr
, 0, &left
, &lbp
);
3997 * If that won't work, see if we can join with the right neighbor block.
3999 } else if (!xfs_btree_ptr_is_null(cur
, &rptr
) &&
4000 rrecs
+ xfs_btree_get_numrecs(block
) <=
4001 cur
->bc_ops
->get_maxrecs(cur
, level
)) {
4003 * Set "left" to be the starting block,
4004 * "right" to be the right neighbor.
4009 error
= xfs_btree_read_buf_block(cur
, &rptr
, 0, &right
, &rbp
);
4014 * Otherwise, we can't fix the imbalance.
4015 * Just return. This is probably a logic error, but it's not fatal.
4018 error
= xfs_btree_dec_cursor(cur
, level
, stat
);
4024 rrecs
= xfs_btree_get_numrecs(right
);
4025 lrecs
= xfs_btree_get_numrecs(left
);
4028 * We're now going to join "left" and "right" by moving all the stuff
4029 * in "right" to "left" and deleting "right".
4031 XFS_BTREE_STATS_ADD(cur
, moves
, rrecs
);
4033 /* It's a non-leaf. Move keys and pointers. */
4034 union xfs_btree_key
*lkp
; /* left btree key */
4035 union xfs_btree_ptr
*lpp
; /* left address pointer */
4036 union xfs_btree_key
*rkp
; /* right btree key */
4037 union xfs_btree_ptr
*rpp
; /* right address pointer */
4039 lkp
= xfs_btree_key_addr(cur
, lrecs
+ 1, left
);
4040 lpp
= xfs_btree_ptr_addr(cur
, lrecs
+ 1, left
);
4041 rkp
= xfs_btree_key_addr(cur
, 1, right
);
4042 rpp
= xfs_btree_ptr_addr(cur
, 1, right
);
4044 for (i
= 1; i
< rrecs
; i
++) {
4045 error
= xfs_btree_debug_check_ptr(cur
, rpp
, i
, level
);
4050 xfs_btree_copy_keys(cur
, lkp
, rkp
, rrecs
);
4051 xfs_btree_copy_ptrs(cur
, lpp
, rpp
, rrecs
);
4053 xfs_btree_log_keys(cur
, lbp
, lrecs
+ 1, lrecs
+ rrecs
);
4054 xfs_btree_log_ptrs(cur
, lbp
, lrecs
+ 1, lrecs
+ rrecs
);
4056 /* It's a leaf. Move records. */
4057 union xfs_btree_rec
*lrp
; /* left record pointer */
4058 union xfs_btree_rec
*rrp
; /* right record pointer */
4060 lrp
= xfs_btree_rec_addr(cur
, lrecs
+ 1, left
);
4061 rrp
= xfs_btree_rec_addr(cur
, 1, right
);
4063 xfs_btree_copy_recs(cur
, lrp
, rrp
, rrecs
);
4064 xfs_btree_log_recs(cur
, lbp
, lrecs
+ 1, lrecs
+ rrecs
);
4067 XFS_BTREE_STATS_INC(cur
, join
);
4070 * Fix up the number of records and right block pointer in the
4071 * surviving block, and log it.
4073 xfs_btree_set_numrecs(left
, lrecs
+ rrecs
);
4074 xfs_btree_get_sibling(cur
, right
, &cptr
, XFS_BB_RIGHTSIB
);
4075 xfs_btree_set_sibling(cur
, left
, &cptr
, XFS_BB_RIGHTSIB
);
4076 xfs_btree_log_block(cur
, lbp
, XFS_BB_NUMRECS
| XFS_BB_RIGHTSIB
);
4078 /* If there is a right sibling, point it to the remaining block. */
4079 xfs_btree_get_sibling(cur
, left
, &cptr
, XFS_BB_RIGHTSIB
);
4080 if (!xfs_btree_ptr_is_null(cur
, &cptr
)) {
4081 error
= xfs_btree_read_buf_block(cur
, &cptr
, 0, &rrblock
, &rrbp
);
4084 xfs_btree_set_sibling(cur
, rrblock
, &lptr
, XFS_BB_LEFTSIB
);
4085 xfs_btree_log_block(cur
, rrbp
, XFS_BB_LEFTSIB
);
4088 /* Free the deleted block. */
4089 error
= xfs_btree_free_block(cur
, rbp
);
4094 * If we joined with the left neighbor, set the buffer in the
4095 * cursor to the left block, and fix up the index.
4098 cur
->bc_bufs
[level
] = lbp
;
4099 cur
->bc_ptrs
[level
] += lrecs
;
4100 cur
->bc_ra
[level
] = 0;
4103 * If we joined with the right neighbor and there's a level above
4104 * us, increment the cursor at that level.
4106 else if ((cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
) ||
4107 (level
+ 1 < cur
->bc_nlevels
)) {
4108 error
= xfs_btree_increment(cur
, level
+ 1, &i
);
4114 * Readjust the ptr at this level if it's not a leaf, since it's
4115 * still pointing at the deletion point, which makes the cursor
4116 * inconsistent. If this makes the ptr 0, the caller fixes it up.
4117 * We can't use decrement because it would change the next level up.
4120 cur
->bc_ptrs
[level
]--;
4123 * We combined blocks, so we have to update the parent keys if the
4124 * btree supports overlapped intervals. However, bc_ptrs[level + 1]
4125 * points to the old block so that the caller knows which record to
4126 * delete. Therefore, the caller must be savvy enough to call updkeys
4127 * for us if we return stat == 2. The other exit points from this
4128 * function don't require deletions further up the tree, so they can
4129 * call updkeys directly.
4132 /* Return value means the next level up has something to do. */
4138 xfs_btree_del_cursor(tcur
, XFS_BTREE_ERROR
);
4143 * Delete the record pointed to by cur.
4144 * The cursor refers to the place where the record was (could be inserted)
4145 * when the operation returns.
4149 struct xfs_btree_cur
*cur
,
4150 int *stat
) /* success/failure */
4152 int error
; /* error return value */
4155 bool joined
= false;
4158 * Go up the tree, starting at leaf level.
4160 * If 2 is returned then a join was done; go to the next level.
4161 * Otherwise we are done.
4163 for (level
= 0, i
= 2; i
== 2; level
++) {
4164 error
= xfs_btree_delrec(cur
, level
, &i
);
4172 * If we combined blocks as part of deleting the record, delrec won't
4173 * have updated the parent high keys so we have to do that here.
4175 if (joined
&& (cur
->bc_flags
& XFS_BTREE_OVERLAPPING
)) {
4176 error
= xfs_btree_updkeys_force(cur
, 0);
4182 for (level
= 1; level
< cur
->bc_nlevels
; level
++) {
4183 if (cur
->bc_ptrs
[level
] == 0) {
4184 error
= xfs_btree_decrement(cur
, level
, &i
);
4199 * Get the data from the pointed-to record.
4203 struct xfs_btree_cur
*cur
, /* btree cursor */
4204 union xfs_btree_rec
**recp
, /* output: btree record */
4205 int *stat
) /* output: success/failure */
4207 struct xfs_btree_block
*block
; /* btree block */
4208 struct xfs_buf
*bp
; /* buffer pointer */
4209 int ptr
; /* record number */
4211 int error
; /* error return value */
4214 ptr
= cur
->bc_ptrs
[0];
4215 block
= xfs_btree_get_block(cur
, 0, &bp
);
4218 error
= xfs_btree_check_block(cur
, block
, 0, bp
);
4224 * Off the right end or left end, return failure.
4226 if (ptr
> xfs_btree_get_numrecs(block
) || ptr
<= 0) {
4232 * Point to the record and extract its data.
4234 *recp
= xfs_btree_rec_addr(cur
, ptr
, block
);
4239 /* Visit a block in a btree. */
4241 xfs_btree_visit_block(
4242 struct xfs_btree_cur
*cur
,
4244 xfs_btree_visit_blocks_fn fn
,
4247 struct xfs_btree_block
*block
;
4249 union xfs_btree_ptr rptr
;
4252 /* do right sibling readahead */
4253 xfs_btree_readahead(cur
, level
, XFS_BTCUR_RIGHTRA
);
4254 block
= xfs_btree_get_block(cur
, level
, &bp
);
4256 /* process the block */
4257 error
= fn(cur
, level
, data
);
4261 /* now read rh sibling block for next iteration */
4262 xfs_btree_get_sibling(cur
, block
, &rptr
, XFS_BB_RIGHTSIB
);
4263 if (xfs_btree_ptr_is_null(cur
, &rptr
))
4266 return xfs_btree_lookup_get_block(cur
, level
, &rptr
, &block
);
4270 /* Visit every block in a btree. */
4272 xfs_btree_visit_blocks(
4273 struct xfs_btree_cur
*cur
,
4274 xfs_btree_visit_blocks_fn fn
,
4278 union xfs_btree_ptr lptr
;
4280 struct xfs_btree_block
*block
= NULL
;
4283 cur
->bc_ops
->init_ptr_from_cur(cur
, &lptr
);
4285 /* for each level */
4286 for (level
= cur
->bc_nlevels
- 1; level
>= 0; level
--) {
4287 /* grab the left hand block */
4288 error
= xfs_btree_lookup_get_block(cur
, level
, &lptr
, &block
);
4292 /* readahead the left most block for the next level down */
4294 union xfs_btree_ptr
*ptr
;
4296 ptr
= xfs_btree_ptr_addr(cur
, 1, block
);
4297 xfs_btree_readahead_ptr(cur
, ptr
, 1);
4299 /* save for the next iteration of the loop */
4300 xfs_btree_copy_ptrs(cur
, &lptr
, ptr
, 1);
4302 if (!(flags
& XFS_BTREE_VISIT_LEAVES
))
4304 } else if (!(flags
& XFS_BTREE_VISIT_RECORDS
)) {
4308 /* for each buffer in the level */
4310 error
= xfs_btree_visit_block(cur
, level
, fn
, data
);
4313 if (error
!= -ENOENT
)
4321 * Change the owner of a btree.
4323 * The mechanism we use here is ordered buffer logging. Because we don't know
4324 * how many buffers were are going to need to modify, we don't really want to
4325 * have to make transaction reservations for the worst case of every buffer in a
4326 * full size btree as that may be more space that we can fit in the log....
4328 * We do the btree walk in the most optimal manner possible - we have sibling
4329 * pointers so we can just walk all the blocks on each level from left to right
4330 * in a single pass, and then move to the next level and do the same. We can
4331 * also do readahead on the sibling pointers to get IO moving more quickly,
4332 * though for slow disks this is unlikely to make much difference to performance
4333 * as the amount of CPU work we have to do before moving to the next block is
4336 * For each btree block that we load, modify the owner appropriately, set the
4337 * buffer as an ordered buffer and log it appropriately. We need to ensure that
4338 * we mark the region we change dirty so that if the buffer is relogged in
4339 * a subsequent transaction the changes we make here as an ordered buffer are
4340 * correctly relogged in that transaction. If we are in recovery context, then
4341 * just queue the modified buffer as delayed write buffer so the transaction
4342 * recovery completion writes the changes to disk.
4344 struct xfs_btree_block_change_owner_info
{
4346 struct list_head
*buffer_list
;
4350 xfs_btree_block_change_owner(
4351 struct xfs_btree_cur
*cur
,
4355 struct xfs_btree_block_change_owner_info
*bbcoi
= data
;
4356 struct xfs_btree_block
*block
;
4359 /* modify the owner */
4360 block
= xfs_btree_get_block(cur
, level
, &bp
);
4361 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
) {
4362 if (block
->bb_u
.l
.bb_owner
== cpu_to_be64(bbcoi
->new_owner
))
4364 block
->bb_u
.l
.bb_owner
= cpu_to_be64(bbcoi
->new_owner
);
4366 if (block
->bb_u
.s
.bb_owner
== cpu_to_be32(bbcoi
->new_owner
))
4368 block
->bb_u
.s
.bb_owner
= cpu_to_be32(bbcoi
->new_owner
);
4372 * If the block is a root block hosted in an inode, we might not have a
4373 * buffer pointer here and we shouldn't attempt to log the change as the
4374 * information is already held in the inode and discarded when the root
4375 * block is formatted into the on-disk inode fork. We still change it,
4376 * though, so everything is consistent in memory.
4379 ASSERT(cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
);
4380 ASSERT(level
== cur
->bc_nlevels
- 1);
4385 if (!xfs_trans_ordered_buf(cur
->bc_tp
, bp
)) {
4386 xfs_btree_log_block(cur
, bp
, XFS_BB_OWNER
);
4390 xfs_buf_delwri_queue(bp
, bbcoi
->buffer_list
);
4397 xfs_btree_change_owner(
4398 struct xfs_btree_cur
*cur
,
4400 struct list_head
*buffer_list
)
4402 struct xfs_btree_block_change_owner_info bbcoi
;
4404 bbcoi
.new_owner
= new_owner
;
4405 bbcoi
.buffer_list
= buffer_list
;
4407 return xfs_btree_visit_blocks(cur
, xfs_btree_block_change_owner
,
4408 XFS_BTREE_VISIT_ALL
, &bbcoi
);
4411 /* Verify the v5 fields of a long-format btree block. */
4413 xfs_btree_lblock_v5hdr_verify(
4417 struct xfs_mount
*mp
= bp
->b_mount
;
4418 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
4420 if (!xfs_sb_version_hascrc(&mp
->m_sb
))
4421 return __this_address
;
4422 if (!uuid_equal(&block
->bb_u
.l
.bb_uuid
, &mp
->m_sb
.sb_meta_uuid
))
4423 return __this_address
;
4424 if (block
->bb_u
.l
.bb_blkno
!= cpu_to_be64(bp
->b_bn
))
4425 return __this_address
;
4426 if (owner
!= XFS_RMAP_OWN_UNKNOWN
&&
4427 be64_to_cpu(block
->bb_u
.l
.bb_owner
) != owner
)
4428 return __this_address
;
4432 /* Verify a long-format btree block. */
4434 xfs_btree_lblock_verify(
4436 unsigned int max_recs
)
4438 struct xfs_mount
*mp
= bp
->b_mount
;
4439 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
4441 /* numrecs verification */
4442 if (be16_to_cpu(block
->bb_numrecs
) > max_recs
)
4443 return __this_address
;
4445 /* sibling pointer verification */
4446 if (block
->bb_u
.l
.bb_leftsib
!= cpu_to_be64(NULLFSBLOCK
) &&
4447 !xfs_verify_fsbno(mp
, be64_to_cpu(block
->bb_u
.l
.bb_leftsib
)))
4448 return __this_address
;
4449 if (block
->bb_u
.l
.bb_rightsib
!= cpu_to_be64(NULLFSBLOCK
) &&
4450 !xfs_verify_fsbno(mp
, be64_to_cpu(block
->bb_u
.l
.bb_rightsib
)))
4451 return __this_address
;
4457 * xfs_btree_sblock_v5hdr_verify() -- verify the v5 fields of a short-format
4460 * @bp: buffer containing the btree block
4463 xfs_btree_sblock_v5hdr_verify(
4466 struct xfs_mount
*mp
= bp
->b_mount
;
4467 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
4468 struct xfs_perag
*pag
= bp
->b_pag
;
4470 if (!xfs_sb_version_hascrc(&mp
->m_sb
))
4471 return __this_address
;
4472 if (!uuid_equal(&block
->bb_u
.s
.bb_uuid
, &mp
->m_sb
.sb_meta_uuid
))
4473 return __this_address
;
4474 if (block
->bb_u
.s
.bb_blkno
!= cpu_to_be64(bp
->b_bn
))
4475 return __this_address
;
4476 if (pag
&& be32_to_cpu(block
->bb_u
.s
.bb_owner
) != pag
->pag_agno
)
4477 return __this_address
;
4482 * xfs_btree_sblock_verify() -- verify a short-format btree block
4484 * @bp: buffer containing the btree block
4485 * @max_recs: maximum records allowed in this btree node
4488 xfs_btree_sblock_verify(
4490 unsigned int max_recs
)
4492 struct xfs_mount
*mp
= bp
->b_mount
;
4493 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
4496 /* numrecs verification */
4497 if (be16_to_cpu(block
->bb_numrecs
) > max_recs
)
4498 return __this_address
;
4500 /* sibling pointer verification */
4501 agno
= xfs_daddr_to_agno(mp
, XFS_BUF_ADDR(bp
));
4502 if (block
->bb_u
.s
.bb_leftsib
!= cpu_to_be32(NULLAGBLOCK
) &&
4503 !xfs_verify_agbno(mp
, agno
, be32_to_cpu(block
->bb_u
.s
.bb_leftsib
)))
4504 return __this_address
;
4505 if (block
->bb_u
.s
.bb_rightsib
!= cpu_to_be32(NULLAGBLOCK
) &&
4506 !xfs_verify_agbno(mp
, agno
, be32_to_cpu(block
->bb_u
.s
.bb_rightsib
)))
4507 return __this_address
;
4513 * Calculate the number of btree levels needed to store a given number of
4514 * records in a short-format btree.
4517 xfs_btree_compute_maxlevels(
4522 unsigned long maxblocks
;
4524 maxblocks
= (len
+ limits
[0] - 1) / limits
[0];
4525 for (level
= 1; maxblocks
> 1; level
++)
4526 maxblocks
= (maxblocks
+ limits
[1] - 1) / limits
[1];
4531 * Query a regular btree for all records overlapping a given interval.
4532 * Start with a LE lookup of the key of low_rec and return all records
4533 * until we find a record with a key greater than the key of high_rec.
4536 xfs_btree_simple_query_range(
4537 struct xfs_btree_cur
*cur
,
4538 union xfs_btree_key
*low_key
,
4539 union xfs_btree_key
*high_key
,
4540 xfs_btree_query_range_fn fn
,
4543 union xfs_btree_rec
*recp
;
4544 union xfs_btree_key rec_key
;
4547 bool firstrec
= true;
4550 ASSERT(cur
->bc_ops
->init_high_key_from_rec
);
4551 ASSERT(cur
->bc_ops
->diff_two_keys
);
4554 * Find the leftmost record. The btree cursor must be set
4555 * to the low record used to generate low_key.
4558 error
= xfs_btree_lookup(cur
, XFS_LOOKUP_LE
, &stat
);
4562 /* Nothing? See if there's anything to the right. */
4564 error
= xfs_btree_increment(cur
, 0, &stat
);
4570 /* Find the record. */
4571 error
= xfs_btree_get_rec(cur
, &recp
, &stat
);
4575 /* Skip if high_key(rec) < low_key. */
4577 cur
->bc_ops
->init_high_key_from_rec(&rec_key
, recp
);
4579 diff
= cur
->bc_ops
->diff_two_keys(cur
, low_key
,
4585 /* Stop if high_key < low_key(rec). */
4586 cur
->bc_ops
->init_key_from_rec(&rec_key
, recp
);
4587 diff
= cur
->bc_ops
->diff_two_keys(cur
, &rec_key
, high_key
);
4592 error
= fn(cur
, recp
, priv
);
4597 /* Move on to the next record. */
4598 error
= xfs_btree_increment(cur
, 0, &stat
);
4608 * Query an overlapped interval btree for all records overlapping a given
4609 * interval. This function roughly follows the algorithm given in
4610 * "Interval Trees" of _Introduction to Algorithms_, which is section
4611 * 14.3 in the 2nd and 3rd editions.
4613 * First, generate keys for the low and high records passed in.
4615 * For any leaf node, generate the high and low keys for the record.
4616 * If the record keys overlap with the query low/high keys, pass the
4617 * record to the function iterator.
4619 * For any internal node, compare the low and high keys of each
4620 * pointer against the query low/high keys. If there's an overlap,
4621 * follow the pointer.
4623 * As an optimization, we stop scanning a block when we find a low key
4624 * that is greater than the query's high key.
4627 xfs_btree_overlapped_query_range(
4628 struct xfs_btree_cur
*cur
,
4629 union xfs_btree_key
*low_key
,
4630 union xfs_btree_key
*high_key
,
4631 xfs_btree_query_range_fn fn
,
4634 union xfs_btree_ptr ptr
;
4635 union xfs_btree_ptr
*pp
;
4636 union xfs_btree_key rec_key
;
4637 union xfs_btree_key rec_hkey
;
4638 union xfs_btree_key
*lkp
;
4639 union xfs_btree_key
*hkp
;
4640 union xfs_btree_rec
*recp
;
4641 struct xfs_btree_block
*block
;
4649 /* Load the root of the btree. */
4650 level
= cur
->bc_nlevels
- 1;
4651 cur
->bc_ops
->init_ptr_from_cur(cur
, &ptr
);
4652 error
= xfs_btree_lookup_get_block(cur
, level
, &ptr
, &block
);
4655 xfs_btree_get_block(cur
, level
, &bp
);
4656 trace_xfs_btree_overlapped_query_range(cur
, level
, bp
);
4658 error
= xfs_btree_check_block(cur
, block
, level
, bp
);
4662 cur
->bc_ptrs
[level
] = 1;
4664 while (level
< cur
->bc_nlevels
) {
4665 block
= xfs_btree_get_block(cur
, level
, &bp
);
4667 /* End of node, pop back towards the root. */
4668 if (cur
->bc_ptrs
[level
] > be16_to_cpu(block
->bb_numrecs
)) {
4670 if (level
< cur
->bc_nlevels
- 1)
4671 cur
->bc_ptrs
[level
+ 1]++;
4677 /* Handle a leaf node. */
4678 recp
= xfs_btree_rec_addr(cur
, cur
->bc_ptrs
[0], block
);
4680 cur
->bc_ops
->init_high_key_from_rec(&rec_hkey
, recp
);
4681 ldiff
= cur
->bc_ops
->diff_two_keys(cur
, &rec_hkey
,
4684 cur
->bc_ops
->init_key_from_rec(&rec_key
, recp
);
4685 hdiff
= cur
->bc_ops
->diff_two_keys(cur
, high_key
,
4689 * If (record's high key >= query's low key) and
4690 * (query's high key >= record's low key), then
4691 * this record overlaps the query range; callback.
4693 if (ldiff
>= 0 && hdiff
>= 0) {
4694 error
= fn(cur
, recp
, priv
);
4697 } else if (hdiff
< 0) {
4698 /* Record is larger than high key; pop. */
4701 cur
->bc_ptrs
[level
]++;
4705 /* Handle an internal node. */
4706 lkp
= xfs_btree_key_addr(cur
, cur
->bc_ptrs
[level
], block
);
4707 hkp
= xfs_btree_high_key_addr(cur
, cur
->bc_ptrs
[level
], block
);
4708 pp
= xfs_btree_ptr_addr(cur
, cur
->bc_ptrs
[level
], block
);
4710 ldiff
= cur
->bc_ops
->diff_two_keys(cur
, hkp
, low_key
);
4711 hdiff
= cur
->bc_ops
->diff_two_keys(cur
, high_key
, lkp
);
4714 * If (pointer's high key >= query's low key) and
4715 * (query's high key >= pointer's low key), then
4716 * this record overlaps the query range; follow pointer.
4718 if (ldiff
>= 0 && hdiff
>= 0) {
4720 error
= xfs_btree_lookup_get_block(cur
, level
, pp
,
4724 xfs_btree_get_block(cur
, level
, &bp
);
4725 trace_xfs_btree_overlapped_query_range(cur
, level
, bp
);
4727 error
= xfs_btree_check_block(cur
, block
, level
, bp
);
4731 cur
->bc_ptrs
[level
] = 1;
4733 } else if (hdiff
< 0) {
4734 /* The low key is larger than the upper range; pop. */
4737 cur
->bc_ptrs
[level
]++;
4742 * If we don't end this function with the cursor pointing at a record
4743 * block, a subsequent non-error cursor deletion will not release
4744 * node-level buffers, causing a buffer leak. This is quite possible
4745 * with a zero-results range query, so release the buffers if we
4746 * failed to return any results.
4748 if (cur
->bc_bufs
[0] == NULL
) {
4749 for (i
= 0; i
< cur
->bc_nlevels
; i
++) {
4750 if (cur
->bc_bufs
[i
]) {
4751 xfs_trans_brelse(cur
->bc_tp
, cur
->bc_bufs
[i
]);
4752 cur
->bc_bufs
[i
] = NULL
;
4753 cur
->bc_ptrs
[i
] = 0;
4763 * Query a btree for all records overlapping a given interval of keys. The
4764 * supplied function will be called with each record found; return one of the
4765 * XFS_BTREE_QUERY_RANGE_{CONTINUE,ABORT} values or the usual negative error
4766 * code. This function returns -ECANCELED, zero, or a negative error code.
4769 xfs_btree_query_range(
4770 struct xfs_btree_cur
*cur
,
4771 union xfs_btree_irec
*low_rec
,
4772 union xfs_btree_irec
*high_rec
,
4773 xfs_btree_query_range_fn fn
,
4776 union xfs_btree_rec rec
;
4777 union xfs_btree_key low_key
;
4778 union xfs_btree_key high_key
;
4780 /* Find the keys of both ends of the interval. */
4781 cur
->bc_rec
= *high_rec
;
4782 cur
->bc_ops
->init_rec_from_cur(cur
, &rec
);
4783 cur
->bc_ops
->init_key_from_rec(&high_key
, &rec
);
4785 cur
->bc_rec
= *low_rec
;
4786 cur
->bc_ops
->init_rec_from_cur(cur
, &rec
);
4787 cur
->bc_ops
->init_key_from_rec(&low_key
, &rec
);
4789 /* Enforce low key < high key. */
4790 if (cur
->bc_ops
->diff_two_keys(cur
, &low_key
, &high_key
) > 0)
4793 if (!(cur
->bc_flags
& XFS_BTREE_OVERLAPPING
))
4794 return xfs_btree_simple_query_range(cur
, &low_key
,
4795 &high_key
, fn
, priv
);
4796 return xfs_btree_overlapped_query_range(cur
, &low_key
, &high_key
,
4800 /* Query a btree for all records. */
4802 xfs_btree_query_all(
4803 struct xfs_btree_cur
*cur
,
4804 xfs_btree_query_range_fn fn
,
4807 union xfs_btree_key low_key
;
4808 union xfs_btree_key high_key
;
4810 memset(&cur
->bc_rec
, 0, sizeof(cur
->bc_rec
));
4811 memset(&low_key
, 0, sizeof(low_key
));
4812 memset(&high_key
, 0xFF, sizeof(high_key
));
4814 return xfs_btree_simple_query_range(cur
, &low_key
, &high_key
, fn
, priv
);
4818 * Calculate the number of blocks needed to store a given number of records
4819 * in a short-format (per-AG metadata) btree.
4822 xfs_btree_calc_size(
4824 unsigned long long len
)
4828 unsigned long long rval
;
4830 maxrecs
= limits
[0];
4831 for (level
= 0, rval
= 0; len
> 1; level
++) {
4833 do_div(len
, maxrecs
);
4834 maxrecs
= limits
[1];
4841 xfs_btree_count_blocks_helper(
4842 struct xfs_btree_cur
*cur
,
4846 xfs_extlen_t
*blocks
= data
;
4852 /* Count the blocks in a btree and return the result in *blocks. */
4854 xfs_btree_count_blocks(
4855 struct xfs_btree_cur
*cur
,
4856 xfs_extlen_t
*blocks
)
4859 return xfs_btree_visit_blocks(cur
, xfs_btree_count_blocks_helper
,
4860 XFS_BTREE_VISIT_ALL
, blocks
);
4863 /* Compare two btree pointers. */
4865 xfs_btree_diff_two_ptrs(
4866 struct xfs_btree_cur
*cur
,
4867 const union xfs_btree_ptr
*a
,
4868 const union xfs_btree_ptr
*b
)
4870 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
)
4871 return (int64_t)be64_to_cpu(a
->l
) - be64_to_cpu(b
->l
);
4872 return (int64_t)be32_to_cpu(a
->s
) - be32_to_cpu(b
->s
);
4875 /* If there's an extent, we're done. */
4877 xfs_btree_has_record_helper(
4878 struct xfs_btree_cur
*cur
,
4879 union xfs_btree_rec
*rec
,
4885 /* Is there a record covering a given range of keys? */
4887 xfs_btree_has_record(
4888 struct xfs_btree_cur
*cur
,
4889 union xfs_btree_irec
*low
,
4890 union xfs_btree_irec
*high
,
4895 error
= xfs_btree_query_range(cur
, low
, high
,
4896 &xfs_btree_has_record_helper
, NULL
);
4897 if (error
== -ECANCELED
) {
4905 /* Are there more records in this btree? */
4907 xfs_btree_has_more_records(
4908 struct xfs_btree_cur
*cur
)
4910 struct xfs_btree_block
*block
;
4913 block
= xfs_btree_get_block(cur
, 0, &bp
);
4915 /* There are still records in this block. */
4916 if (cur
->bc_ptrs
[0] < xfs_btree_get_numrecs(block
))
4919 /* There are more record blocks. */
4920 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
)
4921 return block
->bb_u
.l
.bb_rightsib
!= cpu_to_be64(NULLFSBLOCK
);
4923 return block
->bb_u
.s
.bb_rightsib
!= cpu_to_be32(NULLAGBLOCK
);