130f712c9SDave Chinner /* 230f712c9SDave Chinner * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc. 330f712c9SDave Chinner * All Rights Reserved. 430f712c9SDave Chinner * 530f712c9SDave Chinner * This program is free software; you can redistribute it and/or 630f712c9SDave Chinner * modify it under the terms of the GNU General Public License as 730f712c9SDave Chinner * published by the Free Software Foundation. 830f712c9SDave Chinner * 930f712c9SDave Chinner * This program is distributed in the hope that it would be useful, 1030f712c9SDave Chinner * but WITHOUT ANY WARRANTY; without even the implied warranty of 1130f712c9SDave Chinner * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1230f712c9SDave Chinner * GNU General Public License for more details. 1330f712c9SDave Chinner * 1430f712c9SDave Chinner * You should have received a copy of the GNU General Public License 1530f712c9SDave Chinner * along with this program; if not, write the Free Software Foundation, 1630f712c9SDave Chinner * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 1730f712c9SDave Chinner */ 1830f712c9SDave Chinner #include "xfs.h" 1930f712c9SDave Chinner #include "xfs_fs.h" 2030f712c9SDave Chinner #include "xfs_shared.h" 2130f712c9SDave Chinner #include "xfs_format.h" 2230f712c9SDave Chinner #include "xfs_log_format.h" 2330f712c9SDave Chinner #include "xfs_trans_resv.h" 2430f712c9SDave Chinner #include "xfs_bit.h" 2530f712c9SDave Chinner #include "xfs_mount.h" 2630f712c9SDave Chinner #include "xfs_inode.h" 2730f712c9SDave Chinner #include "xfs_btree.h" 2830f712c9SDave Chinner #include "xfs_ialloc.h" 2930f712c9SDave Chinner #include "xfs_ialloc_btree.h" 3030f712c9SDave Chinner #include "xfs_alloc.h" 3130f712c9SDave Chinner #include "xfs_error.h" 3230f712c9SDave Chinner #include "xfs_trace.h" 3330f712c9SDave Chinner #include "xfs_cksum.h" 3430f712c9SDave Chinner #include "xfs_trans.h" 3530f712c9SDave Chinner 3630f712c9SDave Chinner 3730f712c9SDave Chinner STATIC int 3830f712c9SDave Chinner xfs_inobt_get_minrecs( 3930f712c9SDave Chinner struct xfs_btree_cur *cur, 4030f712c9SDave Chinner int level) 4130f712c9SDave Chinner { 4230f712c9SDave Chinner return cur->bc_mp->m_inobt_mnr[level != 0]; 4330f712c9SDave Chinner } 4430f712c9SDave Chinner 4530f712c9SDave Chinner STATIC struct xfs_btree_cur * 4630f712c9SDave Chinner xfs_inobt_dup_cursor( 4730f712c9SDave Chinner struct xfs_btree_cur *cur) 4830f712c9SDave Chinner { 4930f712c9SDave Chinner return xfs_inobt_init_cursor(cur->bc_mp, cur->bc_tp, 5030f712c9SDave Chinner cur->bc_private.a.agbp, cur->bc_private.a.agno, 5130f712c9SDave Chinner cur->bc_btnum); 5230f712c9SDave Chinner } 5330f712c9SDave Chinner 5430f712c9SDave Chinner STATIC void 5530f712c9SDave Chinner xfs_inobt_set_root( 5630f712c9SDave Chinner struct xfs_btree_cur *cur, 5730f712c9SDave Chinner union xfs_btree_ptr *nptr, 5830f712c9SDave Chinner int inc) /* level change */ 5930f712c9SDave Chinner { 6030f712c9SDave Chinner struct xfs_buf *agbp = cur->bc_private.a.agbp; 6130f712c9SDave Chinner struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp); 6230f712c9SDave Chinner 6330f712c9SDave Chinner agi->agi_root = nptr->s; 6430f712c9SDave Chinner be32_add_cpu(&agi->agi_level, inc); 6530f712c9SDave Chinner xfs_ialloc_log_agi(cur->bc_tp, agbp, XFS_AGI_ROOT | XFS_AGI_LEVEL); 6630f712c9SDave Chinner } 6730f712c9SDave Chinner 6830f712c9SDave Chinner STATIC void 6930f712c9SDave Chinner xfs_finobt_set_root( 7030f712c9SDave Chinner struct xfs_btree_cur *cur, 7130f712c9SDave Chinner union xfs_btree_ptr *nptr, 7230f712c9SDave Chinner int inc) /* level change */ 7330f712c9SDave Chinner { 7430f712c9SDave Chinner struct xfs_buf *agbp = cur->bc_private.a.agbp; 7530f712c9SDave Chinner struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp); 7630f712c9SDave Chinner 7730f712c9SDave Chinner agi->agi_free_root = nptr->s; 7830f712c9SDave Chinner be32_add_cpu(&agi->agi_free_level, inc); 7930f712c9SDave Chinner xfs_ialloc_log_agi(cur->bc_tp, agbp, 8030f712c9SDave Chinner XFS_AGI_FREE_ROOT | XFS_AGI_FREE_LEVEL); 8130f712c9SDave Chinner } 8230f712c9SDave Chinner 8330f712c9SDave Chinner STATIC int 8430f712c9SDave Chinner xfs_inobt_alloc_block( 8530f712c9SDave Chinner struct xfs_btree_cur *cur, 8630f712c9SDave Chinner union xfs_btree_ptr *start, 8730f712c9SDave Chinner union xfs_btree_ptr *new, 8830f712c9SDave Chinner int *stat) 8930f712c9SDave Chinner { 9030f712c9SDave Chinner xfs_alloc_arg_t args; /* block allocation args */ 9130f712c9SDave Chinner int error; /* error return value */ 9230f712c9SDave Chinner xfs_agblock_t sbno = be32_to_cpu(start->s); 9330f712c9SDave Chinner 9430f712c9SDave Chinner XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 9530f712c9SDave Chinner 9630f712c9SDave Chinner memset(&args, 0, sizeof(args)); 9730f712c9SDave Chinner args.tp = cur->bc_tp; 9830f712c9SDave Chinner args.mp = cur->bc_mp; 9930f712c9SDave Chinner args.fsbno = XFS_AGB_TO_FSB(args.mp, cur->bc_private.a.agno, sbno); 10030f712c9SDave Chinner args.minlen = 1; 10130f712c9SDave Chinner args.maxlen = 1; 10230f712c9SDave Chinner args.prod = 1; 10330f712c9SDave Chinner args.type = XFS_ALLOCTYPE_NEAR_BNO; 10430f712c9SDave Chinner 10530f712c9SDave Chinner error = xfs_alloc_vextent(&args); 10630f712c9SDave Chinner if (error) { 10730f712c9SDave Chinner XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 10830f712c9SDave Chinner return error; 10930f712c9SDave Chinner } 11030f712c9SDave Chinner if (args.fsbno == NULLFSBLOCK) { 11130f712c9SDave Chinner XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 11230f712c9SDave Chinner *stat = 0; 11330f712c9SDave Chinner return 0; 11430f712c9SDave Chinner } 11530f712c9SDave Chinner ASSERT(args.len == 1); 11630f712c9SDave Chinner XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 11730f712c9SDave Chinner 11830f712c9SDave Chinner new->s = cpu_to_be32(XFS_FSB_TO_AGBNO(args.mp, args.fsbno)); 11930f712c9SDave Chinner *stat = 1; 12030f712c9SDave Chinner return 0; 12130f712c9SDave Chinner } 12230f712c9SDave Chinner 12330f712c9SDave Chinner STATIC int 12430f712c9SDave Chinner xfs_inobt_free_block( 12530f712c9SDave Chinner struct xfs_btree_cur *cur, 12630f712c9SDave Chinner struct xfs_buf *bp) 12730f712c9SDave Chinner { 12830f712c9SDave Chinner xfs_fsblock_t fsbno; 12930f712c9SDave Chinner int error; 13030f712c9SDave Chinner 13130f712c9SDave Chinner fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, XFS_BUF_ADDR(bp)); 13230f712c9SDave Chinner error = xfs_free_extent(cur->bc_tp, fsbno, 1); 13330f712c9SDave Chinner if (error) 13430f712c9SDave Chinner return error; 13530f712c9SDave Chinner 13630f712c9SDave Chinner xfs_trans_binval(cur->bc_tp, bp); 13730f712c9SDave Chinner return error; 13830f712c9SDave Chinner } 13930f712c9SDave Chinner 14030f712c9SDave Chinner STATIC int 14130f712c9SDave Chinner xfs_inobt_get_maxrecs( 14230f712c9SDave Chinner struct xfs_btree_cur *cur, 14330f712c9SDave Chinner int level) 14430f712c9SDave Chinner { 14530f712c9SDave Chinner return cur->bc_mp->m_inobt_mxr[level != 0]; 14630f712c9SDave Chinner } 14730f712c9SDave Chinner 14830f712c9SDave Chinner STATIC void 14930f712c9SDave Chinner xfs_inobt_init_key_from_rec( 15030f712c9SDave Chinner union xfs_btree_key *key, 15130f712c9SDave Chinner union xfs_btree_rec *rec) 15230f712c9SDave Chinner { 15330f712c9SDave Chinner key->inobt.ir_startino = rec->inobt.ir_startino; 15430f712c9SDave Chinner } 15530f712c9SDave Chinner 15630f712c9SDave Chinner STATIC void 15730f712c9SDave Chinner xfs_inobt_init_rec_from_key( 15830f712c9SDave Chinner union xfs_btree_key *key, 15930f712c9SDave Chinner union xfs_btree_rec *rec) 16030f712c9SDave Chinner { 16130f712c9SDave Chinner rec->inobt.ir_startino = key->inobt.ir_startino; 16230f712c9SDave Chinner } 16330f712c9SDave Chinner 16430f712c9SDave Chinner STATIC void 16530f712c9SDave Chinner xfs_inobt_init_rec_from_cur( 16630f712c9SDave Chinner struct xfs_btree_cur *cur, 16730f712c9SDave Chinner union xfs_btree_rec *rec) 16830f712c9SDave Chinner { 16930f712c9SDave Chinner rec->inobt.ir_startino = cpu_to_be32(cur->bc_rec.i.ir_startino); 1705419040fSBrian Foster if (xfs_sb_version_hassparseinodes(&cur->bc_mp->m_sb)) { 1715419040fSBrian Foster rec->inobt.ir_u.sp.ir_holemask = 1725419040fSBrian Foster cpu_to_be16(cur->bc_rec.i.ir_holemask); 1735419040fSBrian Foster rec->inobt.ir_u.sp.ir_count = cur->bc_rec.i.ir_count; 1745419040fSBrian Foster rec->inobt.ir_u.sp.ir_freecount = cur->bc_rec.i.ir_freecount; 1755419040fSBrian Foster } else { 1765419040fSBrian Foster /* ir_holemask/ir_count not supported on-disk */ 1775419040fSBrian Foster rec->inobt.ir_u.f.ir_freecount = 1785419040fSBrian Foster cpu_to_be32(cur->bc_rec.i.ir_freecount); 1795419040fSBrian Foster } 18030f712c9SDave Chinner rec->inobt.ir_free = cpu_to_be64(cur->bc_rec.i.ir_free); 18130f712c9SDave Chinner } 18230f712c9SDave Chinner 18330f712c9SDave Chinner /* 18430f712c9SDave Chinner * initial value of ptr for lookup 18530f712c9SDave Chinner */ 18630f712c9SDave Chinner STATIC void 18730f712c9SDave Chinner xfs_inobt_init_ptr_from_cur( 18830f712c9SDave Chinner struct xfs_btree_cur *cur, 18930f712c9SDave Chinner union xfs_btree_ptr *ptr) 19030f712c9SDave Chinner { 19130f712c9SDave Chinner struct xfs_agi *agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp); 19230f712c9SDave Chinner 19330f712c9SDave Chinner ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno)); 19430f712c9SDave Chinner 19530f712c9SDave Chinner ptr->s = agi->agi_root; 19630f712c9SDave Chinner } 19730f712c9SDave Chinner 19830f712c9SDave Chinner STATIC void 19930f712c9SDave Chinner xfs_finobt_init_ptr_from_cur( 20030f712c9SDave Chinner struct xfs_btree_cur *cur, 20130f712c9SDave Chinner union xfs_btree_ptr *ptr) 20230f712c9SDave Chinner { 20330f712c9SDave Chinner struct xfs_agi *agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp); 20430f712c9SDave Chinner 20530f712c9SDave Chinner ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno)); 20630f712c9SDave Chinner ptr->s = agi->agi_free_root; 20730f712c9SDave Chinner } 20830f712c9SDave Chinner 20930f712c9SDave Chinner STATIC __int64_t 21030f712c9SDave Chinner xfs_inobt_key_diff( 21130f712c9SDave Chinner struct xfs_btree_cur *cur, 21230f712c9SDave Chinner union xfs_btree_key *key) 21330f712c9SDave Chinner { 21430f712c9SDave Chinner return (__int64_t)be32_to_cpu(key->inobt.ir_startino) - 21530f712c9SDave Chinner cur->bc_rec.i.ir_startino; 21630f712c9SDave Chinner } 21730f712c9SDave Chinner 21830f712c9SDave Chinner static int 21930f712c9SDave Chinner xfs_inobt_verify( 22030f712c9SDave Chinner struct xfs_buf *bp) 22130f712c9SDave Chinner { 22230f712c9SDave Chinner struct xfs_mount *mp = bp->b_target->bt_mount; 22330f712c9SDave Chinner struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); 22430f712c9SDave Chinner struct xfs_perag *pag = bp->b_pag; 22530f712c9SDave Chinner unsigned int level; 22630f712c9SDave Chinner 22730f712c9SDave Chinner /* 22830f712c9SDave Chinner * During growfs operations, we can't verify the exact owner as the 22930f712c9SDave Chinner * perag is not fully initialised and hence not attached to the buffer. 23030f712c9SDave Chinner * 23130f712c9SDave Chinner * Similarly, during log recovery we will have a perag structure 23230f712c9SDave Chinner * attached, but the agi information will not yet have been initialised 23330f712c9SDave Chinner * from the on disk AGI. We don't currently use any of this information, 23430f712c9SDave Chinner * but beware of the landmine (i.e. need to check pag->pagi_init) if we 23530f712c9SDave Chinner * ever do. 23630f712c9SDave Chinner */ 23730f712c9SDave Chinner switch (block->bb_magic) { 23830f712c9SDave Chinner case cpu_to_be32(XFS_IBT_CRC_MAGIC): 23930f712c9SDave Chinner case cpu_to_be32(XFS_FIBT_CRC_MAGIC): 24030f712c9SDave Chinner if (!xfs_sb_version_hascrc(&mp->m_sb)) 24130f712c9SDave Chinner return false; 242ce748eaaSEric Sandeen if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid)) 24330f712c9SDave Chinner return false; 24430f712c9SDave Chinner if (block->bb_u.s.bb_blkno != cpu_to_be64(bp->b_bn)) 24530f712c9SDave Chinner return false; 24630f712c9SDave Chinner if (pag && 24730f712c9SDave Chinner be32_to_cpu(block->bb_u.s.bb_owner) != pag->pag_agno) 24830f712c9SDave Chinner return false; 24930f712c9SDave Chinner /* fall through */ 25030f712c9SDave Chinner case cpu_to_be32(XFS_IBT_MAGIC): 25130f712c9SDave Chinner case cpu_to_be32(XFS_FIBT_MAGIC): 25230f712c9SDave Chinner break; 25330f712c9SDave Chinner default: 25430f712c9SDave Chinner return 0; 25530f712c9SDave Chinner } 25630f712c9SDave Chinner 25730f712c9SDave Chinner /* numrecs and level verification */ 25830f712c9SDave Chinner level = be16_to_cpu(block->bb_level); 25930f712c9SDave Chinner if (level >= mp->m_in_maxlevels) 26030f712c9SDave Chinner return false; 26130f712c9SDave Chinner if (be16_to_cpu(block->bb_numrecs) > mp->m_inobt_mxr[level != 0]) 26230f712c9SDave Chinner return false; 26330f712c9SDave Chinner 26430f712c9SDave Chinner /* sibling pointer verification */ 26530f712c9SDave Chinner if (!block->bb_u.s.bb_leftsib || 26630f712c9SDave Chinner (be32_to_cpu(block->bb_u.s.bb_leftsib) >= mp->m_sb.sb_agblocks && 26730f712c9SDave Chinner block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK))) 26830f712c9SDave Chinner return false; 26930f712c9SDave Chinner if (!block->bb_u.s.bb_rightsib || 27030f712c9SDave Chinner (be32_to_cpu(block->bb_u.s.bb_rightsib) >= mp->m_sb.sb_agblocks && 27130f712c9SDave Chinner block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK))) 27230f712c9SDave Chinner return false; 27330f712c9SDave Chinner 27430f712c9SDave Chinner return true; 27530f712c9SDave Chinner } 27630f712c9SDave Chinner 27730f712c9SDave Chinner static void 27830f712c9SDave Chinner xfs_inobt_read_verify( 27930f712c9SDave Chinner struct xfs_buf *bp) 28030f712c9SDave Chinner { 28130f712c9SDave Chinner if (!xfs_btree_sblock_verify_crc(bp)) 2822451337dSDave Chinner xfs_buf_ioerror(bp, -EFSBADCRC); 28330f712c9SDave Chinner else if (!xfs_inobt_verify(bp)) 2842451337dSDave Chinner xfs_buf_ioerror(bp, -EFSCORRUPTED); 28530f712c9SDave Chinner 28630f712c9SDave Chinner if (bp->b_error) { 28730f712c9SDave Chinner trace_xfs_btree_corrupt(bp, _RET_IP_); 28830f712c9SDave Chinner xfs_verifier_error(bp); 28930f712c9SDave Chinner } 29030f712c9SDave Chinner } 29130f712c9SDave Chinner 29230f712c9SDave Chinner static void 29330f712c9SDave Chinner xfs_inobt_write_verify( 29430f712c9SDave Chinner struct xfs_buf *bp) 29530f712c9SDave Chinner { 29630f712c9SDave Chinner if (!xfs_inobt_verify(bp)) { 29730f712c9SDave Chinner trace_xfs_btree_corrupt(bp, _RET_IP_); 2982451337dSDave Chinner xfs_buf_ioerror(bp, -EFSCORRUPTED); 29930f712c9SDave Chinner xfs_verifier_error(bp); 30030f712c9SDave Chinner return; 30130f712c9SDave Chinner } 30230f712c9SDave Chinner xfs_btree_sblock_calc_crc(bp); 30330f712c9SDave Chinner 30430f712c9SDave Chinner } 30530f712c9SDave Chinner 30630f712c9SDave Chinner const struct xfs_buf_ops xfs_inobt_buf_ops = { 307233135b7SEric Sandeen .name = "xfs_inobt", 30830f712c9SDave Chinner .verify_read = xfs_inobt_read_verify, 30930f712c9SDave Chinner .verify_write = xfs_inobt_write_verify, 31030f712c9SDave Chinner }; 31130f712c9SDave Chinner 31230f712c9SDave Chinner #if defined(DEBUG) || defined(XFS_WARN) 31330f712c9SDave Chinner STATIC int 31430f712c9SDave Chinner xfs_inobt_keys_inorder( 31530f712c9SDave Chinner struct xfs_btree_cur *cur, 31630f712c9SDave Chinner union xfs_btree_key *k1, 31730f712c9SDave Chinner union xfs_btree_key *k2) 31830f712c9SDave Chinner { 31930f712c9SDave Chinner return be32_to_cpu(k1->inobt.ir_startino) < 32030f712c9SDave Chinner be32_to_cpu(k2->inobt.ir_startino); 32130f712c9SDave Chinner } 32230f712c9SDave Chinner 32330f712c9SDave Chinner STATIC int 32430f712c9SDave Chinner xfs_inobt_recs_inorder( 32530f712c9SDave Chinner struct xfs_btree_cur *cur, 32630f712c9SDave Chinner union xfs_btree_rec *r1, 32730f712c9SDave Chinner union xfs_btree_rec *r2) 32830f712c9SDave Chinner { 32930f712c9SDave Chinner return be32_to_cpu(r1->inobt.ir_startino) + XFS_INODES_PER_CHUNK <= 33030f712c9SDave Chinner be32_to_cpu(r2->inobt.ir_startino); 33130f712c9SDave Chinner } 33230f712c9SDave Chinner #endif /* DEBUG */ 33330f712c9SDave Chinner 33430f712c9SDave Chinner static const struct xfs_btree_ops xfs_inobt_ops = { 33530f712c9SDave Chinner .rec_len = sizeof(xfs_inobt_rec_t), 33630f712c9SDave Chinner .key_len = sizeof(xfs_inobt_key_t), 33730f712c9SDave Chinner 33830f712c9SDave Chinner .dup_cursor = xfs_inobt_dup_cursor, 33930f712c9SDave Chinner .set_root = xfs_inobt_set_root, 34030f712c9SDave Chinner .alloc_block = xfs_inobt_alloc_block, 34130f712c9SDave Chinner .free_block = xfs_inobt_free_block, 34230f712c9SDave Chinner .get_minrecs = xfs_inobt_get_minrecs, 34330f712c9SDave Chinner .get_maxrecs = xfs_inobt_get_maxrecs, 34430f712c9SDave Chinner .init_key_from_rec = xfs_inobt_init_key_from_rec, 34530f712c9SDave Chinner .init_rec_from_key = xfs_inobt_init_rec_from_key, 34630f712c9SDave Chinner .init_rec_from_cur = xfs_inobt_init_rec_from_cur, 34730f712c9SDave Chinner .init_ptr_from_cur = xfs_inobt_init_ptr_from_cur, 34830f712c9SDave Chinner .key_diff = xfs_inobt_key_diff, 34930f712c9SDave Chinner .buf_ops = &xfs_inobt_buf_ops, 35030f712c9SDave Chinner #if defined(DEBUG) || defined(XFS_WARN) 35130f712c9SDave Chinner .keys_inorder = xfs_inobt_keys_inorder, 35230f712c9SDave Chinner .recs_inorder = xfs_inobt_recs_inorder, 35330f712c9SDave Chinner #endif 35430f712c9SDave Chinner }; 35530f712c9SDave Chinner 35630f712c9SDave Chinner static const struct xfs_btree_ops xfs_finobt_ops = { 35730f712c9SDave Chinner .rec_len = sizeof(xfs_inobt_rec_t), 35830f712c9SDave Chinner .key_len = sizeof(xfs_inobt_key_t), 35930f712c9SDave Chinner 36030f712c9SDave Chinner .dup_cursor = xfs_inobt_dup_cursor, 36130f712c9SDave Chinner .set_root = xfs_finobt_set_root, 36230f712c9SDave Chinner .alloc_block = xfs_inobt_alloc_block, 36330f712c9SDave Chinner .free_block = xfs_inobt_free_block, 36430f712c9SDave Chinner .get_minrecs = xfs_inobt_get_minrecs, 36530f712c9SDave Chinner .get_maxrecs = xfs_inobt_get_maxrecs, 36630f712c9SDave Chinner .init_key_from_rec = xfs_inobt_init_key_from_rec, 36730f712c9SDave Chinner .init_rec_from_key = xfs_inobt_init_rec_from_key, 36830f712c9SDave Chinner .init_rec_from_cur = xfs_inobt_init_rec_from_cur, 36930f712c9SDave Chinner .init_ptr_from_cur = xfs_finobt_init_ptr_from_cur, 37030f712c9SDave Chinner .key_diff = xfs_inobt_key_diff, 37130f712c9SDave Chinner .buf_ops = &xfs_inobt_buf_ops, 37230f712c9SDave Chinner #if defined(DEBUG) || defined(XFS_WARN) 37330f712c9SDave Chinner .keys_inorder = xfs_inobt_keys_inorder, 37430f712c9SDave Chinner .recs_inorder = xfs_inobt_recs_inorder, 37530f712c9SDave Chinner #endif 37630f712c9SDave Chinner }; 37730f712c9SDave Chinner 37830f712c9SDave Chinner /* 37930f712c9SDave Chinner * Allocate a new inode btree cursor. 38030f712c9SDave Chinner */ 38130f712c9SDave Chinner struct xfs_btree_cur * /* new inode btree cursor */ 38230f712c9SDave Chinner xfs_inobt_init_cursor( 38330f712c9SDave Chinner struct xfs_mount *mp, /* file system mount point */ 38430f712c9SDave Chinner struct xfs_trans *tp, /* transaction pointer */ 38530f712c9SDave Chinner struct xfs_buf *agbp, /* buffer for agi structure */ 38630f712c9SDave Chinner xfs_agnumber_t agno, /* allocation group number */ 38730f712c9SDave Chinner xfs_btnum_t btnum) /* ialloc or free ino btree */ 38830f712c9SDave Chinner { 38930f712c9SDave Chinner struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp); 39030f712c9SDave Chinner struct xfs_btree_cur *cur; 39130f712c9SDave Chinner 39230f712c9SDave Chinner cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP); 39330f712c9SDave Chinner 39430f712c9SDave Chinner cur->bc_tp = tp; 39530f712c9SDave Chinner cur->bc_mp = mp; 39630f712c9SDave Chinner cur->bc_btnum = btnum; 39730f712c9SDave Chinner if (btnum == XFS_BTNUM_INO) { 39830f712c9SDave Chinner cur->bc_nlevels = be32_to_cpu(agi->agi_level); 39930f712c9SDave Chinner cur->bc_ops = &xfs_inobt_ops; 40030f712c9SDave Chinner } else { 40130f712c9SDave Chinner cur->bc_nlevels = be32_to_cpu(agi->agi_free_level); 40230f712c9SDave Chinner cur->bc_ops = &xfs_finobt_ops; 40330f712c9SDave Chinner } 40430f712c9SDave Chinner 40530f712c9SDave Chinner cur->bc_blocklog = mp->m_sb.sb_blocklog; 40630f712c9SDave Chinner 40730f712c9SDave Chinner if (xfs_sb_version_hascrc(&mp->m_sb)) 40830f712c9SDave Chinner cur->bc_flags |= XFS_BTREE_CRC_BLOCKS; 40930f712c9SDave Chinner 41030f712c9SDave Chinner cur->bc_private.a.agbp = agbp; 41130f712c9SDave Chinner cur->bc_private.a.agno = agno; 41230f712c9SDave Chinner 41330f712c9SDave Chinner return cur; 41430f712c9SDave Chinner } 41530f712c9SDave Chinner 41630f712c9SDave Chinner /* 41730f712c9SDave Chinner * Calculate number of records in an inobt btree block. 41830f712c9SDave Chinner */ 41930f712c9SDave Chinner int 42030f712c9SDave Chinner xfs_inobt_maxrecs( 42130f712c9SDave Chinner struct xfs_mount *mp, 42230f712c9SDave Chinner int blocklen, 42330f712c9SDave Chinner int leaf) 42430f712c9SDave Chinner { 42530f712c9SDave Chinner blocklen -= XFS_INOBT_BLOCK_LEN(mp); 42630f712c9SDave Chinner 42730f712c9SDave Chinner if (leaf) 42830f712c9SDave Chinner return blocklen / sizeof(xfs_inobt_rec_t); 42930f712c9SDave Chinner return blocklen / (sizeof(xfs_inobt_key_t) + sizeof(xfs_inobt_ptr_t)); 43030f712c9SDave Chinner } 4314148c347SBrian Foster 4324148c347SBrian Foster /* 4334148c347SBrian Foster * Convert the inode record holemask to an inode allocation bitmap. The inode 4344148c347SBrian Foster * allocation bitmap is inode granularity and specifies whether an inode is 4354148c347SBrian Foster * physically allocated on disk (not whether the inode is considered allocated 4364148c347SBrian Foster * or free by the fs). 4374148c347SBrian Foster * 4384148c347SBrian Foster * A bit value of 1 means the inode is allocated, a value of 0 means it is free. 4394148c347SBrian Foster */ 4404148c347SBrian Foster uint64_t 4414148c347SBrian Foster xfs_inobt_irec_to_allocmask( 4424148c347SBrian Foster struct xfs_inobt_rec_incore *rec) 4434148c347SBrian Foster { 4444148c347SBrian Foster uint64_t bitmap = 0; 4454148c347SBrian Foster uint64_t inodespbit; 4464148c347SBrian Foster int nextbit; 4474148c347SBrian Foster uint allocbitmap; 4484148c347SBrian Foster 4494148c347SBrian Foster /* 4504148c347SBrian Foster * The holemask has 16-bits for a 64 inode record. Therefore each 4514148c347SBrian Foster * holemask bit represents multiple inodes. Create a mask of bits to set 4524148c347SBrian Foster * in the allocmask for each holemask bit. 4534148c347SBrian Foster */ 4544148c347SBrian Foster inodespbit = (1 << XFS_INODES_PER_HOLEMASK_BIT) - 1; 4554148c347SBrian Foster 4564148c347SBrian Foster /* 4574148c347SBrian Foster * Allocated inodes are represented by 0 bits in holemask. Invert the 0 4584148c347SBrian Foster * bits to 1 and convert to a uint so we can use xfs_next_bit(). Mask 4594148c347SBrian Foster * anything beyond the 16 holemask bits since this casts to a larger 4604148c347SBrian Foster * type. 4614148c347SBrian Foster */ 4624148c347SBrian Foster allocbitmap = ~rec->ir_holemask & ((1 << XFS_INOBT_HOLEMASK_BITS) - 1); 4634148c347SBrian Foster 4644148c347SBrian Foster /* 4654148c347SBrian Foster * allocbitmap is the inverted holemask so every set bit represents 4664148c347SBrian Foster * allocated inodes. To expand from 16-bit holemask granularity to 4674148c347SBrian Foster * 64-bit (e.g., bit-per-inode), set inodespbit bits in the target 4684148c347SBrian Foster * bitmap for every holemask bit. 4694148c347SBrian Foster */ 4704148c347SBrian Foster nextbit = xfs_next_bit(&allocbitmap, 1, 0); 4714148c347SBrian Foster while (nextbit != -1) { 4724148c347SBrian Foster ASSERT(nextbit < (sizeof(rec->ir_holemask) * NBBY)); 4734148c347SBrian Foster 4744148c347SBrian Foster bitmap |= (inodespbit << 4754148c347SBrian Foster (nextbit * XFS_INODES_PER_HOLEMASK_BIT)); 4764148c347SBrian Foster 4774148c347SBrian Foster nextbit = xfs_next_bit(&allocbitmap, 1, nextbit + 1); 4784148c347SBrian Foster } 4794148c347SBrian Foster 4804148c347SBrian Foster return bitmap; 4814148c347SBrian Foster } 48256d1115cSBrian Foster 48356d1115cSBrian Foster #if defined(DEBUG) || defined(XFS_WARN) 48456d1115cSBrian Foster /* 48556d1115cSBrian Foster * Verify that an in-core inode record has a valid inode count. 48656d1115cSBrian Foster */ 48756d1115cSBrian Foster int 48856d1115cSBrian Foster xfs_inobt_rec_check_count( 48956d1115cSBrian Foster struct xfs_mount *mp, 49056d1115cSBrian Foster struct xfs_inobt_rec_incore *rec) 49156d1115cSBrian Foster { 49256d1115cSBrian Foster int inocount = 0; 49356d1115cSBrian Foster int nextbit = 0; 49456d1115cSBrian Foster uint64_t allocbmap; 49556d1115cSBrian Foster int wordsz; 49656d1115cSBrian Foster 49756d1115cSBrian Foster wordsz = sizeof(allocbmap) / sizeof(unsigned int); 49856d1115cSBrian Foster allocbmap = xfs_inobt_irec_to_allocmask(rec); 49956d1115cSBrian Foster 50056d1115cSBrian Foster nextbit = xfs_next_bit((uint *) &allocbmap, wordsz, nextbit); 50156d1115cSBrian Foster while (nextbit != -1) { 50256d1115cSBrian Foster inocount++; 50356d1115cSBrian Foster nextbit = xfs_next_bit((uint *) &allocbmap, wordsz, 50456d1115cSBrian Foster nextbit + 1); 50556d1115cSBrian Foster } 50656d1115cSBrian Foster 50756d1115cSBrian Foster if (inocount != rec->ir_count) 50856d1115cSBrian Foster return -EFSCORRUPTED; 50956d1115cSBrian Foster 51056d1115cSBrian Foster return 0; 51156d1115cSBrian Foster } 51256d1115cSBrian Foster #endif /* DEBUG */ 513