1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
8 #include "xfs_shared.h"
9 #include "xfs_format.h"
10 #include "xfs_log_format.h"
11 #include "xfs_trans_resv.h"
13 #include "xfs_mount.h"
14 #include "xfs_inode.h"
15 #include "xfs_trans.h"
16 #include "xfs_buf_item.h"
17 #include "xfs_btree.h"
18 #include "xfs_errortag.h"
19 #include "xfs_error.h"
20 #include "xfs_trace.h"
21 #include "xfs_alloc.h"
23 #include "xfs_btree_staging.h"
27 * Cursor allocation zone.
29 kmem_zone_t *xfs_btree_cur_zone;
32 * Btree magic numbers.
34 static const uint32_t xfs_magics[2][XFS_BTNUM_MAX] = {
35 { XFS_ABTB_MAGIC, XFS_ABTC_MAGIC, 0, XFS_BMAP_MAGIC, XFS_IBT_MAGIC,
37 { XFS_ABTB_CRC_MAGIC, XFS_ABTC_CRC_MAGIC, XFS_RMAP_CRC_MAGIC,
38 XFS_BMAP_CRC_MAGIC, XFS_IBT_CRC_MAGIC, XFS_FIBT_CRC_MAGIC,
47 uint32_t magic = xfs_magics[crc][btnum];
49 /* Ensure we asked for crc for crc-only magics. */
55 * Check a long btree block header. Return the address of the failing check,
56 * or NULL if everything is ok.
59 __xfs_btree_check_lblock(
60 struct xfs_btree_cur *cur,
61 struct xfs_btree_block *block,
65 struct xfs_mount *mp = cur->bc_mp;
66 xfs_btnum_t btnum = cur->bc_btnum;
67 int crc = xfs_sb_version_hascrc(&mp->m_sb);
70 if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid))
71 return __this_address;
72 if (block->bb_u.l.bb_blkno !=
73 cpu_to_be64(bp ? bp->b_bn : XFS_BUF_DADDR_NULL))
74 return __this_address;
75 if (block->bb_u.l.bb_pad != cpu_to_be32(0))
76 return __this_address;
79 if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(crc, btnum))
80 return __this_address;
81 if (be16_to_cpu(block->bb_level) != level)
82 return __this_address;
83 if (be16_to_cpu(block->bb_numrecs) >
84 cur->bc_ops->get_maxrecs(cur, level))
85 return __this_address;
86 if (block->bb_u.l.bb_leftsib != cpu_to_be64(NULLFSBLOCK) &&
87 !xfs_btree_check_lptr(cur, be64_to_cpu(block->bb_u.l.bb_leftsib),
89 return __this_address;
90 if (block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK) &&
91 !xfs_btree_check_lptr(cur, be64_to_cpu(block->bb_u.l.bb_rightsib),
93 return __this_address;
98 /* Check a long btree block header. */
100 xfs_btree_check_lblock(
101 struct xfs_btree_cur *cur,
102 struct xfs_btree_block *block,
106 struct xfs_mount *mp = cur->bc_mp;
109 fa = __xfs_btree_check_lblock(cur, block, level, bp);
110 if (XFS_IS_CORRUPT(mp, fa != NULL) ||
111 XFS_TEST_ERROR(false, mp, XFS_ERRTAG_BTREE_CHECK_LBLOCK)) {
113 trace_xfs_btree_corrupt(bp, _RET_IP_);
114 return -EFSCORRUPTED;
120 * Check a short btree block header. Return the address of the failing check,
121 * or NULL if everything is ok.
124 __xfs_btree_check_sblock(
125 struct xfs_btree_cur *cur,
126 struct xfs_btree_block *block,
130 struct xfs_mount *mp = cur->bc_mp;
131 xfs_btnum_t btnum = cur->bc_btnum;
132 int crc = xfs_sb_version_hascrc(&mp->m_sb);
135 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid))
136 return __this_address;
137 if (block->bb_u.s.bb_blkno !=
138 cpu_to_be64(bp ? bp->b_bn : XFS_BUF_DADDR_NULL))
139 return __this_address;
142 if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(crc, btnum))
143 return __this_address;
144 if (be16_to_cpu(block->bb_level) != level)
145 return __this_address;
146 if (be16_to_cpu(block->bb_numrecs) >
147 cur->bc_ops->get_maxrecs(cur, level))
148 return __this_address;
149 if (block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK) &&
150 !xfs_btree_check_sptr(cur, be32_to_cpu(block->bb_u.s.bb_leftsib),
152 return __this_address;
153 if (block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK) &&
154 !xfs_btree_check_sptr(cur, be32_to_cpu(block->bb_u.s.bb_rightsib),
156 return __this_address;
161 /* Check a short btree block header. */
163 xfs_btree_check_sblock(
164 struct xfs_btree_cur *cur,
165 struct xfs_btree_block *block,
169 struct xfs_mount *mp = cur->bc_mp;
172 fa = __xfs_btree_check_sblock(cur, block, level, bp);
173 if (XFS_IS_CORRUPT(mp, fa != NULL) ||
174 XFS_TEST_ERROR(false, mp, XFS_ERRTAG_BTREE_CHECK_SBLOCK)) {
176 trace_xfs_btree_corrupt(bp, _RET_IP_);
177 return -EFSCORRUPTED;
183 * Debug routine: check that block header is ok.
186 xfs_btree_check_block(
187 struct xfs_btree_cur *cur, /* btree cursor */
188 struct xfs_btree_block *block, /* generic btree block pointer */
189 int level, /* level of the btree block */
190 struct xfs_buf *bp) /* buffer containing block, if any */
192 if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
193 return xfs_btree_check_lblock(cur, block, level, bp);
195 return xfs_btree_check_sblock(cur, block, level, bp);
198 /* Check that this long pointer is valid and points within the fs. */
200 xfs_btree_check_lptr(
201 struct xfs_btree_cur *cur,
207 return xfs_verify_fsbno(cur->bc_mp, fsbno);
210 /* Check that this short pointer is valid and points within the AG. */
212 xfs_btree_check_sptr(
213 struct xfs_btree_cur *cur,
219 return xfs_verify_agbno(cur->bc_mp, cur->bc_ag.pag->pag_agno, agbno);
223 * Check that a given (indexed) btree pointer at a certain level of a
224 * btree is valid and doesn't point past where it should.
228 struct xfs_btree_cur *cur,
229 const union xfs_btree_ptr *ptr,
233 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
234 if (xfs_btree_check_lptr(cur, be64_to_cpu((&ptr->l)[index]),
238 "Inode %llu fork %d: Corrupt btree %d pointer at level %d index %d.",
239 cur->bc_ino.ip->i_ino,
240 cur->bc_ino.whichfork, cur->bc_btnum,
243 if (xfs_btree_check_sptr(cur, be32_to_cpu((&ptr->s)[index]),
247 "AG %u: Corrupt btree %d pointer at level %d index %d.",
248 cur->bc_ag.pag->pag_agno, cur->bc_btnum,
252 return -EFSCORRUPTED;
256 # define xfs_btree_debug_check_ptr xfs_btree_check_ptr
258 # define xfs_btree_debug_check_ptr(...) (0)
262 * Calculate CRC on the whole btree block and stuff it into the
263 * long-form btree header.
265 * Prior to calculting the CRC, pull the LSN out of the buffer log item and put
266 * it into the buffer so recovery knows what the last modification was that made
270 xfs_btree_lblock_calc_crc(
273 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
274 struct xfs_buf_log_item *bip = bp->b_log_item;
276 if (!xfs_sb_version_hascrc(&bp->b_mount->m_sb))
279 block->bb_u.l.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn);
280 xfs_buf_update_cksum(bp, XFS_BTREE_LBLOCK_CRC_OFF);
284 xfs_btree_lblock_verify_crc(
287 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
288 struct xfs_mount *mp = bp->b_mount;
290 if (xfs_sb_version_hascrc(&mp->m_sb)) {
291 if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.l.bb_lsn)))
293 return xfs_buf_verify_cksum(bp, XFS_BTREE_LBLOCK_CRC_OFF);
300 * Calculate CRC on the whole btree block and stuff it into the
301 * short-form btree header.
303 * Prior to calculting the CRC, pull the LSN out of the buffer log item and put
304 * it into the buffer so recovery knows what the last modification was that made
308 xfs_btree_sblock_calc_crc(
311 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
312 struct xfs_buf_log_item *bip = bp->b_log_item;
314 if (!xfs_sb_version_hascrc(&bp->b_mount->m_sb))
317 block->bb_u.s.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn);
318 xfs_buf_update_cksum(bp, XFS_BTREE_SBLOCK_CRC_OFF);
322 xfs_btree_sblock_verify_crc(
325 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
326 struct xfs_mount *mp = bp->b_mount;
328 if (xfs_sb_version_hascrc(&mp->m_sb)) {
329 if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.s.bb_lsn)))
331 return xfs_buf_verify_cksum(bp, XFS_BTREE_SBLOCK_CRC_OFF);
338 xfs_btree_free_block(
339 struct xfs_btree_cur *cur,
344 error = cur->bc_ops->free_block(cur, bp);
346 xfs_trans_binval(cur->bc_tp, bp);
347 XFS_BTREE_STATS_INC(cur, free);
353 * Delete the btree cursor.
356 xfs_btree_del_cursor(
357 struct xfs_btree_cur *cur, /* btree cursor */
358 int error) /* del because of error */
360 int i; /* btree level */
363 * Clear the buffer pointers and release the buffers. If we're doing
364 * this because of an error, inspect all of the entries in the bc_bufs
365 * array for buffers to be unlocked. This is because some of the btree
366 * code works from level n down to 0, and if we get an error along the
367 * way we won't have initialized all the entries down to 0.
369 for (i = 0; i < cur->bc_nlevels; i++) {
371 xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[i]);
376 ASSERT(cur->bc_btnum != XFS_BTNUM_BMAP || cur->bc_ino.allocated == 0 ||
377 XFS_FORCED_SHUTDOWN(cur->bc_mp));
378 if (unlikely(cur->bc_flags & XFS_BTREE_STAGING))
379 kmem_free(cur->bc_ops);
380 if (!(cur->bc_flags & XFS_BTREE_LONG_PTRS) && cur->bc_ag.pag)
381 xfs_perag_put(cur->bc_ag.pag);
382 kmem_cache_free(xfs_btree_cur_zone, cur);
386 * Duplicate the btree cursor.
387 * Allocate a new one, copy the record, re-get the buffers.
390 xfs_btree_dup_cursor(
391 xfs_btree_cur_t *cur, /* input cursor */
392 xfs_btree_cur_t **ncur) /* output cursor */
394 struct xfs_buf *bp; /* btree block's buffer pointer */
395 int error; /* error return value */
396 int i; /* level number of btree block */
397 xfs_mount_t *mp; /* mount structure for filesystem */
398 xfs_btree_cur_t *new; /* new cursor value */
399 xfs_trans_t *tp; /* transaction pointer, can be NULL */
405 * Allocate a new cursor like the old one.
407 new = cur->bc_ops->dup_cursor(cur);
410 * Copy the record currently in the cursor.
412 new->bc_rec = cur->bc_rec;
415 * For each level current, re-get the buffer and copy the ptr value.
417 for (i = 0; i < new->bc_nlevels; i++) {
418 new->bc_ptrs[i] = cur->bc_ptrs[i];
419 new->bc_ra[i] = cur->bc_ra[i];
420 bp = cur->bc_bufs[i];
422 error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp,
423 XFS_BUF_ADDR(bp), mp->m_bsize,
425 cur->bc_ops->buf_ops);
427 xfs_btree_del_cursor(new, error);
432 new->bc_bufs[i] = bp;
439 * XFS btree block layout and addressing:
441 * There are two types of blocks in the btree: leaf and non-leaf blocks.
443 * The leaf record start with a header then followed by records containing
444 * the values. A non-leaf block also starts with the same header, and
445 * then first contains lookup keys followed by an equal number of pointers
446 * to the btree blocks at the previous level.
448 * +--------+-------+-------+-------+-------+-------+-------+
449 * Leaf: | header | rec 1 | rec 2 | rec 3 | rec 4 | rec 5 | rec N |
450 * +--------+-------+-------+-------+-------+-------+-------+
452 * +--------+-------+-------+-------+-------+-------+-------+
453 * Non-Leaf: | header | key 1 | key 2 | key N | ptr 1 | ptr 2 | ptr N |
454 * +--------+-------+-------+-------+-------+-------+-------+
456 * The header is called struct xfs_btree_block for reasons better left unknown
457 * and comes in different versions for short (32bit) and long (64bit) block
458 * pointers. The record and key structures are defined by the btree instances
459 * and opaque to the btree core. The block pointers are simple disk endian
460 * integers, available in a short (32bit) and long (64bit) variant.
462 * The helpers below calculate the offset of a given record, key or pointer
463 * into a btree block (xfs_btree_*_offset) or return a pointer to the given
464 * record, key or pointer (xfs_btree_*_addr). Note that all addressing
465 * inside the btree block is done using indices starting at one, not zero!
467 * If XFS_BTREE_OVERLAPPING is set, then this btree supports keys containing
468 * overlapping intervals. In such a tree, records are still sorted lowest to
469 * highest and indexed by the smallest key value that refers to the record.
470 * However, nodes are different: each pointer has two associated keys -- one
471 * indexing the lowest key available in the block(s) below (the same behavior
472 * as the key in a regular btree) and another indexing the highest key
473 * available in the block(s) below. Because records are /not/ sorted by the
474 * highest key, all leaf block updates require us to compute the highest key
475 * that matches any record in the leaf and to recursively update the high keys
476 * in the nodes going further up in the tree, if necessary. Nodes look like
479 * +--------+-----+-----+-----+-----+-----+-------+-------+-----+
480 * Non-Leaf: | header | lo1 | hi1 | lo2 | hi2 | ... | ptr 1 | ptr 2 | ... |
481 * +--------+-----+-----+-----+-----+-----+-------+-------+-----+
483 * To perform an interval query on an overlapped tree, perform the usual
484 * depth-first search and use the low and high keys to decide if we can skip
485 * that particular node. If a leaf node is reached, return the records that
486 * intersect the interval. Note that an interval query may return numerous
487 * entries. For a non-overlapped tree, simply search for the record associated
488 * with the lowest key and iterate forward until a non-matching record is
489 * found. Section 14.3 ("Interval Trees") of _Introduction to Algorithms_ by
490 * Cormen, Leiserson, Rivest, and Stein (2nd or 3rd ed. only) discuss this in
493 * Why do we care about overlapping intervals? Let's say you have a bunch of
494 * reverse mapping records on a reflink filesystem:
496 * 1: +- file A startblock B offset C length D -----------+
497 * 2: +- file E startblock F offset G length H --------------+
498 * 3: +- file I startblock F offset J length K --+
499 * 4: +- file L... --+
501 * Now say we want to map block (B+D) into file A at offset (C+D). Ideally,
502 * we'd simply increment the length of record 1. But how do we find the record
503 * that ends at (B+D-1) (i.e. record 1)? A LE lookup of (B+D-1) would return
504 * record 3 because the keys are ordered first by startblock. An interval
505 * query would return records 1 and 2 because they both overlap (B+D-1), and
506 * from that we can pick out record 1 as the appropriate left neighbor.
508 * In the non-overlapped case you can do a LE lookup and decrement the cursor
509 * because a record's interval must end before the next record.
513 * Return size of the btree block header for this btree instance.
515 static inline size_t xfs_btree_block_len(struct xfs_btree_cur *cur)
517 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
518 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS)
519 return XFS_BTREE_LBLOCK_CRC_LEN;
520 return XFS_BTREE_LBLOCK_LEN;
522 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS)
523 return XFS_BTREE_SBLOCK_CRC_LEN;
524 return XFS_BTREE_SBLOCK_LEN;
528 * Return size of btree block pointers for this btree instance.
530 static inline size_t xfs_btree_ptr_len(struct xfs_btree_cur *cur)
532 return (cur->bc_flags & XFS_BTREE_LONG_PTRS) ?
533 sizeof(__be64) : sizeof(__be32);
537 * Calculate offset of the n-th record in a btree block.
540 xfs_btree_rec_offset(
541 struct xfs_btree_cur *cur,
544 return xfs_btree_block_len(cur) +
545 (n - 1) * cur->bc_ops->rec_len;
549 * Calculate offset of the n-th key in a btree block.
552 xfs_btree_key_offset(
553 struct xfs_btree_cur *cur,
556 return xfs_btree_block_len(cur) +
557 (n - 1) * cur->bc_ops->key_len;
561 * Calculate offset of the n-th high key in a btree block.
564 xfs_btree_high_key_offset(
565 struct xfs_btree_cur *cur,
568 return xfs_btree_block_len(cur) +
569 (n - 1) * cur->bc_ops->key_len + (cur->bc_ops->key_len / 2);
573 * Calculate offset of the n-th block pointer in a btree block.
576 xfs_btree_ptr_offset(
577 struct xfs_btree_cur *cur,
581 return xfs_btree_block_len(cur) +
582 cur->bc_ops->get_maxrecs(cur, level) * cur->bc_ops->key_len +
583 (n - 1) * xfs_btree_ptr_len(cur);
587 * Return a pointer to the n-th record in the btree block.
589 union xfs_btree_rec *
591 struct xfs_btree_cur *cur,
593 struct xfs_btree_block *block)
595 return (union xfs_btree_rec *)
596 ((char *)block + xfs_btree_rec_offset(cur, n));
600 * Return a pointer to the n-th key in the btree block.
602 union xfs_btree_key *
604 struct xfs_btree_cur *cur,
606 struct xfs_btree_block *block)
608 return (union xfs_btree_key *)
609 ((char *)block + xfs_btree_key_offset(cur, n));
613 * Return a pointer to the n-th high key in the btree block.
615 union xfs_btree_key *
616 xfs_btree_high_key_addr(
617 struct xfs_btree_cur *cur,
619 struct xfs_btree_block *block)
621 return (union xfs_btree_key *)
622 ((char *)block + xfs_btree_high_key_offset(cur, n));
626 * Return a pointer to the n-th block pointer in the btree block.
628 union xfs_btree_ptr *
630 struct xfs_btree_cur *cur,
632 struct xfs_btree_block *block)
634 int level = xfs_btree_get_level(block);
636 ASSERT(block->bb_level != 0);
638 return (union xfs_btree_ptr *)
639 ((char *)block + xfs_btree_ptr_offset(cur, n, level));
644 struct xfs_btree_cur *cur)
646 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE);
648 if (cur->bc_flags & XFS_BTREE_STAGING)
649 return cur->bc_ino.ifake->if_fork;
650 return XFS_IFORK_PTR(cur->bc_ino.ip, cur->bc_ino.whichfork);
654 * Get the root block which is stored in the inode.
656 * For now this btree implementation assumes the btree root is always
657 * stored in the if_broot field of an inode fork.
659 STATIC struct xfs_btree_block *
661 struct xfs_btree_cur *cur)
663 struct xfs_ifork *ifp = xfs_btree_ifork_ptr(cur);
665 return (struct xfs_btree_block *)ifp->if_broot;
669 * Retrieve the block pointer from the cursor at the given level.
670 * This may be an inode btree root or from a buffer.
672 struct xfs_btree_block * /* generic btree block pointer */
674 struct xfs_btree_cur *cur, /* btree cursor */
675 int level, /* level in btree */
676 struct xfs_buf **bpp) /* buffer containing the block */
678 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
679 (level == cur->bc_nlevels - 1)) {
681 return xfs_btree_get_iroot(cur);
684 *bpp = cur->bc_bufs[level];
685 return XFS_BUF_TO_BLOCK(*bpp);
689 * Change the cursor to point to the first record at the given level.
690 * Other levels are unaffected.
692 STATIC int /* success=1, failure=0 */
694 xfs_btree_cur_t *cur, /* btree cursor */
695 int level) /* level to change */
697 struct xfs_btree_block *block; /* generic btree block pointer */
698 struct xfs_buf *bp; /* buffer containing block */
701 * Get the block pointer for this level.
703 block = xfs_btree_get_block(cur, level, &bp);
704 if (xfs_btree_check_block(cur, block, level, bp))
707 * It's empty, there is no such record.
709 if (!block->bb_numrecs)
712 * Set the ptr value to 1, that's the first record/key.
714 cur->bc_ptrs[level] = 1;
719 * Change the cursor to point to the last record in the current block
720 * at the given level. Other levels are unaffected.
722 STATIC int /* success=1, failure=0 */
724 xfs_btree_cur_t *cur, /* btree cursor */
725 int level) /* level to change */
727 struct xfs_btree_block *block; /* generic btree block pointer */
728 struct xfs_buf *bp; /* buffer containing block */
731 * Get the block pointer for this level.
733 block = xfs_btree_get_block(cur, level, &bp);
734 if (xfs_btree_check_block(cur, block, level, bp))
737 * It's empty, there is no such record.
739 if (!block->bb_numrecs)
742 * Set the ptr value to numrecs, that's the last record/key.
744 cur->bc_ptrs[level] = be16_to_cpu(block->bb_numrecs);
749 * Compute first and last byte offsets for the fields given.
750 * Interprets the offsets table, which contains struct field offsets.
754 int64_t fields, /* bitmask of fields */
755 const short *offsets, /* table of field offsets */
756 int nbits, /* number of bits to inspect */
757 int *first, /* output: first byte offset */
758 int *last) /* output: last byte offset */
760 int i; /* current bit number */
761 int64_t imask; /* mask for current bit number */
765 * Find the lowest bit, so the first byte offset.
767 for (i = 0, imask = 1LL; ; i++, imask <<= 1) {
768 if (imask & fields) {
774 * Find the highest bit, so the last byte offset.
776 for (i = nbits - 1, imask = 1LL << i; ; i--, imask >>= 1) {
777 if (imask & fields) {
778 *last = offsets[i + 1] - 1;
785 * Get a buffer for the block, return it read in.
786 * Long-form addressing.
790 struct xfs_mount *mp, /* file system mount point */
791 struct xfs_trans *tp, /* transaction pointer */
792 xfs_fsblock_t fsbno, /* file system block number */
793 struct xfs_buf **bpp, /* buffer for fsbno */
794 int refval, /* ref count value for buffer */
795 const struct xfs_buf_ops *ops)
797 struct xfs_buf *bp; /* return value */
798 xfs_daddr_t d; /* real disk block address */
801 if (!xfs_verify_fsbno(mp, fsbno))
802 return -EFSCORRUPTED;
803 d = XFS_FSB_TO_DADDR(mp, fsbno);
804 error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, d,
805 mp->m_bsize, 0, &bp, ops);
809 xfs_buf_set_ref(bp, refval);
815 * Read-ahead the block, don't wait for it, don't return a buffer.
816 * Long-form addressing.
820 xfs_btree_reada_bufl(
821 struct xfs_mount *mp, /* file system mount point */
822 xfs_fsblock_t fsbno, /* file system block number */
823 xfs_extlen_t count, /* count of filesystem blocks */
824 const struct xfs_buf_ops *ops)
828 ASSERT(fsbno != NULLFSBLOCK);
829 d = XFS_FSB_TO_DADDR(mp, fsbno);
830 xfs_buf_readahead(mp->m_ddev_targp, d, mp->m_bsize * count, ops);
834 * Read-ahead the block, don't wait for it, don't return a buffer.
835 * Short-form addressing.
839 xfs_btree_reada_bufs(
840 struct xfs_mount *mp, /* file system mount point */
841 xfs_agnumber_t agno, /* allocation group number */
842 xfs_agblock_t agbno, /* allocation group block number */
843 xfs_extlen_t count, /* count of filesystem blocks */
844 const struct xfs_buf_ops *ops)
848 ASSERT(agno != NULLAGNUMBER);
849 ASSERT(agbno != NULLAGBLOCK);
850 d = XFS_AGB_TO_DADDR(mp, agno, agbno);
851 xfs_buf_readahead(mp->m_ddev_targp, d, mp->m_bsize * count, ops);
855 xfs_btree_readahead_lblock(
856 struct xfs_btree_cur *cur,
858 struct xfs_btree_block *block)
861 xfs_fsblock_t left = be64_to_cpu(block->bb_u.l.bb_leftsib);
862 xfs_fsblock_t right = be64_to_cpu(block->bb_u.l.bb_rightsib);
864 if ((lr & XFS_BTCUR_LEFTRA) && left != NULLFSBLOCK) {
865 xfs_btree_reada_bufl(cur->bc_mp, left, 1,
866 cur->bc_ops->buf_ops);
870 if ((lr & XFS_BTCUR_RIGHTRA) && right != NULLFSBLOCK) {
871 xfs_btree_reada_bufl(cur->bc_mp, right, 1,
872 cur->bc_ops->buf_ops);
880 xfs_btree_readahead_sblock(
881 struct xfs_btree_cur *cur,
883 struct xfs_btree_block *block)
886 xfs_agblock_t left = be32_to_cpu(block->bb_u.s.bb_leftsib);
887 xfs_agblock_t right = be32_to_cpu(block->bb_u.s.bb_rightsib);
890 if ((lr & XFS_BTCUR_LEFTRA) && left != NULLAGBLOCK) {
891 xfs_btree_reada_bufs(cur->bc_mp, cur->bc_ag.pag->pag_agno,
892 left, 1, cur->bc_ops->buf_ops);
896 if ((lr & XFS_BTCUR_RIGHTRA) && right != NULLAGBLOCK) {
897 xfs_btree_reada_bufs(cur->bc_mp, cur->bc_ag.pag->pag_agno,
898 right, 1, cur->bc_ops->buf_ops);
906 * Read-ahead btree blocks, at the given level.
907 * Bits in lr are set from XFS_BTCUR_{LEFT,RIGHT}RA.
911 struct xfs_btree_cur *cur, /* btree cursor */
912 int lev, /* level in btree */
913 int lr) /* left/right bits */
915 struct xfs_btree_block *block;
918 * No readahead needed if we are at the root level and the
919 * btree root is stored in the inode.
921 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
922 (lev == cur->bc_nlevels - 1))
925 if ((cur->bc_ra[lev] | lr) == cur->bc_ra[lev])
928 cur->bc_ra[lev] |= lr;
929 block = XFS_BUF_TO_BLOCK(cur->bc_bufs[lev]);
931 if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
932 return xfs_btree_readahead_lblock(cur, lr, block);
933 return xfs_btree_readahead_sblock(cur, lr, block);
937 xfs_btree_ptr_to_daddr(
938 struct xfs_btree_cur *cur,
939 const union xfs_btree_ptr *ptr,
946 error = xfs_btree_check_ptr(cur, ptr, 0, 1);
950 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
951 fsbno = be64_to_cpu(ptr->l);
952 *daddr = XFS_FSB_TO_DADDR(cur->bc_mp, fsbno);
954 agbno = be32_to_cpu(ptr->s);
955 *daddr = XFS_AGB_TO_DADDR(cur->bc_mp, cur->bc_ag.pag->pag_agno,
963 * Readahead @count btree blocks at the given @ptr location.
965 * We don't need to care about long or short form btrees here as we have a
966 * method of converting the ptr directly to a daddr available to us.
969 xfs_btree_readahead_ptr(
970 struct xfs_btree_cur *cur,
971 union xfs_btree_ptr *ptr,
976 if (xfs_btree_ptr_to_daddr(cur, ptr, &daddr))
978 xfs_buf_readahead(cur->bc_mp->m_ddev_targp, daddr,
979 cur->bc_mp->m_bsize * count, cur->bc_ops->buf_ops);
983 * Set the buffer for level "lev" in the cursor to bp, releasing
984 * any previous buffer.
988 xfs_btree_cur_t *cur, /* btree cursor */
989 int lev, /* level in btree */
990 struct xfs_buf *bp) /* new buffer to set */
992 struct xfs_btree_block *b; /* btree block */
994 if (cur->bc_bufs[lev])
995 xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[lev]);
996 cur->bc_bufs[lev] = bp;
999 b = XFS_BUF_TO_BLOCK(bp);
1000 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
1001 if (b->bb_u.l.bb_leftsib == cpu_to_be64(NULLFSBLOCK))
1002 cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA;
1003 if (b->bb_u.l.bb_rightsib == cpu_to_be64(NULLFSBLOCK))
1004 cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA;
1006 if (b->bb_u.s.bb_leftsib == cpu_to_be32(NULLAGBLOCK))
1007 cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA;
1008 if (b->bb_u.s.bb_rightsib == cpu_to_be32(NULLAGBLOCK))
1009 cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA;
1014 xfs_btree_ptr_is_null(
1015 struct xfs_btree_cur *cur,
1016 const union xfs_btree_ptr *ptr)
1018 if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
1019 return ptr->l == cpu_to_be64(NULLFSBLOCK);
1021 return ptr->s == cpu_to_be32(NULLAGBLOCK);
1025 xfs_btree_set_ptr_null(
1026 struct xfs_btree_cur *cur,
1027 union xfs_btree_ptr *ptr)
1029 if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
1030 ptr->l = cpu_to_be64(NULLFSBLOCK);
1032 ptr->s = cpu_to_be32(NULLAGBLOCK);
1036 * Get/set/init sibling pointers
1039 xfs_btree_get_sibling(
1040 struct xfs_btree_cur *cur,
1041 struct xfs_btree_block *block,
1042 union xfs_btree_ptr *ptr,
1045 ASSERT(lr == XFS_BB_LEFTSIB || lr == XFS_BB_RIGHTSIB);
1047 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
1048 if (lr == XFS_BB_RIGHTSIB)
1049 ptr->l = block->bb_u.l.bb_rightsib;
1051 ptr->l = block->bb_u.l.bb_leftsib;
1053 if (lr == XFS_BB_RIGHTSIB)
1054 ptr->s = block->bb_u.s.bb_rightsib;
1056 ptr->s = block->bb_u.s.bb_leftsib;
1061 xfs_btree_set_sibling(
1062 struct xfs_btree_cur *cur,
1063 struct xfs_btree_block *block,
1064 const union xfs_btree_ptr *ptr,
1067 ASSERT(lr == XFS_BB_LEFTSIB || lr == XFS_BB_RIGHTSIB);
1069 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
1070 if (lr == XFS_BB_RIGHTSIB)
1071 block->bb_u.l.bb_rightsib = ptr->l;
1073 block->bb_u.l.bb_leftsib = ptr->l;
1075 if (lr == XFS_BB_RIGHTSIB)
1076 block->bb_u.s.bb_rightsib = ptr->s;
1078 block->bb_u.s.bb_leftsib = ptr->s;
1083 xfs_btree_init_block_int(
1084 struct xfs_mount *mp,
1085 struct xfs_btree_block *buf,
1093 int crc = xfs_sb_version_hascrc(&mp->m_sb);
1094 __u32 magic = xfs_btree_magic(crc, btnum);
1096 buf->bb_magic = cpu_to_be32(magic);
1097 buf->bb_level = cpu_to_be16(level);
1098 buf->bb_numrecs = cpu_to_be16(numrecs);
1100 if (flags & XFS_BTREE_LONG_PTRS) {
1101 buf->bb_u.l.bb_leftsib = cpu_to_be64(NULLFSBLOCK);
1102 buf->bb_u.l.bb_rightsib = cpu_to_be64(NULLFSBLOCK);
1104 buf->bb_u.l.bb_blkno = cpu_to_be64(blkno);
1105 buf->bb_u.l.bb_owner = cpu_to_be64(owner);
1106 uuid_copy(&buf->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid);
1107 buf->bb_u.l.bb_pad = 0;
1108 buf->bb_u.l.bb_lsn = 0;
1111 /* owner is a 32 bit value on short blocks */
1112 __u32 __owner = (__u32)owner;
1114 buf->bb_u.s.bb_leftsib = cpu_to_be32(NULLAGBLOCK);
1115 buf->bb_u.s.bb_rightsib = cpu_to_be32(NULLAGBLOCK);
1117 buf->bb_u.s.bb_blkno = cpu_to_be64(blkno);
1118 buf->bb_u.s.bb_owner = cpu_to_be32(__owner);
1119 uuid_copy(&buf->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid);
1120 buf->bb_u.s.bb_lsn = 0;
1126 xfs_btree_init_block(
1127 struct xfs_mount *mp,
1134 xfs_btree_init_block_int(mp, XFS_BUF_TO_BLOCK(bp), bp->b_bn,
1135 btnum, level, numrecs, owner, 0);
1139 xfs_btree_init_block_cur(
1140 struct xfs_btree_cur *cur,
1148 * we can pull the owner from the cursor right now as the different
1149 * owners align directly with the pointer size of the btree. This may
1150 * change in future, but is safe for current users of the generic btree
1153 if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
1154 owner = cur->bc_ino.ip->i_ino;
1156 owner = cur->bc_ag.pag->pag_agno;
1158 xfs_btree_init_block_int(cur->bc_mp, XFS_BUF_TO_BLOCK(bp), bp->b_bn,
1159 cur->bc_btnum, level, numrecs,
1160 owner, cur->bc_flags);
1164 * Return true if ptr is the last record in the btree and
1165 * we need to track updates to this record. The decision
1166 * will be further refined in the update_lastrec method.
1169 xfs_btree_is_lastrec(
1170 struct xfs_btree_cur *cur,
1171 struct xfs_btree_block *block,
1174 union xfs_btree_ptr ptr;
1178 if (!(cur->bc_flags & XFS_BTREE_LASTREC_UPDATE))
1181 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
1182 if (!xfs_btree_ptr_is_null(cur, &ptr))
1188 xfs_btree_buf_to_ptr(
1189 struct xfs_btree_cur *cur,
1191 union xfs_btree_ptr *ptr)
1193 if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
1194 ptr->l = cpu_to_be64(XFS_DADDR_TO_FSB(cur->bc_mp,
1197 ptr->s = cpu_to_be32(xfs_daddr_to_agbno(cur->bc_mp,
1204 struct xfs_btree_cur *cur,
1207 switch (cur->bc_btnum) {
1210 xfs_buf_set_ref(bp, XFS_ALLOC_BTREE_REF);
1213 case XFS_BTNUM_FINO:
1214 xfs_buf_set_ref(bp, XFS_INO_BTREE_REF);
1216 case XFS_BTNUM_BMAP:
1217 xfs_buf_set_ref(bp, XFS_BMAP_BTREE_REF);
1219 case XFS_BTNUM_RMAP:
1220 xfs_buf_set_ref(bp, XFS_RMAP_BTREE_REF);
1222 case XFS_BTNUM_REFC:
1223 xfs_buf_set_ref(bp, XFS_REFC_BTREE_REF);
1231 xfs_btree_get_buf_block(
1232 struct xfs_btree_cur *cur,
1233 const union xfs_btree_ptr *ptr,
1234 struct xfs_btree_block **block,
1235 struct xfs_buf **bpp)
1237 struct xfs_mount *mp = cur->bc_mp;
1241 error = xfs_btree_ptr_to_daddr(cur, ptr, &d);
1244 error = xfs_trans_get_buf(cur->bc_tp, mp->m_ddev_targp, d, mp->m_bsize,
1249 (*bpp)->b_ops = cur->bc_ops->buf_ops;
1250 *block = XFS_BUF_TO_BLOCK(*bpp);
1255 * Read in the buffer at the given ptr and return the buffer and
1256 * the block pointer within the buffer.
1259 xfs_btree_read_buf_block(
1260 struct xfs_btree_cur *cur,
1261 const union xfs_btree_ptr *ptr,
1263 struct xfs_btree_block **block,
1264 struct xfs_buf **bpp)
1266 struct xfs_mount *mp = cur->bc_mp;
1270 /* need to sort out how callers deal with failures first */
1271 ASSERT(!(flags & XBF_TRYLOCK));
1273 error = xfs_btree_ptr_to_daddr(cur, ptr, &d);
1276 error = xfs_trans_read_buf(mp, cur->bc_tp, mp->m_ddev_targp, d,
1277 mp->m_bsize, flags, bpp,
1278 cur->bc_ops->buf_ops);
1282 xfs_btree_set_refs(cur, *bpp);
1283 *block = XFS_BUF_TO_BLOCK(*bpp);
1288 * Copy keys from one btree block to another.
1291 xfs_btree_copy_keys(
1292 struct xfs_btree_cur *cur,
1293 union xfs_btree_key *dst_key,
1294 const union xfs_btree_key *src_key,
1297 ASSERT(numkeys >= 0);
1298 memcpy(dst_key, src_key, numkeys * cur->bc_ops->key_len);
1302 * Copy records from one btree block to another.
1305 xfs_btree_copy_recs(
1306 struct xfs_btree_cur *cur,
1307 union xfs_btree_rec *dst_rec,
1308 union xfs_btree_rec *src_rec,
1311 ASSERT(numrecs >= 0);
1312 memcpy(dst_rec, src_rec, numrecs * cur->bc_ops->rec_len);
1316 * Copy block pointers from one btree block to another.
1319 xfs_btree_copy_ptrs(
1320 struct xfs_btree_cur *cur,
1321 union xfs_btree_ptr *dst_ptr,
1322 const union xfs_btree_ptr *src_ptr,
1325 ASSERT(numptrs >= 0);
1326 memcpy(dst_ptr, src_ptr, numptrs * xfs_btree_ptr_len(cur));
1330 * Shift keys one index left/right inside a single btree block.
1333 xfs_btree_shift_keys(
1334 struct xfs_btree_cur *cur,
1335 union xfs_btree_key *key,
1341 ASSERT(numkeys >= 0);
1342 ASSERT(dir == 1 || dir == -1);
1344 dst_key = (char *)key + (dir * cur->bc_ops->key_len);
1345 memmove(dst_key, key, numkeys * cur->bc_ops->key_len);
1349 * Shift records one index left/right inside a single btree block.
1352 xfs_btree_shift_recs(
1353 struct xfs_btree_cur *cur,
1354 union xfs_btree_rec *rec,
1360 ASSERT(numrecs >= 0);
1361 ASSERT(dir == 1 || dir == -1);
1363 dst_rec = (char *)rec + (dir * cur->bc_ops->rec_len);
1364 memmove(dst_rec, rec, numrecs * cur->bc_ops->rec_len);
1368 * Shift block pointers one index left/right inside a single btree block.
1371 xfs_btree_shift_ptrs(
1372 struct xfs_btree_cur *cur,
1373 union xfs_btree_ptr *ptr,
1379 ASSERT(numptrs >= 0);
1380 ASSERT(dir == 1 || dir == -1);
1382 dst_ptr = (char *)ptr + (dir * xfs_btree_ptr_len(cur));
1383 memmove(dst_ptr, ptr, numptrs * xfs_btree_ptr_len(cur));
1387 * Log key values from the btree block.
1391 struct xfs_btree_cur *cur,
1398 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);
1399 xfs_trans_log_buf(cur->bc_tp, bp,
1400 xfs_btree_key_offset(cur, first),
1401 xfs_btree_key_offset(cur, last + 1) - 1);
1403 xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip,
1404 xfs_ilog_fbroot(cur->bc_ino.whichfork));
1409 * Log record values from the btree block.
1413 struct xfs_btree_cur *cur,
1419 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);
1420 xfs_trans_log_buf(cur->bc_tp, bp,
1421 xfs_btree_rec_offset(cur, first),
1422 xfs_btree_rec_offset(cur, last + 1) - 1);
1427 * Log block pointer fields from a btree block (nonleaf).
1431 struct xfs_btree_cur *cur, /* btree cursor */
1432 struct xfs_buf *bp, /* buffer containing btree block */
1433 int first, /* index of first pointer to log */
1434 int last) /* index of last pointer to log */
1438 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
1439 int level = xfs_btree_get_level(block);
1441 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);
1442 xfs_trans_log_buf(cur->bc_tp, bp,
1443 xfs_btree_ptr_offset(cur, first, level),
1444 xfs_btree_ptr_offset(cur, last + 1, level) - 1);
1446 xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip,
1447 xfs_ilog_fbroot(cur->bc_ino.whichfork));
1453 * Log fields from a btree block header.
1456 xfs_btree_log_block(
1457 struct xfs_btree_cur *cur, /* btree cursor */
1458 struct xfs_buf *bp, /* buffer containing btree block */
1459 int fields) /* mask of fields: XFS_BB_... */
1461 int first; /* first byte offset logged */
1462 int last; /* last byte offset logged */
1463 static const short soffsets[] = { /* table of offsets (short) */
1464 offsetof(struct xfs_btree_block, bb_magic),
1465 offsetof(struct xfs_btree_block, bb_level),
1466 offsetof(struct xfs_btree_block, bb_numrecs),
1467 offsetof(struct xfs_btree_block, bb_u.s.bb_leftsib),
1468 offsetof(struct xfs_btree_block, bb_u.s.bb_rightsib),
1469 offsetof(struct xfs_btree_block, bb_u.s.bb_blkno),
1470 offsetof(struct xfs_btree_block, bb_u.s.bb_lsn),
1471 offsetof(struct xfs_btree_block, bb_u.s.bb_uuid),
1472 offsetof(struct xfs_btree_block, bb_u.s.bb_owner),
1473 offsetof(struct xfs_btree_block, bb_u.s.bb_crc),
1474 XFS_BTREE_SBLOCK_CRC_LEN
1476 static const short loffsets[] = { /* table of offsets (long) */
1477 offsetof(struct xfs_btree_block, bb_magic),
1478 offsetof(struct xfs_btree_block, bb_level),
1479 offsetof(struct xfs_btree_block, bb_numrecs),
1480 offsetof(struct xfs_btree_block, bb_u.l.bb_leftsib),
1481 offsetof(struct xfs_btree_block, bb_u.l.bb_rightsib),
1482 offsetof(struct xfs_btree_block, bb_u.l.bb_blkno),
1483 offsetof(struct xfs_btree_block, bb_u.l.bb_lsn),
1484 offsetof(struct xfs_btree_block, bb_u.l.bb_uuid),
1485 offsetof(struct xfs_btree_block, bb_u.l.bb_owner),
1486 offsetof(struct xfs_btree_block, bb_u.l.bb_crc),
1487 offsetof(struct xfs_btree_block, bb_u.l.bb_pad),
1488 XFS_BTREE_LBLOCK_CRC_LEN
1494 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) {
1496 * We don't log the CRC when updating a btree
1497 * block but instead recreate it during log
1498 * recovery. As the log buffers have checksums
1499 * of their own this is safe and avoids logging a crc
1500 * update in a lot of places.
1502 if (fields == XFS_BB_ALL_BITS)
1503 fields = XFS_BB_ALL_BITS_CRC;
1504 nbits = XFS_BB_NUM_BITS_CRC;
1506 nbits = XFS_BB_NUM_BITS;
1508 xfs_btree_offsets(fields,
1509 (cur->bc_flags & XFS_BTREE_LONG_PTRS) ?
1510 loffsets : soffsets,
1511 nbits, &first, &last);
1512 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);
1513 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
1515 xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip,
1516 xfs_ilog_fbroot(cur->bc_ino.whichfork));
1521 * Increment cursor by one record at the level.
1522 * For nonzero levels the leaf-ward information is untouched.
1525 xfs_btree_increment(
1526 struct xfs_btree_cur *cur,
1528 int *stat) /* success/failure */
1530 struct xfs_btree_block *block;
1531 union xfs_btree_ptr ptr;
1533 int error; /* error return value */
1536 ASSERT(level < cur->bc_nlevels);
1538 /* Read-ahead to the right at this level. */
1539 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
1541 /* Get a pointer to the btree block. */
1542 block = xfs_btree_get_block(cur, level, &bp);
1545 error = xfs_btree_check_block(cur, block, level, bp);
1550 /* We're done if we remain in the block after the increment. */
1551 if (++cur->bc_ptrs[level] <= xfs_btree_get_numrecs(block))
1554 /* Fail if we just went off the right edge of the tree. */
1555 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
1556 if (xfs_btree_ptr_is_null(cur, &ptr))
1559 XFS_BTREE_STATS_INC(cur, increment);
1562 * March up the tree incrementing pointers.
1563 * Stop when we don't go off the right edge of a block.
1565 for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1566 block = xfs_btree_get_block(cur, lev, &bp);
1569 error = xfs_btree_check_block(cur, block, lev, bp);
1574 if (++cur->bc_ptrs[lev] <= xfs_btree_get_numrecs(block))
1577 /* Read-ahead the right block for the next loop. */
1578 xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA);
1582 * If we went off the root then we are either seriously
1583 * confused or have the tree root in an inode.
1585 if (lev == cur->bc_nlevels) {
1586 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
1589 error = -EFSCORRUPTED;
1592 ASSERT(lev < cur->bc_nlevels);
1595 * Now walk back down the tree, fixing up the cursor's buffer
1596 * pointers and key numbers.
1598 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) {
1599 union xfs_btree_ptr *ptrp;
1601 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block);
1603 error = xfs_btree_read_buf_block(cur, ptrp, 0, &block, &bp);
1607 xfs_btree_setbuf(cur, lev, bp);
1608 cur->bc_ptrs[lev] = 1;
1623 * Decrement cursor by one record at the level.
1624 * For nonzero levels the leaf-ward information is untouched.
1627 xfs_btree_decrement(
1628 struct xfs_btree_cur *cur,
1630 int *stat) /* success/failure */
1632 struct xfs_btree_block *block;
1634 int error; /* error return value */
1636 union xfs_btree_ptr ptr;
1638 ASSERT(level < cur->bc_nlevels);
1640 /* Read-ahead to the left at this level. */
1641 xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA);
1643 /* We're done if we remain in the block after the decrement. */
1644 if (--cur->bc_ptrs[level] > 0)
1647 /* Get a pointer to the btree block. */
1648 block = xfs_btree_get_block(cur, level, &bp);
1651 error = xfs_btree_check_block(cur, block, level, bp);
1656 /* Fail if we just went off the left edge of the tree. */
1657 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB);
1658 if (xfs_btree_ptr_is_null(cur, &ptr))
1661 XFS_BTREE_STATS_INC(cur, decrement);
1664 * March up the tree decrementing pointers.
1665 * Stop when we don't go off the left edge of a block.
1667 for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1668 if (--cur->bc_ptrs[lev] > 0)
1670 /* Read-ahead the left block for the next loop. */
1671 xfs_btree_readahead(cur, lev, XFS_BTCUR_LEFTRA);
1675 * If we went off the root then we are seriously confused.
1676 * or the root of the tree is in an inode.
1678 if (lev == cur->bc_nlevels) {
1679 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
1682 error = -EFSCORRUPTED;
1685 ASSERT(lev < cur->bc_nlevels);
1688 * Now walk back down the tree, fixing up the cursor's buffer
1689 * pointers and key numbers.
1691 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) {
1692 union xfs_btree_ptr *ptrp;
1694 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block);
1696 error = xfs_btree_read_buf_block(cur, ptrp, 0, &block, &bp);
1699 xfs_btree_setbuf(cur, lev, bp);
1700 cur->bc_ptrs[lev] = xfs_btree_get_numrecs(block);
1715 xfs_btree_lookup_get_block(
1716 struct xfs_btree_cur *cur, /* btree cursor */
1717 int level, /* level in the btree */
1718 const union xfs_btree_ptr *pp, /* ptr to btree block */
1719 struct xfs_btree_block **blkp) /* return btree block */
1721 struct xfs_buf *bp; /* buffer pointer for btree block */
1725 /* special case the root block if in an inode */
1726 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
1727 (level == cur->bc_nlevels - 1)) {
1728 *blkp = xfs_btree_get_iroot(cur);
1733 * If the old buffer at this level for the disk address we are
1734 * looking for re-use it.
1736 * Otherwise throw it away and get a new one.
1738 bp = cur->bc_bufs[level];
1739 error = xfs_btree_ptr_to_daddr(cur, pp, &daddr);
1742 if (bp && XFS_BUF_ADDR(bp) == daddr) {
1743 *blkp = XFS_BUF_TO_BLOCK(bp);
1747 error = xfs_btree_read_buf_block(cur, pp, 0, blkp, &bp);
1751 /* Check the inode owner since the verifiers don't. */
1752 if (xfs_sb_version_hascrc(&cur->bc_mp->m_sb) &&
1753 !(cur->bc_ino.flags & XFS_BTCUR_BMBT_INVALID_OWNER) &&
1754 (cur->bc_flags & XFS_BTREE_LONG_PTRS) &&
1755 be64_to_cpu((*blkp)->bb_u.l.bb_owner) !=
1756 cur->bc_ino.ip->i_ino)
1759 /* Did we get the level we were looking for? */
1760 if (be16_to_cpu((*blkp)->bb_level) != level)
1763 /* Check that internal nodes have at least one record. */
1764 if (level != 0 && be16_to_cpu((*blkp)->bb_numrecs) == 0)
1767 xfs_btree_setbuf(cur, level, bp);
1772 xfs_buf_mark_corrupt(bp);
1773 xfs_trans_brelse(cur->bc_tp, bp);
1774 return -EFSCORRUPTED;
1778 * Get current search key. For level 0 we don't actually have a key
1779 * structure so we make one up from the record. For all other levels
1780 * we just return the right key.
1782 STATIC union xfs_btree_key *
1783 xfs_lookup_get_search_key(
1784 struct xfs_btree_cur *cur,
1787 struct xfs_btree_block *block,
1788 union xfs_btree_key *kp)
1791 cur->bc_ops->init_key_from_rec(kp,
1792 xfs_btree_rec_addr(cur, keyno, block));
1796 return xfs_btree_key_addr(cur, keyno, block);
1800 * Lookup the record. The cursor is made to point to it, based on dir.
1801 * stat is set to 0 if can't find any such record, 1 for success.
1805 struct xfs_btree_cur *cur, /* btree cursor */
1806 xfs_lookup_t dir, /* <=, ==, or >= */
1807 int *stat) /* success/failure */
1809 struct xfs_btree_block *block; /* current btree block */
1810 int64_t diff; /* difference for the current key */
1811 int error; /* error return value */
1812 int keyno; /* current key number */
1813 int level; /* level in the btree */
1814 union xfs_btree_ptr *pp; /* ptr to btree block */
1815 union xfs_btree_ptr ptr; /* ptr to btree block */
1817 XFS_BTREE_STATS_INC(cur, lookup);
1819 /* No such thing as a zero-level tree. */
1820 if (XFS_IS_CORRUPT(cur->bc_mp, cur->bc_nlevels == 0))
1821 return -EFSCORRUPTED;
1826 /* initialise start pointer from cursor */
1827 cur->bc_ops->init_ptr_from_cur(cur, &ptr);
1831 * Iterate over each level in the btree, starting at the root.
1832 * For each level above the leaves, find the key we need, based
1833 * on the lookup record, then follow the corresponding block
1834 * pointer down to the next level.
1836 for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {
1837 /* Get the block we need to do the lookup on. */
1838 error = xfs_btree_lookup_get_block(cur, level, pp, &block);
1844 * If we already had a key match at a higher level, we
1845 * know we need to use the first entry in this block.
1849 /* Otherwise search this block. Do a binary search. */
1851 int high; /* high entry number */
1852 int low; /* low entry number */
1854 /* Set low and high entry numbers, 1-based. */
1856 high = xfs_btree_get_numrecs(block);
1858 /* Block is empty, must be an empty leaf. */
1859 if (level != 0 || cur->bc_nlevels != 1) {
1860 XFS_CORRUPTION_ERROR(__func__,
1864 return -EFSCORRUPTED;
1867 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE;
1872 /* Binary search the block. */
1873 while (low <= high) {
1874 union xfs_btree_key key;
1875 union xfs_btree_key *kp;
1877 XFS_BTREE_STATS_INC(cur, compare);
1879 /* keyno is average of low and high. */
1880 keyno = (low + high) >> 1;
1882 /* Get current search key */
1883 kp = xfs_lookup_get_search_key(cur, level,
1884 keyno, block, &key);
1887 * Compute difference to get next direction:
1888 * - less than, move right
1889 * - greater than, move left
1890 * - equal, we're done
1892 diff = cur->bc_ops->key_diff(cur, kp);
1903 * If there are more levels, set up for the next level
1904 * by getting the block number and filling in the cursor.
1908 * If we moved left, need the previous key number,
1909 * unless there isn't one.
1911 if (diff > 0 && --keyno < 1)
1913 pp = xfs_btree_ptr_addr(cur, keyno, block);
1915 error = xfs_btree_debug_check_ptr(cur, pp, 0, level);
1919 cur->bc_ptrs[level] = keyno;
1923 /* Done with the search. See if we need to adjust the results. */
1924 if (dir != XFS_LOOKUP_LE && diff < 0) {
1927 * If ge search and we went off the end of the block, but it's
1928 * not the last block, we're in the wrong block.
1930 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
1931 if (dir == XFS_LOOKUP_GE &&
1932 keyno > xfs_btree_get_numrecs(block) &&
1933 !xfs_btree_ptr_is_null(cur, &ptr)) {
1936 cur->bc_ptrs[0] = keyno;
1937 error = xfs_btree_increment(cur, 0, &i);
1940 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1))
1941 return -EFSCORRUPTED;
1945 } else if (dir == XFS_LOOKUP_LE && diff > 0)
1947 cur->bc_ptrs[0] = keyno;
1949 /* Return if we succeeded or not. */
1950 if (keyno == 0 || keyno > xfs_btree_get_numrecs(block))
1952 else if (dir != XFS_LOOKUP_EQ || diff == 0)
1962 /* Find the high key storage area from a regular key. */
1963 union xfs_btree_key *
1964 xfs_btree_high_key_from_key(
1965 struct xfs_btree_cur *cur,
1966 union xfs_btree_key *key)
1968 ASSERT(cur->bc_flags & XFS_BTREE_OVERLAPPING);
1969 return (union xfs_btree_key *)((char *)key +
1970 (cur->bc_ops->key_len / 2));
1973 /* Determine the low (and high if overlapped) keys of a leaf block */
1975 xfs_btree_get_leaf_keys(
1976 struct xfs_btree_cur *cur,
1977 struct xfs_btree_block *block,
1978 union xfs_btree_key *key)
1980 union xfs_btree_key max_hkey;
1981 union xfs_btree_key hkey;
1982 union xfs_btree_rec *rec;
1983 union xfs_btree_key *high;
1986 rec = xfs_btree_rec_addr(cur, 1, block);
1987 cur->bc_ops->init_key_from_rec(key, rec);
1989 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) {
1991 cur->bc_ops->init_high_key_from_rec(&max_hkey, rec);
1992 for (n = 2; n <= xfs_btree_get_numrecs(block); n++) {
1993 rec = xfs_btree_rec_addr(cur, n, block);
1994 cur->bc_ops->init_high_key_from_rec(&hkey, rec);
1995 if (cur->bc_ops->diff_two_keys(cur, &hkey, &max_hkey)
2000 high = xfs_btree_high_key_from_key(cur, key);
2001 memcpy(high, &max_hkey, cur->bc_ops->key_len / 2);
2005 /* Determine the low (and high if overlapped) keys of a node block */
2007 xfs_btree_get_node_keys(
2008 struct xfs_btree_cur *cur,
2009 struct xfs_btree_block *block,
2010 union xfs_btree_key *key)
2012 union xfs_btree_key *hkey;
2013 union xfs_btree_key *max_hkey;
2014 union xfs_btree_key *high;
2017 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) {
2018 memcpy(key, xfs_btree_key_addr(cur, 1, block),
2019 cur->bc_ops->key_len / 2);
2021 max_hkey = xfs_btree_high_key_addr(cur, 1, block);
2022 for (n = 2; n <= xfs_btree_get_numrecs(block); n++) {
2023 hkey = xfs_btree_high_key_addr(cur, n, block);
2024 if (cur->bc_ops->diff_two_keys(cur, hkey, max_hkey) > 0)
2028 high = xfs_btree_high_key_from_key(cur, key);
2029 memcpy(high, max_hkey, cur->bc_ops->key_len / 2);
2031 memcpy(key, xfs_btree_key_addr(cur, 1, block),
2032 cur->bc_ops->key_len);
2036 /* Derive the keys for any btree block. */
2039 struct xfs_btree_cur *cur,
2040 struct xfs_btree_block *block,
2041 union xfs_btree_key *key)
2043 if (be16_to_cpu(block->bb_level) == 0)
2044 xfs_btree_get_leaf_keys(cur, block, key);
2046 xfs_btree_get_node_keys(cur, block, key);
2050 * Decide if we need to update the parent keys of a btree block. For
2051 * a standard btree this is only necessary if we're updating the first
2052 * record/key. For an overlapping btree, we must always update the
2053 * keys because the highest key can be in any of the records or keys
2057 xfs_btree_needs_key_update(
2058 struct xfs_btree_cur *cur,
2061 return (cur->bc_flags & XFS_BTREE_OVERLAPPING) || ptr == 1;
2065 * Update the low and high parent keys of the given level, progressing
2066 * towards the root. If force_all is false, stop if the keys for a given
2067 * level do not need updating.
2070 __xfs_btree_updkeys(
2071 struct xfs_btree_cur *cur,
2073 struct xfs_btree_block *block,
2074 struct xfs_buf *bp0,
2077 union xfs_btree_key key; /* keys from current level */
2078 union xfs_btree_key *lkey; /* keys from the next level up */
2079 union xfs_btree_key *hkey;
2080 union xfs_btree_key *nlkey; /* keys from the next level up */
2081 union xfs_btree_key *nhkey;
2085 ASSERT(cur->bc_flags & XFS_BTREE_OVERLAPPING);
2087 /* Exit if there aren't any parent levels to update. */
2088 if (level + 1 >= cur->bc_nlevels)
2091 trace_xfs_btree_updkeys(cur, level, bp0);
2094 hkey = xfs_btree_high_key_from_key(cur, lkey);
2095 xfs_btree_get_keys(cur, block, lkey);
2096 for (level++; level < cur->bc_nlevels; level++) {
2100 block = xfs_btree_get_block(cur, level, &bp);
2101 trace_xfs_btree_updkeys(cur, level, bp);
2103 error = xfs_btree_check_block(cur, block, level, bp);
2107 ptr = cur->bc_ptrs[level];
2108 nlkey = xfs_btree_key_addr(cur, ptr, block);
2109 nhkey = xfs_btree_high_key_addr(cur, ptr, block);
2111 !(cur->bc_ops->diff_two_keys(cur, nlkey, lkey) != 0 ||
2112 cur->bc_ops->diff_two_keys(cur, nhkey, hkey) != 0))
2114 xfs_btree_copy_keys(cur, nlkey, lkey, 1);
2115 xfs_btree_log_keys(cur, bp, ptr, ptr);
2116 if (level + 1 >= cur->bc_nlevels)
2118 xfs_btree_get_node_keys(cur, block, lkey);
2124 /* Update all the keys from some level in cursor back to the root. */
2126 xfs_btree_updkeys_force(
2127 struct xfs_btree_cur *cur,
2131 struct xfs_btree_block *block;
2133 block = xfs_btree_get_block(cur, level, &bp);
2134 return __xfs_btree_updkeys(cur, level, block, bp, true);
2138 * Update the parent keys of the given level, progressing towards the root.
2141 xfs_btree_update_keys(
2142 struct xfs_btree_cur *cur,
2145 struct xfs_btree_block *block;
2147 union xfs_btree_key *kp;
2148 union xfs_btree_key key;
2153 block = xfs_btree_get_block(cur, level, &bp);
2154 if (cur->bc_flags & XFS_BTREE_OVERLAPPING)
2155 return __xfs_btree_updkeys(cur, level, block, bp, false);
2158 * Go up the tree from this level toward the root.
2159 * At each level, update the key value to the value input.
2160 * Stop when we reach a level where the cursor isn't pointing
2161 * at the first entry in the block.
2163 xfs_btree_get_keys(cur, block, &key);
2164 for (level++, ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) {
2168 block = xfs_btree_get_block(cur, level, &bp);
2170 error = xfs_btree_check_block(cur, block, level, bp);
2174 ptr = cur->bc_ptrs[level];
2175 kp = xfs_btree_key_addr(cur, ptr, block);
2176 xfs_btree_copy_keys(cur, kp, &key, 1);
2177 xfs_btree_log_keys(cur, bp, ptr, ptr);
2184 * Update the record referred to by cur to the value in the
2185 * given record. This either works (return 0) or gets an
2186 * EFSCORRUPTED error.
2190 struct xfs_btree_cur *cur,
2191 union xfs_btree_rec *rec)
2193 struct xfs_btree_block *block;
2197 union xfs_btree_rec *rp;
2199 /* Pick up the current block. */
2200 block = xfs_btree_get_block(cur, 0, &bp);
2203 error = xfs_btree_check_block(cur, block, 0, bp);
2207 /* Get the address of the rec to be updated. */
2208 ptr = cur->bc_ptrs[0];
2209 rp = xfs_btree_rec_addr(cur, ptr, block);
2211 /* Fill in the new contents and log them. */
2212 xfs_btree_copy_recs(cur, rp, rec, 1);
2213 xfs_btree_log_recs(cur, bp, ptr, ptr);
2216 * If we are tracking the last record in the tree and
2217 * we are at the far right edge of the tree, update it.
2219 if (xfs_btree_is_lastrec(cur, block, 0)) {
2220 cur->bc_ops->update_lastrec(cur, block, rec,
2221 ptr, LASTREC_UPDATE);
2224 /* Pass new key value up to our parent. */
2225 if (xfs_btree_needs_key_update(cur, ptr)) {
2226 error = xfs_btree_update_keys(cur, 0);
2238 * Move 1 record left from cur/level if possible.
2239 * Update cur to reflect the new path.
2241 STATIC int /* error */
2243 struct xfs_btree_cur *cur,
2245 int *stat) /* success/failure */
2247 struct xfs_buf *lbp; /* left buffer pointer */
2248 struct xfs_btree_block *left; /* left btree block */
2249 int lrecs; /* left record count */
2250 struct xfs_buf *rbp; /* right buffer pointer */
2251 struct xfs_btree_block *right; /* right btree block */
2252 struct xfs_btree_cur *tcur; /* temporary btree cursor */
2253 int rrecs; /* right record count */
2254 union xfs_btree_ptr lptr; /* left btree pointer */
2255 union xfs_btree_key *rkp = NULL; /* right btree key */
2256 union xfs_btree_ptr *rpp = NULL; /* right address pointer */
2257 union xfs_btree_rec *rrp = NULL; /* right record pointer */
2258 int error; /* error return value */
2261 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
2262 level == cur->bc_nlevels - 1)
2265 /* Set up variables for this block as "right". */
2266 right = xfs_btree_get_block(cur, level, &rbp);
2269 error = xfs_btree_check_block(cur, right, level, rbp);
2274 /* If we've got no left sibling then we can't shift an entry left. */
2275 xfs_btree_get_sibling(cur, right, &lptr, XFS_BB_LEFTSIB);
2276 if (xfs_btree_ptr_is_null(cur, &lptr))
2280 * If the cursor entry is the one that would be moved, don't
2281 * do it... it's too complicated.
2283 if (cur->bc_ptrs[level] <= 1)
2286 /* Set up the left neighbor as "left". */
2287 error = xfs_btree_read_buf_block(cur, &lptr, 0, &left, &lbp);
2291 /* If it's full, it can't take another entry. */
2292 lrecs = xfs_btree_get_numrecs(left);
2293 if (lrecs == cur->bc_ops->get_maxrecs(cur, level))
2296 rrecs = xfs_btree_get_numrecs(right);
2299 * We add one entry to the left side and remove one for the right side.
2300 * Account for it here, the changes will be updated on disk and logged
2306 XFS_BTREE_STATS_INC(cur, lshift);
2307 XFS_BTREE_STATS_ADD(cur, moves, 1);
2310 * If non-leaf, copy a key and a ptr to the left block.
2311 * Log the changes to the left block.
2314 /* It's a non-leaf. Move keys and pointers. */
2315 union xfs_btree_key *lkp; /* left btree key */
2316 union xfs_btree_ptr *lpp; /* left address pointer */
2318 lkp = xfs_btree_key_addr(cur, lrecs, left);
2319 rkp = xfs_btree_key_addr(cur, 1, right);
2321 lpp = xfs_btree_ptr_addr(cur, lrecs, left);
2322 rpp = xfs_btree_ptr_addr(cur, 1, right);
2324 error = xfs_btree_debug_check_ptr(cur, rpp, 0, level);
2328 xfs_btree_copy_keys(cur, lkp, rkp, 1);
2329 xfs_btree_copy_ptrs(cur, lpp, rpp, 1);
2331 xfs_btree_log_keys(cur, lbp, lrecs, lrecs);
2332 xfs_btree_log_ptrs(cur, lbp, lrecs, lrecs);
2334 ASSERT(cur->bc_ops->keys_inorder(cur,
2335 xfs_btree_key_addr(cur, lrecs - 1, left), lkp));
2337 /* It's a leaf. Move records. */
2338 union xfs_btree_rec *lrp; /* left record pointer */
2340 lrp = xfs_btree_rec_addr(cur, lrecs, left);
2341 rrp = xfs_btree_rec_addr(cur, 1, right);
2343 xfs_btree_copy_recs(cur, lrp, rrp, 1);
2344 xfs_btree_log_recs(cur, lbp, lrecs, lrecs);
2346 ASSERT(cur->bc_ops->recs_inorder(cur,
2347 xfs_btree_rec_addr(cur, lrecs - 1, left), lrp));
2350 xfs_btree_set_numrecs(left, lrecs);
2351 xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS);
2353 xfs_btree_set_numrecs(right, rrecs);
2354 xfs_btree_log_block(cur, rbp, XFS_BB_NUMRECS);
2357 * Slide the contents of right down one entry.
2359 XFS_BTREE_STATS_ADD(cur, moves, rrecs - 1);
2361 /* It's a nonleaf. operate on keys and ptrs */
2362 for (i = 0; i < rrecs; i++) {
2363 error = xfs_btree_debug_check_ptr(cur, rpp, i + 1, level);
2368 xfs_btree_shift_keys(cur,
2369 xfs_btree_key_addr(cur, 2, right),
2371 xfs_btree_shift_ptrs(cur,
2372 xfs_btree_ptr_addr(cur, 2, right),
2375 xfs_btree_log_keys(cur, rbp, 1, rrecs);
2376 xfs_btree_log_ptrs(cur, rbp, 1, rrecs);
2378 /* It's a leaf. operate on records */
2379 xfs_btree_shift_recs(cur,
2380 xfs_btree_rec_addr(cur, 2, right),
2382 xfs_btree_log_recs(cur, rbp, 1, rrecs);
2386 * Using a temporary cursor, update the parent key values of the
2387 * block on the left.
2389 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) {
2390 error = xfs_btree_dup_cursor(cur, &tcur);
2393 i = xfs_btree_firstrec(tcur, level);
2394 if (XFS_IS_CORRUPT(tcur->bc_mp, i != 1)) {
2395 error = -EFSCORRUPTED;
2399 error = xfs_btree_decrement(tcur, level, &i);
2403 /* Update the parent high keys of the left block, if needed. */
2404 error = xfs_btree_update_keys(tcur, level);
2408 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
2411 /* Update the parent keys of the right block. */
2412 error = xfs_btree_update_keys(cur, level);
2416 /* Slide the cursor value left one. */
2417 cur->bc_ptrs[level]--;
2430 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
2435 * Move 1 record right from cur/level if possible.
2436 * Update cur to reflect the new path.
2438 STATIC int /* error */
2440 struct xfs_btree_cur *cur,
2442 int *stat) /* success/failure */
2444 struct xfs_buf *lbp; /* left buffer pointer */
2445 struct xfs_btree_block *left; /* left btree block */
2446 struct xfs_buf *rbp; /* right buffer pointer */
2447 struct xfs_btree_block *right; /* right btree block */
2448 struct xfs_btree_cur *tcur; /* temporary btree cursor */
2449 union xfs_btree_ptr rptr; /* right block pointer */
2450 union xfs_btree_key *rkp; /* right btree key */
2451 int rrecs; /* right record count */
2452 int lrecs; /* left record count */
2453 int error; /* error return value */
2454 int i; /* loop counter */
2456 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
2457 (level == cur->bc_nlevels - 1))
2460 /* Set up variables for this block as "left". */
2461 left = xfs_btree_get_block(cur, level, &lbp);
2464 error = xfs_btree_check_block(cur, left, level, lbp);
2469 /* If we've got no right sibling then we can't shift an entry right. */
2470 xfs_btree_get_sibling(cur, left, &rptr, XFS_BB_RIGHTSIB);
2471 if (xfs_btree_ptr_is_null(cur, &rptr))
2475 * If the cursor entry is the one that would be moved, don't
2476 * do it... it's too complicated.
2478 lrecs = xfs_btree_get_numrecs(left);
2479 if (cur->bc_ptrs[level] >= lrecs)
2482 /* Set up the right neighbor as "right". */
2483 error = xfs_btree_read_buf_block(cur, &rptr, 0, &right, &rbp);
2487 /* If it's full, it can't take another entry. */
2488 rrecs = xfs_btree_get_numrecs(right);
2489 if (rrecs == cur->bc_ops->get_maxrecs(cur, level))
2492 XFS_BTREE_STATS_INC(cur, rshift);
2493 XFS_BTREE_STATS_ADD(cur, moves, rrecs);
2496 * Make a hole at the start of the right neighbor block, then
2497 * copy the last left block entry to the hole.
2500 /* It's a nonleaf. make a hole in the keys and ptrs */
2501 union xfs_btree_key *lkp;
2502 union xfs_btree_ptr *lpp;
2503 union xfs_btree_ptr *rpp;
2505 lkp = xfs_btree_key_addr(cur, lrecs, left);
2506 lpp = xfs_btree_ptr_addr(cur, lrecs, left);
2507 rkp = xfs_btree_key_addr(cur, 1, right);
2508 rpp = xfs_btree_ptr_addr(cur, 1, right);
2510 for (i = rrecs - 1; i >= 0; i--) {
2511 error = xfs_btree_debug_check_ptr(cur, rpp, i, level);
2516 xfs_btree_shift_keys(cur, rkp, 1, rrecs);
2517 xfs_btree_shift_ptrs(cur, rpp, 1, rrecs);
2519 error = xfs_btree_debug_check_ptr(cur, lpp, 0, level);
2523 /* Now put the new data in, and log it. */
2524 xfs_btree_copy_keys(cur, rkp, lkp, 1);
2525 xfs_btree_copy_ptrs(cur, rpp, lpp, 1);
2527 xfs_btree_log_keys(cur, rbp, 1, rrecs + 1);
2528 xfs_btree_log_ptrs(cur, rbp, 1, rrecs + 1);
2530 ASSERT(cur->bc_ops->keys_inorder(cur, rkp,
2531 xfs_btree_key_addr(cur, 2, right)));
2533 /* It's a leaf. make a hole in the records */
2534 union xfs_btree_rec *lrp;
2535 union xfs_btree_rec *rrp;
2537 lrp = xfs_btree_rec_addr(cur, lrecs, left);
2538 rrp = xfs_btree_rec_addr(cur, 1, right);
2540 xfs_btree_shift_recs(cur, rrp, 1, rrecs);
2542 /* Now put the new data in, and log it. */
2543 xfs_btree_copy_recs(cur, rrp, lrp, 1);
2544 xfs_btree_log_recs(cur, rbp, 1, rrecs + 1);
2548 * Decrement and log left's numrecs, bump and log right's numrecs.
2550 xfs_btree_set_numrecs(left, --lrecs);
2551 xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS);
2553 xfs_btree_set_numrecs(right, ++rrecs);
2554 xfs_btree_log_block(cur, rbp, XFS_BB_NUMRECS);
2557 * Using a temporary cursor, update the parent key values of the
2558 * block on the right.
2560 error = xfs_btree_dup_cursor(cur, &tcur);
2563 i = xfs_btree_lastrec(tcur, level);
2564 if (XFS_IS_CORRUPT(tcur->bc_mp, i != 1)) {
2565 error = -EFSCORRUPTED;
2569 error = xfs_btree_increment(tcur, level, &i);
2573 /* Update the parent high keys of the left block, if needed. */
2574 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) {
2575 error = xfs_btree_update_keys(cur, level);
2580 /* Update the parent keys of the right block. */
2581 error = xfs_btree_update_keys(tcur, level);
2585 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
2598 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
2603 * Split cur/level block in half.
2604 * Return new block number and the key to its first
2605 * record (to be inserted into parent).
2607 STATIC int /* error */
2609 struct xfs_btree_cur *cur,
2611 union xfs_btree_ptr *ptrp,
2612 union xfs_btree_key *key,
2613 struct xfs_btree_cur **curp,
2614 int *stat) /* success/failure */
2616 union xfs_btree_ptr lptr; /* left sibling block ptr */
2617 struct xfs_buf *lbp; /* left buffer pointer */
2618 struct xfs_btree_block *left; /* left btree block */
2619 union xfs_btree_ptr rptr; /* right sibling block ptr */
2620 struct xfs_buf *rbp; /* right buffer pointer */
2621 struct xfs_btree_block *right; /* right btree block */
2622 union xfs_btree_ptr rrptr; /* right-right sibling ptr */
2623 struct xfs_buf *rrbp; /* right-right buffer pointer */
2624 struct xfs_btree_block *rrblock; /* right-right btree block */
2628 int error; /* error return value */
2631 XFS_BTREE_STATS_INC(cur, split);
2633 /* Set up left block (current one). */
2634 left = xfs_btree_get_block(cur, level, &lbp);
2637 error = xfs_btree_check_block(cur, left, level, lbp);
2642 xfs_btree_buf_to_ptr(cur, lbp, &lptr);
2644 /* Allocate the new block. If we can't do it, we're toast. Give up. */
2645 error = cur->bc_ops->alloc_block(cur, &lptr, &rptr, stat);
2650 XFS_BTREE_STATS_INC(cur, alloc);
2652 /* Set up the new block as "right". */
2653 error = xfs_btree_get_buf_block(cur, &rptr, &right, &rbp);
2657 /* Fill in the btree header for the new right block. */
2658 xfs_btree_init_block_cur(cur, rbp, xfs_btree_get_level(left), 0);
2661 * Split the entries between the old and the new block evenly.
2662 * Make sure that if there's an odd number of entries now, that
2663 * each new block will have the same number of entries.
2665 lrecs = xfs_btree_get_numrecs(left);
2667 if ((lrecs & 1) && cur->bc_ptrs[level] <= rrecs + 1)
2669 src_index = (lrecs - rrecs + 1);
2671 XFS_BTREE_STATS_ADD(cur, moves, rrecs);
2673 /* Adjust numrecs for the later get_*_keys() calls. */
2675 xfs_btree_set_numrecs(left, lrecs);
2676 xfs_btree_set_numrecs(right, xfs_btree_get_numrecs(right) + rrecs);
2679 * Copy btree block entries from the left block over to the
2680 * new block, the right. Update the right block and log the
2684 /* It's a non-leaf. Move keys and pointers. */
2685 union xfs_btree_key *lkp; /* left btree key */
2686 union xfs_btree_ptr *lpp; /* left address pointer */
2687 union xfs_btree_key *rkp; /* right btree key */
2688 union xfs_btree_ptr *rpp; /* right address pointer */
2690 lkp = xfs_btree_key_addr(cur, src_index, left);
2691 lpp = xfs_btree_ptr_addr(cur, src_index, left);
2692 rkp = xfs_btree_key_addr(cur, 1, right);
2693 rpp = xfs_btree_ptr_addr(cur, 1, right);
2695 for (i = src_index; i < rrecs; i++) {
2696 error = xfs_btree_debug_check_ptr(cur, lpp, i, level);
2701 /* Copy the keys & pointers to the new block. */
2702 xfs_btree_copy_keys(cur, rkp, lkp, rrecs);
2703 xfs_btree_copy_ptrs(cur, rpp, lpp, rrecs);
2705 xfs_btree_log_keys(cur, rbp, 1, rrecs);
2706 xfs_btree_log_ptrs(cur, rbp, 1, rrecs);
2708 /* Stash the keys of the new block for later insertion. */
2709 xfs_btree_get_node_keys(cur, right, key);
2711 /* It's a leaf. Move records. */
2712 union xfs_btree_rec *lrp; /* left record pointer */
2713 union xfs_btree_rec *rrp; /* right record pointer */
2715 lrp = xfs_btree_rec_addr(cur, src_index, left);
2716 rrp = xfs_btree_rec_addr(cur, 1, right);
2718 /* Copy records to the new block. */
2719 xfs_btree_copy_recs(cur, rrp, lrp, rrecs);
2720 xfs_btree_log_recs(cur, rbp, 1, rrecs);
2722 /* Stash the keys of the new block for later insertion. */
2723 xfs_btree_get_leaf_keys(cur, right, key);
2727 * Find the left block number by looking in the buffer.
2728 * Adjust sibling pointers.
2730 xfs_btree_get_sibling(cur, left, &rrptr, XFS_BB_RIGHTSIB);
2731 xfs_btree_set_sibling(cur, right, &rrptr, XFS_BB_RIGHTSIB);
2732 xfs_btree_set_sibling(cur, right, &lptr, XFS_BB_LEFTSIB);
2733 xfs_btree_set_sibling(cur, left, &rptr, XFS_BB_RIGHTSIB);
2735 xfs_btree_log_block(cur, rbp, XFS_BB_ALL_BITS);
2736 xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
2739 * If there's a block to the new block's right, make that block
2740 * point back to right instead of to left.
2742 if (!xfs_btree_ptr_is_null(cur, &rrptr)) {
2743 error = xfs_btree_read_buf_block(cur, &rrptr,
2744 0, &rrblock, &rrbp);
2747 xfs_btree_set_sibling(cur, rrblock, &rptr, XFS_BB_LEFTSIB);
2748 xfs_btree_log_block(cur, rrbp, XFS_BB_LEFTSIB);
2751 /* Update the parent high keys of the left block, if needed. */
2752 if (cur->bc_flags & XFS_BTREE_OVERLAPPING) {
2753 error = xfs_btree_update_keys(cur, level);
2759 * If the cursor is really in the right block, move it there.
2760 * If it's just pointing past the last entry in left, then we'll
2761 * insert there, so don't change anything in that case.
2763 if (cur->bc_ptrs[level] > lrecs + 1) {
2764 xfs_btree_setbuf(cur, level, rbp);
2765 cur->bc_ptrs[level] -= lrecs;
2768 * If there are more levels, we'll need another cursor which refers
2769 * the right block, no matter where this cursor was.
2771 if (level + 1 < cur->bc_nlevels) {
2772 error = xfs_btree_dup_cursor(cur, curp);
2775 (*curp)->bc_ptrs[level + 1]++;
2788 struct xfs_btree_split_args {
2789 struct xfs_btree_cur *cur;
2791 union xfs_btree_ptr *ptrp;
2792 union xfs_btree_key *key;
2793 struct xfs_btree_cur **curp;
2794 int *stat; /* success/failure */
2796 bool kswapd; /* allocation in kswapd context */
2797 struct completion *done;
2798 struct work_struct work;
2802 * Stack switching interfaces for allocation
2805 xfs_btree_split_worker(
2806 struct work_struct *work)
2808 struct xfs_btree_split_args *args = container_of(work,
2809 struct xfs_btree_split_args, work);
2810 unsigned long pflags;
2811 unsigned long new_pflags = 0;
2814 * we are in a transaction context here, but may also be doing work
2815 * in kswapd context, and hence we may need to inherit that state
2816 * temporarily to ensure that we don't block waiting for memory reclaim
2820 new_pflags |= PF_MEMALLOC | PF_SWAPWRITE | PF_KSWAPD;
2822 current_set_flags_nested(&pflags, new_pflags);
2823 xfs_trans_set_context(args->cur->bc_tp);
2825 args->result = __xfs_btree_split(args->cur, args->level, args->ptrp,
2826 args->key, args->curp, args->stat);
2828 xfs_trans_clear_context(args->cur->bc_tp);
2829 current_restore_flags_nested(&pflags, new_pflags);
2832 * Do not access args after complete() has run here. We don't own args
2833 * and the owner may run and free args before we return here.
2835 complete(args->done);
2840 * BMBT split requests often come in with little stack to work on. Push
2841 * them off to a worker thread so there is lots of stack to use. For the other
2842 * btree types, just call directly to avoid the context switch overhead here.
2844 STATIC int /* error */
2846 struct xfs_btree_cur *cur,
2848 union xfs_btree_ptr *ptrp,
2849 union xfs_btree_key *key,
2850 struct xfs_btree_cur **curp,
2851 int *stat) /* success/failure */
2853 struct xfs_btree_split_args args;
2854 DECLARE_COMPLETION_ONSTACK(done);
2856 if (cur->bc_btnum != XFS_BTNUM_BMAP)
2857 return __xfs_btree_split(cur, level, ptrp, key, curp, stat);
2866 args.kswapd = current_is_kswapd();
2867 INIT_WORK_ONSTACK(&args.work, xfs_btree_split_worker);
2868 queue_work(xfs_alloc_wq, &args.work);
2869 wait_for_completion(&done);
2870 destroy_work_on_stack(&args.work);
2876 * Copy the old inode root contents into a real block and make the
2877 * broot point to it.
2880 xfs_btree_new_iroot(
2881 struct xfs_btree_cur *cur, /* btree cursor */
2882 int *logflags, /* logging flags for inode */
2883 int *stat) /* return status - 0 fail */
2885 struct xfs_buf *cbp; /* buffer for cblock */
2886 struct xfs_btree_block *block; /* btree block */
2887 struct xfs_btree_block *cblock; /* child btree block */
2888 union xfs_btree_key *ckp; /* child key pointer */
2889 union xfs_btree_ptr *cpp; /* child ptr pointer */
2890 union xfs_btree_key *kp; /* pointer to btree key */
2891 union xfs_btree_ptr *pp; /* pointer to block addr */
2892 union xfs_btree_ptr nptr; /* new block addr */
2893 int level; /* btree level */
2894 int error; /* error return code */
2895 int i; /* loop counter */
2897 XFS_BTREE_STATS_INC(cur, newroot);
2899 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE);
2901 level = cur->bc_nlevels - 1;
2903 block = xfs_btree_get_iroot(cur);
2904 pp = xfs_btree_ptr_addr(cur, 1, block);
2906 /* Allocate the new block. If we can't do it, we're toast. Give up. */
2907 error = cur->bc_ops->alloc_block(cur, pp, &nptr, stat);
2913 XFS_BTREE_STATS_INC(cur, alloc);
2915 /* Copy the root into a real block. */
2916 error = xfs_btree_get_buf_block(cur, &nptr, &cblock, &cbp);
2921 * we can't just memcpy() the root in for CRC enabled btree blocks.
2922 * In that case have to also ensure the blkno remains correct
2924 memcpy(cblock, block, xfs_btree_block_len(cur));
2925 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) {
2926 if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
2927 cblock->bb_u.l.bb_blkno = cpu_to_be64(cbp->b_bn);
2929 cblock->bb_u.s.bb_blkno = cpu_to_be64(cbp->b_bn);
2932 be16_add_cpu(&block->bb_level, 1);
2933 xfs_btree_set_numrecs(block, 1);
2935 cur->bc_ptrs[level + 1] = 1;
2937 kp = xfs_btree_key_addr(cur, 1, block);
2938 ckp = xfs_btree_key_addr(cur, 1, cblock);
2939 xfs_btree_copy_keys(cur, ckp, kp, xfs_btree_get_numrecs(cblock));
2941 cpp = xfs_btree_ptr_addr(cur, 1, cblock);
2942 for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) {
2943 error = xfs_btree_debug_check_ptr(cur, pp, i, level);
2948 xfs_btree_copy_ptrs(cur, cpp, pp, xfs_btree_get_numrecs(cblock));
2950 error = xfs_btree_debug_check_ptr(cur, &nptr, 0, level);
2954 xfs_btree_copy_ptrs(cur, pp, &nptr, 1);
2956 xfs_iroot_realloc(cur->bc_ino.ip,
2957 1 - xfs_btree_get_numrecs(cblock),
2958 cur->bc_ino.whichfork);
2960 xfs_btree_setbuf(cur, level, cbp);
2963 * Do all this logging at the end so that
2964 * the root is at the right level.
2966 xfs_btree_log_block(cur, cbp, XFS_BB_ALL_BITS);
2967 xfs_btree_log_keys(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs));
2968 xfs_btree_log_ptrs(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs));
2971 XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_ino.whichfork);
2979 * Allocate a new root block, fill it in.
2981 STATIC int /* error */
2983 struct xfs_btree_cur *cur, /* btree cursor */
2984 int *stat) /* success/failure */
2986 struct xfs_btree_block *block; /* one half of the old root block */
2987 struct xfs_buf *bp; /* buffer containing block */
2988 int error; /* error return value */
2989 struct xfs_buf *lbp; /* left buffer pointer */
2990 struct xfs_btree_block *left; /* left btree block */
2991 struct xfs_buf *nbp; /* new (root) buffer */
2992 struct xfs_btree_block *new; /* new (root) btree block */
2993 int nptr; /* new value for key index, 1 or 2 */
2994 struct xfs_buf *rbp; /* right buffer pointer */
2995 struct xfs_btree_block *right; /* right btree block */
2996 union xfs_btree_ptr rptr;
2997 union xfs_btree_ptr lptr;
2999 XFS_BTREE_STATS_INC(cur, newroot);
3001 /* initialise our start point from the cursor */
3002 cur->bc_ops->init_ptr_from_cur(cur, &rptr);
3004 /* Allocate the new block. If we can't do it, we're toast. Give up. */
3005 error = cur->bc_ops->alloc_block(cur, &rptr, &lptr, stat);
3010 XFS_BTREE_STATS_INC(cur, alloc);
3012 /* Set up the new block. */
3013 error = xfs_btree_get_buf_block(cur, &lptr, &new, &nbp);
3017 /* Set the root in the holding structure increasing the level by 1. */
3018 cur->bc_ops->set_root(cur, &lptr, 1);
3021 * At the previous root level there are now two blocks: the old root,
3022 * and the new block generated when it was split. We don't know which
3023 * one the cursor is pointing at, so we set up variables "left" and
3024 * "right" for each case.
3026 block = xfs_btree_get_block(cur, cur->bc_nlevels - 1, &bp);
3029 error = xfs_btree_check_block(cur, block, cur->bc_nlevels - 1, bp);
3034 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB);
3035 if (!xfs_btree_ptr_is_null(cur, &rptr)) {
3036 /* Our block is left, pick up the right block. */
3038 xfs_btree_buf_to_ptr(cur, lbp, &lptr);
3040 error = xfs_btree_read_buf_block(cur, &rptr, 0, &right, &rbp);
3046 /* Our block is right, pick up the left block. */
3048 xfs_btree_buf_to_ptr(cur, rbp, &rptr);
3050 xfs_btree_get_sibling(cur, right, &lptr, XFS_BB_LEFTSIB);
3051 error = xfs_btree_read_buf_block(cur, &lptr, 0, &left, &lbp);
3058 /* Fill in the new block's btree header and log it. */
3059 xfs_btree_init_block_cur(cur, nbp, cur->bc_nlevels, 2);
3060 xfs_btree_log_block(cur, nbp, XFS_BB_ALL_BITS);
3061 ASSERT(!xfs_btree_ptr_is_null(cur, &lptr) &&
3062 !xfs_btree_ptr_is_null(cur, &rptr));
3064 /* Fill in the key data in the new root. */
3065 if (xfs_btree_get_level(left) > 0) {
3067 * Get the keys for the left block's keys and put them directly
3068 * in the parent block. Do the same for the right block.
3070 xfs_btree_get_node_keys(cur, left,
3071 xfs_btree_key_addr(cur, 1, new));
3072 xfs_btree_get_node_keys(cur, right,
3073 xfs_btree_key_addr(cur, 2, new));
3076 * Get the keys for the left block's records and put them
3077 * directly in the parent block. Do the same for the right
3080 xfs_btree_get_leaf_keys(cur, left,
3081 xfs_btree_key_addr(cur, 1, new));
3082 xfs_btree_get_leaf_keys(cur, right,
3083 xfs_btree_key_addr(cur, 2, new));
3085 xfs_btree_log_keys(cur, nbp, 1, 2);
3087 /* Fill in the pointer data in the new root. */
3088 xfs_btree_copy_ptrs(cur,
3089 xfs_btree_ptr_addr(cur, 1, new), &lptr, 1);
3090 xfs_btree_copy_ptrs(cur,
3091 xfs_btree_ptr_addr(cur, 2, new), &rptr, 1);
3092 xfs_btree_log_ptrs(cur, nbp, 1, 2);
3094 /* Fix up the cursor. */
3095 xfs_btree_setbuf(cur, cur->bc_nlevels, nbp);
3096 cur->bc_ptrs[cur->bc_nlevels] = nptr;
3108 xfs_btree_make_block_unfull(
3109 struct xfs_btree_cur *cur, /* btree cursor */
3110 int level, /* btree level */
3111 int numrecs,/* # of recs in block */
3112 int *oindex,/* old tree index */
3113 int *index, /* new tree index */
3114 union xfs_btree_ptr *nptr, /* new btree ptr */
3115 struct xfs_btree_cur **ncur, /* new btree cursor */
3116 union xfs_btree_key *key, /* key of new block */
3121 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
3122 level == cur->bc_nlevels - 1) {
3123 struct xfs_inode *ip = cur->bc_ino.ip;
3125 if (numrecs < cur->bc_ops->get_dmaxrecs(cur, level)) {
3126 /* A root block that can be made bigger. */
3127 xfs_iroot_realloc(ip, 1, cur->bc_ino.whichfork);
3130 /* A root block that needs replacing */
3133 error = xfs_btree_new_iroot(cur, &logflags, stat);
3134 if (error || *stat == 0)
3137 xfs_trans_log_inode(cur->bc_tp, ip, logflags);
3143 /* First, try shifting an entry to the right neighbor. */
3144 error = xfs_btree_rshift(cur, level, stat);
3148 /* Next, try shifting an entry to the left neighbor. */
3149 error = xfs_btree_lshift(cur, level, stat);
3154 *oindex = *index = cur->bc_ptrs[level];
3159 * Next, try splitting the current block in half.
3161 * If this works we have to re-set our variables because we
3162 * could be in a different block now.
3164 error = xfs_btree_split(cur, level, nptr, key, ncur, stat);
3165 if (error || *stat == 0)
3169 *index = cur->bc_ptrs[level];
3174 * Insert one record/level. Return information to the caller
3175 * allowing the next level up to proceed if necessary.
3179 struct xfs_btree_cur *cur, /* btree cursor */
3180 int level, /* level to insert record at */
3181 union xfs_btree_ptr *ptrp, /* i/o: block number inserted */
3182 union xfs_btree_rec *rec, /* record to insert */
3183 union xfs_btree_key *key, /* i/o: block key for ptrp */
3184 struct xfs_btree_cur **curp, /* output: new cursor replacing cur */
3185 int *stat) /* success/failure */
3187 struct xfs_btree_block *block; /* btree block */
3188 struct xfs_buf *bp; /* buffer for block */
3189 union xfs_btree_ptr nptr; /* new block ptr */
3190 struct xfs_btree_cur *ncur; /* new btree cursor */
3191 union xfs_btree_key nkey; /* new block key */
3192 union xfs_btree_key *lkey;
3193 int optr; /* old key/record index */
3194 int ptr; /* key/record index */
3195 int numrecs;/* number of records */
3196 int error; /* error return value */
3204 * If we have an external root pointer, and we've made it to the
3205 * root level, allocate a new root block and we're done.
3207 if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
3208 (level >= cur->bc_nlevels)) {
3209 error = xfs_btree_new_root(cur, stat);
3210 xfs_btree_set_ptr_null(cur, ptrp);
3215 /* If we're off the left edge, return failure. */
3216 ptr = cur->bc_ptrs[level];
3224 XFS_BTREE_STATS_INC(cur, insrec);
3226 /* Get pointers to the btree buffer and block. */
3227 block = xfs_btree_get_block(cur, level, &bp);
3228 old_bn = bp ? bp->b_bn : XFS_BUF_DADDR_NULL;
3229 numrecs = xfs_btree_get_numrecs(block);
3232 error = xfs_btree_check_block(cur, block, level, bp);
3236 /* Check that the new entry is being inserted in the right place. */
3237 if (ptr <= numrecs) {
3239 ASSERT(cur->bc_ops->recs_inorder(cur, rec,
3240 xfs_btree_rec_addr(cur, ptr, block)));
3242 ASSERT(cur->bc_ops->keys_inorder(cur, key,
3243 xfs_btree_key_addr(cur, ptr, block)));
3249 * If the block is full, we can't insert the new entry until we
3250 * make the block un-full.
3252 xfs_btree_set_ptr_null(cur, &nptr);
3253 if (numrecs == cur->bc_ops->get_maxrecs(cur, level)) {
3254 error = xfs_btree_make_block_unfull(cur, level, numrecs,
3255 &optr, &ptr, &nptr, &ncur, lkey, stat);
3256 if (error || *stat == 0)
3261 * The current block may have changed if the block was
3262 * previously full and we have just made space in it.
3264 block = xfs_btree_get_block(cur, level, &bp);
3265 numrecs = xfs_btree_get_numrecs(block);
3268 error = xfs_btree_check_block(cur, block, level, bp);
3274 * At this point we know there's room for our new entry in the block
3275 * we're pointing at.
3277 XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr + 1);
3280 /* It's a nonleaf. make a hole in the keys and ptrs */
3281 union xfs_btree_key *kp;
3282 union xfs_btree_ptr *pp;
3284 kp = xfs_btree_key_addr(cur, ptr, block);
3285 pp = xfs_btree_ptr_addr(cur, ptr, block);
3287 for (i = numrecs - ptr; i >= 0; i--) {
3288 error = xfs_btree_debug_check_ptr(cur, pp, i, level);
3293 xfs_btree_shift_keys(cur, kp, 1, numrecs - ptr + 1);
3294 xfs_btree_shift_ptrs(cur, pp, 1, numrecs - ptr + 1);
3296 error = xfs_btree_debug_check_ptr(cur, ptrp, 0, level);
3300 /* Now put the new data in, bump numrecs and log it. */
3301 xfs_btree_copy_keys(cur, kp, key, 1);
3302 xfs_btree_copy_ptrs(cur, pp, ptrp, 1);
3304 xfs_btree_set_numrecs(block, numrecs);
3305 xfs_btree_log_ptrs(cur, bp, ptr, numrecs);
3306 xfs_btree_log_keys(cur, bp, ptr, numrecs);
3308 if (ptr < numrecs) {
3309 ASSERT(cur->bc_ops->keys_inorder(cur, kp,
3310 xfs_btree_key_addr(cur, ptr + 1, block)));
3314 /* It's a leaf. make a hole in the records */
3315 union xfs_btree_rec *rp;
3317 rp = xfs_btree_rec_addr(cur, ptr, block);
3319 xfs_btree_shift_recs(cur, rp, 1, numrecs - ptr + 1);
3321 /* Now put the new data in, bump numrecs and log it. */
3322 xfs_btree_copy_recs(cur, rp, rec, 1);
3323 xfs_btree_set_numrecs(block, ++numrecs);
3324 xfs_btree_log_recs(cur, bp, ptr, numrecs);
3326 if (ptr < numrecs) {
3327 ASSERT(cur->bc_ops->recs_inorder(cur, rp,
3328 xfs_btree_rec_addr(cur, ptr + 1, block)));
3333 /* Log the new number of records in the btree header. */
3334 xfs_btree_log_block(cur, bp, XFS_BB_NUMRECS);
3337 * If we just inserted into a new tree block, we have to
3338 * recalculate nkey here because nkey is out of date.
3340 * Otherwise we're just updating an existing block (having shoved
3341 * some records into the new tree block), so use the regular key
3344 if (bp && bp->b_bn != old_bn) {
3345 xfs_btree_get_keys(cur, block, lkey);
3346 } else if (xfs_btree_needs_key_update(cur, optr)) {
3347 error = xfs_btree_update_keys(cur, level);
3353 * If we are tracking the last record in the tree and
3354 * we are at the far right edge of the tree, update it.
3356 if (xfs_btree_is_lastrec(cur, block, level)) {
3357 cur->bc_ops->update_lastrec(cur, block, rec,
3358 ptr, LASTREC_INSREC);
3362 * Return the new block number, if any.
3363 * If there is one, give back a record value and a cursor too.
3366 if (!xfs_btree_ptr_is_null(cur, &nptr)) {
3367 xfs_btree_copy_keys(cur, key, lkey, 1);
3379 * Insert the record at the point referenced by cur.
3381 * A multi-level split of the tree on insert will invalidate the original
3382 * cursor. All callers of this function should assume that the cursor is
3383 * no longer valid and revalidate it.
3387 struct xfs_btree_cur *cur,
3390 int error; /* error return value */
3391 int i; /* result value, 0 for failure */
3392 int level; /* current level number in btree */
3393 union xfs_btree_ptr nptr; /* new block number (split result) */
3394 struct xfs_btree_cur *ncur; /* new cursor (split result) */
3395 struct xfs_btree_cur *pcur; /* previous level's cursor */
3396 union xfs_btree_key bkey; /* key of block to insert */
3397 union xfs_btree_key *key;
3398 union xfs_btree_rec rec; /* record to insert */
3405 xfs_btree_set_ptr_null(cur, &nptr);
3407 /* Make a key out of the record data to be inserted, and save it. */
3408 cur->bc_ops->init_rec_from_cur(cur, &rec);
3409 cur->bc_ops->init_key_from_rec(key, &rec);
3412 * Loop going up the tree, starting at the leaf level.
3413 * Stop when we don't get a split block, that must mean that
3414 * the insert is finished with this level.
3418 * Insert nrec/nptr into this level of the tree.
3419 * Note if we fail, nptr will be null.
3421 error = xfs_btree_insrec(pcur, level, &nptr, &rec, key,
3425 xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
3429 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
3430 error = -EFSCORRUPTED;
3436 * See if the cursor we just used is trash.
3437 * Can't trash the caller's cursor, but otherwise we should
3438 * if ncur is a new cursor or we're about to be done.
3441 (ncur || xfs_btree_ptr_is_null(cur, &nptr))) {
3442 /* Save the state from the cursor before we trash it */
3443 if (cur->bc_ops->update_cursor)
3444 cur->bc_ops->update_cursor(pcur, cur);
3445 cur->bc_nlevels = pcur->bc_nlevels;
3446 xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
3448 /* If we got a new cursor, switch to it. */
3453 } while (!xfs_btree_ptr_is_null(cur, &nptr));
3462 * Try to merge a non-leaf block back into the inode root.
3464 * Note: the killroot names comes from the fact that we're effectively
3465 * killing the old root block. But because we can't just delete the
3466 * inode we have to copy the single block it was pointing to into the
3470 xfs_btree_kill_iroot(
3471 struct xfs_btree_cur *cur)
3473 int whichfork = cur->bc_ino.whichfork;
3474 struct xfs_inode *ip = cur->bc_ino.ip;
3475 struct xfs_ifork *ifp = XFS_IFORK_PTR(ip, whichfork);
3476 struct xfs_btree_block *block;
3477 struct xfs_btree_block *cblock;
3478 union xfs_btree_key *kp;
3479 union xfs_btree_key *ckp;
3480 union xfs_btree_ptr *pp;
3481 union xfs_btree_ptr *cpp;
3482 struct xfs_buf *cbp;
3488 union xfs_btree_ptr ptr;
3492 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE);
3493 ASSERT(cur->bc_nlevels > 1);
3496 * Don't deal with the root block needs to be a leaf case.
3497 * We're just going to turn the thing back into extents anyway.
3499 level = cur->bc_nlevels - 1;
3504 * Give up if the root has multiple children.
3506 block = xfs_btree_get_iroot(cur);
3507 if (xfs_btree_get_numrecs(block) != 1)
3510 cblock = xfs_btree_get_block(cur, level - 1, &cbp);
3511 numrecs = xfs_btree_get_numrecs(cblock);
3514 * Only do this if the next level will fit.
3515 * Then the data must be copied up to the inode,
3516 * instead of freeing the root you free the next level.
3518 if (numrecs > cur->bc_ops->get_dmaxrecs(cur, level))
3521 XFS_BTREE_STATS_INC(cur, killroot);
3524 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB);
3525 ASSERT(xfs_btree_ptr_is_null(cur, &ptr));
3526 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
3527 ASSERT(xfs_btree_ptr_is_null(cur, &ptr));
3530 index = numrecs - cur->bc_ops->get_maxrecs(cur, level);
3532 xfs_iroot_realloc(cur->bc_ino.ip, index,
3533 cur->bc_ino.whichfork);
3534 block = ifp->if_broot;
3537 be16_add_cpu(&block->bb_numrecs, index);
3538 ASSERT(block->bb_numrecs == cblock->bb_numrecs);
3540 kp = xfs_btree_key_addr(cur, 1, block);
3541 ckp = xfs_btree_key_addr(cur, 1, cblock);
3542 xfs_btree_copy_keys(cur, kp, ckp, numrecs);
3544 pp = xfs_btree_ptr_addr(cur, 1, block);
3545 cpp = xfs_btree_ptr_addr(cur, 1, cblock);
3547 for (i = 0; i < numrecs; i++) {
3548 error = xfs_btree_debug_check_ptr(cur, cpp, i, level - 1);
3553 xfs_btree_copy_ptrs(cur, pp, cpp, numrecs);
3555 error = xfs_btree_free_block(cur, cbp);
3559 cur->bc_bufs[level - 1] = NULL;
3560 be16_add_cpu(&block->bb_level, -1);
3561 xfs_trans_log_inode(cur->bc_tp, ip,
3562 XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_ino.whichfork));
3569 * Kill the current root node, and replace it with it's only child node.
3572 xfs_btree_kill_root(
3573 struct xfs_btree_cur *cur,
3576 union xfs_btree_ptr *newroot)
3580 XFS_BTREE_STATS_INC(cur, killroot);
3583 * Update the root pointer, decreasing the level by 1 and then
3584 * free the old root.
3586 cur->bc_ops->set_root(cur, newroot, -1);
3588 error = xfs_btree_free_block(cur, bp);
3592 cur->bc_bufs[level] = NULL;
3593 cur->bc_ra[level] = 0;
3600 xfs_btree_dec_cursor(
3601 struct xfs_btree_cur *cur,
3609 error = xfs_btree_decrement(cur, level, &i);
3619 * Single level of the btree record deletion routine.
3620 * Delete record pointed to by cur/level.
3621 * Remove the record from its block then rebalance the tree.
3622 * Return 0 for error, 1 for done, 2 to go on to the next level.
3624 STATIC int /* error */
3626 struct xfs_btree_cur *cur, /* btree cursor */
3627 int level, /* level removing record from */
3628 int *stat) /* fail/done/go-on */
3630 struct xfs_btree_block *block; /* btree block */
3631 union xfs_btree_ptr cptr; /* current block ptr */
3632 struct xfs_buf *bp; /* buffer for block */
3633 int error; /* error return value */
3634 int i; /* loop counter */
3635 union xfs_btree_ptr lptr; /* left sibling block ptr */
3636 struct xfs_buf *lbp; /* left buffer pointer */
3637 struct xfs_btree_block *left; /* left btree block */
3638 int lrecs = 0; /* left record count */
3639 int ptr; /* key/record index */
3640 union xfs_btree_ptr rptr; /* right sibling block ptr */
3641 struct xfs_buf *rbp; /* right buffer pointer */
3642 struct xfs_btree_block *right; /* right btree block */
3643 struct xfs_btree_block *rrblock; /* right-right btree block */
3644 struct xfs_buf *rrbp; /* right-right buffer pointer */
3645 int rrecs = 0; /* right record count */
3646 struct xfs_btree_cur *tcur; /* temporary btree cursor */
3647 int numrecs; /* temporary numrec count */
3651 /* Get the index of the entry being deleted, check for nothing there. */
3652 ptr = cur->bc_ptrs[level];
3658 /* Get the buffer & block containing the record or key/ptr. */
3659 block = xfs_btree_get_block(cur, level, &bp);
3660 numrecs = xfs_btree_get_numrecs(block);
3663 error = xfs_btree_check_block(cur, block, level, bp);
3668 /* Fail if we're off the end of the block. */
3669 if (ptr > numrecs) {
3674 XFS_BTREE_STATS_INC(cur, delrec);
3675 XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr);
3677 /* Excise the entries being deleted. */
3679 /* It's a nonleaf. operate on keys and ptrs */
3680 union xfs_btree_key *lkp;
3681 union xfs_btree_ptr *lpp;
3683 lkp = xfs_btree_key_addr(cur, ptr + 1, block);
3684 lpp = xfs_btree_ptr_addr(cur, ptr + 1, block);
3686 for (i = 0; i < numrecs - ptr; i++) {
3687 error = xfs_btree_debug_check_ptr(cur, lpp, i, level);
3692 if (ptr < numrecs) {
3693 xfs_btree_shift_keys(cur, lkp, -1, numrecs - ptr);
3694 xfs_btree_shift_ptrs(cur, lpp, -1, numrecs - ptr);
3695 xfs_btree_log_keys(cur, bp, ptr, numrecs - 1);
3696 xfs_btree_log_ptrs(cur, bp, ptr, numrecs - 1);
3699 /* It's a leaf. operate on records */
3700 if (ptr < numrecs) {
3701 xfs_btree_shift_recs(cur,
3702 xfs_btree_rec_addr(cur, ptr + 1, block),
3704 xfs_btree_log_recs(cur, bp, ptr, numrecs - 1);
3709 * Decrement and log the number of entries in the block.
3711 xfs_btree_set_numrecs(block, --numrecs);
3712 xfs_btree_log_block(cur, bp, XFS_BB_NUMRECS);
3715 * If we are tracking the last record in the tree and
3716 * we are at the far right edge of the tree, update it.
3718 if (xfs_btree_is_lastrec(cur, block, level)) {
3719 cur->bc_ops->update_lastrec(cur, block, NULL,
3720 ptr, LASTREC_DELREC);
3724 * We're at the root level. First, shrink the root block in-memory.
3725 * Try to get rid of the next level down. If we can't then there's
3726 * nothing left to do.
3728 if (level == cur->bc_nlevels - 1) {
3729 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) {
3730 xfs_iroot_realloc(cur->bc_ino.ip, -1,
3731 cur->bc_ino.whichfork);
3733 error = xfs_btree_kill_iroot(cur);
3737 error = xfs_btree_dec_cursor(cur, level, stat);
3745 * If this is the root level, and there's only one entry left,
3746 * and it's NOT the leaf level, then we can get rid of this
3749 if (numrecs == 1 && level > 0) {
3750 union xfs_btree_ptr *pp;
3752 * pp is still set to the first pointer in the block.
3753 * Make it the new root of the btree.
3755 pp = xfs_btree_ptr_addr(cur, 1, block);
3756 error = xfs_btree_kill_root(cur, bp, level, pp);
3759 } else if (level > 0) {
3760 error = xfs_btree_dec_cursor(cur, level, stat);
3769 * If we deleted the leftmost entry in the block, update the
3770 * key values above us in the tree.
3772 if (xfs_btree_needs_key_update(cur, ptr)) {
3773 error = xfs_btree_update_keys(cur, level);
3779 * If the number of records remaining in the block is at least
3780 * the minimum, we're done.
3782 if (numrecs >= cur->bc_ops->get_minrecs(cur, level)) {
3783 error = xfs_btree_dec_cursor(cur, level, stat);
3790 * Otherwise, we have to move some records around to keep the
3791 * tree balanced. Look at the left and right sibling blocks to
3792 * see if we can re-balance by moving only one record.
3794 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB);
3795 xfs_btree_get_sibling(cur, block, &lptr, XFS_BB_LEFTSIB);
3797 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) {
3799 * One child of root, need to get a chance to copy its contents
3800 * into the root and delete it. Can't go up to next level,
3801 * there's nothing to delete there.
3803 if (xfs_btree_ptr_is_null(cur, &rptr) &&
3804 xfs_btree_ptr_is_null(cur, &lptr) &&
3805 level == cur->bc_nlevels - 2) {
3806 error = xfs_btree_kill_iroot(cur);
3808 error = xfs_btree_dec_cursor(cur, level, stat);
3815 ASSERT(!xfs_btree_ptr_is_null(cur, &rptr) ||
3816 !xfs_btree_ptr_is_null(cur, &lptr));
3819 * Duplicate the cursor so our btree manipulations here won't
3820 * disrupt the next level up.
3822 error = xfs_btree_dup_cursor(cur, &tcur);
3827 * If there's a right sibling, see if it's ok to shift an entry
3830 if (!xfs_btree_ptr_is_null(cur, &rptr)) {
3832 * Move the temp cursor to the last entry in the next block.
3833 * Actually any entry but the first would suffice.
3835 i = xfs_btree_lastrec(tcur, level);
3836 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
3837 error = -EFSCORRUPTED;
3841 error = xfs_btree_increment(tcur, level, &i);
3844 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
3845 error = -EFSCORRUPTED;
3849 i = xfs_btree_lastrec(tcur, level);
3850 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
3851 error = -EFSCORRUPTED;
3855 /* Grab a pointer to the block. */
3856 right = xfs_btree_get_block(tcur, level, &rbp);
3858 error = xfs_btree_check_block(tcur, right, level, rbp);
3862 /* Grab the current block number, for future use. */
3863 xfs_btree_get_sibling(tcur, right, &cptr, XFS_BB_LEFTSIB);
3866 * If right block is full enough so that removing one entry
3867 * won't make it too empty, and left-shifting an entry out
3868 * of right to us works, we're done.
3870 if (xfs_btree_get_numrecs(right) - 1 >=
3871 cur->bc_ops->get_minrecs(tcur, level)) {
3872 error = xfs_btree_lshift(tcur, level, &i);
3876 ASSERT(xfs_btree_get_numrecs(block) >=
3877 cur->bc_ops->get_minrecs(tcur, level));
3879 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
3882 error = xfs_btree_dec_cursor(cur, level, stat);
3890 * Otherwise, grab the number of records in right for
3891 * future reference, and fix up the temp cursor to point
3892 * to our block again (last record).
3894 rrecs = xfs_btree_get_numrecs(right);
3895 if (!xfs_btree_ptr_is_null(cur, &lptr)) {
3896 i = xfs_btree_firstrec(tcur, level);
3897 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
3898 error = -EFSCORRUPTED;
3902 error = xfs_btree_decrement(tcur, level, &i);
3905 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
3906 error = -EFSCORRUPTED;
3913 * If there's a left sibling, see if it's ok to shift an entry
3916 if (!xfs_btree_ptr_is_null(cur, &lptr)) {
3918 * Move the temp cursor to the first entry in the
3921 i = xfs_btree_firstrec(tcur, level);
3922 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
3923 error = -EFSCORRUPTED;
3927 error = xfs_btree_decrement(tcur, level, &i);
3930 i = xfs_btree_firstrec(tcur, level);
3931 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
3932 error = -EFSCORRUPTED;
3936 /* Grab a pointer to the block. */
3937 left = xfs_btree_get_block(tcur, level, &lbp);
3939 error = xfs_btree_check_block(cur, left, level, lbp);
3943 /* Grab the current block number, for future use. */
3944 xfs_btree_get_sibling(tcur, left, &cptr, XFS_BB_RIGHTSIB);
3947 * If left block is full enough so that removing one entry
3948 * won't make it too empty, and right-shifting an entry out
3949 * of left to us works, we're done.
3951 if (xfs_btree_get_numrecs(left) - 1 >=
3952 cur->bc_ops->get_minrecs(tcur, level)) {
3953 error = xfs_btree_rshift(tcur, level, &i);
3957 ASSERT(xfs_btree_get_numrecs(block) >=
3958 cur->bc_ops->get_minrecs(tcur, level));
3959 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
3970 * Otherwise, grab the number of records in right for
3973 lrecs = xfs_btree_get_numrecs(left);
3976 /* Delete the temp cursor, we're done with it. */
3977 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
3980 /* If here, we need to do a join to keep the tree balanced. */
3981 ASSERT(!xfs_btree_ptr_is_null(cur, &cptr));
3983 if (!xfs_btree_ptr_is_null(cur, &lptr) &&
3984 lrecs + xfs_btree_get_numrecs(block) <=
3985 cur->bc_ops->get_maxrecs(cur, level)) {
3987 * Set "right" to be the starting block,
3988 * "left" to be the left neighbor.
3993 error = xfs_btree_read_buf_block(cur, &lptr, 0, &left, &lbp);
3998 * If that won't work, see if we can join with the right neighbor block.
4000 } else if (!xfs_btree_ptr_is_null(cur, &rptr) &&
4001 rrecs + xfs_btree_get_numrecs(block) <=
4002 cur->bc_ops->get_maxrecs(cur, level)) {
4004 * Set "left" to be the starting block,
4005 * "right" to be the right neighbor.
4010 error = xfs_btree_read_buf_block(cur, &rptr, 0, &right, &rbp);
4015 * Otherwise, we can't fix the imbalance.
4016 * Just return. This is probably a logic error, but it's not fatal.
4019 error = xfs_btree_dec_cursor(cur, level, stat);
4025 rrecs = xfs_btree_get_numrecs(right);
4026 lrecs = xfs_btree_get_numrecs(left);
4029 * We're now going to join "left" and "right" by moving all the stuff
4030 * in "right" to "left" and deleting "right".
4032 XFS_BTREE_STATS_ADD(cur, moves, rrecs);
4034 /* It's a non-leaf. Move keys and pointers. */
4035 union xfs_btree_key *lkp; /* left btree key */
4036 union xfs_btree_ptr *lpp; /* left address pointer */
4037 union xfs_btree_key *rkp; /* right btree key */
4038 union xfs_btree_ptr *rpp; /* right address pointer */
4040 lkp = xfs_btree_key_addr(cur, lrecs + 1, left);
4041 lpp = xfs_btree_ptr_addr(cur, lrecs + 1, left);
4042 rkp = xfs_btree_key_addr(cur, 1, right);
4043 rpp = xfs_btree_ptr_addr(cur, 1, right);
4045 for (i = 1; i < rrecs; i++) {
4046 error = xfs_btree_debug_check_ptr(cur, rpp, i, level);
4051 xfs_btree_copy_keys(cur, lkp, rkp, rrecs);
4052 xfs_btree_copy_ptrs(cur, lpp, rpp, rrecs);
4054 xfs_btree_log_keys(cur, lbp, lrecs + 1, lrecs + rrecs);
4055 xfs_btree_log_ptrs(cur, lbp, lrecs + 1, lrecs + rrecs);
4057 /* It's a leaf. Move records. */
4058 union xfs_btree_rec *lrp; /* left record pointer */
4059 union xfs_btree_rec *rrp; /* right record pointer */
4061 lrp = xfs_btree_rec_addr(cur, lrecs + 1, left);
4062 rrp = xfs_btree_rec_addr(cur, 1, right);
4064 xfs_btree_copy_recs(cur, lrp, rrp, rrecs);
4065 xfs_btree_log_recs(cur, lbp, lrecs + 1, lrecs + rrecs);
4068 XFS_BTREE_STATS_INC(cur, join);
4071 * Fix up the number of records and right block pointer in the
4072 * surviving block, and log it.
4074 xfs_btree_set_numrecs(left, lrecs + rrecs);
4075 xfs_btree_get_sibling(cur, right, &cptr, XFS_BB_RIGHTSIB);
4076 xfs_btree_set_sibling(cur, left, &cptr, XFS_BB_RIGHTSIB);
4077 xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
4079 /* If there is a right sibling, point it to the remaining block. */
4080 xfs_btree_get_sibling(cur, left, &cptr, XFS_BB_RIGHTSIB);
4081 if (!xfs_btree_ptr_is_null(cur, &cptr)) {
4082 error = xfs_btree_read_buf_block(cur, &cptr, 0, &rrblock, &rrbp);
4085 xfs_btree_set_sibling(cur, rrblock, &lptr, XFS_BB_LEFTSIB);
4086 xfs_btree_log_block(cur, rrbp, XFS_BB_LEFTSIB);
4089 /* Free the deleted block. */
4090 error = xfs_btree_free_block(cur, rbp);
4095 * If we joined with the left neighbor, set the buffer in the
4096 * cursor to the left block, and fix up the index.
4099 cur->bc_bufs[level] = lbp;
4100 cur->bc_ptrs[level] += lrecs;
4101 cur->bc_ra[level] = 0;
4104 * If we joined with the right neighbor and there's a level above
4105 * us, increment the cursor at that level.
4107 else if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) ||
4108 (level + 1 < cur->bc_nlevels)) {
4109 error = xfs_btree_increment(cur, level + 1, &i);
4115 * Readjust the ptr at this level if it's not a leaf, since it's
4116 * still pointing at the deletion point, which makes the cursor
4117 * inconsistent. If this makes the ptr 0, the caller fixes it up.
4118 * We can't use decrement because it would change the next level up.
4121 cur->bc_ptrs[level]--;
4124 * We combined blocks, so we have to update the parent keys if the
4125 * btree supports overlapped intervals. However, bc_ptrs[level + 1]
4126 * points to the old block so that the caller knows which record to
4127 * delete. Therefore, the caller must be savvy enough to call updkeys
4128 * for us if we return stat == 2. The other exit points from this
4129 * function don't require deletions further up the tree, so they can
4130 * call updkeys directly.
4133 /* Return value means the next level up has something to do. */
4139 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
4144 * Delete the record pointed to by cur.
4145 * The cursor refers to the place where the record was (could be inserted)
4146 * when the operation returns.
4150 struct xfs_btree_cur *cur,
4151 int *stat) /* success/failure */
4153 int error; /* error return value */
4156 bool joined = false;
4159 * Go up the tree, starting at leaf level.
4161 * If 2 is returned then a join was done; go to the next level.
4162 * Otherwise we are done.
4164 for (level = 0, i = 2; i == 2; level++) {
4165 error = xfs_btree_delrec(cur, level, &i);
4173 * If we combined blocks as part of deleting the record, delrec won't
4174 * have updated the parent high keys so we have to do that here.
4176 if (joined && (cur->bc_flags & XFS_BTREE_OVERLAPPING)) {
4177 error = xfs_btree_updkeys_force(cur, 0);
4183 for (level = 1; level < cur->bc_nlevels; level++) {
4184 if (cur->bc_ptrs[level] == 0) {
4185 error = xfs_btree_decrement(cur, level, &i);
4200 * Get the data from the pointed-to record.
4204 struct xfs_btree_cur *cur, /* btree cursor */
4205 union xfs_btree_rec **recp, /* output: btree record */
4206 int *stat) /* output: success/failure */
4208 struct xfs_btree_block *block; /* btree block */
4209 struct xfs_buf *bp; /* buffer pointer */
4210 int ptr; /* record number */
4212 int error; /* error return value */
4215 ptr = cur->bc_ptrs[0];
4216 block = xfs_btree_get_block(cur, 0, &bp);
4219 error = xfs_btree_check_block(cur, block, 0, bp);
4225 * Off the right end or left end, return failure.
4227 if (ptr > xfs_btree_get_numrecs(block) || ptr <= 0) {
4233 * Point to the record and extract its data.
4235 *recp = xfs_btree_rec_addr(cur, ptr, block);
4240 /* Visit a block in a btree. */
4242 xfs_btree_visit_block(
4243 struct xfs_btree_cur *cur,
4245 xfs_btree_visit_blocks_fn fn,
4248 struct xfs_btree_block *block;
4250 union xfs_btree_ptr rptr;
4253 /* do right sibling readahead */
4254 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
4255 block = xfs_btree_get_block(cur, level, &bp);
4257 /* process the block */
4258 error = fn(cur, level, data);
4262 /* now read rh sibling block for next iteration */
4263 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB);
4264 if (xfs_btree_ptr_is_null(cur, &rptr))
4267 return xfs_btree_lookup_get_block(cur, level, &rptr, &block);
4271 /* Visit every block in a btree. */
4273 xfs_btree_visit_blocks(
4274 struct xfs_btree_cur *cur,
4275 xfs_btree_visit_blocks_fn fn,
4279 union xfs_btree_ptr lptr;
4281 struct xfs_btree_block *block = NULL;
4284 cur->bc_ops->init_ptr_from_cur(cur, &lptr);
4286 /* for each level */
4287 for (level = cur->bc_nlevels - 1; level >= 0; level--) {
4288 /* grab the left hand block */
4289 error = xfs_btree_lookup_get_block(cur, level, &lptr, &block);
4293 /* readahead the left most block for the next level down */
4295 union xfs_btree_ptr *ptr;
4297 ptr = xfs_btree_ptr_addr(cur, 1, block);
4298 xfs_btree_readahead_ptr(cur, ptr, 1);
4300 /* save for the next iteration of the loop */
4301 xfs_btree_copy_ptrs(cur, &lptr, ptr, 1);
4303 if (!(flags & XFS_BTREE_VISIT_LEAVES))
4305 } else if (!(flags & XFS_BTREE_VISIT_RECORDS)) {
4309 /* for each buffer in the level */
4311 error = xfs_btree_visit_block(cur, level, fn, data);
4314 if (error != -ENOENT)
4322 * Change the owner of a btree.
4324 * The mechanism we use here is ordered buffer logging. Because we don't know
4325 * how many buffers were are going to need to modify, we don't really want to
4326 * have to make transaction reservations for the worst case of every buffer in a
4327 * full size btree as that may be more space that we can fit in the log....
4329 * We do the btree walk in the most optimal manner possible - we have sibling
4330 * pointers so we can just walk all the blocks on each level from left to right
4331 * in a single pass, and then move to the next level and do the same. We can
4332 * also do readahead on the sibling pointers to get IO moving more quickly,
4333 * though for slow disks this is unlikely to make much difference to performance
4334 * as the amount of CPU work we have to do before moving to the next block is
4337 * For each btree block that we load, modify the owner appropriately, set the
4338 * buffer as an ordered buffer and log it appropriately. We need to ensure that
4339 * we mark the region we change dirty so that if the buffer is relogged in
4340 * a subsequent transaction the changes we make here as an ordered buffer are
4341 * correctly relogged in that transaction. If we are in recovery context, then
4342 * just queue the modified buffer as delayed write buffer so the transaction
4343 * recovery completion writes the changes to disk.
4345 struct xfs_btree_block_change_owner_info {
4347 struct list_head *buffer_list;
4351 xfs_btree_block_change_owner(
4352 struct xfs_btree_cur *cur,
4356 struct xfs_btree_block_change_owner_info *bbcoi = data;
4357 struct xfs_btree_block *block;
4360 /* modify the owner */
4361 block = xfs_btree_get_block(cur, level, &bp);
4362 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
4363 if (block->bb_u.l.bb_owner == cpu_to_be64(bbcoi->new_owner))
4365 block->bb_u.l.bb_owner = cpu_to_be64(bbcoi->new_owner);
4367 if (block->bb_u.s.bb_owner == cpu_to_be32(bbcoi->new_owner))
4369 block->bb_u.s.bb_owner = cpu_to_be32(bbcoi->new_owner);
4373 * If the block is a root block hosted in an inode, we might not have a
4374 * buffer pointer here and we shouldn't attempt to log the change as the
4375 * information is already held in the inode and discarded when the root
4376 * block is formatted into the on-disk inode fork. We still change it,
4377 * though, so everything is consistent in memory.
4380 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE);
4381 ASSERT(level == cur->bc_nlevels - 1);
4386 if (!xfs_trans_ordered_buf(cur->bc_tp, bp)) {
4387 xfs_btree_log_block(cur, bp, XFS_BB_OWNER);
4391 xfs_buf_delwri_queue(bp, bbcoi->buffer_list);
4398 xfs_btree_change_owner(
4399 struct xfs_btree_cur *cur,
4401 struct list_head *buffer_list)
4403 struct xfs_btree_block_change_owner_info bbcoi;
4405 bbcoi.new_owner = new_owner;
4406 bbcoi.buffer_list = buffer_list;
4408 return xfs_btree_visit_blocks(cur, xfs_btree_block_change_owner,
4409 XFS_BTREE_VISIT_ALL, &bbcoi);
4412 /* Verify the v5 fields of a long-format btree block. */
4414 xfs_btree_lblock_v5hdr_verify(
4418 struct xfs_mount *mp = bp->b_mount;
4419 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
4421 if (!xfs_sb_version_hascrc(&mp->m_sb))
4422 return __this_address;
4423 if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid))
4424 return __this_address;
4425 if (block->bb_u.l.bb_blkno != cpu_to_be64(bp->b_bn))
4426 return __this_address;
4427 if (owner != XFS_RMAP_OWN_UNKNOWN &&
4428 be64_to_cpu(block->bb_u.l.bb_owner) != owner)
4429 return __this_address;
4433 /* Verify a long-format btree block. */
4435 xfs_btree_lblock_verify(
4437 unsigned int max_recs)
4439 struct xfs_mount *mp = bp->b_mount;
4440 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
4442 /* numrecs verification */
4443 if (be16_to_cpu(block->bb_numrecs) > max_recs)
4444 return __this_address;
4446 /* sibling pointer verification */
4447 if (block->bb_u.l.bb_leftsib != cpu_to_be64(NULLFSBLOCK) &&
4448 !xfs_verify_fsbno(mp, be64_to_cpu(block->bb_u.l.bb_leftsib)))
4449 return __this_address;
4450 if (block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK) &&
4451 !xfs_verify_fsbno(mp, be64_to_cpu(block->bb_u.l.bb_rightsib)))
4452 return __this_address;
4458 * xfs_btree_sblock_v5hdr_verify() -- verify the v5 fields of a short-format
4461 * @bp: buffer containing the btree block
4464 xfs_btree_sblock_v5hdr_verify(
4467 struct xfs_mount *mp = bp->b_mount;
4468 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
4469 struct xfs_perag *pag = bp->b_pag;
4471 if (!xfs_sb_version_hascrc(&mp->m_sb))
4472 return __this_address;
4473 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid))
4474 return __this_address;
4475 if (block->bb_u.s.bb_blkno != cpu_to_be64(bp->b_bn))
4476 return __this_address;
4477 if (pag && be32_to_cpu(block->bb_u.s.bb_owner) != pag->pag_agno)
4478 return __this_address;
4483 * xfs_btree_sblock_verify() -- verify a short-format btree block
4485 * @bp: buffer containing the btree block
4486 * @max_recs: maximum records allowed in this btree node
4489 xfs_btree_sblock_verify(
4491 unsigned int max_recs)
4493 struct xfs_mount *mp = bp->b_mount;
4494 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
4497 /* numrecs verification */
4498 if (be16_to_cpu(block->bb_numrecs) > max_recs)
4499 return __this_address;
4501 /* sibling pointer verification */
4502 agno = xfs_daddr_to_agno(mp, XFS_BUF_ADDR(bp));
4503 if (block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK) &&
4504 !xfs_verify_agbno(mp, agno, be32_to_cpu(block->bb_u.s.bb_leftsib)))
4505 return __this_address;
4506 if (block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK) &&
4507 !xfs_verify_agbno(mp, agno, be32_to_cpu(block->bb_u.s.bb_rightsib)))
4508 return __this_address;
4514 * Calculate the number of btree levels needed to store a given number of
4515 * records in a short-format btree.
4518 xfs_btree_compute_maxlevels(
4523 unsigned long maxblocks;
4525 maxblocks = (len + limits[0] - 1) / limits[0];
4526 for (level = 1; maxblocks > 1; level++)
4527 maxblocks = (maxblocks + limits[1] - 1) / limits[1];
4532 * Query a regular btree for all records overlapping a given interval.
4533 * Start with a LE lookup of the key of low_rec and return all records
4534 * until we find a record with a key greater than the key of high_rec.
4537 xfs_btree_simple_query_range(
4538 struct xfs_btree_cur *cur,
4539 const union xfs_btree_key *low_key,
4540 const union xfs_btree_key *high_key,
4541 xfs_btree_query_range_fn fn,
4544 union xfs_btree_rec *recp;
4545 union xfs_btree_key rec_key;
4548 bool firstrec = true;
4551 ASSERT(cur->bc_ops->init_high_key_from_rec);
4552 ASSERT(cur->bc_ops->diff_two_keys);
4555 * Find the leftmost record. The btree cursor must be set
4556 * to the low record used to generate low_key.
4559 error = xfs_btree_lookup(cur, XFS_LOOKUP_LE, &stat);
4563 /* Nothing? See if there's anything to the right. */
4565 error = xfs_btree_increment(cur, 0, &stat);
4571 /* Find the record. */
4572 error = xfs_btree_get_rec(cur, &recp, &stat);
4576 /* Skip if high_key(rec) < low_key. */
4578 cur->bc_ops->init_high_key_from_rec(&rec_key, recp);
4580 diff = cur->bc_ops->diff_two_keys(cur, low_key,
4586 /* Stop if high_key < low_key(rec). */
4587 cur->bc_ops->init_key_from_rec(&rec_key, recp);
4588 diff = cur->bc_ops->diff_two_keys(cur, &rec_key, high_key);
4593 error = fn(cur, recp, priv);
4598 /* Move on to the next record. */
4599 error = xfs_btree_increment(cur, 0, &stat);
4609 * Query an overlapped interval btree for all records overlapping a given
4610 * interval. This function roughly follows the algorithm given in
4611 * "Interval Trees" of _Introduction to Algorithms_, which is section
4612 * 14.3 in the 2nd and 3rd editions.
4614 * First, generate keys for the low and high records passed in.
4616 * For any leaf node, generate the high and low keys for the record.
4617 * If the record keys overlap with the query low/high keys, pass the
4618 * record to the function iterator.
4620 * For any internal node, compare the low and high keys of each
4621 * pointer against the query low/high keys. If there's an overlap,
4622 * follow the pointer.
4624 * As an optimization, we stop scanning a block when we find a low key
4625 * that is greater than the query's high key.
4628 xfs_btree_overlapped_query_range(
4629 struct xfs_btree_cur *cur,
4630 const union xfs_btree_key *low_key,
4631 const union xfs_btree_key *high_key,
4632 xfs_btree_query_range_fn fn,
4635 union xfs_btree_ptr ptr;
4636 union xfs_btree_ptr *pp;
4637 union xfs_btree_key rec_key;
4638 union xfs_btree_key rec_hkey;
4639 union xfs_btree_key *lkp;
4640 union xfs_btree_key *hkp;
4641 union xfs_btree_rec *recp;
4642 struct xfs_btree_block *block;
4650 /* Load the root of the btree. */
4651 level = cur->bc_nlevels - 1;
4652 cur->bc_ops->init_ptr_from_cur(cur, &ptr);
4653 error = xfs_btree_lookup_get_block(cur, level, &ptr, &block);
4656 xfs_btree_get_block(cur, level, &bp);
4657 trace_xfs_btree_overlapped_query_range(cur, level, bp);
4659 error = xfs_btree_check_block(cur, block, level, bp);
4663 cur->bc_ptrs[level] = 1;
4665 while (level < cur->bc_nlevels) {
4666 block = xfs_btree_get_block(cur, level, &bp);
4668 /* End of node, pop back towards the root. */
4669 if (cur->bc_ptrs[level] > be16_to_cpu(block->bb_numrecs)) {
4671 if (level < cur->bc_nlevels - 1)
4672 cur->bc_ptrs[level + 1]++;
4678 /* Handle a leaf node. */
4679 recp = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block);
4681 cur->bc_ops->init_high_key_from_rec(&rec_hkey, recp);
4682 ldiff = cur->bc_ops->diff_two_keys(cur, &rec_hkey,
4685 cur->bc_ops->init_key_from_rec(&rec_key, recp);
4686 hdiff = cur->bc_ops->diff_two_keys(cur, high_key,
4690 * If (record's high key >= query's low key) and
4691 * (query's high key >= record's low key), then
4692 * this record overlaps the query range; callback.
4694 if (ldiff >= 0 && hdiff >= 0) {
4695 error = fn(cur, recp, priv);
4698 } else if (hdiff < 0) {
4699 /* Record is larger than high key; pop. */
4702 cur->bc_ptrs[level]++;
4706 /* Handle an internal node. */
4707 lkp = xfs_btree_key_addr(cur, cur->bc_ptrs[level], block);
4708 hkp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level], block);
4709 pp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[level], block);
4711 ldiff = cur->bc_ops->diff_two_keys(cur, hkp, low_key);
4712 hdiff = cur->bc_ops->diff_two_keys(cur, high_key, lkp);
4715 * If (pointer's high key >= query's low key) and
4716 * (query's high key >= pointer's low key), then
4717 * this record overlaps the query range; follow pointer.
4719 if (ldiff >= 0 && hdiff >= 0) {
4721 error = xfs_btree_lookup_get_block(cur, level, pp,
4725 xfs_btree_get_block(cur, level, &bp);
4726 trace_xfs_btree_overlapped_query_range(cur, level, bp);
4728 error = xfs_btree_check_block(cur, block, level, bp);
4732 cur->bc_ptrs[level] = 1;
4734 } else if (hdiff < 0) {
4735 /* The low key is larger than the upper range; pop. */
4738 cur->bc_ptrs[level]++;
4743 * If we don't end this function with the cursor pointing at a record
4744 * block, a subsequent non-error cursor deletion will not release
4745 * node-level buffers, causing a buffer leak. This is quite possible
4746 * with a zero-results range query, so release the buffers if we
4747 * failed to return any results.
4749 if (cur->bc_bufs[0] == NULL) {
4750 for (i = 0; i < cur->bc_nlevels; i++) {
4751 if (cur->bc_bufs[i]) {
4752 xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[i]);
4753 cur->bc_bufs[i] = NULL;
4754 cur->bc_ptrs[i] = 0;
4764 * Query a btree for all records overlapping a given interval of keys. The
4765 * supplied function will be called with each record found; return one of the
4766 * XFS_BTREE_QUERY_RANGE_{CONTINUE,ABORT} values or the usual negative error
4767 * code. This function returns -ECANCELED, zero, or a negative error code.
4770 xfs_btree_query_range(
4771 struct xfs_btree_cur *cur,
4772 const union xfs_btree_irec *low_rec,
4773 const union xfs_btree_irec *high_rec,
4774 xfs_btree_query_range_fn fn,
4777 union xfs_btree_rec rec;
4778 union xfs_btree_key low_key;
4779 union xfs_btree_key high_key;
4781 /* Find the keys of both ends of the interval. */
4782 cur->bc_rec = *high_rec;
4783 cur->bc_ops->init_rec_from_cur(cur, &rec);
4784 cur->bc_ops->init_key_from_rec(&high_key, &rec);
4786 cur->bc_rec = *low_rec;
4787 cur->bc_ops->init_rec_from_cur(cur, &rec);
4788 cur->bc_ops->init_key_from_rec(&low_key, &rec);
4790 /* Enforce low key < high key. */
4791 if (cur->bc_ops->diff_two_keys(cur, &low_key, &high_key) > 0)
4794 if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
4795 return xfs_btree_simple_query_range(cur, &low_key,
4796 &high_key, fn, priv);
4797 return xfs_btree_overlapped_query_range(cur, &low_key, &high_key,
4801 /* Query a btree for all records. */
4803 xfs_btree_query_all(
4804 struct xfs_btree_cur *cur,
4805 xfs_btree_query_range_fn fn,
4808 union xfs_btree_key low_key;
4809 union xfs_btree_key high_key;
4811 memset(&cur->bc_rec, 0, sizeof(cur->bc_rec));
4812 memset(&low_key, 0, sizeof(low_key));
4813 memset(&high_key, 0xFF, sizeof(high_key));
4815 return xfs_btree_simple_query_range(cur, &low_key, &high_key, fn, priv);
4819 * Calculate the number of blocks needed to store a given number of records
4820 * in a short-format (per-AG metadata) btree.
4823 xfs_btree_calc_size(
4825 unsigned long long len)
4829 unsigned long long rval;
4831 maxrecs = limits[0];
4832 for (level = 0, rval = 0; len > 1; level++) {
4834 do_div(len, maxrecs);
4835 maxrecs = limits[1];
4842 xfs_btree_count_blocks_helper(
4843 struct xfs_btree_cur *cur,
4847 xfs_extlen_t *blocks = data;
4853 /* Count the blocks in a btree and return the result in *blocks. */
4855 xfs_btree_count_blocks(
4856 struct xfs_btree_cur *cur,
4857 xfs_extlen_t *blocks)
4860 return xfs_btree_visit_blocks(cur, xfs_btree_count_blocks_helper,
4861 XFS_BTREE_VISIT_ALL, blocks);
4864 /* Compare two btree pointers. */
4866 xfs_btree_diff_two_ptrs(
4867 struct xfs_btree_cur *cur,
4868 const union xfs_btree_ptr *a,
4869 const union xfs_btree_ptr *b)
4871 if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
4872 return (int64_t)be64_to_cpu(a->l) - be64_to_cpu(b->l);
4873 return (int64_t)be32_to_cpu(a->s) - be32_to_cpu(b->s);
4876 /* If there's an extent, we're done. */
4878 xfs_btree_has_record_helper(
4879 struct xfs_btree_cur *cur,
4880 const union xfs_btree_rec *rec,
4886 /* Is there a record covering a given range of keys? */
4888 xfs_btree_has_record(
4889 struct xfs_btree_cur *cur,
4890 const union xfs_btree_irec *low,
4891 const union xfs_btree_irec *high,
4896 error = xfs_btree_query_range(cur, low, high,
4897 &xfs_btree_has_record_helper, NULL);
4898 if (error == -ECANCELED) {
4906 /* Are there more records in this btree? */
4908 xfs_btree_has_more_records(
4909 struct xfs_btree_cur *cur)
4911 struct xfs_btree_block *block;
4914 block = xfs_btree_get_block(cur, 0, &bp);
4916 /* There are still records in this block. */
4917 if (cur->bc_ptrs[0] < xfs_btree_get_numrecs(block))
4920 /* There are more record blocks. */
4921 if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
4922 return block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK);
4924 return block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK);