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_defer.h"
15 #include "xfs_inode.h"
16 #include "xfs_trans.h"
17 #include "xfs_btree.h"
18 #include "xfs_errortag.h"
19 #include "xfs_trace.h"
20 #include "xfs_cksum.h"
21 #include "xfs_alloc.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 (unlikely(XFS_TEST_ERROR(fa
!= NULL
, mp
,
108 XFS_ERRTAG_BTREE_CHECK_LBLOCK
))) {
110 trace_xfs_btree_corrupt(bp
, _RET_IP_
);
111 XFS_ERROR_REPORT(__func__
, XFS_ERRLEVEL_LOW
, mp
);
112 return -EFSCORRUPTED
;
118 * Check a short btree block header. Return the address of the failing check,
119 * or NULL if everything is ok.
122 __xfs_btree_check_sblock(
123 struct xfs_btree_cur
*cur
,
124 struct xfs_btree_block
*block
,
128 struct xfs_mount
*mp
= cur
->bc_mp
;
129 xfs_btnum_t btnum
= cur
->bc_btnum
;
130 int crc
= xfs_sb_version_hascrc(&mp
->m_sb
);
133 if (!uuid_equal(&block
->bb_u
.s
.bb_uuid
, &mp
->m_sb
.sb_meta_uuid
))
134 return __this_address
;
135 if (block
->bb_u
.s
.bb_blkno
!=
136 cpu_to_be64(bp
? bp
->b_bn
: XFS_BUF_DADDR_NULL
))
137 return __this_address
;
140 if (be32_to_cpu(block
->bb_magic
) != xfs_btree_magic(crc
, btnum
))
141 return __this_address
;
142 if (be16_to_cpu(block
->bb_level
) != level
)
143 return __this_address
;
144 if (be16_to_cpu(block
->bb_numrecs
) >
145 cur
->bc_ops
->get_maxrecs(cur
, level
))
146 return __this_address
;
147 if (block
->bb_u
.s
.bb_leftsib
!= cpu_to_be32(NULLAGBLOCK
) &&
148 !xfs_btree_check_sptr(cur
, be32_to_cpu(block
->bb_u
.s
.bb_leftsib
),
150 return __this_address
;
151 if (block
->bb_u
.s
.bb_rightsib
!= cpu_to_be32(NULLAGBLOCK
) &&
152 !xfs_btree_check_sptr(cur
, be32_to_cpu(block
->bb_u
.s
.bb_rightsib
),
154 return __this_address
;
159 /* Check a short btree block header. */
161 xfs_btree_check_sblock(
162 struct xfs_btree_cur
*cur
,
163 struct xfs_btree_block
*block
,
167 struct xfs_mount
*mp
= cur
->bc_mp
;
170 fa
= __xfs_btree_check_sblock(cur
, block
, level
, bp
);
171 if (unlikely(XFS_TEST_ERROR(fa
!= NULL
, mp
,
172 XFS_ERRTAG_BTREE_CHECK_SBLOCK
))) {
174 trace_xfs_btree_corrupt(bp
, _RET_IP_
);
175 XFS_ERROR_REPORT(__func__
, XFS_ERRLEVEL_LOW
, mp
);
176 return -EFSCORRUPTED
;
182 * Debug routine: check that block header is ok.
185 xfs_btree_check_block(
186 struct xfs_btree_cur
*cur
, /* btree cursor */
187 struct xfs_btree_block
*block
, /* generic btree block pointer */
188 int level
, /* level of the btree block */
189 struct xfs_buf
*bp
) /* buffer containing block, if any */
191 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
)
192 return xfs_btree_check_lblock(cur
, block
, level
, bp
);
194 return xfs_btree_check_sblock(cur
, block
, level
, bp
);
197 /* Check that this long pointer is valid and points within the fs. */
199 xfs_btree_check_lptr(
200 struct xfs_btree_cur
*cur
,
206 return xfs_verify_fsbno(cur
->bc_mp
, fsbno
);
209 /* Check that this short pointer is valid and points within the AG. */
211 xfs_btree_check_sptr(
212 struct xfs_btree_cur
*cur
,
218 return xfs_verify_agbno(cur
->bc_mp
, cur
->bc_private
.a
.agno
, agbno
);
222 * Check that a given (indexed) btree pointer at a certain level of a
223 * btree is valid and doesn't point past where it should.
227 struct xfs_btree_cur
*cur
,
228 union xfs_btree_ptr
*ptr
,
232 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
) {
233 if (xfs_btree_check_lptr(cur
, be64_to_cpu((&ptr
->l
)[index
]),
237 "Inode %llu fork %d: Corrupt btree %d pointer at level %d index %d.",
238 cur
->bc_private
.b
.ip
->i_ino
,
239 cur
->bc_private
.b
.whichfork
, cur
->bc_btnum
,
242 if (xfs_btree_check_sptr(cur
, be32_to_cpu((&ptr
->s
)[index
]),
246 "AG %u: Corrupt btree %d pointer at level %d index %d.",
247 cur
->bc_private
.a
.agno
, cur
->bc_btnum
,
251 return -EFSCORRUPTED
;
255 # define xfs_btree_debug_check_ptr xfs_btree_check_ptr
257 # define xfs_btree_debug_check_ptr(...) (0)
261 * Calculate CRC on the whole btree block and stuff it into the
262 * long-form btree header.
264 * Prior to calculting the CRC, pull the LSN out of the buffer log item and put
265 * it into the buffer so recovery knows what the last modification was that made
269 xfs_btree_lblock_calc_crc(
272 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
273 struct xfs_buf_log_item
*bip
= bp
->b_log_item
;
275 if (!xfs_sb_version_hascrc(&bp
->b_target
->bt_mount
->m_sb
))
278 block
->bb_u
.l
.bb_lsn
= cpu_to_be64(bip
->bli_item
.li_lsn
);
279 xfs_buf_update_cksum(bp
, XFS_BTREE_LBLOCK_CRC_OFF
);
283 xfs_btree_lblock_verify_crc(
286 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
287 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
289 if (xfs_sb_version_hascrc(&mp
->m_sb
)) {
290 if (!xfs_log_check_lsn(mp
, be64_to_cpu(block
->bb_u
.l
.bb_lsn
)))
292 return xfs_buf_verify_cksum(bp
, XFS_BTREE_LBLOCK_CRC_OFF
);
299 * Calculate CRC on the whole btree block and stuff it into the
300 * short-form btree header.
302 * Prior to calculting the CRC, pull the LSN out of the buffer log item and put
303 * it into the buffer so recovery knows what the last modification was that made
307 xfs_btree_sblock_calc_crc(
310 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
311 struct xfs_buf_log_item
*bip
= bp
->b_log_item
;
313 if (!xfs_sb_version_hascrc(&bp
->b_target
->bt_mount
->m_sb
))
316 block
->bb_u
.s
.bb_lsn
= cpu_to_be64(bip
->bli_item
.li_lsn
);
317 xfs_buf_update_cksum(bp
, XFS_BTREE_SBLOCK_CRC_OFF
);
321 xfs_btree_sblock_verify_crc(
324 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
325 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
327 if (xfs_sb_version_hascrc(&mp
->m_sb
)) {
328 if (!xfs_log_check_lsn(mp
, be64_to_cpu(block
->bb_u
.s
.bb_lsn
)))
330 return xfs_buf_verify_cksum(bp
, XFS_BTREE_SBLOCK_CRC_OFF
);
337 xfs_btree_free_block(
338 struct xfs_btree_cur
*cur
,
343 error
= cur
->bc_ops
->free_block(cur
, bp
);
345 xfs_trans_binval(cur
->bc_tp
, bp
);
346 XFS_BTREE_STATS_INC(cur
, free
);
352 * Delete the btree cursor.
355 xfs_btree_del_cursor(
356 xfs_btree_cur_t
*cur
, /* btree cursor */
357 int error
) /* del because of error */
359 int i
; /* btree level */
362 * Clear the buffer pointers, and release the buffers.
363 * If we're doing this in the face of an error, we
364 * need to make sure to inspect all of the entries
365 * in the bc_bufs array for buffers to be unlocked.
366 * This is because some of the btree code works from
367 * level n down to 0, and if we get an error along
368 * the way we won't have initialized all the entries
371 for (i
= 0; i
< cur
->bc_nlevels
; i
++) {
373 xfs_trans_brelse(cur
->bc_tp
, cur
->bc_bufs
[i
]);
378 * Can't free a bmap cursor without having dealt with the
379 * allocated indirect blocks' accounting.
381 ASSERT(cur
->bc_btnum
!= XFS_BTNUM_BMAP
||
382 cur
->bc_private
.b
.allocated
== 0);
386 kmem_zone_free(xfs_btree_cur_zone
, cur
);
390 * Duplicate the btree cursor.
391 * Allocate a new one, copy the record, re-get the buffers.
394 xfs_btree_dup_cursor(
395 xfs_btree_cur_t
*cur
, /* input cursor */
396 xfs_btree_cur_t
**ncur
) /* output cursor */
398 xfs_buf_t
*bp
; /* btree block's buffer pointer */
399 int error
; /* error return value */
400 int i
; /* level number of btree block */
401 xfs_mount_t
*mp
; /* mount structure for filesystem */
402 xfs_btree_cur_t
*new; /* new cursor value */
403 xfs_trans_t
*tp
; /* transaction pointer, can be NULL */
409 * Allocate a new cursor like the old one.
411 new = cur
->bc_ops
->dup_cursor(cur
);
414 * Copy the record currently in the cursor.
416 new->bc_rec
= cur
->bc_rec
;
419 * For each level current, re-get the buffer and copy the ptr value.
421 for (i
= 0; i
< new->bc_nlevels
; i
++) {
422 new->bc_ptrs
[i
] = cur
->bc_ptrs
[i
];
423 new->bc_ra
[i
] = cur
->bc_ra
[i
];
424 bp
= cur
->bc_bufs
[i
];
426 error
= xfs_trans_read_buf(mp
, tp
, mp
->m_ddev_targp
,
427 XFS_BUF_ADDR(bp
), mp
->m_bsize
,
429 cur
->bc_ops
->buf_ops
);
431 xfs_btree_del_cursor(new, error
);
436 new->bc_bufs
[i
] = bp
;
443 * XFS btree block layout and addressing:
445 * There are two types of blocks in the btree: leaf and non-leaf blocks.
447 * The leaf record start with a header then followed by records containing
448 * the values. A non-leaf block also starts with the same header, and
449 * then first contains lookup keys followed by an equal number of pointers
450 * to the btree blocks at the previous level.
452 * +--------+-------+-------+-------+-------+-------+-------+
453 * Leaf: | header | rec 1 | rec 2 | rec 3 | rec 4 | rec 5 | rec N |
454 * +--------+-------+-------+-------+-------+-------+-------+
456 * +--------+-------+-------+-------+-------+-------+-------+
457 * Non-Leaf: | header | key 1 | key 2 | key N | ptr 1 | ptr 2 | ptr N |
458 * +--------+-------+-------+-------+-------+-------+-------+
460 * The header is called struct xfs_btree_block for reasons better left unknown
461 * and comes in different versions for short (32bit) and long (64bit) block
462 * pointers. The record and key structures are defined by the btree instances
463 * and opaque to the btree core. The block pointers are simple disk endian
464 * integers, available in a short (32bit) and long (64bit) variant.
466 * The helpers below calculate the offset of a given record, key or pointer
467 * into a btree block (xfs_btree_*_offset) or return a pointer to the given
468 * record, key or pointer (xfs_btree_*_addr). Note that all addressing
469 * inside the btree block is done using indices starting at one, not zero!
471 * If XFS_BTREE_OVERLAPPING is set, then this btree supports keys containing
472 * overlapping intervals. In such a tree, records are still sorted lowest to
473 * highest and indexed by the smallest key value that refers to the record.
474 * However, nodes are different: each pointer has two associated keys -- one
475 * indexing the lowest key available in the block(s) below (the same behavior
476 * as the key in a regular btree) and another indexing the highest key
477 * available in the block(s) below. Because records are /not/ sorted by the
478 * highest key, all leaf block updates require us to compute the highest key
479 * that matches any record in the leaf and to recursively update the high keys
480 * in the nodes going further up in the tree, if necessary. Nodes look like
483 * +--------+-----+-----+-----+-----+-----+-------+-------+-----+
484 * Non-Leaf: | header | lo1 | hi1 | lo2 | hi2 | ... | ptr 1 | ptr 2 | ... |
485 * +--------+-----+-----+-----+-----+-----+-------+-------+-----+
487 * To perform an interval query on an overlapped tree, perform the usual
488 * depth-first search and use the low and high keys to decide if we can skip
489 * that particular node. If a leaf node is reached, return the records that
490 * intersect the interval. Note that an interval query may return numerous
491 * entries. For a non-overlapped tree, simply search for the record associated
492 * with the lowest key and iterate forward until a non-matching record is
493 * found. Section 14.3 ("Interval Trees") of _Introduction to Algorithms_ by
494 * Cormen, Leiserson, Rivest, and Stein (2nd or 3rd ed. only) discuss this in
497 * Why do we care about overlapping intervals? Let's say you have a bunch of
498 * reverse mapping records on a reflink filesystem:
500 * 1: +- file A startblock B offset C length D -----------+
501 * 2: +- file E startblock F offset G length H --------------+
502 * 3: +- file I startblock F offset J length K --+
503 * 4: +- file L... --+
505 * Now say we want to map block (B+D) into file A at offset (C+D). Ideally,
506 * we'd simply increment the length of record 1. But how do we find the record
507 * that ends at (B+D-1) (i.e. record 1)? A LE lookup of (B+D-1) would return
508 * record 3 because the keys are ordered first by startblock. An interval
509 * query would return records 1 and 2 because they both overlap (B+D-1), and
510 * from that we can pick out record 1 as the appropriate left neighbor.
512 * In the non-overlapped case you can do a LE lookup and decrement the cursor
513 * because a record's interval must end before the next record.
517 * Return size of the btree block header for this btree instance.
519 static inline size_t xfs_btree_block_len(struct xfs_btree_cur
*cur
)
521 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
) {
522 if (cur
->bc_flags
& XFS_BTREE_CRC_BLOCKS
)
523 return XFS_BTREE_LBLOCK_CRC_LEN
;
524 return XFS_BTREE_LBLOCK_LEN
;
526 if (cur
->bc_flags
& XFS_BTREE_CRC_BLOCKS
)
527 return XFS_BTREE_SBLOCK_CRC_LEN
;
528 return XFS_BTREE_SBLOCK_LEN
;
532 * Return size of btree block pointers for this btree instance.
534 static inline size_t xfs_btree_ptr_len(struct xfs_btree_cur
*cur
)
536 return (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
) ?
537 sizeof(__be64
) : sizeof(__be32
);
541 * Calculate offset of the n-th record in a btree block.
544 xfs_btree_rec_offset(
545 struct xfs_btree_cur
*cur
,
548 return xfs_btree_block_len(cur
) +
549 (n
- 1) * cur
->bc_ops
->rec_len
;
553 * Calculate offset of the n-th key in a btree block.
556 xfs_btree_key_offset(
557 struct xfs_btree_cur
*cur
,
560 return xfs_btree_block_len(cur
) +
561 (n
- 1) * cur
->bc_ops
->key_len
;
565 * Calculate offset of the n-th high key in a btree block.
568 xfs_btree_high_key_offset(
569 struct xfs_btree_cur
*cur
,
572 return xfs_btree_block_len(cur
) +
573 (n
- 1) * cur
->bc_ops
->key_len
+ (cur
->bc_ops
->key_len
/ 2);
577 * Calculate offset of the n-th block pointer in a btree block.
580 xfs_btree_ptr_offset(
581 struct xfs_btree_cur
*cur
,
585 return xfs_btree_block_len(cur
) +
586 cur
->bc_ops
->get_maxrecs(cur
, level
) * cur
->bc_ops
->key_len
+
587 (n
- 1) * xfs_btree_ptr_len(cur
);
591 * Return a pointer to the n-th record in the btree block.
593 union xfs_btree_rec
*
595 struct xfs_btree_cur
*cur
,
597 struct xfs_btree_block
*block
)
599 return (union xfs_btree_rec
*)
600 ((char *)block
+ xfs_btree_rec_offset(cur
, n
));
604 * Return a pointer to the n-th key in the btree block.
606 union xfs_btree_key
*
608 struct xfs_btree_cur
*cur
,
610 struct xfs_btree_block
*block
)
612 return (union xfs_btree_key
*)
613 ((char *)block
+ xfs_btree_key_offset(cur
, n
));
617 * Return a pointer to the n-th high key in the btree block.
619 union xfs_btree_key
*
620 xfs_btree_high_key_addr(
621 struct xfs_btree_cur
*cur
,
623 struct xfs_btree_block
*block
)
625 return (union xfs_btree_key
*)
626 ((char *)block
+ xfs_btree_high_key_offset(cur
, n
));
630 * Return a pointer to the n-th block pointer in the btree block.
632 union xfs_btree_ptr
*
634 struct xfs_btree_cur
*cur
,
636 struct xfs_btree_block
*block
)
638 int level
= xfs_btree_get_level(block
);
640 ASSERT(block
->bb_level
!= 0);
642 return (union xfs_btree_ptr
*)
643 ((char *)block
+ xfs_btree_ptr_offset(cur
, n
, level
));
647 * Get the root block which is stored in the inode.
649 * For now this btree implementation assumes the btree root is always
650 * stored in the if_broot field of an inode fork.
652 STATIC
struct xfs_btree_block
*
654 struct xfs_btree_cur
*cur
)
656 struct xfs_ifork
*ifp
;
658 ifp
= XFS_IFORK_PTR(cur
->bc_private
.b
.ip
, cur
->bc_private
.b
.whichfork
);
659 return (struct xfs_btree_block
*)ifp
->if_broot
;
663 * Retrieve the block pointer from the cursor at the given level.
664 * This may be an inode btree root or from a buffer.
666 struct xfs_btree_block
* /* generic btree block pointer */
668 struct xfs_btree_cur
*cur
, /* btree cursor */
669 int level
, /* level in btree */
670 struct xfs_buf
**bpp
) /* buffer containing the block */
672 if ((cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
) &&
673 (level
== cur
->bc_nlevels
- 1)) {
675 return xfs_btree_get_iroot(cur
);
678 *bpp
= cur
->bc_bufs
[level
];
679 return XFS_BUF_TO_BLOCK(*bpp
);
683 * Get a buffer for the block, return it with no data read.
684 * Long-form addressing.
686 xfs_buf_t
* /* buffer for fsbno */
688 xfs_mount_t
*mp
, /* file system mount point */
689 xfs_trans_t
*tp
, /* transaction pointer */
690 xfs_fsblock_t fsbno
, /* file system block number */
691 uint lock
) /* lock flags for get_buf */
693 xfs_daddr_t d
; /* real disk block address */
695 ASSERT(fsbno
!= NULLFSBLOCK
);
696 d
= XFS_FSB_TO_DADDR(mp
, fsbno
);
697 return xfs_trans_get_buf(tp
, mp
->m_ddev_targp
, d
, mp
->m_bsize
, lock
);
701 * Get a buffer for the block, return it with no data read.
702 * Short-form addressing.
704 xfs_buf_t
* /* buffer for agno/agbno */
706 xfs_mount_t
*mp
, /* file system mount point */
707 xfs_trans_t
*tp
, /* transaction pointer */
708 xfs_agnumber_t agno
, /* allocation group number */
709 xfs_agblock_t agbno
, /* allocation group block number */
710 uint lock
) /* lock flags for get_buf */
712 xfs_daddr_t d
; /* real disk block address */
714 ASSERT(agno
!= NULLAGNUMBER
);
715 ASSERT(agbno
!= NULLAGBLOCK
);
716 d
= XFS_AGB_TO_DADDR(mp
, agno
, agbno
);
717 return xfs_trans_get_buf(tp
, mp
->m_ddev_targp
, d
, mp
->m_bsize
, lock
);
721 * Check for the cursor referring to the last block at the given level.
723 int /* 1=is last block, 0=not last block */
724 xfs_btree_islastblock(
725 xfs_btree_cur_t
*cur
, /* btree cursor */
726 int level
) /* level to check */
728 struct xfs_btree_block
*block
; /* generic btree block pointer */
729 xfs_buf_t
*bp
; /* buffer containing block */
731 block
= xfs_btree_get_block(cur
, level
, &bp
);
732 xfs_btree_check_block(cur
, block
, level
, bp
);
733 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
)
734 return block
->bb_u
.l
.bb_rightsib
== cpu_to_be64(NULLFSBLOCK
);
736 return block
->bb_u
.s
.bb_rightsib
== cpu_to_be32(NULLAGBLOCK
);
740 * Change the cursor to point to the first record at the given level.
741 * Other levels are unaffected.
743 STATIC
int /* success=1, failure=0 */
745 xfs_btree_cur_t
*cur
, /* btree cursor */
746 int level
) /* level to change */
748 struct xfs_btree_block
*block
; /* generic btree block pointer */
749 xfs_buf_t
*bp
; /* buffer containing block */
752 * Get the block pointer for this level.
754 block
= xfs_btree_get_block(cur
, level
, &bp
);
755 if (xfs_btree_check_block(cur
, block
, level
, bp
))
758 * It's empty, there is no such record.
760 if (!block
->bb_numrecs
)
763 * Set the ptr value to 1, that's the first record/key.
765 cur
->bc_ptrs
[level
] = 1;
770 * Change the cursor to point to the last record in the current block
771 * at the given level. Other levels are unaffected.
773 STATIC
int /* success=1, failure=0 */
775 xfs_btree_cur_t
*cur
, /* btree cursor */
776 int level
) /* level to change */
778 struct xfs_btree_block
*block
; /* generic btree block pointer */
779 xfs_buf_t
*bp
; /* buffer containing block */
782 * Get the block pointer for this level.
784 block
= xfs_btree_get_block(cur
, level
, &bp
);
785 if (xfs_btree_check_block(cur
, block
, level
, bp
))
788 * It's empty, there is no such record.
790 if (!block
->bb_numrecs
)
793 * Set the ptr value to numrecs, that's the last record/key.
795 cur
->bc_ptrs
[level
] = be16_to_cpu(block
->bb_numrecs
);
800 * Compute first and last byte offsets for the fields given.
801 * Interprets the offsets table, which contains struct field offsets.
805 int64_t fields
, /* bitmask of fields */
806 const short *offsets
, /* table of field offsets */
807 int nbits
, /* number of bits to inspect */
808 int *first
, /* output: first byte offset */
809 int *last
) /* output: last byte offset */
811 int i
; /* current bit number */
812 int64_t imask
; /* mask for current bit number */
816 * Find the lowest bit, so the first byte offset.
818 for (i
= 0, imask
= 1LL; ; i
++, imask
<<= 1) {
819 if (imask
& fields
) {
825 * Find the highest bit, so the last byte offset.
827 for (i
= nbits
- 1, imask
= 1LL << i
; ; i
--, imask
>>= 1) {
828 if (imask
& fields
) {
829 *last
= offsets
[i
+ 1] - 1;
836 * Get a buffer for the block, return it read in.
837 * Long-form addressing.
841 struct xfs_mount
*mp
, /* file system mount point */
842 struct xfs_trans
*tp
, /* transaction pointer */
843 xfs_fsblock_t fsbno
, /* file system block number */
844 uint lock
, /* lock flags for read_buf */
845 struct xfs_buf
**bpp
, /* buffer for fsbno */
846 int refval
, /* ref count value for buffer */
847 const struct xfs_buf_ops
*ops
)
849 struct xfs_buf
*bp
; /* return value */
850 xfs_daddr_t d
; /* real disk block address */
853 if (!xfs_verify_fsbno(mp
, fsbno
))
854 return -EFSCORRUPTED
;
855 d
= XFS_FSB_TO_DADDR(mp
, fsbno
);
856 error
= xfs_trans_read_buf(mp
, tp
, mp
->m_ddev_targp
, d
,
857 mp
->m_bsize
, lock
, &bp
, ops
);
861 xfs_buf_set_ref(bp
, refval
);
867 * Read-ahead the block, don't wait for it, don't return a buffer.
868 * Long-form addressing.
872 xfs_btree_reada_bufl(
873 struct xfs_mount
*mp
, /* file system mount point */
874 xfs_fsblock_t fsbno
, /* file system block number */
875 xfs_extlen_t count
, /* count of filesystem blocks */
876 const struct xfs_buf_ops
*ops
)
880 ASSERT(fsbno
!= NULLFSBLOCK
);
881 d
= XFS_FSB_TO_DADDR(mp
, fsbno
);
882 xfs_buf_readahead(mp
->m_ddev_targp
, d
, mp
->m_bsize
* count
, ops
);
886 * Read-ahead the block, don't wait for it, don't return a buffer.
887 * Short-form addressing.
891 xfs_btree_reada_bufs(
892 struct xfs_mount
*mp
, /* file system mount point */
893 xfs_agnumber_t agno
, /* allocation group number */
894 xfs_agblock_t agbno
, /* allocation group block number */
895 xfs_extlen_t count
, /* count of filesystem blocks */
896 const struct xfs_buf_ops
*ops
)
900 ASSERT(agno
!= NULLAGNUMBER
);
901 ASSERT(agbno
!= NULLAGBLOCK
);
902 d
= XFS_AGB_TO_DADDR(mp
, agno
, agbno
);
903 xfs_buf_readahead(mp
->m_ddev_targp
, d
, mp
->m_bsize
* count
, ops
);
907 xfs_btree_readahead_lblock(
908 struct xfs_btree_cur
*cur
,
910 struct xfs_btree_block
*block
)
913 xfs_fsblock_t left
= be64_to_cpu(block
->bb_u
.l
.bb_leftsib
);
914 xfs_fsblock_t right
= be64_to_cpu(block
->bb_u
.l
.bb_rightsib
);
916 if ((lr
& XFS_BTCUR_LEFTRA
) && left
!= NULLFSBLOCK
) {
917 xfs_btree_reada_bufl(cur
->bc_mp
, left
, 1,
918 cur
->bc_ops
->buf_ops
);
922 if ((lr
& XFS_BTCUR_RIGHTRA
) && right
!= NULLFSBLOCK
) {
923 xfs_btree_reada_bufl(cur
->bc_mp
, right
, 1,
924 cur
->bc_ops
->buf_ops
);
932 xfs_btree_readahead_sblock(
933 struct xfs_btree_cur
*cur
,
935 struct xfs_btree_block
*block
)
938 xfs_agblock_t left
= be32_to_cpu(block
->bb_u
.s
.bb_leftsib
);
939 xfs_agblock_t right
= be32_to_cpu(block
->bb_u
.s
.bb_rightsib
);
942 if ((lr
& XFS_BTCUR_LEFTRA
) && left
!= NULLAGBLOCK
) {
943 xfs_btree_reada_bufs(cur
->bc_mp
, cur
->bc_private
.a
.agno
,
944 left
, 1, cur
->bc_ops
->buf_ops
);
948 if ((lr
& XFS_BTCUR_RIGHTRA
) && right
!= NULLAGBLOCK
) {
949 xfs_btree_reada_bufs(cur
->bc_mp
, cur
->bc_private
.a
.agno
,
950 right
, 1, cur
->bc_ops
->buf_ops
);
958 * Read-ahead btree blocks, at the given level.
959 * Bits in lr are set from XFS_BTCUR_{LEFT,RIGHT}RA.
963 struct xfs_btree_cur
*cur
, /* btree cursor */
964 int lev
, /* level in btree */
965 int lr
) /* left/right bits */
967 struct xfs_btree_block
*block
;
970 * No readahead needed if we are at the root level and the
971 * btree root is stored in the inode.
973 if ((cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
) &&
974 (lev
== cur
->bc_nlevels
- 1))
977 if ((cur
->bc_ra
[lev
] | lr
) == cur
->bc_ra
[lev
])
980 cur
->bc_ra
[lev
] |= lr
;
981 block
= XFS_BUF_TO_BLOCK(cur
->bc_bufs
[lev
]);
983 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
)
984 return xfs_btree_readahead_lblock(cur
, lr
, block
);
985 return xfs_btree_readahead_sblock(cur
, lr
, block
);
989 xfs_btree_ptr_to_daddr(
990 struct xfs_btree_cur
*cur
,
991 union xfs_btree_ptr
*ptr
,
998 error
= xfs_btree_check_ptr(cur
, ptr
, 0, 1);
1002 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
) {
1003 fsbno
= be64_to_cpu(ptr
->l
);
1004 *daddr
= XFS_FSB_TO_DADDR(cur
->bc_mp
, fsbno
);
1006 agbno
= be32_to_cpu(ptr
->s
);
1007 *daddr
= XFS_AGB_TO_DADDR(cur
->bc_mp
, cur
->bc_private
.a
.agno
,
1015 * Readahead @count btree blocks at the given @ptr location.
1017 * We don't need to care about long or short form btrees here as we have a
1018 * method of converting the ptr directly to a daddr available to us.
1021 xfs_btree_readahead_ptr(
1022 struct xfs_btree_cur
*cur
,
1023 union xfs_btree_ptr
*ptr
,
1028 if (xfs_btree_ptr_to_daddr(cur
, ptr
, &daddr
))
1030 xfs_buf_readahead(cur
->bc_mp
->m_ddev_targp
, daddr
,
1031 cur
->bc_mp
->m_bsize
* count
, cur
->bc_ops
->buf_ops
);
1035 * Set the buffer for level "lev" in the cursor to bp, releasing
1036 * any previous buffer.
1040 xfs_btree_cur_t
*cur
, /* btree cursor */
1041 int lev
, /* level in btree */
1042 xfs_buf_t
*bp
) /* new buffer to set */
1044 struct xfs_btree_block
*b
; /* btree block */
1046 if (cur
->bc_bufs
[lev
])
1047 xfs_trans_brelse(cur
->bc_tp
, cur
->bc_bufs
[lev
]);
1048 cur
->bc_bufs
[lev
] = bp
;
1049 cur
->bc_ra
[lev
] = 0;
1051 b
= XFS_BUF_TO_BLOCK(bp
);
1052 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
) {
1053 if (b
->bb_u
.l
.bb_leftsib
== cpu_to_be64(NULLFSBLOCK
))
1054 cur
->bc_ra
[lev
] |= XFS_BTCUR_LEFTRA
;
1055 if (b
->bb_u
.l
.bb_rightsib
== cpu_to_be64(NULLFSBLOCK
))
1056 cur
->bc_ra
[lev
] |= XFS_BTCUR_RIGHTRA
;
1058 if (b
->bb_u
.s
.bb_leftsib
== cpu_to_be32(NULLAGBLOCK
))
1059 cur
->bc_ra
[lev
] |= XFS_BTCUR_LEFTRA
;
1060 if (b
->bb_u
.s
.bb_rightsib
== cpu_to_be32(NULLAGBLOCK
))
1061 cur
->bc_ra
[lev
] |= XFS_BTCUR_RIGHTRA
;
1066 xfs_btree_ptr_is_null(
1067 struct xfs_btree_cur
*cur
,
1068 union xfs_btree_ptr
*ptr
)
1070 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
)
1071 return ptr
->l
== cpu_to_be64(NULLFSBLOCK
);
1073 return ptr
->s
== cpu_to_be32(NULLAGBLOCK
);
1077 xfs_btree_set_ptr_null(
1078 struct xfs_btree_cur
*cur
,
1079 union xfs_btree_ptr
*ptr
)
1081 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
)
1082 ptr
->l
= cpu_to_be64(NULLFSBLOCK
);
1084 ptr
->s
= cpu_to_be32(NULLAGBLOCK
);
1088 * Get/set/init sibling pointers
1091 xfs_btree_get_sibling(
1092 struct xfs_btree_cur
*cur
,
1093 struct xfs_btree_block
*block
,
1094 union xfs_btree_ptr
*ptr
,
1097 ASSERT(lr
== XFS_BB_LEFTSIB
|| lr
== XFS_BB_RIGHTSIB
);
1099 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
) {
1100 if (lr
== XFS_BB_RIGHTSIB
)
1101 ptr
->l
= block
->bb_u
.l
.bb_rightsib
;
1103 ptr
->l
= block
->bb_u
.l
.bb_leftsib
;
1105 if (lr
== XFS_BB_RIGHTSIB
)
1106 ptr
->s
= block
->bb_u
.s
.bb_rightsib
;
1108 ptr
->s
= block
->bb_u
.s
.bb_leftsib
;
1113 xfs_btree_set_sibling(
1114 struct xfs_btree_cur
*cur
,
1115 struct xfs_btree_block
*block
,
1116 union xfs_btree_ptr
*ptr
,
1119 ASSERT(lr
== XFS_BB_LEFTSIB
|| lr
== XFS_BB_RIGHTSIB
);
1121 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
) {
1122 if (lr
== XFS_BB_RIGHTSIB
)
1123 block
->bb_u
.l
.bb_rightsib
= ptr
->l
;
1125 block
->bb_u
.l
.bb_leftsib
= ptr
->l
;
1127 if (lr
== XFS_BB_RIGHTSIB
)
1128 block
->bb_u
.s
.bb_rightsib
= ptr
->s
;
1130 block
->bb_u
.s
.bb_leftsib
= ptr
->s
;
1135 xfs_btree_init_block_int(
1136 struct xfs_mount
*mp
,
1137 struct xfs_btree_block
*buf
,
1145 int crc
= xfs_sb_version_hascrc(&mp
->m_sb
);
1146 __u32 magic
= xfs_btree_magic(crc
, btnum
);
1148 buf
->bb_magic
= cpu_to_be32(magic
);
1149 buf
->bb_level
= cpu_to_be16(level
);
1150 buf
->bb_numrecs
= cpu_to_be16(numrecs
);
1152 if (flags
& XFS_BTREE_LONG_PTRS
) {
1153 buf
->bb_u
.l
.bb_leftsib
= cpu_to_be64(NULLFSBLOCK
);
1154 buf
->bb_u
.l
.bb_rightsib
= cpu_to_be64(NULLFSBLOCK
);
1156 buf
->bb_u
.l
.bb_blkno
= cpu_to_be64(blkno
);
1157 buf
->bb_u
.l
.bb_owner
= cpu_to_be64(owner
);
1158 uuid_copy(&buf
->bb_u
.l
.bb_uuid
, &mp
->m_sb
.sb_meta_uuid
);
1159 buf
->bb_u
.l
.bb_pad
= 0;
1160 buf
->bb_u
.l
.bb_lsn
= 0;
1163 /* owner is a 32 bit value on short blocks */
1164 __u32 __owner
= (__u32
)owner
;
1166 buf
->bb_u
.s
.bb_leftsib
= cpu_to_be32(NULLAGBLOCK
);
1167 buf
->bb_u
.s
.bb_rightsib
= cpu_to_be32(NULLAGBLOCK
);
1169 buf
->bb_u
.s
.bb_blkno
= cpu_to_be64(blkno
);
1170 buf
->bb_u
.s
.bb_owner
= cpu_to_be32(__owner
);
1171 uuid_copy(&buf
->bb_u
.s
.bb_uuid
, &mp
->m_sb
.sb_meta_uuid
);
1172 buf
->bb_u
.s
.bb_lsn
= 0;
1178 xfs_btree_init_block(
1179 struct xfs_mount
*mp
,
1187 xfs_btree_init_block_int(mp
, XFS_BUF_TO_BLOCK(bp
), bp
->b_bn
,
1188 btnum
, level
, numrecs
, owner
, flags
);
1192 xfs_btree_init_block_cur(
1193 struct xfs_btree_cur
*cur
,
1201 * we can pull the owner from the cursor right now as the different
1202 * owners align directly with the pointer size of the btree. This may
1203 * change in future, but is safe for current users of the generic btree
1206 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
)
1207 owner
= cur
->bc_private
.b
.ip
->i_ino
;
1209 owner
= cur
->bc_private
.a
.agno
;
1211 xfs_btree_init_block_int(cur
->bc_mp
, XFS_BUF_TO_BLOCK(bp
), bp
->b_bn
,
1212 cur
->bc_btnum
, level
, numrecs
,
1213 owner
, cur
->bc_flags
);
1217 * Return true if ptr is the last record in the btree and
1218 * we need to track updates to this record. The decision
1219 * will be further refined in the update_lastrec method.
1222 xfs_btree_is_lastrec(
1223 struct xfs_btree_cur
*cur
,
1224 struct xfs_btree_block
*block
,
1227 union xfs_btree_ptr ptr
;
1231 if (!(cur
->bc_flags
& XFS_BTREE_LASTREC_UPDATE
))
1234 xfs_btree_get_sibling(cur
, block
, &ptr
, XFS_BB_RIGHTSIB
);
1235 if (!xfs_btree_ptr_is_null(cur
, &ptr
))
1241 xfs_btree_buf_to_ptr(
1242 struct xfs_btree_cur
*cur
,
1244 union xfs_btree_ptr
*ptr
)
1246 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
)
1247 ptr
->l
= cpu_to_be64(XFS_DADDR_TO_FSB(cur
->bc_mp
,
1250 ptr
->s
= cpu_to_be32(xfs_daddr_to_agbno(cur
->bc_mp
,
1257 struct xfs_btree_cur
*cur
,
1260 switch (cur
->bc_btnum
) {
1263 xfs_buf_set_ref(bp
, XFS_ALLOC_BTREE_REF
);
1266 case XFS_BTNUM_FINO
:
1267 xfs_buf_set_ref(bp
, XFS_INO_BTREE_REF
);
1269 case XFS_BTNUM_BMAP
:
1270 xfs_buf_set_ref(bp
, XFS_BMAP_BTREE_REF
);
1272 case XFS_BTNUM_RMAP
:
1273 xfs_buf_set_ref(bp
, XFS_RMAP_BTREE_REF
);
1275 case XFS_BTNUM_REFC
:
1276 xfs_buf_set_ref(bp
, XFS_REFC_BTREE_REF
);
1284 xfs_btree_get_buf_block(
1285 struct xfs_btree_cur
*cur
,
1286 union xfs_btree_ptr
*ptr
,
1288 struct xfs_btree_block
**block
,
1289 struct xfs_buf
**bpp
)
1291 struct xfs_mount
*mp
= cur
->bc_mp
;
1295 /* need to sort out how callers deal with failures first */
1296 ASSERT(!(flags
& XBF_TRYLOCK
));
1298 error
= xfs_btree_ptr_to_daddr(cur
, ptr
, &d
);
1301 *bpp
= xfs_trans_get_buf(cur
->bc_tp
, mp
->m_ddev_targp
, d
,
1302 mp
->m_bsize
, flags
);
1307 (*bpp
)->b_ops
= cur
->bc_ops
->buf_ops
;
1308 *block
= XFS_BUF_TO_BLOCK(*bpp
);
1313 * Read in the buffer at the given ptr and return the buffer and
1314 * the block pointer within the buffer.
1317 xfs_btree_read_buf_block(
1318 struct xfs_btree_cur
*cur
,
1319 union xfs_btree_ptr
*ptr
,
1321 struct xfs_btree_block
**block
,
1322 struct xfs_buf
**bpp
)
1324 struct xfs_mount
*mp
= cur
->bc_mp
;
1328 /* need to sort out how callers deal with failures first */
1329 ASSERT(!(flags
& XBF_TRYLOCK
));
1331 error
= xfs_btree_ptr_to_daddr(cur
, ptr
, &d
);
1334 error
= xfs_trans_read_buf(mp
, cur
->bc_tp
, mp
->m_ddev_targp
, d
,
1335 mp
->m_bsize
, flags
, bpp
,
1336 cur
->bc_ops
->buf_ops
);
1340 xfs_btree_set_refs(cur
, *bpp
);
1341 *block
= XFS_BUF_TO_BLOCK(*bpp
);
1346 * Copy keys from one btree block to another.
1349 xfs_btree_copy_keys(
1350 struct xfs_btree_cur
*cur
,
1351 union xfs_btree_key
*dst_key
,
1352 union xfs_btree_key
*src_key
,
1355 ASSERT(numkeys
>= 0);
1356 memcpy(dst_key
, src_key
, numkeys
* cur
->bc_ops
->key_len
);
1360 * Copy records from one btree block to another.
1363 xfs_btree_copy_recs(
1364 struct xfs_btree_cur
*cur
,
1365 union xfs_btree_rec
*dst_rec
,
1366 union xfs_btree_rec
*src_rec
,
1369 ASSERT(numrecs
>= 0);
1370 memcpy(dst_rec
, src_rec
, numrecs
* cur
->bc_ops
->rec_len
);
1374 * Copy block pointers from one btree block to another.
1377 xfs_btree_copy_ptrs(
1378 struct xfs_btree_cur
*cur
,
1379 union xfs_btree_ptr
*dst_ptr
,
1380 union xfs_btree_ptr
*src_ptr
,
1383 ASSERT(numptrs
>= 0);
1384 memcpy(dst_ptr
, src_ptr
, numptrs
* xfs_btree_ptr_len(cur
));
1388 * Shift keys one index left/right inside a single btree block.
1391 xfs_btree_shift_keys(
1392 struct xfs_btree_cur
*cur
,
1393 union xfs_btree_key
*key
,
1399 ASSERT(numkeys
>= 0);
1400 ASSERT(dir
== 1 || dir
== -1);
1402 dst_key
= (char *)key
+ (dir
* cur
->bc_ops
->key_len
);
1403 memmove(dst_key
, key
, numkeys
* cur
->bc_ops
->key_len
);
1407 * Shift records one index left/right inside a single btree block.
1410 xfs_btree_shift_recs(
1411 struct xfs_btree_cur
*cur
,
1412 union xfs_btree_rec
*rec
,
1418 ASSERT(numrecs
>= 0);
1419 ASSERT(dir
== 1 || dir
== -1);
1421 dst_rec
= (char *)rec
+ (dir
* cur
->bc_ops
->rec_len
);
1422 memmove(dst_rec
, rec
, numrecs
* cur
->bc_ops
->rec_len
);
1426 * Shift block pointers one index left/right inside a single btree block.
1429 xfs_btree_shift_ptrs(
1430 struct xfs_btree_cur
*cur
,
1431 union xfs_btree_ptr
*ptr
,
1437 ASSERT(numptrs
>= 0);
1438 ASSERT(dir
== 1 || dir
== -1);
1440 dst_ptr
= (char *)ptr
+ (dir
* xfs_btree_ptr_len(cur
));
1441 memmove(dst_ptr
, ptr
, numptrs
* xfs_btree_ptr_len(cur
));
1445 * Log key values from the btree block.
1449 struct xfs_btree_cur
*cur
,
1456 xfs_trans_buf_set_type(cur
->bc_tp
, bp
, XFS_BLFT_BTREE_BUF
);
1457 xfs_trans_log_buf(cur
->bc_tp
, bp
,
1458 xfs_btree_key_offset(cur
, first
),
1459 xfs_btree_key_offset(cur
, last
+ 1) - 1);
1461 xfs_trans_log_inode(cur
->bc_tp
, cur
->bc_private
.b
.ip
,
1462 xfs_ilog_fbroot(cur
->bc_private
.b
.whichfork
));
1467 * Log record values from the btree block.
1471 struct xfs_btree_cur
*cur
,
1477 xfs_trans_buf_set_type(cur
->bc_tp
, bp
, XFS_BLFT_BTREE_BUF
);
1478 xfs_trans_log_buf(cur
->bc_tp
, bp
,
1479 xfs_btree_rec_offset(cur
, first
),
1480 xfs_btree_rec_offset(cur
, last
+ 1) - 1);
1485 * Log block pointer fields from a btree block (nonleaf).
1489 struct xfs_btree_cur
*cur
, /* btree cursor */
1490 struct xfs_buf
*bp
, /* buffer containing btree block */
1491 int first
, /* index of first pointer to log */
1492 int last
) /* index of last pointer to log */
1496 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
1497 int level
= xfs_btree_get_level(block
);
1499 xfs_trans_buf_set_type(cur
->bc_tp
, bp
, XFS_BLFT_BTREE_BUF
);
1500 xfs_trans_log_buf(cur
->bc_tp
, bp
,
1501 xfs_btree_ptr_offset(cur
, first
, level
),
1502 xfs_btree_ptr_offset(cur
, last
+ 1, level
) - 1);
1504 xfs_trans_log_inode(cur
->bc_tp
, cur
->bc_private
.b
.ip
,
1505 xfs_ilog_fbroot(cur
->bc_private
.b
.whichfork
));
1511 * Log fields from a btree block header.
1514 xfs_btree_log_block(
1515 struct xfs_btree_cur
*cur
, /* btree cursor */
1516 struct xfs_buf
*bp
, /* buffer containing btree block */
1517 int fields
) /* mask of fields: XFS_BB_... */
1519 int first
; /* first byte offset logged */
1520 int last
; /* last byte offset logged */
1521 static const short soffsets
[] = { /* table of offsets (short) */
1522 offsetof(struct xfs_btree_block
, bb_magic
),
1523 offsetof(struct xfs_btree_block
, bb_level
),
1524 offsetof(struct xfs_btree_block
, bb_numrecs
),
1525 offsetof(struct xfs_btree_block
, bb_u
.s
.bb_leftsib
),
1526 offsetof(struct xfs_btree_block
, bb_u
.s
.bb_rightsib
),
1527 offsetof(struct xfs_btree_block
, bb_u
.s
.bb_blkno
),
1528 offsetof(struct xfs_btree_block
, bb_u
.s
.bb_lsn
),
1529 offsetof(struct xfs_btree_block
, bb_u
.s
.bb_uuid
),
1530 offsetof(struct xfs_btree_block
, bb_u
.s
.bb_owner
),
1531 offsetof(struct xfs_btree_block
, bb_u
.s
.bb_crc
),
1532 XFS_BTREE_SBLOCK_CRC_LEN
1534 static const short loffsets
[] = { /* table of offsets (long) */
1535 offsetof(struct xfs_btree_block
, bb_magic
),
1536 offsetof(struct xfs_btree_block
, bb_level
),
1537 offsetof(struct xfs_btree_block
, bb_numrecs
),
1538 offsetof(struct xfs_btree_block
, bb_u
.l
.bb_leftsib
),
1539 offsetof(struct xfs_btree_block
, bb_u
.l
.bb_rightsib
),
1540 offsetof(struct xfs_btree_block
, bb_u
.l
.bb_blkno
),
1541 offsetof(struct xfs_btree_block
, bb_u
.l
.bb_lsn
),
1542 offsetof(struct xfs_btree_block
, bb_u
.l
.bb_uuid
),
1543 offsetof(struct xfs_btree_block
, bb_u
.l
.bb_owner
),
1544 offsetof(struct xfs_btree_block
, bb_u
.l
.bb_crc
),
1545 offsetof(struct xfs_btree_block
, bb_u
.l
.bb_pad
),
1546 XFS_BTREE_LBLOCK_CRC_LEN
1552 if (cur
->bc_flags
& XFS_BTREE_CRC_BLOCKS
) {
1554 * We don't log the CRC when updating a btree
1555 * block but instead recreate it during log
1556 * recovery. As the log buffers have checksums
1557 * of their own this is safe and avoids logging a crc
1558 * update in a lot of places.
1560 if (fields
== XFS_BB_ALL_BITS
)
1561 fields
= XFS_BB_ALL_BITS_CRC
;
1562 nbits
= XFS_BB_NUM_BITS_CRC
;
1564 nbits
= XFS_BB_NUM_BITS
;
1566 xfs_btree_offsets(fields
,
1567 (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
) ?
1568 loffsets
: soffsets
,
1569 nbits
, &first
, &last
);
1570 xfs_trans_buf_set_type(cur
->bc_tp
, bp
, XFS_BLFT_BTREE_BUF
);
1571 xfs_trans_log_buf(cur
->bc_tp
, bp
, first
, last
);
1573 xfs_trans_log_inode(cur
->bc_tp
, cur
->bc_private
.b
.ip
,
1574 xfs_ilog_fbroot(cur
->bc_private
.b
.whichfork
));
1579 * Increment cursor by one record at the level.
1580 * For nonzero levels the leaf-ward information is untouched.
1583 xfs_btree_increment(
1584 struct xfs_btree_cur
*cur
,
1586 int *stat
) /* success/failure */
1588 struct xfs_btree_block
*block
;
1589 union xfs_btree_ptr ptr
;
1591 int error
; /* error return value */
1594 ASSERT(level
< cur
->bc_nlevels
);
1596 /* Read-ahead to the right at this level. */
1597 xfs_btree_readahead(cur
, level
, XFS_BTCUR_RIGHTRA
);
1599 /* Get a pointer to the btree block. */
1600 block
= xfs_btree_get_block(cur
, level
, &bp
);
1603 error
= xfs_btree_check_block(cur
, block
, level
, bp
);
1608 /* We're done if we remain in the block after the increment. */
1609 if (++cur
->bc_ptrs
[level
] <= xfs_btree_get_numrecs(block
))
1612 /* Fail if we just went off the right edge of the tree. */
1613 xfs_btree_get_sibling(cur
, block
, &ptr
, XFS_BB_RIGHTSIB
);
1614 if (xfs_btree_ptr_is_null(cur
, &ptr
))
1617 XFS_BTREE_STATS_INC(cur
, increment
);
1620 * March up the tree incrementing pointers.
1621 * Stop when we don't go off the right edge of a block.
1623 for (lev
= level
+ 1; lev
< cur
->bc_nlevels
; lev
++) {
1624 block
= xfs_btree_get_block(cur
, lev
, &bp
);
1627 error
= xfs_btree_check_block(cur
, block
, lev
, bp
);
1632 if (++cur
->bc_ptrs
[lev
] <= xfs_btree_get_numrecs(block
))
1635 /* Read-ahead the right block for the next loop. */
1636 xfs_btree_readahead(cur
, lev
, XFS_BTCUR_RIGHTRA
);
1640 * If we went off the root then we are either seriously
1641 * confused or have the tree root in an inode.
1643 if (lev
== cur
->bc_nlevels
) {
1644 if (cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
)
1647 error
= -EFSCORRUPTED
;
1650 ASSERT(lev
< cur
->bc_nlevels
);
1653 * Now walk back down the tree, fixing up the cursor's buffer
1654 * pointers and key numbers.
1656 for (block
= xfs_btree_get_block(cur
, lev
, &bp
); lev
> level
; ) {
1657 union xfs_btree_ptr
*ptrp
;
1659 ptrp
= xfs_btree_ptr_addr(cur
, cur
->bc_ptrs
[lev
], block
);
1661 error
= xfs_btree_read_buf_block(cur
, ptrp
, 0, &block
, &bp
);
1665 xfs_btree_setbuf(cur
, lev
, bp
);
1666 cur
->bc_ptrs
[lev
] = 1;
1681 * Decrement cursor by one record at the level.
1682 * For nonzero levels the leaf-ward information is untouched.
1685 xfs_btree_decrement(
1686 struct xfs_btree_cur
*cur
,
1688 int *stat
) /* success/failure */
1690 struct xfs_btree_block
*block
;
1692 int error
; /* error return value */
1694 union xfs_btree_ptr ptr
;
1696 ASSERT(level
< cur
->bc_nlevels
);
1698 /* Read-ahead to the left at this level. */
1699 xfs_btree_readahead(cur
, level
, XFS_BTCUR_LEFTRA
);
1701 /* We're done if we remain in the block after the decrement. */
1702 if (--cur
->bc_ptrs
[level
] > 0)
1705 /* Get a pointer to the btree block. */
1706 block
= xfs_btree_get_block(cur
, level
, &bp
);
1709 error
= xfs_btree_check_block(cur
, block
, level
, bp
);
1714 /* Fail if we just went off the left edge of the tree. */
1715 xfs_btree_get_sibling(cur
, block
, &ptr
, XFS_BB_LEFTSIB
);
1716 if (xfs_btree_ptr_is_null(cur
, &ptr
))
1719 XFS_BTREE_STATS_INC(cur
, decrement
);
1722 * March up the tree decrementing pointers.
1723 * Stop when we don't go off the left edge of a block.
1725 for (lev
= level
+ 1; lev
< cur
->bc_nlevels
; lev
++) {
1726 if (--cur
->bc_ptrs
[lev
] > 0)
1728 /* Read-ahead the left block for the next loop. */
1729 xfs_btree_readahead(cur
, lev
, XFS_BTCUR_LEFTRA
);
1733 * If we went off the root then we are seriously confused.
1734 * or the root of the tree is in an inode.
1736 if (lev
== cur
->bc_nlevels
) {
1737 if (cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
)
1740 error
= -EFSCORRUPTED
;
1743 ASSERT(lev
< cur
->bc_nlevels
);
1746 * Now walk back down the tree, fixing up the cursor's buffer
1747 * pointers and key numbers.
1749 for (block
= xfs_btree_get_block(cur
, lev
, &bp
); lev
> level
; ) {
1750 union xfs_btree_ptr
*ptrp
;
1752 ptrp
= xfs_btree_ptr_addr(cur
, cur
->bc_ptrs
[lev
], block
);
1754 error
= xfs_btree_read_buf_block(cur
, ptrp
, 0, &block
, &bp
);
1757 xfs_btree_setbuf(cur
, lev
, bp
);
1758 cur
->bc_ptrs
[lev
] = xfs_btree_get_numrecs(block
);
1773 xfs_btree_lookup_get_block(
1774 struct xfs_btree_cur
*cur
, /* btree cursor */
1775 int level
, /* level in the btree */
1776 union xfs_btree_ptr
*pp
, /* ptr to btree block */
1777 struct xfs_btree_block
**blkp
) /* return btree block */
1779 struct xfs_buf
*bp
; /* buffer pointer for btree block */
1783 /* special case the root block if in an inode */
1784 if ((cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
) &&
1785 (level
== cur
->bc_nlevels
- 1)) {
1786 *blkp
= xfs_btree_get_iroot(cur
);
1791 * If the old buffer at this level for the disk address we are
1792 * looking for re-use it.
1794 * Otherwise throw it away and get a new one.
1796 bp
= cur
->bc_bufs
[level
];
1797 error
= xfs_btree_ptr_to_daddr(cur
, pp
, &daddr
);
1800 if (bp
&& XFS_BUF_ADDR(bp
) == daddr
) {
1801 *blkp
= XFS_BUF_TO_BLOCK(bp
);
1805 error
= xfs_btree_read_buf_block(cur
, pp
, 0, blkp
, &bp
);
1809 /* Check the inode owner since the verifiers don't. */
1810 if (xfs_sb_version_hascrc(&cur
->bc_mp
->m_sb
) &&
1811 !(cur
->bc_private
.b
.flags
& XFS_BTCUR_BPRV_INVALID_OWNER
) &&
1812 (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
) &&
1813 be64_to_cpu((*blkp
)->bb_u
.l
.bb_owner
) !=
1814 cur
->bc_private
.b
.ip
->i_ino
)
1817 /* Did we get the level we were looking for? */
1818 if (be16_to_cpu((*blkp
)->bb_level
) != level
)
1821 /* Check that internal nodes have at least one record. */
1822 if (level
!= 0 && be16_to_cpu((*blkp
)->bb_numrecs
) == 0)
1825 xfs_btree_setbuf(cur
, level
, bp
);
1830 xfs_trans_brelse(cur
->bc_tp
, bp
);
1831 return -EFSCORRUPTED
;
1835 * Get current search key. For level 0 we don't actually have a key
1836 * structure so we make one up from the record. For all other levels
1837 * we just return the right key.
1839 STATIC
union xfs_btree_key
*
1840 xfs_lookup_get_search_key(
1841 struct xfs_btree_cur
*cur
,
1844 struct xfs_btree_block
*block
,
1845 union xfs_btree_key
*kp
)
1848 cur
->bc_ops
->init_key_from_rec(kp
,
1849 xfs_btree_rec_addr(cur
, keyno
, block
));
1853 return xfs_btree_key_addr(cur
, keyno
, block
);
1857 * Lookup the record. The cursor is made to point to it, based on dir.
1858 * stat is set to 0 if can't find any such record, 1 for success.
1862 struct xfs_btree_cur
*cur
, /* btree cursor */
1863 xfs_lookup_t dir
, /* <=, ==, or >= */
1864 int *stat
) /* success/failure */
1866 struct xfs_btree_block
*block
; /* current btree block */
1867 int64_t diff
; /* difference for the current key */
1868 int error
; /* error return value */
1869 int keyno
; /* current key number */
1870 int level
; /* level in the btree */
1871 union xfs_btree_ptr
*pp
; /* ptr to btree block */
1872 union xfs_btree_ptr ptr
; /* ptr to btree block */
1874 XFS_BTREE_STATS_INC(cur
, lookup
);
1876 /* No such thing as a zero-level tree. */
1877 if (cur
->bc_nlevels
== 0)
1878 return -EFSCORRUPTED
;
1883 /* initialise start pointer from cursor */
1884 cur
->bc_ops
->init_ptr_from_cur(cur
, &ptr
);
1888 * Iterate over each level in the btree, starting at the root.
1889 * For each level above the leaves, find the key we need, based
1890 * on the lookup record, then follow the corresponding block
1891 * pointer down to the next level.
1893 for (level
= cur
->bc_nlevels
- 1, diff
= 1; level
>= 0; level
--) {
1894 /* Get the block we need to do the lookup on. */
1895 error
= xfs_btree_lookup_get_block(cur
, level
, pp
, &block
);
1901 * If we already had a key match at a higher level, we
1902 * know we need to use the first entry in this block.
1906 /* Otherwise search this block. Do a binary search. */
1908 int high
; /* high entry number */
1909 int low
; /* low entry number */
1911 /* Set low and high entry numbers, 1-based. */
1913 high
= xfs_btree_get_numrecs(block
);
1915 /* Block is empty, must be an empty leaf. */
1916 if (level
!= 0 || cur
->bc_nlevels
!= 1) {
1917 XFS_CORRUPTION_ERROR(__func__
,
1921 return -EFSCORRUPTED
;
1924 cur
->bc_ptrs
[0] = dir
!= XFS_LOOKUP_LE
;
1929 /* Binary search the block. */
1930 while (low
<= high
) {
1931 union xfs_btree_key key
;
1932 union xfs_btree_key
*kp
;
1934 XFS_BTREE_STATS_INC(cur
, compare
);
1936 /* keyno is average of low and high. */
1937 keyno
= (low
+ high
) >> 1;
1939 /* Get current search key */
1940 kp
= xfs_lookup_get_search_key(cur
, level
,
1941 keyno
, block
, &key
);
1944 * Compute difference to get next direction:
1945 * - less than, move right
1946 * - greater than, move left
1947 * - equal, we're done
1949 diff
= cur
->bc_ops
->key_diff(cur
, kp
);
1960 * If there are more levels, set up for the next level
1961 * by getting the block number and filling in the cursor.
1965 * If we moved left, need the previous key number,
1966 * unless there isn't one.
1968 if (diff
> 0 && --keyno
< 1)
1970 pp
= xfs_btree_ptr_addr(cur
, keyno
, block
);
1972 error
= xfs_btree_debug_check_ptr(cur
, pp
, 0, level
);
1976 cur
->bc_ptrs
[level
] = keyno
;
1980 /* Done with the search. See if we need to adjust the results. */
1981 if (dir
!= XFS_LOOKUP_LE
&& diff
< 0) {
1984 * If ge search and we went off the end of the block, but it's
1985 * not the last block, we're in the wrong block.
1987 xfs_btree_get_sibling(cur
, block
, &ptr
, XFS_BB_RIGHTSIB
);
1988 if (dir
== XFS_LOOKUP_GE
&&
1989 keyno
> xfs_btree_get_numrecs(block
) &&
1990 !xfs_btree_ptr_is_null(cur
, &ptr
)) {
1993 cur
->bc_ptrs
[0] = keyno
;
1994 error
= xfs_btree_increment(cur
, 0, &i
);
1997 XFS_WANT_CORRUPTED_RETURN(cur
->bc_mp
, i
== 1);
2001 } else if (dir
== XFS_LOOKUP_LE
&& diff
> 0)
2003 cur
->bc_ptrs
[0] = keyno
;
2005 /* Return if we succeeded or not. */
2006 if (keyno
== 0 || keyno
> xfs_btree_get_numrecs(block
))
2008 else if (dir
!= XFS_LOOKUP_EQ
|| diff
== 0)
2018 /* Find the high key storage area from a regular key. */
2019 union xfs_btree_key
*
2020 xfs_btree_high_key_from_key(
2021 struct xfs_btree_cur
*cur
,
2022 union xfs_btree_key
*key
)
2024 ASSERT(cur
->bc_flags
& XFS_BTREE_OVERLAPPING
);
2025 return (union xfs_btree_key
*)((char *)key
+
2026 (cur
->bc_ops
->key_len
/ 2));
2029 /* Determine the low (and high if overlapped) keys of a leaf block */
2031 xfs_btree_get_leaf_keys(
2032 struct xfs_btree_cur
*cur
,
2033 struct xfs_btree_block
*block
,
2034 union xfs_btree_key
*key
)
2036 union xfs_btree_key max_hkey
;
2037 union xfs_btree_key hkey
;
2038 union xfs_btree_rec
*rec
;
2039 union xfs_btree_key
*high
;
2042 rec
= xfs_btree_rec_addr(cur
, 1, block
);
2043 cur
->bc_ops
->init_key_from_rec(key
, rec
);
2045 if (cur
->bc_flags
& XFS_BTREE_OVERLAPPING
) {
2047 cur
->bc_ops
->init_high_key_from_rec(&max_hkey
, rec
);
2048 for (n
= 2; n
<= xfs_btree_get_numrecs(block
); n
++) {
2049 rec
= xfs_btree_rec_addr(cur
, n
, block
);
2050 cur
->bc_ops
->init_high_key_from_rec(&hkey
, rec
);
2051 if (cur
->bc_ops
->diff_two_keys(cur
, &hkey
, &max_hkey
)
2056 high
= xfs_btree_high_key_from_key(cur
, key
);
2057 memcpy(high
, &max_hkey
, cur
->bc_ops
->key_len
/ 2);
2061 /* Determine the low (and high if overlapped) keys of a node block */
2063 xfs_btree_get_node_keys(
2064 struct xfs_btree_cur
*cur
,
2065 struct xfs_btree_block
*block
,
2066 union xfs_btree_key
*key
)
2068 union xfs_btree_key
*hkey
;
2069 union xfs_btree_key
*max_hkey
;
2070 union xfs_btree_key
*high
;
2073 if (cur
->bc_flags
& XFS_BTREE_OVERLAPPING
) {
2074 memcpy(key
, xfs_btree_key_addr(cur
, 1, block
),
2075 cur
->bc_ops
->key_len
/ 2);
2077 max_hkey
= xfs_btree_high_key_addr(cur
, 1, block
);
2078 for (n
= 2; n
<= xfs_btree_get_numrecs(block
); n
++) {
2079 hkey
= xfs_btree_high_key_addr(cur
, n
, block
);
2080 if (cur
->bc_ops
->diff_two_keys(cur
, hkey
, max_hkey
) > 0)
2084 high
= xfs_btree_high_key_from_key(cur
, key
);
2085 memcpy(high
, max_hkey
, cur
->bc_ops
->key_len
/ 2);
2087 memcpy(key
, xfs_btree_key_addr(cur
, 1, block
),
2088 cur
->bc_ops
->key_len
);
2092 /* Derive the keys for any btree block. */
2095 struct xfs_btree_cur
*cur
,
2096 struct xfs_btree_block
*block
,
2097 union xfs_btree_key
*key
)
2099 if (be16_to_cpu(block
->bb_level
) == 0)
2100 xfs_btree_get_leaf_keys(cur
, block
, key
);
2102 xfs_btree_get_node_keys(cur
, block
, key
);
2106 * Decide if we need to update the parent keys of a btree block. For
2107 * a standard btree this is only necessary if we're updating the first
2108 * record/key. For an overlapping btree, we must always update the
2109 * keys because the highest key can be in any of the records or keys
2113 xfs_btree_needs_key_update(
2114 struct xfs_btree_cur
*cur
,
2117 return (cur
->bc_flags
& XFS_BTREE_OVERLAPPING
) || ptr
== 1;
2121 * Update the low and high parent keys of the given level, progressing
2122 * towards the root. If force_all is false, stop if the keys for a given
2123 * level do not need updating.
2126 __xfs_btree_updkeys(
2127 struct xfs_btree_cur
*cur
,
2129 struct xfs_btree_block
*block
,
2130 struct xfs_buf
*bp0
,
2133 union xfs_btree_key key
; /* keys from current level */
2134 union xfs_btree_key
*lkey
; /* keys from the next level up */
2135 union xfs_btree_key
*hkey
;
2136 union xfs_btree_key
*nlkey
; /* keys from the next level up */
2137 union xfs_btree_key
*nhkey
;
2141 ASSERT(cur
->bc_flags
& XFS_BTREE_OVERLAPPING
);
2143 /* Exit if there aren't any parent levels to update. */
2144 if (level
+ 1 >= cur
->bc_nlevels
)
2147 trace_xfs_btree_updkeys(cur
, level
, bp0
);
2150 hkey
= xfs_btree_high_key_from_key(cur
, lkey
);
2151 xfs_btree_get_keys(cur
, block
, lkey
);
2152 for (level
++; level
< cur
->bc_nlevels
; level
++) {
2156 block
= xfs_btree_get_block(cur
, level
, &bp
);
2157 trace_xfs_btree_updkeys(cur
, level
, bp
);
2159 error
= xfs_btree_check_block(cur
, block
, level
, bp
);
2163 ptr
= cur
->bc_ptrs
[level
];
2164 nlkey
= xfs_btree_key_addr(cur
, ptr
, block
);
2165 nhkey
= xfs_btree_high_key_addr(cur
, ptr
, block
);
2167 !(cur
->bc_ops
->diff_two_keys(cur
, nlkey
, lkey
) != 0 ||
2168 cur
->bc_ops
->diff_two_keys(cur
, nhkey
, hkey
) != 0))
2170 xfs_btree_copy_keys(cur
, nlkey
, lkey
, 1);
2171 xfs_btree_log_keys(cur
, bp
, ptr
, ptr
);
2172 if (level
+ 1 >= cur
->bc_nlevels
)
2174 xfs_btree_get_node_keys(cur
, block
, lkey
);
2180 /* Update all the keys from some level in cursor back to the root. */
2182 xfs_btree_updkeys_force(
2183 struct xfs_btree_cur
*cur
,
2187 struct xfs_btree_block
*block
;
2189 block
= xfs_btree_get_block(cur
, level
, &bp
);
2190 return __xfs_btree_updkeys(cur
, level
, block
, bp
, true);
2194 * Update the parent keys of the given level, progressing towards the root.
2197 xfs_btree_update_keys(
2198 struct xfs_btree_cur
*cur
,
2201 struct xfs_btree_block
*block
;
2203 union xfs_btree_key
*kp
;
2204 union xfs_btree_key key
;
2209 block
= xfs_btree_get_block(cur
, level
, &bp
);
2210 if (cur
->bc_flags
& XFS_BTREE_OVERLAPPING
)
2211 return __xfs_btree_updkeys(cur
, level
, block
, bp
, false);
2214 * Go up the tree from this level toward the root.
2215 * At each level, update the key value to the value input.
2216 * Stop when we reach a level where the cursor isn't pointing
2217 * at the first entry in the block.
2219 xfs_btree_get_keys(cur
, block
, &key
);
2220 for (level
++, ptr
= 1; ptr
== 1 && level
< cur
->bc_nlevels
; level
++) {
2224 block
= xfs_btree_get_block(cur
, level
, &bp
);
2226 error
= xfs_btree_check_block(cur
, block
, level
, bp
);
2230 ptr
= cur
->bc_ptrs
[level
];
2231 kp
= xfs_btree_key_addr(cur
, ptr
, block
);
2232 xfs_btree_copy_keys(cur
, kp
, &key
, 1);
2233 xfs_btree_log_keys(cur
, bp
, ptr
, ptr
);
2240 * Update the record referred to by cur to the value in the
2241 * given record. This either works (return 0) or gets an
2242 * EFSCORRUPTED error.
2246 struct xfs_btree_cur
*cur
,
2247 union xfs_btree_rec
*rec
)
2249 struct xfs_btree_block
*block
;
2253 union xfs_btree_rec
*rp
;
2255 /* Pick up the current block. */
2256 block
= xfs_btree_get_block(cur
, 0, &bp
);
2259 error
= xfs_btree_check_block(cur
, block
, 0, bp
);
2263 /* Get the address of the rec to be updated. */
2264 ptr
= cur
->bc_ptrs
[0];
2265 rp
= xfs_btree_rec_addr(cur
, ptr
, block
);
2267 /* Fill in the new contents and log them. */
2268 xfs_btree_copy_recs(cur
, rp
, rec
, 1);
2269 xfs_btree_log_recs(cur
, bp
, ptr
, ptr
);
2272 * If we are tracking the last record in the tree and
2273 * we are at the far right edge of the tree, update it.
2275 if (xfs_btree_is_lastrec(cur
, block
, 0)) {
2276 cur
->bc_ops
->update_lastrec(cur
, block
, rec
,
2277 ptr
, LASTREC_UPDATE
);
2280 /* Pass new key value up to our parent. */
2281 if (xfs_btree_needs_key_update(cur
, ptr
)) {
2282 error
= xfs_btree_update_keys(cur
, 0);
2294 * Move 1 record left from cur/level if possible.
2295 * Update cur to reflect the new path.
2297 STATIC
int /* error */
2299 struct xfs_btree_cur
*cur
,
2301 int *stat
) /* success/failure */
2303 struct xfs_buf
*lbp
; /* left buffer pointer */
2304 struct xfs_btree_block
*left
; /* left btree block */
2305 int lrecs
; /* left record count */
2306 struct xfs_buf
*rbp
; /* right buffer pointer */
2307 struct xfs_btree_block
*right
; /* right btree block */
2308 struct xfs_btree_cur
*tcur
; /* temporary btree cursor */
2309 int rrecs
; /* right record count */
2310 union xfs_btree_ptr lptr
; /* left btree pointer */
2311 union xfs_btree_key
*rkp
= NULL
; /* right btree key */
2312 union xfs_btree_ptr
*rpp
= NULL
; /* right address pointer */
2313 union xfs_btree_rec
*rrp
= NULL
; /* right record pointer */
2314 int error
; /* error return value */
2317 if ((cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
) &&
2318 level
== cur
->bc_nlevels
- 1)
2321 /* Set up variables for this block as "right". */
2322 right
= xfs_btree_get_block(cur
, level
, &rbp
);
2325 error
= xfs_btree_check_block(cur
, right
, level
, rbp
);
2330 /* If we've got no left sibling then we can't shift an entry left. */
2331 xfs_btree_get_sibling(cur
, right
, &lptr
, XFS_BB_LEFTSIB
);
2332 if (xfs_btree_ptr_is_null(cur
, &lptr
))
2336 * If the cursor entry is the one that would be moved, don't
2337 * do it... it's too complicated.
2339 if (cur
->bc_ptrs
[level
] <= 1)
2342 /* Set up the left neighbor as "left". */
2343 error
= xfs_btree_read_buf_block(cur
, &lptr
, 0, &left
, &lbp
);
2347 /* If it's full, it can't take another entry. */
2348 lrecs
= xfs_btree_get_numrecs(left
);
2349 if (lrecs
== cur
->bc_ops
->get_maxrecs(cur
, level
))
2352 rrecs
= xfs_btree_get_numrecs(right
);
2355 * We add one entry to the left side and remove one for the right side.
2356 * Account for it here, the changes will be updated on disk and logged
2362 XFS_BTREE_STATS_INC(cur
, lshift
);
2363 XFS_BTREE_STATS_ADD(cur
, moves
, 1);
2366 * If non-leaf, copy a key and a ptr to the left block.
2367 * Log the changes to the left block.
2370 /* It's a non-leaf. Move keys and pointers. */
2371 union xfs_btree_key
*lkp
; /* left btree key */
2372 union xfs_btree_ptr
*lpp
; /* left address pointer */
2374 lkp
= xfs_btree_key_addr(cur
, lrecs
, left
);
2375 rkp
= xfs_btree_key_addr(cur
, 1, right
);
2377 lpp
= xfs_btree_ptr_addr(cur
, lrecs
, left
);
2378 rpp
= xfs_btree_ptr_addr(cur
, 1, right
);
2380 error
= xfs_btree_debug_check_ptr(cur
, rpp
, 0, level
);
2384 xfs_btree_copy_keys(cur
, lkp
, rkp
, 1);
2385 xfs_btree_copy_ptrs(cur
, lpp
, rpp
, 1);
2387 xfs_btree_log_keys(cur
, lbp
, lrecs
, lrecs
);
2388 xfs_btree_log_ptrs(cur
, lbp
, lrecs
, lrecs
);
2390 ASSERT(cur
->bc_ops
->keys_inorder(cur
,
2391 xfs_btree_key_addr(cur
, lrecs
- 1, left
), lkp
));
2393 /* It's a leaf. Move records. */
2394 union xfs_btree_rec
*lrp
; /* left record pointer */
2396 lrp
= xfs_btree_rec_addr(cur
, lrecs
, left
);
2397 rrp
= xfs_btree_rec_addr(cur
, 1, right
);
2399 xfs_btree_copy_recs(cur
, lrp
, rrp
, 1);
2400 xfs_btree_log_recs(cur
, lbp
, lrecs
, lrecs
);
2402 ASSERT(cur
->bc_ops
->recs_inorder(cur
,
2403 xfs_btree_rec_addr(cur
, lrecs
- 1, left
), lrp
));
2406 xfs_btree_set_numrecs(left
, lrecs
);
2407 xfs_btree_log_block(cur
, lbp
, XFS_BB_NUMRECS
);
2409 xfs_btree_set_numrecs(right
, rrecs
);
2410 xfs_btree_log_block(cur
, rbp
, XFS_BB_NUMRECS
);
2413 * Slide the contents of right down one entry.
2415 XFS_BTREE_STATS_ADD(cur
, moves
, rrecs
- 1);
2417 /* It's a nonleaf. operate on keys and ptrs */
2418 int i
; /* loop index */
2420 for (i
= 0; i
< rrecs
; i
++) {
2421 error
= xfs_btree_debug_check_ptr(cur
, rpp
, i
+ 1, level
);
2426 xfs_btree_shift_keys(cur
,
2427 xfs_btree_key_addr(cur
, 2, right
),
2429 xfs_btree_shift_ptrs(cur
,
2430 xfs_btree_ptr_addr(cur
, 2, right
),
2433 xfs_btree_log_keys(cur
, rbp
, 1, rrecs
);
2434 xfs_btree_log_ptrs(cur
, rbp
, 1, rrecs
);
2436 /* It's a leaf. operate on records */
2437 xfs_btree_shift_recs(cur
,
2438 xfs_btree_rec_addr(cur
, 2, right
),
2440 xfs_btree_log_recs(cur
, rbp
, 1, rrecs
);
2444 * Using a temporary cursor, update the parent key values of the
2445 * block on the left.
2447 if (cur
->bc_flags
& XFS_BTREE_OVERLAPPING
) {
2448 error
= xfs_btree_dup_cursor(cur
, &tcur
);
2451 i
= xfs_btree_firstrec(tcur
, level
);
2452 XFS_WANT_CORRUPTED_GOTO(tcur
->bc_mp
, i
== 1, error0
);
2454 error
= xfs_btree_decrement(tcur
, level
, &i
);
2458 /* Update the parent high keys of the left block, if needed. */
2459 error
= xfs_btree_update_keys(tcur
, level
);
2463 xfs_btree_del_cursor(tcur
, XFS_BTREE_NOERROR
);
2466 /* Update the parent keys of the right block. */
2467 error
= xfs_btree_update_keys(cur
, level
);
2471 /* Slide the cursor value left one. */
2472 cur
->bc_ptrs
[level
]--;
2485 xfs_btree_del_cursor(tcur
, XFS_BTREE_ERROR
);
2490 * Move 1 record right from cur/level if possible.
2491 * Update cur to reflect the new path.
2493 STATIC
int /* error */
2495 struct xfs_btree_cur
*cur
,
2497 int *stat
) /* success/failure */
2499 struct xfs_buf
*lbp
; /* left buffer pointer */
2500 struct xfs_btree_block
*left
; /* left btree block */
2501 struct xfs_buf
*rbp
; /* right buffer pointer */
2502 struct xfs_btree_block
*right
; /* right btree block */
2503 struct xfs_btree_cur
*tcur
; /* temporary btree cursor */
2504 union xfs_btree_ptr rptr
; /* right block pointer */
2505 union xfs_btree_key
*rkp
; /* right btree key */
2506 int rrecs
; /* right record count */
2507 int lrecs
; /* left record count */
2508 int error
; /* error return value */
2509 int i
; /* loop counter */
2511 if ((cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
) &&
2512 (level
== cur
->bc_nlevels
- 1))
2515 /* Set up variables for this block as "left". */
2516 left
= xfs_btree_get_block(cur
, level
, &lbp
);
2519 error
= xfs_btree_check_block(cur
, left
, level
, lbp
);
2524 /* If we've got no right sibling then we can't shift an entry right. */
2525 xfs_btree_get_sibling(cur
, left
, &rptr
, XFS_BB_RIGHTSIB
);
2526 if (xfs_btree_ptr_is_null(cur
, &rptr
))
2530 * If the cursor entry is the one that would be moved, don't
2531 * do it... it's too complicated.
2533 lrecs
= xfs_btree_get_numrecs(left
);
2534 if (cur
->bc_ptrs
[level
] >= lrecs
)
2537 /* Set up the right neighbor as "right". */
2538 error
= xfs_btree_read_buf_block(cur
, &rptr
, 0, &right
, &rbp
);
2542 /* If it's full, it can't take another entry. */
2543 rrecs
= xfs_btree_get_numrecs(right
);
2544 if (rrecs
== cur
->bc_ops
->get_maxrecs(cur
, level
))
2547 XFS_BTREE_STATS_INC(cur
, rshift
);
2548 XFS_BTREE_STATS_ADD(cur
, moves
, rrecs
);
2551 * Make a hole at the start of the right neighbor block, then
2552 * copy the last left block entry to the hole.
2555 /* It's a nonleaf. make a hole in the keys and ptrs */
2556 union xfs_btree_key
*lkp
;
2557 union xfs_btree_ptr
*lpp
;
2558 union xfs_btree_ptr
*rpp
;
2560 lkp
= xfs_btree_key_addr(cur
, lrecs
, left
);
2561 lpp
= xfs_btree_ptr_addr(cur
, lrecs
, left
);
2562 rkp
= xfs_btree_key_addr(cur
, 1, right
);
2563 rpp
= xfs_btree_ptr_addr(cur
, 1, right
);
2565 for (i
= rrecs
- 1; i
>= 0; i
--) {
2566 error
= xfs_btree_debug_check_ptr(cur
, rpp
, i
, level
);
2571 xfs_btree_shift_keys(cur
, rkp
, 1, rrecs
);
2572 xfs_btree_shift_ptrs(cur
, rpp
, 1, rrecs
);
2574 error
= xfs_btree_debug_check_ptr(cur
, lpp
, 0, level
);
2578 /* Now put the new data in, and log it. */
2579 xfs_btree_copy_keys(cur
, rkp
, lkp
, 1);
2580 xfs_btree_copy_ptrs(cur
, rpp
, lpp
, 1);
2582 xfs_btree_log_keys(cur
, rbp
, 1, rrecs
+ 1);
2583 xfs_btree_log_ptrs(cur
, rbp
, 1, rrecs
+ 1);
2585 ASSERT(cur
->bc_ops
->keys_inorder(cur
, rkp
,
2586 xfs_btree_key_addr(cur
, 2, right
)));
2588 /* It's a leaf. make a hole in the records */
2589 union xfs_btree_rec
*lrp
;
2590 union xfs_btree_rec
*rrp
;
2592 lrp
= xfs_btree_rec_addr(cur
, lrecs
, left
);
2593 rrp
= xfs_btree_rec_addr(cur
, 1, right
);
2595 xfs_btree_shift_recs(cur
, rrp
, 1, rrecs
);
2597 /* Now put the new data in, and log it. */
2598 xfs_btree_copy_recs(cur
, rrp
, lrp
, 1);
2599 xfs_btree_log_recs(cur
, rbp
, 1, rrecs
+ 1);
2603 * Decrement and log left's numrecs, bump and log right's numrecs.
2605 xfs_btree_set_numrecs(left
, --lrecs
);
2606 xfs_btree_log_block(cur
, lbp
, XFS_BB_NUMRECS
);
2608 xfs_btree_set_numrecs(right
, ++rrecs
);
2609 xfs_btree_log_block(cur
, rbp
, XFS_BB_NUMRECS
);
2612 * Using a temporary cursor, update the parent key values of the
2613 * block on the right.
2615 error
= xfs_btree_dup_cursor(cur
, &tcur
);
2618 i
= xfs_btree_lastrec(tcur
, level
);
2619 XFS_WANT_CORRUPTED_GOTO(tcur
->bc_mp
, i
== 1, error0
);
2621 error
= xfs_btree_increment(tcur
, level
, &i
);
2625 /* Update the parent high keys of the left block, if needed. */
2626 if (cur
->bc_flags
& XFS_BTREE_OVERLAPPING
) {
2627 error
= xfs_btree_update_keys(cur
, level
);
2632 /* Update the parent keys of the right block. */
2633 error
= xfs_btree_update_keys(tcur
, level
);
2637 xfs_btree_del_cursor(tcur
, XFS_BTREE_NOERROR
);
2650 xfs_btree_del_cursor(tcur
, XFS_BTREE_ERROR
);
2655 * Split cur/level block in half.
2656 * Return new block number and the key to its first
2657 * record (to be inserted into parent).
2659 STATIC
int /* error */
2661 struct xfs_btree_cur
*cur
,
2663 union xfs_btree_ptr
*ptrp
,
2664 union xfs_btree_key
*key
,
2665 struct xfs_btree_cur
**curp
,
2666 int *stat
) /* success/failure */
2668 union xfs_btree_ptr lptr
; /* left sibling block ptr */
2669 struct xfs_buf
*lbp
; /* left buffer pointer */
2670 struct xfs_btree_block
*left
; /* left btree block */
2671 union xfs_btree_ptr rptr
; /* right sibling block ptr */
2672 struct xfs_buf
*rbp
; /* right buffer pointer */
2673 struct xfs_btree_block
*right
; /* right btree block */
2674 union xfs_btree_ptr rrptr
; /* right-right sibling ptr */
2675 struct xfs_buf
*rrbp
; /* right-right buffer pointer */
2676 struct xfs_btree_block
*rrblock
; /* right-right btree block */
2680 int error
; /* error return value */
2683 XFS_BTREE_STATS_INC(cur
, split
);
2685 /* Set up left block (current one). */
2686 left
= xfs_btree_get_block(cur
, level
, &lbp
);
2689 error
= xfs_btree_check_block(cur
, left
, level
, lbp
);
2694 xfs_btree_buf_to_ptr(cur
, lbp
, &lptr
);
2696 /* Allocate the new block. If we can't do it, we're toast. Give up. */
2697 error
= cur
->bc_ops
->alloc_block(cur
, &lptr
, &rptr
, stat
);
2702 XFS_BTREE_STATS_INC(cur
, alloc
);
2704 /* Set up the new block as "right". */
2705 error
= xfs_btree_get_buf_block(cur
, &rptr
, 0, &right
, &rbp
);
2709 /* Fill in the btree header for the new right block. */
2710 xfs_btree_init_block_cur(cur
, rbp
, xfs_btree_get_level(left
), 0);
2713 * Split the entries between the old and the new block evenly.
2714 * Make sure that if there's an odd number of entries now, that
2715 * each new block will have the same number of entries.
2717 lrecs
= xfs_btree_get_numrecs(left
);
2719 if ((lrecs
& 1) && cur
->bc_ptrs
[level
] <= rrecs
+ 1)
2721 src_index
= (lrecs
- rrecs
+ 1);
2723 XFS_BTREE_STATS_ADD(cur
, moves
, rrecs
);
2725 /* Adjust numrecs for the later get_*_keys() calls. */
2727 xfs_btree_set_numrecs(left
, lrecs
);
2728 xfs_btree_set_numrecs(right
, xfs_btree_get_numrecs(right
) + rrecs
);
2731 * Copy btree block entries from the left block over to the
2732 * new block, the right. Update the right block and log the
2736 /* It's a non-leaf. Move keys and pointers. */
2737 union xfs_btree_key
*lkp
; /* left btree key */
2738 union xfs_btree_ptr
*lpp
; /* left address pointer */
2739 union xfs_btree_key
*rkp
; /* right btree key */
2740 union xfs_btree_ptr
*rpp
; /* right address pointer */
2742 lkp
= xfs_btree_key_addr(cur
, src_index
, left
);
2743 lpp
= xfs_btree_ptr_addr(cur
, src_index
, left
);
2744 rkp
= xfs_btree_key_addr(cur
, 1, right
);
2745 rpp
= xfs_btree_ptr_addr(cur
, 1, right
);
2747 for (i
= src_index
; i
< rrecs
; i
++) {
2748 error
= xfs_btree_debug_check_ptr(cur
, lpp
, i
, level
);
2753 /* Copy the keys & pointers to the new block. */
2754 xfs_btree_copy_keys(cur
, rkp
, lkp
, rrecs
);
2755 xfs_btree_copy_ptrs(cur
, rpp
, lpp
, rrecs
);
2757 xfs_btree_log_keys(cur
, rbp
, 1, rrecs
);
2758 xfs_btree_log_ptrs(cur
, rbp
, 1, rrecs
);
2760 /* Stash the keys of the new block for later insertion. */
2761 xfs_btree_get_node_keys(cur
, right
, key
);
2763 /* It's a leaf. Move records. */
2764 union xfs_btree_rec
*lrp
; /* left record pointer */
2765 union xfs_btree_rec
*rrp
; /* right record pointer */
2767 lrp
= xfs_btree_rec_addr(cur
, src_index
, left
);
2768 rrp
= xfs_btree_rec_addr(cur
, 1, right
);
2770 /* Copy records to the new block. */
2771 xfs_btree_copy_recs(cur
, rrp
, lrp
, rrecs
);
2772 xfs_btree_log_recs(cur
, rbp
, 1, rrecs
);
2774 /* Stash the keys of the new block for later insertion. */
2775 xfs_btree_get_leaf_keys(cur
, right
, key
);
2779 * Find the left block number by looking in the buffer.
2780 * Adjust sibling pointers.
2782 xfs_btree_get_sibling(cur
, left
, &rrptr
, XFS_BB_RIGHTSIB
);
2783 xfs_btree_set_sibling(cur
, right
, &rrptr
, XFS_BB_RIGHTSIB
);
2784 xfs_btree_set_sibling(cur
, right
, &lptr
, XFS_BB_LEFTSIB
);
2785 xfs_btree_set_sibling(cur
, left
, &rptr
, XFS_BB_RIGHTSIB
);
2787 xfs_btree_log_block(cur
, rbp
, XFS_BB_ALL_BITS
);
2788 xfs_btree_log_block(cur
, lbp
, XFS_BB_NUMRECS
| XFS_BB_RIGHTSIB
);
2791 * If there's a block to the new block's right, make that block
2792 * point back to right instead of to left.
2794 if (!xfs_btree_ptr_is_null(cur
, &rrptr
)) {
2795 error
= xfs_btree_read_buf_block(cur
, &rrptr
,
2796 0, &rrblock
, &rrbp
);
2799 xfs_btree_set_sibling(cur
, rrblock
, &rptr
, XFS_BB_LEFTSIB
);
2800 xfs_btree_log_block(cur
, rrbp
, XFS_BB_LEFTSIB
);
2803 /* Update the parent high keys of the left block, if needed. */
2804 if (cur
->bc_flags
& XFS_BTREE_OVERLAPPING
) {
2805 error
= xfs_btree_update_keys(cur
, level
);
2811 * If the cursor is really in the right block, move it there.
2812 * If it's just pointing past the last entry in left, then we'll
2813 * insert there, so don't change anything in that case.
2815 if (cur
->bc_ptrs
[level
] > lrecs
+ 1) {
2816 xfs_btree_setbuf(cur
, level
, rbp
);
2817 cur
->bc_ptrs
[level
] -= lrecs
;
2820 * If there are more levels, we'll need another cursor which refers
2821 * the right block, no matter where this cursor was.
2823 if (level
+ 1 < cur
->bc_nlevels
) {
2824 error
= xfs_btree_dup_cursor(cur
, curp
);
2827 (*curp
)->bc_ptrs
[level
+ 1]++;
2841 struct xfs_btree_split_args
{
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 bool kswapd
; /* allocation in kswapd context */
2850 struct completion
*done
;
2851 struct work_struct work
;
2855 * Stack switching interfaces for allocation
2858 xfs_btree_split_worker(
2859 struct work_struct
*work
)
2861 struct xfs_btree_split_args
*args
= container_of(work
,
2862 struct xfs_btree_split_args
, work
);
2863 unsigned long pflags
;
2864 unsigned long new_pflags
= PF_MEMALLOC_NOFS
;
2867 * we are in a transaction context here, but may also be doing work
2868 * in kswapd context, and hence we may need to inherit that state
2869 * temporarily to ensure that we don't block waiting for memory reclaim
2873 new_pflags
|= PF_MEMALLOC
| PF_SWAPWRITE
| PF_KSWAPD
;
2875 current_set_flags_nested(&pflags
, new_pflags
);
2877 args
->result
= __xfs_btree_split(args
->cur
, args
->level
, args
->ptrp
,
2878 args
->key
, args
->curp
, args
->stat
);
2879 complete(args
->done
);
2881 current_restore_flags_nested(&pflags
, new_pflags
);
2885 * BMBT split requests often come in with little stack to work on. Push
2886 * them off to a worker thread so there is lots of stack to use. For the other
2887 * btree types, just call directly to avoid the context switch overhead here.
2889 STATIC
int /* error */
2891 struct xfs_btree_cur
*cur
,
2893 union xfs_btree_ptr
*ptrp
,
2894 union xfs_btree_key
*key
,
2895 struct xfs_btree_cur
**curp
,
2896 int *stat
) /* success/failure */
2898 struct xfs_btree_split_args args
;
2899 DECLARE_COMPLETION_ONSTACK(done
);
2901 if (cur
->bc_btnum
!= XFS_BTNUM_BMAP
)
2902 return __xfs_btree_split(cur
, level
, ptrp
, key
, curp
, stat
);
2911 args
.kswapd
= current_is_kswapd();
2912 INIT_WORK_ONSTACK(&args
.work
, xfs_btree_split_worker
);
2913 queue_work(xfs_alloc_wq
, &args
.work
);
2914 wait_for_completion(&done
);
2915 destroy_work_on_stack(&args
.work
);
2919 #define xfs_btree_split __xfs_btree_split
2924 * Copy the old inode root contents into a real block and make the
2925 * broot point to it.
2928 xfs_btree_new_iroot(
2929 struct xfs_btree_cur
*cur
, /* btree cursor */
2930 int *logflags
, /* logging flags for inode */
2931 int *stat
) /* return status - 0 fail */
2933 struct xfs_buf
*cbp
; /* buffer for cblock */
2934 struct xfs_btree_block
*block
; /* btree block */
2935 struct xfs_btree_block
*cblock
; /* child btree block */
2936 union xfs_btree_key
*ckp
; /* child key pointer */
2937 union xfs_btree_ptr
*cpp
; /* child ptr pointer */
2938 union xfs_btree_key
*kp
; /* pointer to btree key */
2939 union xfs_btree_ptr
*pp
; /* pointer to block addr */
2940 union xfs_btree_ptr nptr
; /* new block addr */
2941 int level
; /* btree level */
2942 int error
; /* error return code */
2943 int i
; /* loop counter */
2945 XFS_BTREE_STATS_INC(cur
, newroot
);
2947 ASSERT(cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
);
2949 level
= cur
->bc_nlevels
- 1;
2951 block
= xfs_btree_get_iroot(cur
);
2952 pp
= xfs_btree_ptr_addr(cur
, 1, block
);
2954 /* Allocate the new block. If we can't do it, we're toast. Give up. */
2955 error
= cur
->bc_ops
->alloc_block(cur
, pp
, &nptr
, stat
);
2961 XFS_BTREE_STATS_INC(cur
, alloc
);
2963 /* Copy the root into a real block. */
2964 error
= xfs_btree_get_buf_block(cur
, &nptr
, 0, &cblock
, &cbp
);
2969 * we can't just memcpy() the root in for CRC enabled btree blocks.
2970 * In that case have to also ensure the blkno remains correct
2972 memcpy(cblock
, block
, xfs_btree_block_len(cur
));
2973 if (cur
->bc_flags
& XFS_BTREE_CRC_BLOCKS
) {
2974 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
)
2975 cblock
->bb_u
.l
.bb_blkno
= cpu_to_be64(cbp
->b_bn
);
2977 cblock
->bb_u
.s
.bb_blkno
= cpu_to_be64(cbp
->b_bn
);
2980 be16_add_cpu(&block
->bb_level
, 1);
2981 xfs_btree_set_numrecs(block
, 1);
2983 cur
->bc_ptrs
[level
+ 1] = 1;
2985 kp
= xfs_btree_key_addr(cur
, 1, block
);
2986 ckp
= xfs_btree_key_addr(cur
, 1, cblock
);
2987 xfs_btree_copy_keys(cur
, ckp
, kp
, xfs_btree_get_numrecs(cblock
));
2989 cpp
= xfs_btree_ptr_addr(cur
, 1, cblock
);
2990 for (i
= 0; i
< be16_to_cpu(cblock
->bb_numrecs
); i
++) {
2991 error
= xfs_btree_debug_check_ptr(cur
, pp
, i
, level
);
2996 xfs_btree_copy_ptrs(cur
, cpp
, pp
, xfs_btree_get_numrecs(cblock
));
2998 error
= xfs_btree_debug_check_ptr(cur
, &nptr
, 0, level
);
3002 xfs_btree_copy_ptrs(cur
, pp
, &nptr
, 1);
3004 xfs_iroot_realloc(cur
->bc_private
.b
.ip
,
3005 1 - xfs_btree_get_numrecs(cblock
),
3006 cur
->bc_private
.b
.whichfork
);
3008 xfs_btree_setbuf(cur
, level
, cbp
);
3011 * Do all this logging at the end so that
3012 * the root is at the right level.
3014 xfs_btree_log_block(cur
, cbp
, XFS_BB_ALL_BITS
);
3015 xfs_btree_log_keys(cur
, cbp
, 1, be16_to_cpu(cblock
->bb_numrecs
));
3016 xfs_btree_log_ptrs(cur
, cbp
, 1, be16_to_cpu(cblock
->bb_numrecs
));
3019 XFS_ILOG_CORE
| xfs_ilog_fbroot(cur
->bc_private
.b
.whichfork
);
3027 * Allocate a new root block, fill it in.
3029 STATIC
int /* error */
3031 struct xfs_btree_cur
*cur
, /* btree cursor */
3032 int *stat
) /* success/failure */
3034 struct xfs_btree_block
*block
; /* one half of the old root block */
3035 struct xfs_buf
*bp
; /* buffer containing block */
3036 int error
; /* error return value */
3037 struct xfs_buf
*lbp
; /* left buffer pointer */
3038 struct xfs_btree_block
*left
; /* left btree block */
3039 struct xfs_buf
*nbp
; /* new (root) buffer */
3040 struct xfs_btree_block
*new; /* new (root) btree block */
3041 int nptr
; /* new value for key index, 1 or 2 */
3042 struct xfs_buf
*rbp
; /* right buffer pointer */
3043 struct xfs_btree_block
*right
; /* right btree block */
3044 union xfs_btree_ptr rptr
;
3045 union xfs_btree_ptr lptr
;
3047 XFS_BTREE_STATS_INC(cur
, newroot
);
3049 /* initialise our start point from the cursor */
3050 cur
->bc_ops
->init_ptr_from_cur(cur
, &rptr
);
3052 /* Allocate the new block. If we can't do it, we're toast. Give up. */
3053 error
= cur
->bc_ops
->alloc_block(cur
, &rptr
, &lptr
, stat
);
3058 XFS_BTREE_STATS_INC(cur
, alloc
);
3060 /* Set up the new block. */
3061 error
= xfs_btree_get_buf_block(cur
, &lptr
, 0, &new, &nbp
);
3065 /* Set the root in the holding structure increasing the level by 1. */
3066 cur
->bc_ops
->set_root(cur
, &lptr
, 1);
3069 * At the previous root level there are now two blocks: the old root,
3070 * and the new block generated when it was split. We don't know which
3071 * one the cursor is pointing at, so we set up variables "left" and
3072 * "right" for each case.
3074 block
= xfs_btree_get_block(cur
, cur
->bc_nlevels
- 1, &bp
);
3077 error
= xfs_btree_check_block(cur
, block
, cur
->bc_nlevels
- 1, bp
);
3082 xfs_btree_get_sibling(cur
, block
, &rptr
, XFS_BB_RIGHTSIB
);
3083 if (!xfs_btree_ptr_is_null(cur
, &rptr
)) {
3084 /* Our block is left, pick up the right block. */
3086 xfs_btree_buf_to_ptr(cur
, lbp
, &lptr
);
3088 error
= xfs_btree_read_buf_block(cur
, &rptr
, 0, &right
, &rbp
);
3094 /* Our block is right, pick up the left block. */
3096 xfs_btree_buf_to_ptr(cur
, rbp
, &rptr
);
3098 xfs_btree_get_sibling(cur
, right
, &lptr
, XFS_BB_LEFTSIB
);
3099 error
= xfs_btree_read_buf_block(cur
, &lptr
, 0, &left
, &lbp
);
3106 /* Fill in the new block's btree header and log it. */
3107 xfs_btree_init_block_cur(cur
, nbp
, cur
->bc_nlevels
, 2);
3108 xfs_btree_log_block(cur
, nbp
, XFS_BB_ALL_BITS
);
3109 ASSERT(!xfs_btree_ptr_is_null(cur
, &lptr
) &&
3110 !xfs_btree_ptr_is_null(cur
, &rptr
));
3112 /* Fill in the key data in the new root. */
3113 if (xfs_btree_get_level(left
) > 0) {
3115 * Get the keys for the left block's keys and put them directly
3116 * in the parent block. Do the same for the right block.
3118 xfs_btree_get_node_keys(cur
, left
,
3119 xfs_btree_key_addr(cur
, 1, new));
3120 xfs_btree_get_node_keys(cur
, right
,
3121 xfs_btree_key_addr(cur
, 2, new));
3124 * Get the keys for the left block's records and put them
3125 * directly in the parent block. Do the same for the right
3128 xfs_btree_get_leaf_keys(cur
, left
,
3129 xfs_btree_key_addr(cur
, 1, new));
3130 xfs_btree_get_leaf_keys(cur
, right
,
3131 xfs_btree_key_addr(cur
, 2, new));
3133 xfs_btree_log_keys(cur
, nbp
, 1, 2);
3135 /* Fill in the pointer data in the new root. */
3136 xfs_btree_copy_ptrs(cur
,
3137 xfs_btree_ptr_addr(cur
, 1, new), &lptr
, 1);
3138 xfs_btree_copy_ptrs(cur
,
3139 xfs_btree_ptr_addr(cur
, 2, new), &rptr
, 1);
3140 xfs_btree_log_ptrs(cur
, nbp
, 1, 2);
3142 /* Fix up the cursor. */
3143 xfs_btree_setbuf(cur
, cur
->bc_nlevels
, nbp
);
3144 cur
->bc_ptrs
[cur
->bc_nlevels
] = nptr
;
3156 xfs_btree_make_block_unfull(
3157 struct xfs_btree_cur
*cur
, /* btree cursor */
3158 int level
, /* btree level */
3159 int numrecs
,/* # of recs in block */
3160 int *oindex
,/* old tree index */
3161 int *index
, /* new tree index */
3162 union xfs_btree_ptr
*nptr
, /* new btree ptr */
3163 struct xfs_btree_cur
**ncur
, /* new btree cursor */
3164 union xfs_btree_key
*key
, /* key of new block */
3169 if ((cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
) &&
3170 level
== cur
->bc_nlevels
- 1) {
3171 struct xfs_inode
*ip
= cur
->bc_private
.b
.ip
;
3173 if (numrecs
< cur
->bc_ops
->get_dmaxrecs(cur
, level
)) {
3174 /* A root block that can be made bigger. */
3175 xfs_iroot_realloc(ip
, 1, cur
->bc_private
.b
.whichfork
);
3178 /* A root block that needs replacing */
3181 error
= xfs_btree_new_iroot(cur
, &logflags
, stat
);
3182 if (error
|| *stat
== 0)
3185 xfs_trans_log_inode(cur
->bc_tp
, ip
, logflags
);
3191 /* First, try shifting an entry to the right neighbor. */
3192 error
= xfs_btree_rshift(cur
, level
, stat
);
3196 /* Next, try shifting an entry to the left neighbor. */
3197 error
= xfs_btree_lshift(cur
, level
, stat
);
3202 *oindex
= *index
= cur
->bc_ptrs
[level
];
3207 * Next, try splitting the current block in half.
3209 * If this works we have to re-set our variables because we
3210 * could be in a different block now.
3212 error
= xfs_btree_split(cur
, level
, nptr
, key
, ncur
, stat
);
3213 if (error
|| *stat
== 0)
3217 *index
= cur
->bc_ptrs
[level
];
3222 * Insert one record/level. Return information to the caller
3223 * allowing the next level up to proceed if necessary.
3227 struct xfs_btree_cur
*cur
, /* btree cursor */
3228 int level
, /* level to insert record at */
3229 union xfs_btree_ptr
*ptrp
, /* i/o: block number inserted */
3230 union xfs_btree_rec
*rec
, /* record to insert */
3231 union xfs_btree_key
*key
, /* i/o: block key for ptrp */
3232 struct xfs_btree_cur
**curp
, /* output: new cursor replacing cur */
3233 int *stat
) /* success/failure */
3235 struct xfs_btree_block
*block
; /* btree block */
3236 struct xfs_buf
*bp
; /* buffer for block */
3237 union xfs_btree_ptr nptr
; /* new block ptr */
3238 struct xfs_btree_cur
*ncur
; /* new btree cursor */
3239 union xfs_btree_key nkey
; /* new block key */
3240 union xfs_btree_key
*lkey
;
3241 int optr
; /* old key/record index */
3242 int ptr
; /* key/record index */
3243 int numrecs
;/* number of records */
3244 int error
; /* error return value */
3252 * If we have an external root pointer, and we've made it to the
3253 * root level, allocate a new root block and we're done.
3255 if (!(cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
) &&
3256 (level
>= cur
->bc_nlevels
)) {
3257 error
= xfs_btree_new_root(cur
, stat
);
3258 xfs_btree_set_ptr_null(cur
, ptrp
);
3263 /* If we're off the left edge, return failure. */
3264 ptr
= cur
->bc_ptrs
[level
];
3272 XFS_BTREE_STATS_INC(cur
, insrec
);
3274 /* Get pointers to the btree buffer and block. */
3275 block
= xfs_btree_get_block(cur
, level
, &bp
);
3276 old_bn
= bp
? bp
->b_bn
: XFS_BUF_DADDR_NULL
;
3277 numrecs
= xfs_btree_get_numrecs(block
);
3280 error
= xfs_btree_check_block(cur
, block
, level
, bp
);
3284 /* Check that the new entry is being inserted in the right place. */
3285 if (ptr
<= numrecs
) {
3287 ASSERT(cur
->bc_ops
->recs_inorder(cur
, rec
,
3288 xfs_btree_rec_addr(cur
, ptr
, block
)));
3290 ASSERT(cur
->bc_ops
->keys_inorder(cur
, key
,
3291 xfs_btree_key_addr(cur
, ptr
, block
)));
3297 * If the block is full, we can't insert the new entry until we
3298 * make the block un-full.
3300 xfs_btree_set_ptr_null(cur
, &nptr
);
3301 if (numrecs
== cur
->bc_ops
->get_maxrecs(cur
, level
)) {
3302 error
= xfs_btree_make_block_unfull(cur
, level
, numrecs
,
3303 &optr
, &ptr
, &nptr
, &ncur
, lkey
, stat
);
3304 if (error
|| *stat
== 0)
3309 * The current block may have changed if the block was
3310 * previously full and we have just made space in it.
3312 block
= xfs_btree_get_block(cur
, level
, &bp
);
3313 numrecs
= xfs_btree_get_numrecs(block
);
3316 error
= xfs_btree_check_block(cur
, block
, level
, bp
);
3322 * At this point we know there's room for our new entry in the block
3323 * we're pointing at.
3325 XFS_BTREE_STATS_ADD(cur
, moves
, numrecs
- ptr
+ 1);
3328 /* It's a nonleaf. make a hole in the keys and ptrs */
3329 union xfs_btree_key
*kp
;
3330 union xfs_btree_ptr
*pp
;
3332 kp
= xfs_btree_key_addr(cur
, ptr
, block
);
3333 pp
= xfs_btree_ptr_addr(cur
, ptr
, block
);
3335 for (i
= numrecs
- ptr
; i
>= 0; i
--) {
3336 error
= xfs_btree_debug_check_ptr(cur
, pp
, i
, level
);
3341 xfs_btree_shift_keys(cur
, kp
, 1, numrecs
- ptr
+ 1);
3342 xfs_btree_shift_ptrs(cur
, pp
, 1, numrecs
- ptr
+ 1);
3344 error
= xfs_btree_debug_check_ptr(cur
, ptrp
, 0, level
);
3348 /* Now put the new data in, bump numrecs and log it. */
3349 xfs_btree_copy_keys(cur
, kp
, key
, 1);
3350 xfs_btree_copy_ptrs(cur
, pp
, ptrp
, 1);
3352 xfs_btree_set_numrecs(block
, numrecs
);
3353 xfs_btree_log_ptrs(cur
, bp
, ptr
, numrecs
);
3354 xfs_btree_log_keys(cur
, bp
, ptr
, numrecs
);
3356 if (ptr
< numrecs
) {
3357 ASSERT(cur
->bc_ops
->keys_inorder(cur
, kp
,
3358 xfs_btree_key_addr(cur
, ptr
+ 1, block
)));
3362 /* It's a leaf. make a hole in the records */
3363 union xfs_btree_rec
*rp
;
3365 rp
= xfs_btree_rec_addr(cur
, ptr
, block
);
3367 xfs_btree_shift_recs(cur
, rp
, 1, numrecs
- ptr
+ 1);
3369 /* Now put the new data in, bump numrecs and log it. */
3370 xfs_btree_copy_recs(cur
, rp
, rec
, 1);
3371 xfs_btree_set_numrecs(block
, ++numrecs
);
3372 xfs_btree_log_recs(cur
, bp
, ptr
, numrecs
);
3374 if (ptr
< numrecs
) {
3375 ASSERT(cur
->bc_ops
->recs_inorder(cur
, rp
,
3376 xfs_btree_rec_addr(cur
, ptr
+ 1, block
)));
3381 /* Log the new number of records in the btree header. */
3382 xfs_btree_log_block(cur
, bp
, XFS_BB_NUMRECS
);
3385 * If we just inserted into a new tree block, we have to
3386 * recalculate nkey here because nkey is out of date.
3388 * Otherwise we're just updating an existing block (having shoved
3389 * some records into the new tree block), so use the regular key
3392 if (bp
&& bp
->b_bn
!= old_bn
) {
3393 xfs_btree_get_keys(cur
, block
, lkey
);
3394 } else if (xfs_btree_needs_key_update(cur
, optr
)) {
3395 error
= xfs_btree_update_keys(cur
, level
);
3401 * If we are tracking the last record in the tree and
3402 * we are at the far right edge of the tree, update it.
3404 if (xfs_btree_is_lastrec(cur
, block
, level
)) {
3405 cur
->bc_ops
->update_lastrec(cur
, block
, rec
,
3406 ptr
, LASTREC_INSREC
);
3410 * Return the new block number, if any.
3411 * If there is one, give back a record value and a cursor too.
3414 if (!xfs_btree_ptr_is_null(cur
, &nptr
)) {
3415 xfs_btree_copy_keys(cur
, key
, lkey
, 1);
3427 * Insert the record at the point referenced by cur.
3429 * A multi-level split of the tree on insert will invalidate the original
3430 * cursor. All callers of this function should assume that the cursor is
3431 * no longer valid and revalidate it.
3435 struct xfs_btree_cur
*cur
,
3438 int error
; /* error return value */
3439 int i
; /* result value, 0 for failure */
3440 int level
; /* current level number in btree */
3441 union xfs_btree_ptr nptr
; /* new block number (split result) */
3442 struct xfs_btree_cur
*ncur
; /* new cursor (split result) */
3443 struct xfs_btree_cur
*pcur
; /* previous level's cursor */
3444 union xfs_btree_key bkey
; /* key of block to insert */
3445 union xfs_btree_key
*key
;
3446 union xfs_btree_rec rec
; /* record to insert */
3453 xfs_btree_set_ptr_null(cur
, &nptr
);
3455 /* Make a key out of the record data to be inserted, and save it. */
3456 cur
->bc_ops
->init_rec_from_cur(cur
, &rec
);
3457 cur
->bc_ops
->init_key_from_rec(key
, &rec
);
3460 * Loop going up the tree, starting at the leaf level.
3461 * Stop when we don't get a split block, that must mean that
3462 * the insert is finished with this level.
3466 * Insert nrec/nptr into this level of the tree.
3467 * Note if we fail, nptr will be null.
3469 error
= xfs_btree_insrec(pcur
, level
, &nptr
, &rec
, key
,
3473 xfs_btree_del_cursor(pcur
, XFS_BTREE_ERROR
);
3477 XFS_WANT_CORRUPTED_GOTO(cur
->bc_mp
, i
== 1, error0
);
3481 * See if the cursor we just used is trash.
3482 * Can't trash the caller's cursor, but otherwise we should
3483 * if ncur is a new cursor or we're about to be done.
3486 (ncur
|| xfs_btree_ptr_is_null(cur
, &nptr
))) {
3487 /* Save the state from the cursor before we trash it */
3488 if (cur
->bc_ops
->update_cursor
)
3489 cur
->bc_ops
->update_cursor(pcur
, cur
);
3490 cur
->bc_nlevels
= pcur
->bc_nlevels
;
3491 xfs_btree_del_cursor(pcur
, XFS_BTREE_NOERROR
);
3493 /* If we got a new cursor, switch to it. */
3498 } while (!xfs_btree_ptr_is_null(cur
, &nptr
));
3507 * Try to merge a non-leaf block back into the inode root.
3509 * Note: the killroot names comes from the fact that we're effectively
3510 * killing the old root block. But because we can't just delete the
3511 * inode we have to copy the single block it was pointing to into the
3515 xfs_btree_kill_iroot(
3516 struct xfs_btree_cur
*cur
)
3518 int whichfork
= cur
->bc_private
.b
.whichfork
;
3519 struct xfs_inode
*ip
= cur
->bc_private
.b
.ip
;
3520 struct xfs_ifork
*ifp
= XFS_IFORK_PTR(ip
, whichfork
);
3521 struct xfs_btree_block
*block
;
3522 struct xfs_btree_block
*cblock
;
3523 union xfs_btree_key
*kp
;
3524 union xfs_btree_key
*ckp
;
3525 union xfs_btree_ptr
*pp
;
3526 union xfs_btree_ptr
*cpp
;
3527 struct xfs_buf
*cbp
;
3533 union xfs_btree_ptr ptr
;
3537 ASSERT(cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
);
3538 ASSERT(cur
->bc_nlevels
> 1);
3541 * Don't deal with the root block needs to be a leaf case.
3542 * We're just going to turn the thing back into extents anyway.
3544 level
= cur
->bc_nlevels
- 1;
3549 * Give up if the root has multiple children.
3551 block
= xfs_btree_get_iroot(cur
);
3552 if (xfs_btree_get_numrecs(block
) != 1)
3555 cblock
= xfs_btree_get_block(cur
, level
- 1, &cbp
);
3556 numrecs
= xfs_btree_get_numrecs(cblock
);
3559 * Only do this if the next level will fit.
3560 * Then the data must be copied up to the inode,
3561 * instead of freeing the root you free the next level.
3563 if (numrecs
> cur
->bc_ops
->get_dmaxrecs(cur
, level
))
3566 XFS_BTREE_STATS_INC(cur
, killroot
);
3569 xfs_btree_get_sibling(cur
, block
, &ptr
, XFS_BB_LEFTSIB
);
3570 ASSERT(xfs_btree_ptr_is_null(cur
, &ptr
));
3571 xfs_btree_get_sibling(cur
, block
, &ptr
, XFS_BB_RIGHTSIB
);
3572 ASSERT(xfs_btree_ptr_is_null(cur
, &ptr
));
3575 index
= numrecs
- cur
->bc_ops
->get_maxrecs(cur
, level
);
3577 xfs_iroot_realloc(cur
->bc_private
.b
.ip
, index
,
3578 cur
->bc_private
.b
.whichfork
);
3579 block
= ifp
->if_broot
;
3582 be16_add_cpu(&block
->bb_numrecs
, index
);
3583 ASSERT(block
->bb_numrecs
== cblock
->bb_numrecs
);
3585 kp
= xfs_btree_key_addr(cur
, 1, block
);
3586 ckp
= xfs_btree_key_addr(cur
, 1, cblock
);
3587 xfs_btree_copy_keys(cur
, kp
, ckp
, numrecs
);
3589 pp
= xfs_btree_ptr_addr(cur
, 1, block
);
3590 cpp
= xfs_btree_ptr_addr(cur
, 1, cblock
);
3592 for (i
= 0; i
< numrecs
; i
++) {
3593 error
= xfs_btree_debug_check_ptr(cur
, cpp
, i
, level
- 1);
3598 xfs_btree_copy_ptrs(cur
, pp
, cpp
, numrecs
);
3600 error
= xfs_btree_free_block(cur
, cbp
);
3604 cur
->bc_bufs
[level
- 1] = NULL
;
3605 be16_add_cpu(&block
->bb_level
, -1);
3606 xfs_trans_log_inode(cur
->bc_tp
, ip
,
3607 XFS_ILOG_CORE
| xfs_ilog_fbroot(cur
->bc_private
.b
.whichfork
));
3614 * Kill the current root node, and replace it with it's only child node.
3617 xfs_btree_kill_root(
3618 struct xfs_btree_cur
*cur
,
3621 union xfs_btree_ptr
*newroot
)
3625 XFS_BTREE_STATS_INC(cur
, killroot
);
3628 * Update the root pointer, decreasing the level by 1 and then
3629 * free the old root.
3631 cur
->bc_ops
->set_root(cur
, newroot
, -1);
3633 error
= xfs_btree_free_block(cur
, bp
);
3637 cur
->bc_bufs
[level
] = NULL
;
3638 cur
->bc_ra
[level
] = 0;
3645 xfs_btree_dec_cursor(
3646 struct xfs_btree_cur
*cur
,
3654 error
= xfs_btree_decrement(cur
, level
, &i
);
3664 * Single level of the btree record deletion routine.
3665 * Delete record pointed to by cur/level.
3666 * Remove the record from its block then rebalance the tree.
3667 * Return 0 for error, 1 for done, 2 to go on to the next level.
3669 STATIC
int /* error */
3671 struct xfs_btree_cur
*cur
, /* btree cursor */
3672 int level
, /* level removing record from */
3673 int *stat
) /* fail/done/go-on */
3675 struct xfs_btree_block
*block
; /* btree block */
3676 union xfs_btree_ptr cptr
; /* current block ptr */
3677 struct xfs_buf
*bp
; /* buffer for block */
3678 int error
; /* error return value */
3679 int i
; /* loop counter */
3680 union xfs_btree_ptr lptr
; /* left sibling block ptr */
3681 struct xfs_buf
*lbp
; /* left buffer pointer */
3682 struct xfs_btree_block
*left
; /* left btree block */
3683 int lrecs
= 0; /* left record count */
3684 int ptr
; /* key/record index */
3685 union xfs_btree_ptr rptr
; /* right sibling block ptr */
3686 struct xfs_buf
*rbp
; /* right buffer pointer */
3687 struct xfs_btree_block
*right
; /* right btree block */
3688 struct xfs_btree_block
*rrblock
; /* right-right btree block */
3689 struct xfs_buf
*rrbp
; /* right-right buffer pointer */
3690 int rrecs
= 0; /* right record count */
3691 struct xfs_btree_cur
*tcur
; /* temporary btree cursor */
3692 int numrecs
; /* temporary numrec count */
3696 /* Get the index of the entry being deleted, check for nothing there. */
3697 ptr
= cur
->bc_ptrs
[level
];
3703 /* Get the buffer & block containing the record or key/ptr. */
3704 block
= xfs_btree_get_block(cur
, level
, &bp
);
3705 numrecs
= xfs_btree_get_numrecs(block
);
3708 error
= xfs_btree_check_block(cur
, block
, level
, bp
);
3713 /* Fail if we're off the end of the block. */
3714 if (ptr
> numrecs
) {
3719 XFS_BTREE_STATS_INC(cur
, delrec
);
3720 XFS_BTREE_STATS_ADD(cur
, moves
, numrecs
- ptr
);
3722 /* Excise the entries being deleted. */
3724 /* It's a nonleaf. operate on keys and ptrs */
3725 union xfs_btree_key
*lkp
;
3726 union xfs_btree_ptr
*lpp
;
3728 lkp
= xfs_btree_key_addr(cur
, ptr
+ 1, block
);
3729 lpp
= xfs_btree_ptr_addr(cur
, ptr
+ 1, block
);
3731 for (i
= 0; i
< numrecs
- ptr
; i
++) {
3732 error
= xfs_btree_debug_check_ptr(cur
, lpp
, i
, level
);
3737 if (ptr
< numrecs
) {
3738 xfs_btree_shift_keys(cur
, lkp
, -1, numrecs
- ptr
);
3739 xfs_btree_shift_ptrs(cur
, lpp
, -1, numrecs
- ptr
);
3740 xfs_btree_log_keys(cur
, bp
, ptr
, numrecs
- 1);
3741 xfs_btree_log_ptrs(cur
, bp
, ptr
, numrecs
- 1);
3744 /* It's a leaf. operate on records */
3745 if (ptr
< numrecs
) {
3746 xfs_btree_shift_recs(cur
,
3747 xfs_btree_rec_addr(cur
, ptr
+ 1, block
),
3749 xfs_btree_log_recs(cur
, bp
, ptr
, numrecs
- 1);
3754 * Decrement and log the number of entries in the block.
3756 xfs_btree_set_numrecs(block
, --numrecs
);
3757 xfs_btree_log_block(cur
, bp
, XFS_BB_NUMRECS
);
3760 * If we are tracking the last record in the tree and
3761 * we are at the far right edge of the tree, update it.
3763 if (xfs_btree_is_lastrec(cur
, block
, level
)) {
3764 cur
->bc_ops
->update_lastrec(cur
, block
, NULL
,
3765 ptr
, LASTREC_DELREC
);
3769 * We're at the root level. First, shrink the root block in-memory.
3770 * Try to get rid of the next level down. If we can't then there's
3771 * nothing left to do.
3773 if (level
== cur
->bc_nlevels
- 1) {
3774 if (cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
) {
3775 xfs_iroot_realloc(cur
->bc_private
.b
.ip
, -1,
3776 cur
->bc_private
.b
.whichfork
);
3778 error
= xfs_btree_kill_iroot(cur
);
3782 error
= xfs_btree_dec_cursor(cur
, level
, stat
);
3790 * If this is the root level, and there's only one entry left,
3791 * and it's NOT the leaf level, then we can get rid of this
3794 if (numrecs
== 1 && level
> 0) {
3795 union xfs_btree_ptr
*pp
;
3797 * pp is still set to the first pointer in the block.
3798 * Make it the new root of the btree.
3800 pp
= xfs_btree_ptr_addr(cur
, 1, block
);
3801 error
= xfs_btree_kill_root(cur
, bp
, level
, pp
);
3804 } else if (level
> 0) {
3805 error
= xfs_btree_dec_cursor(cur
, level
, stat
);
3814 * If we deleted the leftmost entry in the block, update the
3815 * key values above us in the tree.
3817 if (xfs_btree_needs_key_update(cur
, ptr
)) {
3818 error
= xfs_btree_update_keys(cur
, level
);
3824 * If the number of records remaining in the block is at least
3825 * the minimum, we're done.
3827 if (numrecs
>= cur
->bc_ops
->get_minrecs(cur
, level
)) {
3828 error
= xfs_btree_dec_cursor(cur
, level
, stat
);
3835 * Otherwise, we have to move some records around to keep the
3836 * tree balanced. Look at the left and right sibling blocks to
3837 * see if we can re-balance by moving only one record.
3839 xfs_btree_get_sibling(cur
, block
, &rptr
, XFS_BB_RIGHTSIB
);
3840 xfs_btree_get_sibling(cur
, block
, &lptr
, XFS_BB_LEFTSIB
);
3842 if (cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
) {
3844 * One child of root, need to get a chance to copy its contents
3845 * into the root and delete it. Can't go up to next level,
3846 * there's nothing to delete there.
3848 if (xfs_btree_ptr_is_null(cur
, &rptr
) &&
3849 xfs_btree_ptr_is_null(cur
, &lptr
) &&
3850 level
== cur
->bc_nlevels
- 2) {
3851 error
= xfs_btree_kill_iroot(cur
);
3853 error
= xfs_btree_dec_cursor(cur
, level
, stat
);
3860 ASSERT(!xfs_btree_ptr_is_null(cur
, &rptr
) ||
3861 !xfs_btree_ptr_is_null(cur
, &lptr
));
3864 * Duplicate the cursor so our btree manipulations here won't
3865 * disrupt the next level up.
3867 error
= xfs_btree_dup_cursor(cur
, &tcur
);
3872 * If there's a right sibling, see if it's ok to shift an entry
3875 if (!xfs_btree_ptr_is_null(cur
, &rptr
)) {
3877 * Move the temp cursor to the last entry in the next block.
3878 * Actually any entry but the first would suffice.
3880 i
= xfs_btree_lastrec(tcur
, level
);
3881 XFS_WANT_CORRUPTED_GOTO(cur
->bc_mp
, i
== 1, error0
);
3883 error
= xfs_btree_increment(tcur
, level
, &i
);
3886 XFS_WANT_CORRUPTED_GOTO(cur
->bc_mp
, i
== 1, error0
);
3888 i
= xfs_btree_lastrec(tcur
, level
);
3889 XFS_WANT_CORRUPTED_GOTO(cur
->bc_mp
, i
== 1, error0
);
3891 /* Grab a pointer to the block. */
3892 right
= xfs_btree_get_block(tcur
, level
, &rbp
);
3894 error
= xfs_btree_check_block(tcur
, right
, level
, rbp
);
3898 /* Grab the current block number, for future use. */
3899 xfs_btree_get_sibling(tcur
, right
, &cptr
, XFS_BB_LEFTSIB
);
3902 * If right block is full enough so that removing one entry
3903 * won't make it too empty, and left-shifting an entry out
3904 * of right to us works, we're done.
3906 if (xfs_btree_get_numrecs(right
) - 1 >=
3907 cur
->bc_ops
->get_minrecs(tcur
, level
)) {
3908 error
= xfs_btree_lshift(tcur
, level
, &i
);
3912 ASSERT(xfs_btree_get_numrecs(block
) >=
3913 cur
->bc_ops
->get_minrecs(tcur
, level
));
3915 xfs_btree_del_cursor(tcur
, XFS_BTREE_NOERROR
);
3918 error
= xfs_btree_dec_cursor(cur
, level
, stat
);
3926 * Otherwise, grab the number of records in right for
3927 * future reference, and fix up the temp cursor to point
3928 * to our block again (last record).
3930 rrecs
= xfs_btree_get_numrecs(right
);
3931 if (!xfs_btree_ptr_is_null(cur
, &lptr
)) {
3932 i
= xfs_btree_firstrec(tcur
, level
);
3933 XFS_WANT_CORRUPTED_GOTO(cur
->bc_mp
, i
== 1, error0
);
3935 error
= xfs_btree_decrement(tcur
, level
, &i
);
3938 XFS_WANT_CORRUPTED_GOTO(cur
->bc_mp
, i
== 1, error0
);
3943 * If there's a left sibling, see if it's ok to shift an entry
3946 if (!xfs_btree_ptr_is_null(cur
, &lptr
)) {
3948 * Move the temp cursor to the first entry in the
3951 i
= xfs_btree_firstrec(tcur
, level
);
3952 XFS_WANT_CORRUPTED_GOTO(cur
->bc_mp
, i
== 1, error0
);
3954 error
= xfs_btree_decrement(tcur
, level
, &i
);
3957 i
= xfs_btree_firstrec(tcur
, level
);
3958 XFS_WANT_CORRUPTED_GOTO(cur
->bc_mp
, i
== 1, error0
);
3960 /* Grab a pointer to the block. */
3961 left
= xfs_btree_get_block(tcur
, level
, &lbp
);
3963 error
= xfs_btree_check_block(cur
, left
, level
, lbp
);
3967 /* Grab the current block number, for future use. */
3968 xfs_btree_get_sibling(tcur
, left
, &cptr
, XFS_BB_RIGHTSIB
);
3971 * If left block is full enough so that removing one entry
3972 * won't make it too empty, and right-shifting an entry out
3973 * of left to us works, we're done.
3975 if (xfs_btree_get_numrecs(left
) - 1 >=
3976 cur
->bc_ops
->get_minrecs(tcur
, level
)) {
3977 error
= xfs_btree_rshift(tcur
, level
, &i
);
3981 ASSERT(xfs_btree_get_numrecs(block
) >=
3982 cur
->bc_ops
->get_minrecs(tcur
, level
));
3983 xfs_btree_del_cursor(tcur
, XFS_BTREE_NOERROR
);
3994 * Otherwise, grab the number of records in right for
3997 lrecs
= xfs_btree_get_numrecs(left
);
4000 /* Delete the temp cursor, we're done with it. */
4001 xfs_btree_del_cursor(tcur
, XFS_BTREE_NOERROR
);
4004 /* If here, we need to do a join to keep the tree balanced. */
4005 ASSERT(!xfs_btree_ptr_is_null(cur
, &cptr
));
4007 if (!xfs_btree_ptr_is_null(cur
, &lptr
) &&
4008 lrecs
+ xfs_btree_get_numrecs(block
) <=
4009 cur
->bc_ops
->get_maxrecs(cur
, level
)) {
4011 * Set "right" to be the starting block,
4012 * "left" to be the left neighbor.
4017 error
= xfs_btree_read_buf_block(cur
, &lptr
, 0, &left
, &lbp
);
4022 * If that won't work, see if we can join with the right neighbor block.
4024 } else if (!xfs_btree_ptr_is_null(cur
, &rptr
) &&
4025 rrecs
+ xfs_btree_get_numrecs(block
) <=
4026 cur
->bc_ops
->get_maxrecs(cur
, level
)) {
4028 * Set "left" to be the starting block,
4029 * "right" to be the right neighbor.
4034 error
= xfs_btree_read_buf_block(cur
, &rptr
, 0, &right
, &rbp
);
4039 * Otherwise, we can't fix the imbalance.
4040 * Just return. This is probably a logic error, but it's not fatal.
4043 error
= xfs_btree_dec_cursor(cur
, level
, stat
);
4049 rrecs
= xfs_btree_get_numrecs(right
);
4050 lrecs
= xfs_btree_get_numrecs(left
);
4053 * We're now going to join "left" and "right" by moving all the stuff
4054 * in "right" to "left" and deleting "right".
4056 XFS_BTREE_STATS_ADD(cur
, moves
, rrecs
);
4058 /* It's a non-leaf. Move keys and pointers. */
4059 union xfs_btree_key
*lkp
; /* left btree key */
4060 union xfs_btree_ptr
*lpp
; /* left address pointer */
4061 union xfs_btree_key
*rkp
; /* right btree key */
4062 union xfs_btree_ptr
*rpp
; /* right address pointer */
4064 lkp
= xfs_btree_key_addr(cur
, lrecs
+ 1, left
);
4065 lpp
= xfs_btree_ptr_addr(cur
, lrecs
+ 1, left
);
4066 rkp
= xfs_btree_key_addr(cur
, 1, right
);
4067 rpp
= xfs_btree_ptr_addr(cur
, 1, right
);
4069 for (i
= 1; i
< rrecs
; i
++) {
4070 error
= xfs_btree_debug_check_ptr(cur
, rpp
, i
, level
);
4075 xfs_btree_copy_keys(cur
, lkp
, rkp
, rrecs
);
4076 xfs_btree_copy_ptrs(cur
, lpp
, rpp
, rrecs
);
4078 xfs_btree_log_keys(cur
, lbp
, lrecs
+ 1, lrecs
+ rrecs
);
4079 xfs_btree_log_ptrs(cur
, lbp
, lrecs
+ 1, lrecs
+ rrecs
);
4081 /* It's a leaf. Move records. */
4082 union xfs_btree_rec
*lrp
; /* left record pointer */
4083 union xfs_btree_rec
*rrp
; /* right record pointer */
4085 lrp
= xfs_btree_rec_addr(cur
, lrecs
+ 1, left
);
4086 rrp
= xfs_btree_rec_addr(cur
, 1, right
);
4088 xfs_btree_copy_recs(cur
, lrp
, rrp
, rrecs
);
4089 xfs_btree_log_recs(cur
, lbp
, lrecs
+ 1, lrecs
+ rrecs
);
4092 XFS_BTREE_STATS_INC(cur
, join
);
4095 * Fix up the number of records and right block pointer in the
4096 * surviving block, and log it.
4098 xfs_btree_set_numrecs(left
, lrecs
+ rrecs
);
4099 xfs_btree_get_sibling(cur
, right
, &cptr
, XFS_BB_RIGHTSIB
),
4100 xfs_btree_set_sibling(cur
, left
, &cptr
, XFS_BB_RIGHTSIB
);
4101 xfs_btree_log_block(cur
, lbp
, XFS_BB_NUMRECS
| XFS_BB_RIGHTSIB
);
4103 /* If there is a right sibling, point it to the remaining block. */
4104 xfs_btree_get_sibling(cur
, left
, &cptr
, XFS_BB_RIGHTSIB
);
4105 if (!xfs_btree_ptr_is_null(cur
, &cptr
)) {
4106 error
= xfs_btree_read_buf_block(cur
, &cptr
, 0, &rrblock
, &rrbp
);
4109 xfs_btree_set_sibling(cur
, rrblock
, &lptr
, XFS_BB_LEFTSIB
);
4110 xfs_btree_log_block(cur
, rrbp
, XFS_BB_LEFTSIB
);
4113 /* Free the deleted block. */
4114 error
= xfs_btree_free_block(cur
, rbp
);
4119 * If we joined with the left neighbor, set the buffer in the
4120 * cursor to the left block, and fix up the index.
4123 cur
->bc_bufs
[level
] = lbp
;
4124 cur
->bc_ptrs
[level
] += lrecs
;
4125 cur
->bc_ra
[level
] = 0;
4128 * If we joined with the right neighbor and there's a level above
4129 * us, increment the cursor at that level.
4131 else if ((cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
) ||
4132 (level
+ 1 < cur
->bc_nlevels
)) {
4133 error
= xfs_btree_increment(cur
, level
+ 1, &i
);
4139 * Readjust the ptr at this level if it's not a leaf, since it's
4140 * still pointing at the deletion point, which makes the cursor
4141 * inconsistent. If this makes the ptr 0, the caller fixes it up.
4142 * We can't use decrement because it would change the next level up.
4145 cur
->bc_ptrs
[level
]--;
4148 * We combined blocks, so we have to update the parent keys if the
4149 * btree supports overlapped intervals. However, bc_ptrs[level + 1]
4150 * points to the old block so that the caller knows which record to
4151 * delete. Therefore, the caller must be savvy enough to call updkeys
4152 * for us if we return stat == 2. The other exit points from this
4153 * function don't require deletions further up the tree, so they can
4154 * call updkeys directly.
4157 /* Return value means the next level up has something to do. */
4163 xfs_btree_del_cursor(tcur
, XFS_BTREE_ERROR
);
4168 * Delete the record pointed to by cur.
4169 * The cursor refers to the place where the record was (could be inserted)
4170 * when the operation returns.
4174 struct xfs_btree_cur
*cur
,
4175 int *stat
) /* success/failure */
4177 int error
; /* error return value */
4180 bool joined
= false;
4183 * Go up the tree, starting at leaf level.
4185 * If 2 is returned then a join was done; go to the next level.
4186 * Otherwise we are done.
4188 for (level
= 0, i
= 2; i
== 2; level
++) {
4189 error
= xfs_btree_delrec(cur
, level
, &i
);
4197 * If we combined blocks as part of deleting the record, delrec won't
4198 * have updated the parent high keys so we have to do that here.
4200 if (joined
&& (cur
->bc_flags
& XFS_BTREE_OVERLAPPING
)) {
4201 error
= xfs_btree_updkeys_force(cur
, 0);
4207 for (level
= 1; level
< cur
->bc_nlevels
; level
++) {
4208 if (cur
->bc_ptrs
[level
] == 0) {
4209 error
= xfs_btree_decrement(cur
, level
, &i
);
4224 * Get the data from the pointed-to record.
4228 struct xfs_btree_cur
*cur
, /* btree cursor */
4229 union xfs_btree_rec
**recp
, /* output: btree record */
4230 int *stat
) /* output: success/failure */
4232 struct xfs_btree_block
*block
; /* btree block */
4233 struct xfs_buf
*bp
; /* buffer pointer */
4234 int ptr
; /* record number */
4236 int error
; /* error return value */
4239 ptr
= cur
->bc_ptrs
[0];
4240 block
= xfs_btree_get_block(cur
, 0, &bp
);
4243 error
= xfs_btree_check_block(cur
, block
, 0, bp
);
4249 * Off the right end or left end, return failure.
4251 if (ptr
> xfs_btree_get_numrecs(block
) || ptr
<= 0) {
4257 * Point to the record and extract its data.
4259 *recp
= xfs_btree_rec_addr(cur
, ptr
, block
);
4264 /* Visit a block in a btree. */
4266 xfs_btree_visit_block(
4267 struct xfs_btree_cur
*cur
,
4269 xfs_btree_visit_blocks_fn fn
,
4272 struct xfs_btree_block
*block
;
4274 union xfs_btree_ptr rptr
;
4277 /* do right sibling readahead */
4278 xfs_btree_readahead(cur
, level
, XFS_BTCUR_RIGHTRA
);
4279 block
= xfs_btree_get_block(cur
, level
, &bp
);
4281 /* process the block */
4282 error
= fn(cur
, level
, data
);
4286 /* now read rh sibling block for next iteration */
4287 xfs_btree_get_sibling(cur
, block
, &rptr
, XFS_BB_RIGHTSIB
);
4288 if (xfs_btree_ptr_is_null(cur
, &rptr
))
4291 return xfs_btree_lookup_get_block(cur
, level
, &rptr
, &block
);
4295 /* Visit every block in a btree. */
4297 xfs_btree_visit_blocks(
4298 struct xfs_btree_cur
*cur
,
4299 xfs_btree_visit_blocks_fn fn
,
4302 union xfs_btree_ptr lptr
;
4304 struct xfs_btree_block
*block
= NULL
;
4307 cur
->bc_ops
->init_ptr_from_cur(cur
, &lptr
);
4309 /* for each level */
4310 for (level
= cur
->bc_nlevels
- 1; level
>= 0; level
--) {
4311 /* grab the left hand block */
4312 error
= xfs_btree_lookup_get_block(cur
, level
, &lptr
, &block
);
4316 /* readahead the left most block for the next level down */
4318 union xfs_btree_ptr
*ptr
;
4320 ptr
= xfs_btree_ptr_addr(cur
, 1, block
);
4321 xfs_btree_readahead_ptr(cur
, ptr
, 1);
4323 /* save for the next iteration of the loop */
4324 xfs_btree_copy_ptrs(cur
, &lptr
, ptr
, 1);
4327 /* for each buffer in the level */
4329 error
= xfs_btree_visit_block(cur
, level
, fn
, data
);
4332 if (error
!= -ENOENT
)
4340 * Change the owner of a btree.
4342 * The mechanism we use here is ordered buffer logging. Because we don't know
4343 * how many buffers were are going to need to modify, we don't really want to
4344 * have to make transaction reservations for the worst case of every buffer in a
4345 * full size btree as that may be more space that we can fit in the log....
4347 * We do the btree walk in the most optimal manner possible - we have sibling
4348 * pointers so we can just walk all the blocks on each level from left to right
4349 * in a single pass, and then move to the next level and do the same. We can
4350 * also do readahead on the sibling pointers to get IO moving more quickly,
4351 * though for slow disks this is unlikely to make much difference to performance
4352 * as the amount of CPU work we have to do before moving to the next block is
4355 * For each btree block that we load, modify the owner appropriately, set the
4356 * buffer as an ordered buffer and log it appropriately. We need to ensure that
4357 * we mark the region we change dirty so that if the buffer is relogged in
4358 * a subsequent transaction the changes we make here as an ordered buffer are
4359 * correctly relogged in that transaction. If we are in recovery context, then
4360 * just queue the modified buffer as delayed write buffer so the transaction
4361 * recovery completion writes the changes to disk.
4363 struct xfs_btree_block_change_owner_info
{
4365 struct list_head
*buffer_list
;
4369 xfs_btree_block_change_owner(
4370 struct xfs_btree_cur
*cur
,
4374 struct xfs_btree_block_change_owner_info
*bbcoi
= data
;
4375 struct xfs_btree_block
*block
;
4378 /* modify the owner */
4379 block
= xfs_btree_get_block(cur
, level
, &bp
);
4380 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
) {
4381 if (block
->bb_u
.l
.bb_owner
== cpu_to_be64(bbcoi
->new_owner
))
4383 block
->bb_u
.l
.bb_owner
= cpu_to_be64(bbcoi
->new_owner
);
4385 if (block
->bb_u
.s
.bb_owner
== cpu_to_be32(bbcoi
->new_owner
))
4387 block
->bb_u
.s
.bb_owner
= cpu_to_be32(bbcoi
->new_owner
);
4391 * If the block is a root block hosted in an inode, we might not have a
4392 * buffer pointer here and we shouldn't attempt to log the change as the
4393 * information is already held in the inode and discarded when the root
4394 * block is formatted into the on-disk inode fork. We still change it,
4395 * though, so everything is consistent in memory.
4398 ASSERT(cur
->bc_flags
& XFS_BTREE_ROOT_IN_INODE
);
4399 ASSERT(level
== cur
->bc_nlevels
- 1);
4404 if (!xfs_trans_ordered_buf(cur
->bc_tp
, bp
)) {
4405 xfs_btree_log_block(cur
, bp
, XFS_BB_OWNER
);
4409 xfs_buf_delwri_queue(bp
, bbcoi
->buffer_list
);
4416 xfs_btree_change_owner(
4417 struct xfs_btree_cur
*cur
,
4419 struct list_head
*buffer_list
)
4421 struct xfs_btree_block_change_owner_info bbcoi
;
4423 bbcoi
.new_owner
= new_owner
;
4424 bbcoi
.buffer_list
= buffer_list
;
4426 return xfs_btree_visit_blocks(cur
, xfs_btree_block_change_owner
,
4430 /* Verify the v5 fields of a long-format btree block. */
4432 xfs_btree_lblock_v5hdr_verify(
4436 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
4437 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
4439 if (!xfs_sb_version_hascrc(&mp
->m_sb
))
4440 return __this_address
;
4441 if (!uuid_equal(&block
->bb_u
.l
.bb_uuid
, &mp
->m_sb
.sb_meta_uuid
))
4442 return __this_address
;
4443 if (block
->bb_u
.l
.bb_blkno
!= cpu_to_be64(bp
->b_bn
))
4444 return __this_address
;
4445 if (owner
!= XFS_RMAP_OWN_UNKNOWN
&&
4446 be64_to_cpu(block
->bb_u
.l
.bb_owner
) != owner
)
4447 return __this_address
;
4451 /* Verify a long-format btree block. */
4453 xfs_btree_lblock_verify(
4455 unsigned int max_recs
)
4457 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
4458 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
4460 /* numrecs verification */
4461 if (be16_to_cpu(block
->bb_numrecs
) > max_recs
)
4462 return __this_address
;
4464 /* sibling pointer verification */
4465 if (block
->bb_u
.l
.bb_leftsib
!= cpu_to_be64(NULLFSBLOCK
) &&
4466 !xfs_verify_fsbno(mp
, be64_to_cpu(block
->bb_u
.l
.bb_leftsib
)))
4467 return __this_address
;
4468 if (block
->bb_u
.l
.bb_rightsib
!= cpu_to_be64(NULLFSBLOCK
) &&
4469 !xfs_verify_fsbno(mp
, be64_to_cpu(block
->bb_u
.l
.bb_rightsib
)))
4470 return __this_address
;
4476 * xfs_btree_sblock_v5hdr_verify() -- verify the v5 fields of a short-format
4479 * @bp: buffer containing the btree block
4480 * @max_recs: pointer to the m_*_mxr max records field in the xfs mount
4481 * @pag_max_level: pointer to the per-ag max level field
4484 xfs_btree_sblock_v5hdr_verify(
4487 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
4488 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
4489 struct xfs_perag
*pag
= bp
->b_pag
;
4491 if (!xfs_sb_version_hascrc(&mp
->m_sb
))
4492 return __this_address
;
4493 if (!uuid_equal(&block
->bb_u
.s
.bb_uuid
, &mp
->m_sb
.sb_meta_uuid
))
4494 return __this_address
;
4495 if (block
->bb_u
.s
.bb_blkno
!= cpu_to_be64(bp
->b_bn
))
4496 return __this_address
;
4497 if (pag
&& be32_to_cpu(block
->bb_u
.s
.bb_owner
) != pag
->pag_agno
)
4498 return __this_address
;
4503 * xfs_btree_sblock_verify() -- verify a short-format btree block
4505 * @bp: buffer containing the btree block
4506 * @max_recs: maximum records allowed in this btree node
4509 xfs_btree_sblock_verify(
4511 unsigned int max_recs
)
4513 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
4514 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
4517 /* numrecs verification */
4518 if (be16_to_cpu(block
->bb_numrecs
) > max_recs
)
4519 return __this_address
;
4521 /* sibling pointer verification */
4522 agno
= xfs_daddr_to_agno(mp
, XFS_BUF_ADDR(bp
));
4523 if (block
->bb_u
.s
.bb_leftsib
!= cpu_to_be32(NULLAGBLOCK
) &&
4524 !xfs_verify_agbno(mp
, agno
, be32_to_cpu(block
->bb_u
.s
.bb_leftsib
)))
4525 return __this_address
;
4526 if (block
->bb_u
.s
.bb_rightsib
!= cpu_to_be32(NULLAGBLOCK
) &&
4527 !xfs_verify_agbno(mp
, agno
, be32_to_cpu(block
->bb_u
.s
.bb_rightsib
)))
4528 return __this_address
;
4534 * Calculate the number of btree levels needed to store a given number of
4535 * records in a short-format btree.
4538 xfs_btree_compute_maxlevels(
4543 unsigned long maxblocks
;
4545 maxblocks
= (len
+ limits
[0] - 1) / limits
[0];
4546 for (level
= 1; maxblocks
> 1; level
++)
4547 maxblocks
= (maxblocks
+ limits
[1] - 1) / limits
[1];
4552 * Query a regular btree for all records overlapping a given interval.
4553 * Start with a LE lookup of the key of low_rec and return all records
4554 * until we find a record with a key greater than the key of high_rec.
4557 xfs_btree_simple_query_range(
4558 struct xfs_btree_cur
*cur
,
4559 union xfs_btree_key
*low_key
,
4560 union xfs_btree_key
*high_key
,
4561 xfs_btree_query_range_fn fn
,
4564 union xfs_btree_rec
*recp
;
4565 union xfs_btree_key rec_key
;
4568 bool firstrec
= true;
4571 ASSERT(cur
->bc_ops
->init_high_key_from_rec
);
4572 ASSERT(cur
->bc_ops
->diff_two_keys
);
4575 * Find the leftmost record. The btree cursor must be set
4576 * to the low record used to generate low_key.
4579 error
= xfs_btree_lookup(cur
, XFS_LOOKUP_LE
, &stat
);
4583 /* Nothing? See if there's anything to the right. */
4585 error
= xfs_btree_increment(cur
, 0, &stat
);
4591 /* Find the record. */
4592 error
= xfs_btree_get_rec(cur
, &recp
, &stat
);
4596 /* Skip if high_key(rec) < low_key. */
4598 cur
->bc_ops
->init_high_key_from_rec(&rec_key
, recp
);
4600 diff
= cur
->bc_ops
->diff_two_keys(cur
, low_key
,
4606 /* Stop if high_key < low_key(rec). */
4607 cur
->bc_ops
->init_key_from_rec(&rec_key
, recp
);
4608 diff
= cur
->bc_ops
->diff_two_keys(cur
, &rec_key
, high_key
);
4613 error
= fn(cur
, recp
, priv
);
4614 if (error
< 0 || error
== XFS_BTREE_QUERY_RANGE_ABORT
)
4618 /* Move on to the next record. */
4619 error
= xfs_btree_increment(cur
, 0, &stat
);
4629 * Query an overlapped interval btree for all records overlapping a given
4630 * interval. This function roughly follows the algorithm given in
4631 * "Interval Trees" of _Introduction to Algorithms_, which is section
4632 * 14.3 in the 2nd and 3rd editions.
4634 * First, generate keys for the low and high records passed in.
4636 * For any leaf node, generate the high and low keys for the record.
4637 * If the record keys overlap with the query low/high keys, pass the
4638 * record to the function iterator.
4640 * For any internal node, compare the low and high keys of each
4641 * pointer against the query low/high keys. If there's an overlap,
4642 * follow the pointer.
4644 * As an optimization, we stop scanning a block when we find a low key
4645 * that is greater than the query's high key.
4648 xfs_btree_overlapped_query_range(
4649 struct xfs_btree_cur
*cur
,
4650 union xfs_btree_key
*low_key
,
4651 union xfs_btree_key
*high_key
,
4652 xfs_btree_query_range_fn fn
,
4655 union xfs_btree_ptr ptr
;
4656 union xfs_btree_ptr
*pp
;
4657 union xfs_btree_key rec_key
;
4658 union xfs_btree_key rec_hkey
;
4659 union xfs_btree_key
*lkp
;
4660 union xfs_btree_key
*hkp
;
4661 union xfs_btree_rec
*recp
;
4662 struct xfs_btree_block
*block
;
4670 /* Load the root of the btree. */
4671 level
= cur
->bc_nlevels
- 1;
4672 cur
->bc_ops
->init_ptr_from_cur(cur
, &ptr
);
4673 error
= xfs_btree_lookup_get_block(cur
, level
, &ptr
, &block
);
4676 xfs_btree_get_block(cur
, level
, &bp
);
4677 trace_xfs_btree_overlapped_query_range(cur
, level
, bp
);
4679 error
= xfs_btree_check_block(cur
, block
, level
, bp
);
4683 cur
->bc_ptrs
[level
] = 1;
4685 while (level
< cur
->bc_nlevels
) {
4686 block
= xfs_btree_get_block(cur
, level
, &bp
);
4688 /* End of node, pop back towards the root. */
4689 if (cur
->bc_ptrs
[level
] > be16_to_cpu(block
->bb_numrecs
)) {
4691 if (level
< cur
->bc_nlevels
- 1)
4692 cur
->bc_ptrs
[level
+ 1]++;
4698 /* Handle a leaf node. */
4699 recp
= xfs_btree_rec_addr(cur
, cur
->bc_ptrs
[0], block
);
4701 cur
->bc_ops
->init_high_key_from_rec(&rec_hkey
, recp
);
4702 ldiff
= cur
->bc_ops
->diff_two_keys(cur
, &rec_hkey
,
4705 cur
->bc_ops
->init_key_from_rec(&rec_key
, recp
);
4706 hdiff
= cur
->bc_ops
->diff_two_keys(cur
, high_key
,
4710 * If (record's high key >= query's low key) and
4711 * (query's high key >= record's low key), then
4712 * this record overlaps the query range; callback.
4714 if (ldiff
>= 0 && hdiff
>= 0) {
4715 error
= fn(cur
, recp
, priv
);
4717 error
== XFS_BTREE_QUERY_RANGE_ABORT
)
4719 } else if (hdiff
< 0) {
4720 /* Record is larger than high key; pop. */
4723 cur
->bc_ptrs
[level
]++;
4727 /* Handle an internal node. */
4728 lkp
= xfs_btree_key_addr(cur
, cur
->bc_ptrs
[level
], block
);
4729 hkp
= xfs_btree_high_key_addr(cur
, cur
->bc_ptrs
[level
], block
);
4730 pp
= xfs_btree_ptr_addr(cur
, cur
->bc_ptrs
[level
], block
);
4732 ldiff
= cur
->bc_ops
->diff_two_keys(cur
, hkp
, low_key
);
4733 hdiff
= cur
->bc_ops
->diff_two_keys(cur
, high_key
, lkp
);
4736 * If (pointer's high key >= query's low key) and
4737 * (query's high key >= pointer's low key), then
4738 * this record overlaps the query range; follow pointer.
4740 if (ldiff
>= 0 && hdiff
>= 0) {
4742 error
= xfs_btree_lookup_get_block(cur
, level
, pp
,
4746 xfs_btree_get_block(cur
, level
, &bp
);
4747 trace_xfs_btree_overlapped_query_range(cur
, level
, bp
);
4749 error
= xfs_btree_check_block(cur
, block
, level
, bp
);
4753 cur
->bc_ptrs
[level
] = 1;
4755 } else if (hdiff
< 0) {
4756 /* The low key is larger than the upper range; pop. */
4759 cur
->bc_ptrs
[level
]++;
4764 * If we don't end this function with the cursor pointing at a record
4765 * block, a subsequent non-error cursor deletion will not release
4766 * node-level buffers, causing a buffer leak. This is quite possible
4767 * with a zero-results range query, so release the buffers if we
4768 * failed to return any results.
4770 if (cur
->bc_bufs
[0] == NULL
) {
4771 for (i
= 0; i
< cur
->bc_nlevels
; i
++) {
4772 if (cur
->bc_bufs
[i
]) {
4773 xfs_trans_brelse(cur
->bc_tp
, cur
->bc_bufs
[i
]);
4774 cur
->bc_bufs
[i
] = NULL
;
4775 cur
->bc_ptrs
[i
] = 0;
4785 * Query a btree for all records overlapping a given interval of keys. The
4786 * supplied function will be called with each record found; return one of the
4787 * XFS_BTREE_QUERY_RANGE_{CONTINUE,ABORT} values or the usual negative error
4788 * code. This function returns XFS_BTREE_QUERY_RANGE_ABORT, zero, or a
4789 * negative error code.
4792 xfs_btree_query_range(
4793 struct xfs_btree_cur
*cur
,
4794 union xfs_btree_irec
*low_rec
,
4795 union xfs_btree_irec
*high_rec
,
4796 xfs_btree_query_range_fn fn
,
4799 union xfs_btree_rec rec
;
4800 union xfs_btree_key low_key
;
4801 union xfs_btree_key high_key
;
4803 /* Find the keys of both ends of the interval. */
4804 cur
->bc_rec
= *high_rec
;
4805 cur
->bc_ops
->init_rec_from_cur(cur
, &rec
);
4806 cur
->bc_ops
->init_key_from_rec(&high_key
, &rec
);
4808 cur
->bc_rec
= *low_rec
;
4809 cur
->bc_ops
->init_rec_from_cur(cur
, &rec
);
4810 cur
->bc_ops
->init_key_from_rec(&low_key
, &rec
);
4812 /* Enforce low key < high key. */
4813 if (cur
->bc_ops
->diff_two_keys(cur
, &low_key
, &high_key
) > 0)
4816 if (!(cur
->bc_flags
& XFS_BTREE_OVERLAPPING
))
4817 return xfs_btree_simple_query_range(cur
, &low_key
,
4818 &high_key
, fn
, priv
);
4819 return xfs_btree_overlapped_query_range(cur
, &low_key
, &high_key
,
4823 /* Query a btree for all records. */
4825 xfs_btree_query_all(
4826 struct xfs_btree_cur
*cur
,
4827 xfs_btree_query_range_fn fn
,
4830 union xfs_btree_key low_key
;
4831 union xfs_btree_key high_key
;
4833 memset(&cur
->bc_rec
, 0, sizeof(cur
->bc_rec
));
4834 memset(&low_key
, 0, sizeof(low_key
));
4835 memset(&high_key
, 0xFF, sizeof(high_key
));
4837 return xfs_btree_simple_query_range(cur
, &low_key
, &high_key
, fn
, priv
);
4841 * Calculate the number of blocks needed to store a given number of records
4842 * in a short-format (per-AG metadata) btree.
4845 xfs_btree_calc_size(
4847 unsigned long long len
)
4851 unsigned long long rval
;
4853 maxrecs
= limits
[0];
4854 for (level
= 0, rval
= 0; len
> 1; level
++) {
4856 do_div(len
, maxrecs
);
4857 maxrecs
= limits
[1];
4864 xfs_btree_count_blocks_helper(
4865 struct xfs_btree_cur
*cur
,
4869 xfs_extlen_t
*blocks
= data
;
4875 /* Count the blocks in a btree and return the result in *blocks. */
4877 xfs_btree_count_blocks(
4878 struct xfs_btree_cur
*cur
,
4879 xfs_extlen_t
*blocks
)
4882 return xfs_btree_visit_blocks(cur
, xfs_btree_count_blocks_helper
,
4886 /* Compare two btree pointers. */
4888 xfs_btree_diff_two_ptrs(
4889 struct xfs_btree_cur
*cur
,
4890 const union xfs_btree_ptr
*a
,
4891 const union xfs_btree_ptr
*b
)
4893 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
)
4894 return (int64_t)be64_to_cpu(a
->l
) - be64_to_cpu(b
->l
);
4895 return (int64_t)be32_to_cpu(a
->s
) - be32_to_cpu(b
->s
);
4898 /* If there's an extent, we're done. */
4900 xfs_btree_has_record_helper(
4901 struct xfs_btree_cur
*cur
,
4902 union xfs_btree_rec
*rec
,
4905 return XFS_BTREE_QUERY_RANGE_ABORT
;
4908 /* Is there a record covering a given range of keys? */
4910 xfs_btree_has_record(
4911 struct xfs_btree_cur
*cur
,
4912 union xfs_btree_irec
*low
,
4913 union xfs_btree_irec
*high
,
4918 error
= xfs_btree_query_range(cur
, low
, high
,
4919 &xfs_btree_has_record_helper
, NULL
);
4920 if (error
== XFS_BTREE_QUERY_RANGE_ABORT
) {
4928 /* Are there more records in this btree? */
4930 xfs_btree_has_more_records(
4931 struct xfs_btree_cur
*cur
)
4933 struct xfs_btree_block
*block
;
4936 block
= xfs_btree_get_block(cur
, 0, &bp
);
4938 /* There are still records in this block. */
4939 if (cur
->bc_ptrs
[0] < xfs_btree_get_numrecs(block
))
4942 /* There are more record blocks. */
4943 if (cur
->bc_flags
& XFS_BTREE_LONG_PTRS
)
4944 return block
->bb_u
.l
.bb_rightsib
!= cpu_to_be64(NULLFSBLOCK
);
4946 return block
->bb_u
.s
.bb_rightsib
!= cpu_to_be32(NULLAGBLOCK
);