/* Ensure we asked for crc for crc-only magics. */
ASSERT(magic != 0); return be32_to_cpu(magic);
}
/* * These sibling pointer checks are optimised for null sibling pointers. This * happens a lot, and we don't need to byte swap at runtime if the sibling * pointer is NULL. * * These are explicitly marked at inline because the cost of calling them as * functions instead of inlining them is about 36 bytes extra code per call site * on x86-64. Yes, gcc-11 fails to inline them, and explicit inlining of these * two sibling check functions reduces the compiled code size by over 300 * bytes.
*/ staticinline xfs_failaddr_t
xfs_btree_check_fsblock_siblings( struct xfs_mount *mp,
xfs_fsblock_t fsb,
__be64 dsibling)
{
xfs_fsblock_t sibling;
if (dsibling == cpu_to_be64(NULLFSBLOCK)) return NULL;
sibling = be64_to_cpu(dsibling); if (sibling == fsb) return __this_address; if (!xfs_verify_fsbno(mp, sibling)) return __this_address; return NULL;
}
if (xfs_has_crc(mp)) { if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid)) return __this_address; if (block->bb_u.l.bb_blkno !=
cpu_to_be64(bp ? xfs_buf_daddr(bp) : XFS_BUF_DADDR_NULL)) return __this_address; if (block->bb_u.l.bb_pad != cpu_to_be32(0)) return __this_address;
}
if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(mp, cur->bc_ops)) return __this_address; if (be16_to_cpu(block->bb_level) != level) return __this_address; if (be16_to_cpu(block->bb_numrecs) >
cur->bc_ops->get_maxrecs(cur, level)) return __this_address;
return NULL;
}
/* * Check a long btree block header. Return the address of the failing check, * or NULL if everything is ok.
*/ static xfs_failaddr_t
__xfs_btree_check_fsblock( struct xfs_btree_cur *cur, struct xfs_btree_block *block, int level, struct xfs_buf *bp)
{ struct xfs_mount *mp = cur->bc_mp;
xfs_failaddr_t fa;
xfs_fsblock_t fsb;
fa = __xfs_btree_check_lblock_hdr(cur, block, level, bp); if (fa) return fa;
/* * For inode-rooted btrees, the root block sits in the inode fork. In * that case bp is NULL, and the block must not have any siblings.
*/ if (!bp) { if (block->bb_u.l.bb_leftsib != cpu_to_be64(NULLFSBLOCK)) return __this_address; if (block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK)) return __this_address; return NULL;
}
fsb = XFS_DADDR_TO_FSB(mp, xfs_buf_daddr(bp));
fa = xfs_btree_check_fsblock_siblings(mp, fsb,
block->bb_u.l.bb_leftsib); if (!fa)
fa = xfs_btree_check_fsblock_siblings(mp, fsb,
block->bb_u.l.bb_rightsib); return fa;
}
/* * Check an in-memory btree block header. Return the address of the failing * check, or NULL if everything is ok.
*/ static xfs_failaddr_t
__xfs_btree_check_memblock( struct xfs_btree_cur *cur, struct xfs_btree_block *block, int level, struct xfs_buf *bp)
{ struct xfs_buftarg *btp = cur->bc_mem.xfbtree->target;
xfs_failaddr_t fa;
xfbno_t bno;
fa = __xfs_btree_check_lblock_hdr(cur, block, level, bp); if (fa) return fa;
bno = xfs_daddr_to_xfbno(xfs_buf_daddr(bp));
fa = xfs_btree_check_memblock_siblings(btp, bno,
block->bb_u.l.bb_leftsib); if (!fa)
fa = xfs_btree_check_memblock_siblings(btp, bno,
block->bb_u.l.bb_rightsib); return fa;
}
/* * Check a short btree block header. Return the address of the failing check, * or NULL if everything is ok.
*/ static xfs_failaddr_t
__xfs_btree_check_agblock( struct xfs_btree_cur *cur, struct xfs_btree_block *block, int level, struct xfs_buf *bp)
{ struct xfs_mount *mp = cur->bc_mp; struct xfs_perag *pag = to_perag(cur->bc_group);
xfs_failaddr_t fa;
xfs_agblock_t agbno;
if (xfs_has_crc(mp)) { if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid)) return __this_address; if (block->bb_u.s.bb_blkno != cpu_to_be64(xfs_buf_daddr(bp))) return __this_address;
}
if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(mp, cur->bc_ops)) return __this_address; if (be16_to_cpu(block->bb_level) != level) return __this_address; if (be16_to_cpu(block->bb_numrecs) >
cur->bc_ops->get_maxrecs(cur, level)) return __this_address;
agbno = xfs_daddr_to_agbno(mp, xfs_buf_daddr(bp));
fa = xfs_btree_check_agblock_siblings(pag, agbno,
block->bb_u.s.bb_leftsib); if (!fa)
fa = xfs_btree_check_agblock_siblings(pag, agbno,
block->bb_u.s.bb_rightsib); return fa;
}
/* * Internal btree block check. * * Return NULL if the block is ok or the address of the failed check otherwise.
*/
xfs_failaddr_t
__xfs_btree_check_block( struct xfs_btree_cur *cur, struct xfs_btree_block *block, int level, struct xfs_buf *bp)
{ switch (cur->bc_ops->type) { case XFS_BTREE_TYPE_MEM: return __xfs_btree_check_memblock(cur, block, level, bp); case XFS_BTREE_TYPE_AG: return __xfs_btree_check_agblock(cur, block, level, bp); case XFS_BTREE_TYPE_INODE: return __xfs_btree_check_fsblock(cur, block, level, bp); default:
ASSERT(0); return __this_address;
}
}
/* * Debug routine: check that block header is ok.
*/ int
xfs_btree_check_block( struct xfs_btree_cur *cur, /* btree cursor */ struct xfs_btree_block *block, /* generic btree block pointer */ int level, /* level of the btree block */ struct xfs_buf *bp) /* buffer containing block, if any */
{ struct xfs_mount *mp = cur->bc_mp;
xfs_failaddr_t fa;
fa = __xfs_btree_check_block(cur, block, level, bp); if (XFS_IS_CORRUPT(mp, fa != NULL) ||
XFS_TEST_ERROR(false, mp, xfs_btree_block_errtag(cur))) { if (bp)
trace_xfs_btree_corrupt(bp, _RET_IP_);
xfs_btree_mark_sick(cur); return -EFSCORRUPTED;
} return 0;
}
int
__xfs_btree_check_ptr( struct xfs_btree_cur *cur, constunion xfs_btree_ptr *ptr, int index, int level)
{ if (level <= 0) return -EFSCORRUPTED;
switch (cur->bc_ops->type) { case XFS_BTREE_TYPE_MEM: if (!xfbtree_verify_bno(cur->bc_mem.xfbtree,
be64_to_cpu((&ptr->l)[index]))) return -EFSCORRUPTED; break; case XFS_BTREE_TYPE_INODE: if (!xfs_verify_fsbno(cur->bc_mp,
be64_to_cpu((&ptr->l)[index]))) return -EFSCORRUPTED; break; case XFS_BTREE_TYPE_AG: if (!xfs_verify_agbno(to_perag(cur->bc_group),
be32_to_cpu((&ptr->s)[index]))) return -EFSCORRUPTED; break;
}
return 0;
}
/* * Check that a given (indexed) btree pointer at a certain level of a * btree is valid and doesn't point past where it should.
*/ staticint
xfs_btree_check_ptr( struct xfs_btree_cur *cur, constunion xfs_btree_ptr *ptr, int index, int level)
{ int error;
error = __xfs_btree_check_ptr(cur, ptr, index, level); if (error) { switch (cur->bc_ops->type) { case XFS_BTREE_TYPE_MEM:
xfs_err(cur->bc_mp, "In-memory: Corrupt %sbt flags 0x%x pointer at level %d index %d fa %pS.",
cur->bc_ops->name, cur->bc_flags, level, index,
__this_address); break; case XFS_BTREE_TYPE_INODE:
xfs_err(cur->bc_mp, "Inode %llu fork %d: Corrupt %sbt pointer at level %d index %d.",
cur->bc_ino.ip->i_ino,
cur->bc_ino.whichfork, cur->bc_ops->name,
level, index); break; case XFS_BTREE_TYPE_AG:
xfs_err(cur->bc_mp, "AG %u: Corrupt %sbt pointer at level %d index %d.",
cur->bc_group->xg_gno, cur->bc_ops->name,
level, index); break;
}
xfs_btree_mark_sick(cur);
}
/* * Calculate CRC on the whole btree block and stuff it into the * long-form btree header. * * Prior to calculting the CRC, pull the LSN out of the buffer log item and put * it into the buffer so recovery knows what the last modification was that made * it to disk.
*/ void
xfs_btree_fsblock_calc_crc( struct xfs_buf *bp)
{ struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); struct xfs_buf_log_item *bip = bp->b_log_item;
if (!xfs_has_crc(bp->b_mount)) return; if (bip)
block->bb_u.l.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn);
xfs_buf_update_cksum(bp, XFS_BTREE_LBLOCK_CRC_OFF);
}
if (xfs_has_crc(mp)) { if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.l.bb_lsn))) returnfalse; return xfs_buf_verify_cksum(bp, XFS_BTREE_LBLOCK_CRC_OFF);
}
returntrue;
}
/* * Calculate CRC on the whole btree block and stuff it into the * short-form btree header. * * Prior to calculting the CRC, pull the LSN out of the buffer log item and put * it into the buffer so recovery knows what the last modification was that made * it to disk.
*/ void
xfs_btree_agblock_calc_crc( struct xfs_buf *bp)
{ struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); struct xfs_buf_log_item *bip = bp->b_log_item;
if (!xfs_has_crc(bp->b_mount)) return; if (bip)
block->bb_u.s.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn);
xfs_buf_update_cksum(bp, XFS_BTREE_SBLOCK_CRC_OFF);
}
/* * Don't allow block freeing for a staging cursor, because staging * cursors do not support regular btree modifications.
*/ if (unlikely(cur->bc_flags & XFS_BTREE_STAGING)) {
ASSERT(0); return -EFSCORRUPTED;
}
/* * Delete the btree cursor.
*/ void
xfs_btree_del_cursor( struct xfs_btree_cur *cur, /* btree cursor */ int error) /* del because of error */
{ int i; /* btree level */
/* * Clear the buffer pointers and release the buffers. If we're doing * this because of an error, inspect all of the entries in the bc_bufs * array for buffers to be unlocked. This is because some of the btree * code works from level n down to 0, and if we get an error along the * way we won't have initialized all the entries down to 0.
*/ for (i = 0; i < cur->bc_nlevels; i++) { if (cur->bc_levels[i].bp)
xfs_trans_brelse(cur->bc_tp, cur->bc_levels[i].bp); elseif (!error) break;
}
/* * If we are doing a BMBT update, the number of unaccounted blocks * allocated during this cursor life time should be zero. If it's not * zero, then we should be shut down or on our way to shutdown due to * cancelling a dirty transaction on error.
*/
ASSERT(!xfs_btree_is_bmap(cur->bc_ops) || cur->bc_bmap.allocated == 0 ||
xfs_is_shutdown(cur->bc_mp) || error != 0);
if (cur->bc_group)
xfs_group_put(cur->bc_group);
kmem_cache_free(cur->bc_cache, cur);
}
/* Return the buffer target for this btree's buffer. */ staticinlinestruct xfs_buftarg *
xfs_btree_buftarg( struct xfs_btree_cur *cur)
{ if (cur->bc_ops->type == XFS_BTREE_TYPE_MEM) return cur->bc_mem.xfbtree->target; return cur->bc_mp->m_ddev_targp;
}
/* Return the block size (in units of 512b sectors) for this btree. */ staticinlineunsignedint
xfs_btree_bbsize( struct xfs_btree_cur *cur)
{ if (cur->bc_ops->type == XFS_BTREE_TYPE_MEM) return XFBNO_BBSIZE; return cur->bc_mp->m_bsize;
}
/* * Duplicate the btree cursor. * Allocate a new one, copy the record, re-get the buffers.
*/ int/* error */
xfs_btree_dup_cursor( struct xfs_btree_cur *cur, /* input cursor */ struct xfs_btree_cur **ncur) /* output cursor */
{ struct xfs_mount *mp = cur->bc_mp; struct xfs_trans *tp = cur->bc_tp; struct xfs_buf *bp; struct xfs_btree_cur *new; int error; int i;
/* * Don't allow staging cursors to be duplicated because they're supposed * to be kept private to a single thread.
*/ if (unlikely(cur->bc_flags & XFS_BTREE_STAGING)) {
ASSERT(0); return -EFSCORRUPTED;
}
/* * Allocate a new cursor like the old one.
*/ new = cur->bc_ops->dup_cursor(cur);
/* * Copy the record currently in the cursor.
*/
new->bc_rec = cur->bc_rec;
/* * For each level current, re-get the buffer and copy the ptr value.
*/ for (i = 0; i < new->bc_nlevels; i++) {
new->bc_levels[i].ptr = cur->bc_levels[i].ptr;
new->bc_levels[i].ra = cur->bc_levels[i].ra;
bp = cur->bc_levels[i].bp; if (bp) {
error = xfs_trans_read_buf(mp, tp,
xfs_btree_buftarg(cur),
xfs_buf_daddr(bp),
xfs_btree_bbsize(cur), 0, &bp,
cur->bc_ops->buf_ops); if (xfs_metadata_is_sick(error))
xfs_btree_mark_sick(new); if (error) {
xfs_btree_del_cursor(new, error);
*ncur = NULL; return error;
}
}
new->bc_levels[i].bp = bp;
}
*ncur = new; return 0;
}
/* * XFS btree block layout and addressing: * * There are two types of blocks in the btree: leaf and non-leaf blocks. * * The leaf record start with a header then followed by records containing * the values. A non-leaf block also starts with the same header, and * then first contains lookup keys followed by an equal number of pointers * to the btree blocks at the previous level. * * +--------+-------+-------+-------+-------+-------+-------+ * Leaf: | header | rec 1 | rec 2 | rec 3 | rec 4 | rec 5 | rec N | * +--------+-------+-------+-------+-------+-------+-------+ * * +--------+-------+-------+-------+-------+-------+-------+ * Non-Leaf: | header | key 1 | key 2 | key N | ptr 1 | ptr 2 | ptr N | * +--------+-------+-------+-------+-------+-------+-------+ * * The header is called struct xfs_btree_block for reasons better left unknown * and comes in different versions for short (32bit) and long (64bit) block * pointers. The record and key structures are defined by the btree instances * and opaque to the btree core. The block pointers are simple disk endian * integers, available in a short (32bit) and long (64bit) variant. * * The helpers below calculate the offset of a given record, key or pointer * into a btree block (xfs_btree_*_offset) or return a pointer to the given * record, key or pointer (xfs_btree_*_addr). Note that all addressing * inside the btree block is done using indices starting at one, not zero! * * If XFS_BTGEO_OVERLAPPING is set, then this btree supports keys containing * overlapping intervals. In such a tree, records are still sorted lowest to * highest and indexed by the smallest key value that refers to the record. * However, nodes are different: each pointer has two associated keys -- one * indexing the lowest key available in the block(s) below (the same behavior * as the key in a regular btree) and another indexing the highest key * available in the block(s) below. Because records are /not/ sorted by the * highest key, all leaf block updates require us to compute the highest key * that matches any record in the leaf and to recursively update the high keys * in the nodes going further up in the tree, if necessary. Nodes look like * this: * * +--------+-----+-----+-----+-----+-----+-------+-------+-----+ * Non-Leaf: | header | lo1 | hi1 | lo2 | hi2 | ... | ptr 1 | ptr 2 | ... | * +--------+-----+-----+-----+-----+-----+-------+-------+-----+ * * To perform an interval query on an overlapped tree, perform the usual * depth-first search and use the low and high keys to decide if we can skip * that particular node. If a leaf node is reached, return the records that * intersect the interval. Note that an interval query may return numerous * entries. For a non-overlapped tree, simply search for the record associated * with the lowest key and iterate forward until a non-matching record is * found. Section 14.3 ("Interval Trees") of _Introduction to Algorithms_ by * Cormen, Leiserson, Rivest, and Stein (2nd or 3rd ed. only) discuss this in * more detail. * * Why do we care about overlapping intervals? Let's say you have a bunch of * reverse mapping records on a reflink filesystem: * * 1: +- file A startblock B offset C length D -----------+ * 2: +- file E startblock F offset G length H --------------+ * 3: +- file I startblock F offset J length K --+ * 4: +- file L... --+ * * Now say we want to map block (B+D) into file A at offset (C+D). Ideally, * we'd simply increment the length of record 1. But how do we find the record * that ends at (B+D-1) (i.e. record 1)? A LE lookup of (B+D-1) would return * record 3 because the keys are ordered first by startblock. An interval * query would return records 1 and 2 because they both overlap (B+D-1), and * from that we can pick out record 1 as the appropriate left neighbor. * * In the non-overlapped case you can do a LE lookup and decrement the cursor * because a record's interval must end before the next record.
*/
/* * Return size of the btree block header for this btree instance.
*/ staticinline size_t xfs_btree_block_len(struct xfs_btree_cur *cur)
{ if (cur->bc_ops->ptr_len == XFS_BTREE_LONG_PTR_LEN) { if (xfs_has_crc(cur->bc_mp)) return XFS_BTREE_LBLOCK_CRC_LEN; return XFS_BTREE_LBLOCK_LEN;
} if (xfs_has_crc(cur->bc_mp)) return XFS_BTREE_SBLOCK_CRC_LEN; return XFS_BTREE_SBLOCK_LEN;
}
/* * Calculate offset of the n-th record in a btree block.
*/ STATIC size_t
xfs_btree_rec_offset( struct xfs_btree_cur *cur, int n)
{ return xfs_btree_block_len(cur) +
(n - 1) * cur->bc_ops->rec_len;
}
/* * Calculate offset of the n-th key in a btree block.
*/ STATIC size_t
xfs_btree_key_offset( struct xfs_btree_cur *cur, int n)
{ return xfs_btree_block_len(cur) +
(n - 1) * cur->bc_ops->key_len;
}
/* * Calculate offset of the n-th high key in a btree block.
*/ STATIC size_t
xfs_btree_high_key_offset( struct xfs_btree_cur *cur, int n)
{ return xfs_btree_block_len(cur) +
(n - 1) * cur->bc_ops->key_len + (cur->bc_ops->key_len / 2);
}
/* * Calculate offset of the n-th block pointer in a btree block.
*/ STATIC size_t
xfs_btree_ptr_offset( struct xfs_btree_cur *cur, int n, int level)
{ return xfs_btree_block_len(cur) +
cur->bc_ops->get_maxrecs(cur, level) * cur->bc_ops->key_len +
(n - 1) * cur->bc_ops->ptr_len;
}
/* * Return a pointer to the n-th record in the btree block.
*/ union xfs_btree_rec *
xfs_btree_rec_addr( struct xfs_btree_cur *cur, int n, struct xfs_btree_block *block)
{ return (union xfs_btree_rec *)
((char *)block + xfs_btree_rec_offset(cur, n));
}
/* * Return a pointer to the n-th key in the btree block.
*/ union xfs_btree_key *
xfs_btree_key_addr( struct xfs_btree_cur *cur, int n, struct xfs_btree_block *block)
{ return (union xfs_btree_key *)
((char *)block + xfs_btree_key_offset(cur, n));
}
/* * Return a pointer to the n-th high key in the btree block.
*/ union xfs_btree_key *
xfs_btree_high_key_addr( struct xfs_btree_cur *cur, int n, struct xfs_btree_block *block)
{ return (union xfs_btree_key *)
((char *)block + xfs_btree_high_key_offset(cur, n));
}
/* * Return a pointer to the n-th block pointer in the btree block.
*/ union xfs_btree_ptr *
xfs_btree_ptr_addr( struct xfs_btree_cur *cur, int n, struct xfs_btree_block *block)
{ int level = xfs_btree_get_level(block);
if (cur->bc_flags & XFS_BTREE_STAGING) return cur->bc_ino.ifake->if_fork; return xfs_ifork_ptr(cur->bc_ino.ip, cur->bc_ino.whichfork);
}
/* * Get the root block which is stored in the inode. * * For now this btree implementation assumes the btree root is always * stored in the if_broot field of an inode fork.
*/ STATICstruct xfs_btree_block *
xfs_btree_get_iroot( struct xfs_btree_cur *cur)
{ struct xfs_ifork *ifp = xfs_btree_ifork_ptr(cur);
return (struct xfs_btree_block *)ifp->if_broot;
}
/* * Retrieve the block pointer from the cursor at the given level. * This may be an inode btree root or from a buffer.
*/ struct xfs_btree_block * /* generic btree block pointer */
xfs_btree_get_block( struct xfs_btree_cur *cur, /* btree cursor */ int level, /* level in btree */ struct xfs_buf **bpp) /* buffer containing the block */
{ if (xfs_btree_at_iroot(cur, level)) {
*bpp = NULL; return xfs_btree_get_iroot(cur);
}
/* * Change the cursor to point to the first record at the given level. * Other levels are unaffected.
*/ STATICint/* success=1, failure=0 */
xfs_btree_firstrec( struct xfs_btree_cur *cur, /* btree cursor */ int level) /* level to change */
{ struct xfs_btree_block *block; /* generic btree block pointer */ struct xfs_buf *bp; /* buffer containing block */
/* * Get the block pointer for this level.
*/
block = xfs_btree_get_block(cur, level, &bp); if (xfs_btree_check_block(cur, block, level, bp)) return 0; /* * It's empty, there is no such record.
*/ if (!block->bb_numrecs) return 0; /* * Set the ptr value to 1, that's the first record/key.
*/
cur->bc_levels[level].ptr = 1; return 1;
}
/* * Change the cursor to point to the last record in the current block * at the given level. Other levels are unaffected.
*/ STATICint/* success=1, failure=0 */
xfs_btree_lastrec( struct xfs_btree_cur *cur, /* btree cursor */ int level) /* level to change */
{ struct xfs_btree_block *block; /* generic btree block pointer */ struct xfs_buf *bp; /* buffer containing block */
/* * Get the block pointer for this level.
*/
block = xfs_btree_get_block(cur, level, &bp); if (xfs_btree_check_block(cur, block, level, bp)) return 0; /* * It's empty, there is no such record.
*/ if (!block->bb_numrecs) return 0; /* * Set the ptr value to numrecs, that's the last record/key.
*/
cur->bc_levels[level].ptr = be16_to_cpu(block->bb_numrecs); return 1;
}
/* * Compute first and last byte offsets for the fields given. * Interprets the offsets table, which contains struct field offsets.
*/ void
xfs_btree_offsets(
uint32_t fields, /* bitmask of fields */ constshort *offsets, /* table of field offsets */ int nbits, /* number of bits to inspect */ int *first, /* output: first byte offset */ int *last) /* output: last byte offset */
{ int i; /* current bit number */
uint32_t imask; /* mask for current bit number */
ASSERT(fields != 0); /* * Find the lowest bit, so the first byte offset.
*/ for (i = 0, imask = 1u; ; i++, imask <<= 1) { if (imask & fields) {
*first = offsets[i]; break;
}
} /* * Find the highest bit, so the last byte offset.
*/ for (i = nbits - 1, imask = 1u << i; ; i--, imask >>= 1) { if (imask & fields) {
*last = offsets[i + 1] - 1; break;
}
}
}
STATICint
xfs_btree_readahead_fsblock( struct xfs_btree_cur *cur, int lr, struct xfs_btree_block *block)
{ struct xfs_mount *mp = cur->bc_mp;
xfs_fsblock_t left = be64_to_cpu(block->bb_u.l.bb_leftsib);
xfs_fsblock_t right = be64_to_cpu(block->bb_u.l.bb_rightsib); int rval = 0;
if ((lr & XFS_BTCUR_LEFTRA) && left != NULLFSBLOCK) {
xfs_buf_readahead(mp->m_ddev_targp, XFS_FSB_TO_DADDR(mp, left),
mp->m_bsize, cur->bc_ops->buf_ops);
rval++;
}
if ((lr & XFS_BTCUR_RIGHTRA) && right != NULLFSBLOCK) {
xfs_buf_readahead(mp->m_ddev_targp, XFS_FSB_TO_DADDR(mp, right),
mp->m_bsize, cur->bc_ops->buf_ops);
rval++;
}
return rval;
}
STATICint
xfs_btree_readahead_memblock( struct xfs_btree_cur *cur, int lr, struct xfs_btree_block *block)
{ struct xfs_buftarg *btp = cur->bc_mem.xfbtree->target;
xfbno_t left = be64_to_cpu(block->bb_u.l.bb_leftsib);
xfbno_t right = be64_to_cpu(block->bb_u.l.bb_rightsib); int rval = 0;
if ((lr & XFS_BTCUR_LEFTRA) && left != NULLFSBLOCK) {
xfs_buf_readahead(btp, xfbno_to_daddr(left), XFBNO_BBSIZE,
cur->bc_ops->buf_ops);
rval++;
}
if ((lr & XFS_BTCUR_RIGHTRA) && right != NULLFSBLOCK) {
xfs_buf_readahead(btp, xfbno_to_daddr(right), XFBNO_BBSIZE,
cur->bc_ops->buf_ops);
rval++;
}
return rval;
}
STATICint
xfs_btree_readahead_agblock( struct xfs_btree_cur *cur, int lr, struct xfs_btree_block *block)
{ struct xfs_mount *mp = cur->bc_mp; struct xfs_perag *pag = to_perag(cur->bc_group);
xfs_agblock_t left = be32_to_cpu(block->bb_u.s.bb_leftsib);
xfs_agblock_t right = be32_to_cpu(block->bb_u.s.bb_rightsib); int rval = 0;
if ((lr & XFS_BTCUR_LEFTRA) && left != NULLAGBLOCK) {
xfs_buf_readahead(mp->m_ddev_targp,
xfs_agbno_to_daddr(pag, left), mp->m_bsize,
cur->bc_ops->buf_ops);
rval++;
}
if ((lr & XFS_BTCUR_RIGHTRA) && right != NULLAGBLOCK) {
xfs_buf_readahead(mp->m_ddev_targp,
xfs_agbno_to_daddr(pag, right), mp->m_bsize,
cur->bc_ops->buf_ops);
rval++;
}
return rval;
}
/* * Read-ahead btree blocks, at the given level. * Bits in lr are set from XFS_BTCUR_{LEFT,RIGHT}RA.
*/ STATICint
xfs_btree_readahead( struct xfs_btree_cur *cur, /* btree cursor */ int lev, /* level in btree */ int lr) /* left/right bits */
{ struct xfs_btree_block *block;
/* * No readahead needed if we are at the root level and the * btree root is stored in the inode.
*/ if (xfs_btree_at_iroot(cur, lev)) return 0;
if ((cur->bc_levels[lev].ra | lr) == cur->bc_levels[lev].ra) return 0;
error = xfs_btree_check_ptr(cur, ptr, 0, 1); if (error) return error;
switch (cur->bc_ops->type) { case XFS_BTREE_TYPE_AG:
*daddr = xfs_agbno_to_daddr(to_perag(cur->bc_group),
be32_to_cpu(ptr->s)); break; case XFS_BTREE_TYPE_INODE:
*daddr = XFS_FSB_TO_DADDR(cur->bc_mp, be64_to_cpu(ptr->l)); break; case XFS_BTREE_TYPE_MEM:
*daddr = xfbno_to_daddr(be64_to_cpu(ptr->l)); break;
} return 0;
}
/* * Readahead @count btree blocks at the given @ptr location. * * We don't need to care about long or short form btrees here as we have a * method of converting the ptr directly to a daddr available to us.
*/ STATICvoid
xfs_btree_readahead_ptr( struct xfs_btree_cur *cur, union xfs_btree_ptr *ptr,
xfs_extlen_t count)
{
xfs_daddr_t daddr;
/* * Set the buffer for level "lev" in the cursor to bp, releasing * any previous buffer.
*/ STATICvoid
xfs_btree_setbuf( struct xfs_btree_cur *cur, /* btree cursor */ int lev, /* level in btree */ struct xfs_buf *bp) /* new buffer to set */
{ struct xfs_btree_block *b; /* btree block */
if (cur->bc_levels[lev].bp)
xfs_trans_brelse(cur->bc_tp, cur->bc_levels[lev].bp);
cur->bc_levels[lev].bp = bp;
cur->bc_levels[lev].ra = 0;
b = XFS_BUF_TO_BLOCK(bp); if (cur->bc_ops->ptr_len == XFS_BTREE_LONG_PTR_LEN) { if (b->bb_u.l.bb_leftsib == cpu_to_be64(NULLFSBLOCK))
cur->bc_levels[lev].ra |= XFS_BTCUR_LEFTRA; if (b->bb_u.l.bb_rightsib == cpu_to_be64(NULLFSBLOCK))
cur->bc_levels[lev].ra |= XFS_BTCUR_RIGHTRA;
} else { if (b->bb_u.s.bb_leftsib == cpu_to_be32(NULLAGBLOCK))
cur->bc_levels[lev].ra |= XFS_BTCUR_LEFTRA; if (b->bb_u.s.bb_rightsib == cpu_to_be32(NULLAGBLOCK))
cur->bc_levels[lev].ra |= XFS_BTCUR_RIGHTRA;
}
}
/* * Read in the buffer at the given ptr and return the buffer and * the block pointer within the buffer.
*/ int
xfs_btree_read_buf_block( struct xfs_btree_cur *cur, constunion xfs_btree_ptr *ptr, int flags, struct xfs_btree_block **block, struct xfs_buf **bpp)
{ struct xfs_mount *mp = cur->bc_mp;
xfs_daddr_t d; int error;
/* need to sort out how callers deal with failures first */
ASSERT(!(flags & XBF_TRYLOCK));
error = xfs_btree_ptr_to_daddr(cur, ptr, &d); if (error) return error;
error = xfs_trans_read_buf(mp, cur->bc_tp, xfs_btree_buftarg(cur), d,
xfs_btree_bbsize(cur), flags, bpp,
cur->bc_ops->buf_ops); if (xfs_metadata_is_sick(error))
xfs_btree_mark_sick(cur); if (error) return error;
/* * Copy keys from one btree block to another.
*/ void
xfs_btree_copy_keys( struct xfs_btree_cur *cur, union xfs_btree_key *dst_key, constunion xfs_btree_key *src_key, int numkeys)
{
ASSERT(numkeys >= 0);
memcpy(dst_key, src_key, numkeys * cur->bc_ops->key_len);
}
/* * Copy records from one btree block to another.
*/ STATICvoid
xfs_btree_copy_recs( struct xfs_btree_cur *cur, union xfs_btree_rec *dst_rec, union xfs_btree_rec *src_rec, int numrecs)
{
ASSERT(numrecs >= 0);
memcpy(dst_rec, src_rec, numrecs * cur->bc_ops->rec_len);
}
/* * Copy block pointers from one btree block to another.
*/ void
xfs_btree_copy_ptrs( struct xfs_btree_cur *cur, union xfs_btree_ptr *dst_ptr, constunion xfs_btree_ptr *src_ptr, int numptrs)
{
ASSERT(numptrs >= 0);
memcpy(dst_ptr, src_ptr, numptrs * cur->bc_ops->ptr_len);
}
/* * Shift keys one index left/right inside a single btree block.
*/ STATICvoid
xfs_btree_shift_keys( struct xfs_btree_cur *cur, union xfs_btree_key *key, int dir, int numkeys)
{ char *dst_key;
ASSERT(numkeys >= 0);
ASSERT(dir == 1 || dir == -1);
/* * Shift records one index left/right inside a single btree block.
*/ STATICvoid
xfs_btree_shift_recs( struct xfs_btree_cur *cur, union xfs_btree_rec *rec, int dir, int numrecs)
{ char *dst_rec;
ASSERT(numrecs >= 0);
ASSERT(dir == 1 || dir == -1);
/* * Shift block pointers one index left/right inside a single btree block.
*/ STATICvoid
xfs_btree_shift_ptrs( struct xfs_btree_cur *cur, union xfs_btree_ptr *ptr, int dir, int numptrs)
{ char *dst_ptr;
ASSERT(numptrs >= 0);
ASSERT(dir == 1 || dir == -1);
/* * Log block pointer fields from a btree block (nonleaf).
*/ STATICvoid
xfs_btree_log_ptrs( struct xfs_btree_cur *cur, /* btree cursor */ struct xfs_buf *bp, /* buffer containing btree block */ int first, /* index of first pointer to log */ int last) /* index of last pointer to log */
{
if (bp) { struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); int level = xfs_btree_get_level(block);
if (xfs_has_crc(cur->bc_mp)) { /* * We don't log the CRC when updating a btree * block but instead recreate it during log * recovery. As the log buffers have checksums * of their own this is safe and avoids logging a crc * update in a lot of places.
*/ if (fields == XFS_BB_ALL_BITS)
fields = XFS_BB_ALL_BITS_CRC;
nbits = XFS_BB_NUM_BITS_CRC;
} else {
nbits = XFS_BB_NUM_BITS;
}
xfs_btree_offsets(fields,
(cur->bc_ops->ptr_len == XFS_BTREE_LONG_PTR_LEN) ?
loffsets : soffsets,
nbits, &first, &last);
xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);
xfs_trans_log_buf(cur->bc_tp, bp, first, last);
} else {
xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip,
xfs_ilog_fbroot(cur->bc_ino.whichfork));
}
}
/* * Increment cursor by one record at the level. * For nonzero levels the leaf-ward information is untouched.
*/ int/* error */
xfs_btree_increment( struct xfs_btree_cur *cur, int level, int *stat) /* success/failure */
{ struct xfs_btree_block *block; union xfs_btree_ptr ptr; struct xfs_buf *bp; int error; /* error return value */ int lev;
ASSERT(level < cur->bc_nlevels);
/* Read-ahead to the right at this level. */
xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
/* Get a pointer to the btree block. */
block = xfs_btree_get_block(cur, level, &bp);
/* We're done if we remain in the block after the increment. */ if (++cur->bc_levels[level].ptr <= xfs_btree_get_numrecs(block)) goto out1;
/* Fail if we just went off the right edge of the tree. */
xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); if (xfs_btree_ptr_is_null(cur, &ptr)) goto out0;
XFS_BTREE_STATS_INC(cur, increment);
/* * March up the tree incrementing pointers. * Stop when we don't go off the right edge of a block.
*/ for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
block = xfs_btree_get_block(cur, lev, &bp);
#ifdef DEBUG
error = xfs_btree_check_block(cur, block, lev, bp); if (error) goto error0; #endif
if (++cur->bc_levels[lev].ptr <= xfs_btree_get_numrecs(block)) break;
/* Read-ahead the right block for the next loop. */
xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA);
}
/* * If we went off the root then we are either seriously * confused or have the tree root in an inode.
*/ if (lev == cur->bc_nlevels) { if (cur->bc_ops->type == XFS_BTREE_TYPE_INODE) goto out0;
ASSERT(0);
xfs_btree_mark_sick(cur);
error = -EFSCORRUPTED; goto error0;
}
ASSERT(lev < cur->bc_nlevels);
/* * Now walk back down the tree, fixing up the cursor's buffer * pointers and key numbers.
*/ for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) { union xfs_btree_ptr *ptrp;
/* * Decrement cursor by one record at the level. * For nonzero levels the leaf-ward information is untouched.
*/ int/* error */
xfs_btree_decrement( struct xfs_btree_cur *cur, int level, int *stat) /* success/failure */
{ struct xfs_btree_block *block; struct xfs_buf *bp; int error; /* error return value */ int lev; union xfs_btree_ptr ptr;
ASSERT(level < cur->bc_nlevels);
/* Read-ahead to the left at this level. */
xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA);
/* We're done if we remain in the block after the decrement. */ if (--cur->bc_levels[level].ptr > 0) goto out1;
/* Get a pointer to the btree block. */
block = xfs_btree_get_block(cur, level, &bp);
/* Fail if we just went off the left edge of the tree. */
xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB); if (xfs_btree_ptr_is_null(cur, &ptr)) goto out0;
XFS_BTREE_STATS_INC(cur, decrement);
/* * March up the tree decrementing pointers. * Stop when we don't go off the left edge of a block.
*/ for (lev = level + 1; lev < cur->bc_nlevels; lev++) { if (--cur->bc_levels[lev].ptr > 0) break; /* Read-ahead the left block for the next loop. */
xfs_btree_readahead(cur, lev, XFS_BTCUR_LEFTRA);
}
/* * If we went off the root then we are seriously confused. * or the root of the tree is in an inode.
*/ if (lev == cur->bc_nlevels) { if (cur->bc_ops->type == XFS_BTREE_TYPE_INODE) goto out0;
ASSERT(0);
xfs_btree_mark_sick(cur);
error = -EFSCORRUPTED; goto error0;
}
ASSERT(lev < cur->bc_nlevels);
/* * Now walk back down the tree, fixing up the cursor's buffer * pointers and key numbers.
*/ for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) { union xfs_btree_ptr *ptrp;
/* * Check the btree block owner now that we have the context to know who the * real owner is.
*/ staticinline xfs_failaddr_t
xfs_btree_check_block_owner( struct xfs_btree_cur *cur, struct xfs_btree_block *block)
{
__u64 owner;
if (!xfs_has_crc(cur->bc_mp) ||
(cur->bc_flags & XFS_BTREE_BMBT_INVALID_OWNER)) return NULL;
owner = xfs_btree_owner(cur); if (cur->bc_ops->ptr_len == XFS_BTREE_LONG_PTR_LEN) { if (be64_to_cpu(block->bb_u.l.bb_owner) != owner) return __this_address;
} else { if (be32_to_cpu(block->bb_u.s.bb_owner) != owner) return __this_address;
}
return NULL;
}
int
xfs_btree_lookup_get_block( struct xfs_btree_cur *cur, /* btree cursor */ int level, /* level in the btree */ constunion xfs_btree_ptr *pp, /* ptr to btree block */ struct xfs_btree_block **blkp) /* return btree block */
{ struct xfs_buf *bp; /* buffer pointer for btree block */
xfs_daddr_t daddr; int error = 0;
/* special case the root block if in an inode */ if (xfs_btree_at_iroot(cur, level)) {
*blkp = xfs_btree_get_iroot(cur); return 0;
}
/* * If the old buffer at this level for the disk address we are * looking for re-use it. * * Otherwise throw it away and get a new one.
*/
bp = cur->bc_levels[level].bp;
error = xfs_btree_ptr_to_daddr(cur, pp, &daddr); if (error) return error; if (bp && xfs_buf_daddr(bp) == daddr) {
*blkp = XFS_BUF_TO_BLOCK(bp); return 0;
}
/* * Get current search key. For level 0 we don't actually have a key * structure so we make one up from the record. For all other levels * we just return the right key.
*/ STATICunion xfs_btree_key *
xfs_lookup_get_search_key( struct xfs_btree_cur *cur, int level, int keyno, struct xfs_btree_block *block, union xfs_btree_key *kp)
{ if (level == 0) {
cur->bc_ops->init_key_from_rec(kp,
xfs_btree_rec_addr(cur, keyno, block)); return kp;
}
return xfs_btree_key_addr(cur, keyno, block);
}
/* * Initialize a pointer to the root block.
*/ void
xfs_btree_init_ptr_from_cur( struct xfs_btree_cur *cur, union xfs_btree_ptr *ptr)
{ if (cur->bc_ops->type == XFS_BTREE_TYPE_INODE) { /* * Inode-rooted btrees call xfs_btree_get_iroot to find the root * in xfs_btree_lookup_get_block and don't need a pointer here.
*/
ptr->l = 0;
} elseif (cur->bc_flags & XFS_BTREE_STAGING) {
ptr->s = cpu_to_be32(cur->bc_ag.afake->af_root);
} else {
cur->bc_ops->init_ptr_from_cur(cur, ptr);
}
}
/* * Lookup the record. The cursor is made to point to it, based on dir. * stat is set to 0 if can't find any such record, 1 for success.
*/ int/* error */
xfs_btree_lookup( struct xfs_btree_cur *cur, /* btree cursor */
xfs_lookup_t dir, /* <=, ==, or >= */ int *stat) /* success/failure */
{ struct xfs_btree_block *block; /* current btree block */ int cmp_r; /* current key comparison result */ int error; /* error return value */ int keyno; /* current key number */ int level; /* level in the btree */ union xfs_btree_ptr *pp; /* ptr to btree block */ union xfs_btree_ptr ptr; /* ptr to btree block */
XFS_BTREE_STATS_INC(cur, lookup);
/* No such thing as a zero-level tree. */ if (XFS_IS_CORRUPT(cur->bc_mp, cur->bc_nlevels == 0)) {
xfs_btree_mark_sick(cur); return -EFSCORRUPTED;
}
/* * Iterate over each level in the btree, starting at the root. * For each level above the leaves, find the key we need, based * on the lookup record, then follow the corresponding block * pointer down to the next level.
*/ for (level = cur->bc_nlevels - 1, cmp_r = 1; level >= 0; level--) { /* Get the block we need to do the lookup on. */
error = xfs_btree_lookup_get_block(cur, level, pp, &block); if (error) goto error0;
if (cmp_r == 0) { /* * If we already had a key match at a higher level, we * know we need to use the first entry in this block.
*/
keyno = 1;
} else { /* Otherwise search this block. Do a binary search. */
int high; /* high entry number */ int low; /* low entry number */
/* Set low and high entry numbers, 1-based. */
low = 1;
high = xfs_btree_get_numrecs(block); if (!high) { /* Block is empty, must be an empty leaf. */ if (level != 0 || cur->bc_nlevels != 1) {
XFS_CORRUPTION_ERROR(__func__,
XFS_ERRLEVEL_LOW,
cur->bc_mp, block, sizeof(*block));
xfs_btree_mark_sick(cur); return -EFSCORRUPTED;
}
/* Binary search the block. */ while (low <= high) { union xfs_btree_key key; union xfs_btree_key *kp;
XFS_BTREE_STATS_INC(cur, compare);
/* keyno is average of low and high. */
keyno = (low + high) >> 1;
/* Get current search key */
kp = xfs_lookup_get_search_key(cur, level,
keyno, block, &key);
/* * Compute comparison result to get next * direction: * - less than, move right * - greater than, move left * - equal, we're done
*/
cmp_r = cur->bc_ops->cmp_key_with_cur(cur, kp); if (cmp_r < 0)
low = keyno + 1; elseif (cmp_r > 0)
high = keyno - 1; else break;
}
}
/* * If there are more levels, set up for the next level * by getting the block number and filling in the cursor.
*/ if (level > 0) { /* * If we moved left, need the previous key number, * unless there isn't one.
*/ if (cmp_r > 0 && --keyno < 1)
keyno = 1;
pp = xfs_btree_ptr_addr(cur, keyno, block);
error = xfs_btree_debug_check_ptr(cur, pp, 0, level); if (error) goto error0;
cur->bc_levels[level].ptr = keyno;
}
}
/* Done with the search. See if we need to adjust the results. */ if (dir != XFS_LOOKUP_LE && cmp_r < 0) {
keyno++; /* * If ge search and we went off the end of the block, but it's * not the last block, we're in the wrong block.
*/
xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB); if (dir == XFS_LOOKUP_GE &&
keyno > xfs_btree_get_numrecs(block) &&
!xfs_btree_ptr_is_null(cur, &ptr)) { int i;
/* Return if we succeeded or not. */ if (keyno == 0 || keyno > xfs_btree_get_numrecs(block))
*stat = 0; elseif (dir != XFS_LOOKUP_EQ || cmp_r == 0)
*stat = 1; else
*stat = 0; return 0;
error0: return error;
}
/* Find the high key storage area from a regular key. */ union xfs_btree_key *
xfs_btree_high_key_from_key( struct xfs_btree_cur *cur, union xfs_btree_key *key)
{
ASSERT(cur->bc_ops->geom_flags & XFS_BTGEO_OVERLAPPING); return (union xfs_btree_key *)((char *)key +
(cur->bc_ops->key_len / 2));
}
/* Determine the low (and high if overlapped) keys of a leaf block */ STATICvoid
xfs_btree_get_leaf_keys( struct xfs_btree_cur *cur, struct xfs_btree_block *block, union xfs_btree_key *key)
{ union xfs_btree_key max_hkey; union xfs_btree_key hkey; union xfs_btree_rec *rec; union xfs_btree_key *high; int n;
/* Determine the low (and high if overlapped) keys of a node block */ STATICvoid
xfs_btree_get_node_keys( struct xfs_btree_cur *cur, struct xfs_btree_block *block, union xfs_btree_key *key)
{ union xfs_btree_key *hkey; union xfs_btree_key *max_hkey; union xfs_btree_key *high; int n;
/* Derive the keys for any btree block. */ void
xfs_btree_get_keys( struct xfs_btree_cur *cur, struct xfs_btree_block *block, union xfs_btree_key *key)
{ if (be16_to_cpu(block->bb_level) == 0)
xfs_btree_get_leaf_keys(cur, block, key); else
xfs_btree_get_node_keys(cur, block, key);
}
/* * Decide if we need to update the parent keys of a btree block. For * a standard btree this is only necessary if we're updating the first * record/key. For an overlapping btree, we must always update the * keys because the highest key can be in any of the records or keys * in the block.
*/ staticinlinebool
xfs_btree_needs_key_update( struct xfs_btree_cur *cur, int ptr)
{ return (cur->bc_ops->geom_flags & XFS_BTGEO_OVERLAPPING) || ptr == 1;
}
/* * Update the low and high parent keys of the given level, progressing * towards the root. If force_all is false, stop if the keys for a given * level do not need updating.
*/ STATICint
__xfs_btree_updkeys( struct xfs_btree_cur *cur, int level, struct xfs_btree_block *block, struct xfs_buf *bp0, bool force_all)
{ union xfs_btree_key key; /* keys from current level */ union xfs_btree_key *lkey; /* keys from the next level up */ union xfs_btree_key *hkey; union xfs_btree_key *nlkey; /* keys from the next level up */ union xfs_btree_key *nhkey; struct xfs_buf *bp; int ptr;
/* Update all the keys from some level in cursor back to the root. */ STATICint
xfs_btree_updkeys_force( struct xfs_btree_cur *cur, int level)
{ struct xfs_buf *bp; struct xfs_btree_block *block;
/* * Update the parent keys of the given level, progressing towards the root.
*/ STATICint
xfs_btree_update_keys( struct xfs_btree_cur *cur, int level)
{ struct xfs_btree_block *block; struct xfs_buf *bp; union xfs_btree_key *kp; union xfs_btree_key key; int ptr;
/* * Go up the tree from this level toward the root. * At each level, update the key value to the value input. * Stop when we reach a level where the cursor isn't pointing * at the first entry in the block.
*/
xfs_btree_get_keys(cur, block, &key); for (level++, ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) { #ifdef DEBUG int error; #endif
block = xfs_btree_get_block(cur, level, &bp); #ifdef DEBUG
error = xfs_btree_check_block(cur, block, level, bp); if (error) return error; #endif
ptr = cur->bc_levels[level].ptr;
kp = xfs_btree_key_addr(cur, ptr, block);
xfs_btree_copy_keys(cur, kp, &key, 1);
xfs_btree_log_keys(cur, bp, ptr, ptr);
}
return 0;
}
/* * Update the record referred to by cur to the value in the * given record. This either works (return 0) or gets an * EFSCORRUPTED error.
*/ int
xfs_btree_update( struct xfs_btree_cur *cur, union xfs_btree_rec *rec)
{ struct xfs_btree_block *block; struct xfs_buf *bp; int error; int ptr; union xfs_btree_rec *rp;
/* Pick up the current block. */
block = xfs_btree_get_block(cur, 0, &bp);
#ifdef DEBUG
error = xfs_btree_check_block(cur, block, 0, bp); if (error) goto error0; #endif /* Get the address of the rec to be updated. */
ptr = cur->bc_levels[0].ptr;
rp = xfs_btree_rec_addr(cur, ptr, block);
/* Fill in the new contents and log them. */
xfs_btree_copy_recs(cur, rp, rec, 1);
xfs_btree_log_recs(cur, bp, ptr, ptr);
/* Pass new key value up to our parent. */ if (xfs_btree_needs_key_update(cur, ptr)) {
error = xfs_btree_update_keys(cur, 0); if (error) goto error0;
}
return 0;
error0: return error;
}
/* * Move 1 record left from cur/level if possible. * Update cur to reflect the new path.
*/ STATICint/* error */
xfs_btree_lshift( struct xfs_btree_cur *cur, int level, int *stat) /* success/failure */
{ struct xfs_buf *lbp; /* left buffer pointer */ struct xfs_btree_block *left; /* left btree block */ int lrecs; /* left record count */ struct xfs_buf *rbp; /* right buffer pointer */ struct xfs_btree_block *right; /* right btree block */ struct xfs_btree_cur *tcur; /* temporary btree cursor */ int rrecs; /* right record count */ union xfs_btree_ptr lptr; /* left btree pointer */ union xfs_btree_key *rkp = NULL; /* right btree key */ union xfs_btree_ptr *rpp = NULL; /* right address pointer */ union xfs_btree_rec *rrp = NULL; /* right record pointer */ int error; /* error return value */ int i;
if (xfs_btree_at_iroot(cur, level)) goto out0;
/* Set up variables for this block as "right". */
right = xfs_btree_get_block(cur, level, &rbp);
/* If we've got no left sibling then we can't shift an entry left. */
xfs_btree_get_sibling(cur, right, &lptr, XFS_BB_LEFTSIB); if (xfs_btree_ptr_is_null(cur, &lptr)) goto out0;
/* * If the cursor entry is the one that would be moved, don't * do it... it's too complicated.
*/ if (cur->bc_levels[level].ptr <= 1) goto out0;
/* Set up the left neighbor as "left". */
error = xfs_btree_read_buf_block(cur, &lptr, 0, &left, &lbp); if (error) goto error0;
/* If it's full, it can't take another entry. */
lrecs = xfs_btree_get_numrecs(left); if (lrecs == cur->bc_ops->get_maxrecs(cur, level)) goto out0;
rrecs = xfs_btree_get_numrecs(right);
/* * We add one entry to the left side and remove one for the right side. * Account for it here, the changes will be updated on disk and logged * later.
*/
lrecs++;
rrecs--;
/* * If non-leaf, copy a key and a ptr to the left block. * Log the changes to the left block.
*/ if (level > 0) { /* It's a non-leaf. Move keys and pointers. */ union xfs_btree_key *lkp; /* left btree key */ union xfs_btree_ptr *lpp; /* left address pointer */
lkp = xfs_btree_key_addr(cur, lrecs, left);
rkp = xfs_btree_key_addr(cur, 1, right);
ASSERT(cur->bc_ops->keys_inorder(cur,
xfs_btree_key_addr(cur, lrecs - 1, left), lkp));
} else { /* It's a leaf. Move records. */ union xfs_btree_rec *lrp; /* left record pointer */
/* * Slide the contents of right down one entry.
*/
XFS_BTREE_STATS_ADD(cur, moves, rrecs - 1); if (level > 0) { /* It's a nonleaf. operate on keys and ptrs */ for (i = 0; i < rrecs; i++) {
error = xfs_btree_debug_check_ptr(cur, rpp, i + 1, level); if (error) goto error0;
}
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.
