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" 35340785ccSDarrick J. Wong #include "xfs_rmap.h" 3630f712c9SDave Chinner 3730f712c9SDave Chinner 3830f712c9SDave Chinner STATIC int 3930f712c9SDave Chinner xfs_inobt_get_minrecs( 4030f712c9SDave Chinner struct xfs_btree_cur *cur, 4130f712c9SDave Chinner int level) 4230f712c9SDave Chinner { 4330f712c9SDave Chinner return cur->bc_mp->m_inobt_mnr[level != 0]; 4430f712c9SDave Chinner } 4530f712c9SDave Chinner 4630f712c9SDave Chinner STATIC struct xfs_btree_cur * 4730f712c9SDave Chinner xfs_inobt_dup_cursor( 4830f712c9SDave Chinner struct xfs_btree_cur *cur) 4930f712c9SDave Chinner { 5030f712c9SDave Chinner return xfs_inobt_init_cursor(cur->bc_mp, cur->bc_tp, 5130f712c9SDave Chinner cur->bc_private.a.agbp, cur->bc_private.a.agno, 5230f712c9SDave Chinner cur->bc_btnum); 5330f712c9SDave Chinner } 5430f712c9SDave Chinner 5530f712c9SDave Chinner STATIC void 5630f712c9SDave Chinner xfs_inobt_set_root( 5730f712c9SDave Chinner struct xfs_btree_cur *cur, 5830f712c9SDave Chinner union xfs_btree_ptr *nptr, 5930f712c9SDave Chinner int inc) /* level change */ 6030f712c9SDave Chinner { 6130f712c9SDave Chinner struct xfs_buf *agbp = cur->bc_private.a.agbp; 6230f712c9SDave Chinner struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp); 6330f712c9SDave Chinner 6430f712c9SDave Chinner agi->agi_root = nptr->s; 6530f712c9SDave Chinner be32_add_cpu(&agi->agi_level, inc); 6630f712c9SDave Chinner xfs_ialloc_log_agi(cur->bc_tp, agbp, XFS_AGI_ROOT | XFS_AGI_LEVEL); 6730f712c9SDave Chinner } 6830f712c9SDave Chinner 6930f712c9SDave Chinner STATIC void 7030f712c9SDave Chinner xfs_finobt_set_root( 7130f712c9SDave Chinner struct xfs_btree_cur *cur, 7230f712c9SDave Chinner union xfs_btree_ptr *nptr, 7330f712c9SDave Chinner int inc) /* level change */ 7430f712c9SDave Chinner { 7530f712c9SDave Chinner struct xfs_buf *agbp = cur->bc_private.a.agbp; 7630f712c9SDave Chinner struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp); 7730f712c9SDave Chinner 7830f712c9SDave Chinner agi->agi_free_root = nptr->s; 7930f712c9SDave Chinner be32_add_cpu(&agi->agi_free_level, inc); 8030f712c9SDave Chinner xfs_ialloc_log_agi(cur->bc_tp, agbp, 8130f712c9SDave Chinner XFS_AGI_FREE_ROOT | XFS_AGI_FREE_LEVEL); 8230f712c9SDave Chinner } 8330f712c9SDave Chinner 8430f712c9SDave Chinner STATIC int 8530f712c9SDave Chinner xfs_inobt_alloc_block( 8630f712c9SDave Chinner struct xfs_btree_cur *cur, 8730f712c9SDave Chinner union xfs_btree_ptr *start, 8830f712c9SDave Chinner union xfs_btree_ptr *new, 8930f712c9SDave Chinner int *stat) 9030f712c9SDave Chinner { 9130f712c9SDave Chinner xfs_alloc_arg_t args; /* block allocation args */ 9230f712c9SDave Chinner int error; /* error return value */ 9330f712c9SDave Chinner xfs_agblock_t sbno = be32_to_cpu(start->s); 9430f712c9SDave Chinner 9530f712c9SDave Chinner XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 9630f712c9SDave Chinner 9730f712c9SDave Chinner memset(&args, 0, sizeof(args)); 9830f712c9SDave Chinner args.tp = cur->bc_tp; 9930f712c9SDave Chinner args.mp = cur->bc_mp; 100340785ccSDarrick J. Wong xfs_rmap_ag_owner(&args.oinfo, XFS_RMAP_OWN_INOBT); 10130f712c9SDave Chinner args.fsbno = XFS_AGB_TO_FSB(args.mp, cur->bc_private.a.agno, sbno); 10230f712c9SDave Chinner args.minlen = 1; 10330f712c9SDave Chinner args.maxlen = 1; 10430f712c9SDave Chinner args.prod = 1; 10530f712c9SDave Chinner args.type = XFS_ALLOCTYPE_NEAR_BNO; 10630f712c9SDave Chinner 10730f712c9SDave Chinner error = xfs_alloc_vextent(&args); 10830f712c9SDave Chinner if (error) { 10930f712c9SDave Chinner XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 11030f712c9SDave Chinner return error; 11130f712c9SDave Chinner } 11230f712c9SDave Chinner if (args.fsbno == NULLFSBLOCK) { 11330f712c9SDave Chinner XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 11430f712c9SDave Chinner *stat = 0; 11530f712c9SDave Chinner return 0; 11630f712c9SDave Chinner } 11730f712c9SDave Chinner ASSERT(args.len == 1); 11830f712c9SDave Chinner XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 11930f712c9SDave Chinner 12030f712c9SDave Chinner new->s = cpu_to_be32(XFS_FSB_TO_AGBNO(args.mp, args.fsbno)); 12130f712c9SDave Chinner *stat = 1; 12230f712c9SDave Chinner return 0; 12330f712c9SDave Chinner } 12430f712c9SDave Chinner 12530f712c9SDave Chinner STATIC int 12630f712c9SDave Chinner xfs_inobt_free_block( 12730f712c9SDave Chinner struct xfs_btree_cur *cur, 12830f712c9SDave Chinner struct xfs_buf *bp) 12930f712c9SDave Chinner { 130340785ccSDarrick J. Wong struct xfs_owner_info oinfo; 131340785ccSDarrick J. Wong 132340785ccSDarrick J. Wong xfs_rmap_ag_owner(&oinfo, XFS_RMAP_OWN_INOBT); 133edfd9dd5SChristoph Hellwig return xfs_free_extent(cur->bc_tp, 134340785ccSDarrick J. Wong XFS_DADDR_TO_FSB(cur->bc_mp, XFS_BUF_ADDR(bp)), 1, 1353fd129b6SDarrick J. Wong &oinfo, XFS_AG_RESV_NONE); 13630f712c9SDave Chinner } 13730f712c9SDave Chinner 13830f712c9SDave Chinner STATIC int 13930f712c9SDave Chinner xfs_inobt_get_maxrecs( 14030f712c9SDave Chinner struct xfs_btree_cur *cur, 14130f712c9SDave Chinner int level) 14230f712c9SDave Chinner { 14330f712c9SDave Chinner return cur->bc_mp->m_inobt_mxr[level != 0]; 14430f712c9SDave Chinner } 14530f712c9SDave Chinner 14630f712c9SDave Chinner STATIC void 14730f712c9SDave Chinner xfs_inobt_init_key_from_rec( 14830f712c9SDave Chinner union xfs_btree_key *key, 14930f712c9SDave Chinner union xfs_btree_rec *rec) 15030f712c9SDave Chinner { 15130f712c9SDave Chinner key->inobt.ir_startino = rec->inobt.ir_startino; 15230f712c9SDave Chinner } 15330f712c9SDave Chinner 15430f712c9SDave Chinner STATIC void 15530f712c9SDave Chinner xfs_inobt_init_rec_from_cur( 15630f712c9SDave Chinner struct xfs_btree_cur *cur, 15730f712c9SDave Chinner union xfs_btree_rec *rec) 15830f712c9SDave Chinner { 15930f712c9SDave Chinner rec->inobt.ir_startino = cpu_to_be32(cur->bc_rec.i.ir_startino); 1605419040fSBrian Foster if (xfs_sb_version_hassparseinodes(&cur->bc_mp->m_sb)) { 1615419040fSBrian Foster rec->inobt.ir_u.sp.ir_holemask = 1625419040fSBrian Foster cpu_to_be16(cur->bc_rec.i.ir_holemask); 1635419040fSBrian Foster rec->inobt.ir_u.sp.ir_count = cur->bc_rec.i.ir_count; 1645419040fSBrian Foster rec->inobt.ir_u.sp.ir_freecount = cur->bc_rec.i.ir_freecount; 1655419040fSBrian Foster } else { 1665419040fSBrian Foster /* ir_holemask/ir_count not supported on-disk */ 1675419040fSBrian Foster rec->inobt.ir_u.f.ir_freecount = 1685419040fSBrian Foster cpu_to_be32(cur->bc_rec.i.ir_freecount); 1695419040fSBrian Foster } 17030f712c9SDave Chinner rec->inobt.ir_free = cpu_to_be64(cur->bc_rec.i.ir_free); 17130f712c9SDave Chinner } 17230f712c9SDave Chinner 17330f712c9SDave Chinner /* 17430f712c9SDave Chinner * initial value of ptr for lookup 17530f712c9SDave Chinner */ 17630f712c9SDave Chinner STATIC void 17730f712c9SDave Chinner xfs_inobt_init_ptr_from_cur( 17830f712c9SDave Chinner struct xfs_btree_cur *cur, 17930f712c9SDave Chinner union xfs_btree_ptr *ptr) 18030f712c9SDave Chinner { 18130f712c9SDave Chinner struct xfs_agi *agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp); 18230f712c9SDave Chinner 18330f712c9SDave Chinner ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno)); 18430f712c9SDave Chinner 18530f712c9SDave Chinner ptr->s = agi->agi_root; 18630f712c9SDave Chinner } 18730f712c9SDave Chinner 18830f712c9SDave Chinner STATIC void 18930f712c9SDave Chinner xfs_finobt_init_ptr_from_cur( 19030f712c9SDave Chinner struct xfs_btree_cur *cur, 19130f712c9SDave Chinner union xfs_btree_ptr *ptr) 19230f712c9SDave Chinner { 19330f712c9SDave Chinner struct xfs_agi *agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp); 19430f712c9SDave Chinner 19530f712c9SDave Chinner ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno)); 19630f712c9SDave Chinner ptr->s = agi->agi_free_root; 19730f712c9SDave Chinner } 19830f712c9SDave Chinner 19930f712c9SDave Chinner STATIC __int64_t 20030f712c9SDave Chinner xfs_inobt_key_diff( 20130f712c9SDave Chinner struct xfs_btree_cur *cur, 20230f712c9SDave Chinner union xfs_btree_key *key) 20330f712c9SDave Chinner { 20430f712c9SDave Chinner return (__int64_t)be32_to_cpu(key->inobt.ir_startino) - 20530f712c9SDave Chinner cur->bc_rec.i.ir_startino; 20630f712c9SDave Chinner } 20730f712c9SDave Chinner 20830f712c9SDave Chinner static int 20930f712c9SDave Chinner xfs_inobt_verify( 21030f712c9SDave Chinner struct xfs_buf *bp) 21130f712c9SDave Chinner { 21230f712c9SDave Chinner struct xfs_mount *mp = bp->b_target->bt_mount; 21330f712c9SDave Chinner struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); 21430f712c9SDave Chinner unsigned int level; 21530f712c9SDave Chinner 21630f712c9SDave Chinner /* 21730f712c9SDave Chinner * During growfs operations, we can't verify the exact owner as the 21830f712c9SDave Chinner * perag is not fully initialised and hence not attached to the buffer. 21930f712c9SDave Chinner * 22030f712c9SDave Chinner * Similarly, during log recovery we will have a perag structure 22130f712c9SDave Chinner * attached, but the agi information will not yet have been initialised 22230f712c9SDave Chinner * from the on disk AGI. We don't currently use any of this information, 22330f712c9SDave Chinner * but beware of the landmine (i.e. need to check pag->pagi_init) if we 22430f712c9SDave Chinner * ever do. 22530f712c9SDave Chinner */ 22630f712c9SDave Chinner switch (block->bb_magic) { 22730f712c9SDave Chinner case cpu_to_be32(XFS_IBT_CRC_MAGIC): 22830f712c9SDave Chinner case cpu_to_be32(XFS_FIBT_CRC_MAGIC): 229c5ab131bSDarrick J. Wong if (!xfs_btree_sblock_v5hdr_verify(bp)) 23030f712c9SDave Chinner return false; 23130f712c9SDave Chinner /* fall through */ 23230f712c9SDave Chinner case cpu_to_be32(XFS_IBT_MAGIC): 23330f712c9SDave Chinner case cpu_to_be32(XFS_FIBT_MAGIC): 23430f712c9SDave Chinner break; 23530f712c9SDave Chinner default: 23630f712c9SDave Chinner return 0; 23730f712c9SDave Chinner } 23830f712c9SDave Chinner 239c5ab131bSDarrick J. Wong /* level verification */ 24030f712c9SDave Chinner level = be16_to_cpu(block->bb_level); 24130f712c9SDave Chinner if (level >= mp->m_in_maxlevels) 24230f712c9SDave Chinner return false; 24330f712c9SDave Chinner 244c5ab131bSDarrick J. Wong return xfs_btree_sblock_verify(bp, mp->m_inobt_mxr[level != 0]); 24530f712c9SDave Chinner } 24630f712c9SDave Chinner 24730f712c9SDave Chinner static void 24830f712c9SDave Chinner xfs_inobt_read_verify( 24930f712c9SDave Chinner struct xfs_buf *bp) 25030f712c9SDave Chinner { 25130f712c9SDave Chinner if (!xfs_btree_sblock_verify_crc(bp)) 2522451337dSDave Chinner xfs_buf_ioerror(bp, -EFSBADCRC); 25330f712c9SDave Chinner else if (!xfs_inobt_verify(bp)) 2542451337dSDave Chinner xfs_buf_ioerror(bp, -EFSCORRUPTED); 25530f712c9SDave Chinner 25630f712c9SDave Chinner if (bp->b_error) { 25730f712c9SDave Chinner trace_xfs_btree_corrupt(bp, _RET_IP_); 25830f712c9SDave Chinner xfs_verifier_error(bp); 25930f712c9SDave Chinner } 26030f712c9SDave Chinner } 26130f712c9SDave Chinner 26230f712c9SDave Chinner static void 26330f712c9SDave Chinner xfs_inobt_write_verify( 26430f712c9SDave Chinner struct xfs_buf *bp) 26530f712c9SDave Chinner { 26630f712c9SDave Chinner if (!xfs_inobt_verify(bp)) { 26730f712c9SDave Chinner trace_xfs_btree_corrupt(bp, _RET_IP_); 2682451337dSDave Chinner xfs_buf_ioerror(bp, -EFSCORRUPTED); 26930f712c9SDave Chinner xfs_verifier_error(bp); 27030f712c9SDave Chinner return; 27130f712c9SDave Chinner } 27230f712c9SDave Chinner xfs_btree_sblock_calc_crc(bp); 27330f712c9SDave Chinner 27430f712c9SDave Chinner } 27530f712c9SDave Chinner 27630f712c9SDave Chinner const struct xfs_buf_ops xfs_inobt_buf_ops = { 277233135b7SEric Sandeen .name = "xfs_inobt", 27830f712c9SDave Chinner .verify_read = xfs_inobt_read_verify, 27930f712c9SDave Chinner .verify_write = xfs_inobt_write_verify, 28030f712c9SDave Chinner }; 28130f712c9SDave Chinner 28230f712c9SDave Chinner #if defined(DEBUG) || defined(XFS_WARN) 28330f712c9SDave Chinner STATIC int 28430f712c9SDave Chinner xfs_inobt_keys_inorder( 28530f712c9SDave Chinner struct xfs_btree_cur *cur, 28630f712c9SDave Chinner union xfs_btree_key *k1, 28730f712c9SDave Chinner union xfs_btree_key *k2) 28830f712c9SDave Chinner { 28930f712c9SDave Chinner return be32_to_cpu(k1->inobt.ir_startino) < 29030f712c9SDave Chinner be32_to_cpu(k2->inobt.ir_startino); 29130f712c9SDave Chinner } 29230f712c9SDave Chinner 29330f712c9SDave Chinner STATIC int 29430f712c9SDave Chinner xfs_inobt_recs_inorder( 29530f712c9SDave Chinner struct xfs_btree_cur *cur, 29630f712c9SDave Chinner union xfs_btree_rec *r1, 29730f712c9SDave Chinner union xfs_btree_rec *r2) 29830f712c9SDave Chinner { 29930f712c9SDave Chinner return be32_to_cpu(r1->inobt.ir_startino) + XFS_INODES_PER_CHUNK <= 30030f712c9SDave Chinner be32_to_cpu(r2->inobt.ir_startino); 30130f712c9SDave Chinner } 30230f712c9SDave Chinner #endif /* DEBUG */ 30330f712c9SDave Chinner 30430f712c9SDave Chinner static const struct xfs_btree_ops xfs_inobt_ops = { 30530f712c9SDave Chinner .rec_len = sizeof(xfs_inobt_rec_t), 30630f712c9SDave Chinner .key_len = sizeof(xfs_inobt_key_t), 30730f712c9SDave Chinner 30830f712c9SDave Chinner .dup_cursor = xfs_inobt_dup_cursor, 30930f712c9SDave Chinner .set_root = xfs_inobt_set_root, 31030f712c9SDave Chinner .alloc_block = xfs_inobt_alloc_block, 31130f712c9SDave Chinner .free_block = xfs_inobt_free_block, 31230f712c9SDave Chinner .get_minrecs = xfs_inobt_get_minrecs, 31330f712c9SDave Chinner .get_maxrecs = xfs_inobt_get_maxrecs, 31430f712c9SDave Chinner .init_key_from_rec = xfs_inobt_init_key_from_rec, 31530f712c9SDave Chinner .init_rec_from_cur = xfs_inobt_init_rec_from_cur, 31630f712c9SDave Chinner .init_ptr_from_cur = xfs_inobt_init_ptr_from_cur, 31730f712c9SDave Chinner .key_diff = xfs_inobt_key_diff, 31830f712c9SDave Chinner .buf_ops = &xfs_inobt_buf_ops, 31930f712c9SDave Chinner #if defined(DEBUG) || defined(XFS_WARN) 32030f712c9SDave Chinner .keys_inorder = xfs_inobt_keys_inorder, 32130f712c9SDave Chinner .recs_inorder = xfs_inobt_recs_inorder, 32230f712c9SDave Chinner #endif 32330f712c9SDave Chinner }; 32430f712c9SDave Chinner 32530f712c9SDave Chinner static const struct xfs_btree_ops xfs_finobt_ops = { 32630f712c9SDave Chinner .rec_len = sizeof(xfs_inobt_rec_t), 32730f712c9SDave Chinner .key_len = sizeof(xfs_inobt_key_t), 32830f712c9SDave Chinner 32930f712c9SDave Chinner .dup_cursor = xfs_inobt_dup_cursor, 33030f712c9SDave Chinner .set_root = xfs_finobt_set_root, 33130f712c9SDave Chinner .alloc_block = xfs_inobt_alloc_block, 33230f712c9SDave Chinner .free_block = xfs_inobt_free_block, 33330f712c9SDave Chinner .get_minrecs = xfs_inobt_get_minrecs, 33430f712c9SDave Chinner .get_maxrecs = xfs_inobt_get_maxrecs, 33530f712c9SDave Chinner .init_key_from_rec = xfs_inobt_init_key_from_rec, 33630f712c9SDave Chinner .init_rec_from_cur = xfs_inobt_init_rec_from_cur, 33730f712c9SDave Chinner .init_ptr_from_cur = xfs_finobt_init_ptr_from_cur, 33830f712c9SDave Chinner .key_diff = xfs_inobt_key_diff, 33930f712c9SDave Chinner .buf_ops = &xfs_inobt_buf_ops, 34030f712c9SDave Chinner #if defined(DEBUG) || defined(XFS_WARN) 34130f712c9SDave Chinner .keys_inorder = xfs_inobt_keys_inorder, 34230f712c9SDave Chinner .recs_inorder = xfs_inobt_recs_inorder, 34330f712c9SDave Chinner #endif 34430f712c9SDave Chinner }; 34530f712c9SDave Chinner 34630f712c9SDave Chinner /* 34730f712c9SDave Chinner * Allocate a new inode btree cursor. 34830f712c9SDave Chinner */ 34930f712c9SDave Chinner struct xfs_btree_cur * /* new inode btree cursor */ 35030f712c9SDave Chinner xfs_inobt_init_cursor( 35130f712c9SDave Chinner struct xfs_mount *mp, /* file system mount point */ 35230f712c9SDave Chinner struct xfs_trans *tp, /* transaction pointer */ 35330f712c9SDave Chinner struct xfs_buf *agbp, /* buffer for agi structure */ 35430f712c9SDave Chinner xfs_agnumber_t agno, /* allocation group number */ 35530f712c9SDave Chinner xfs_btnum_t btnum) /* ialloc or free ino btree */ 35630f712c9SDave Chinner { 35730f712c9SDave Chinner struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp); 35830f712c9SDave Chinner struct xfs_btree_cur *cur; 35930f712c9SDave Chinner 36030f712c9SDave Chinner cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP); 36130f712c9SDave Chinner 36230f712c9SDave Chinner cur->bc_tp = tp; 36330f712c9SDave Chinner cur->bc_mp = mp; 36430f712c9SDave Chinner cur->bc_btnum = btnum; 36530f712c9SDave Chinner if (btnum == XFS_BTNUM_INO) { 36630f712c9SDave Chinner cur->bc_nlevels = be32_to_cpu(agi->agi_level); 36730f712c9SDave Chinner cur->bc_ops = &xfs_inobt_ops; 36811ef38afSDave Chinner cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_ibt_2); 36930f712c9SDave Chinner } else { 37030f712c9SDave Chinner cur->bc_nlevels = be32_to_cpu(agi->agi_free_level); 37130f712c9SDave Chinner cur->bc_ops = &xfs_finobt_ops; 37211ef38afSDave Chinner cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_fibt_2); 37330f712c9SDave Chinner } 37430f712c9SDave Chinner 37530f712c9SDave Chinner cur->bc_blocklog = mp->m_sb.sb_blocklog; 37630f712c9SDave Chinner 37730f712c9SDave Chinner if (xfs_sb_version_hascrc(&mp->m_sb)) 37830f712c9SDave Chinner cur->bc_flags |= XFS_BTREE_CRC_BLOCKS; 37930f712c9SDave Chinner 38030f712c9SDave Chinner cur->bc_private.a.agbp = agbp; 38130f712c9SDave Chinner cur->bc_private.a.agno = agno; 38230f712c9SDave Chinner 38330f712c9SDave Chinner return cur; 38430f712c9SDave Chinner } 38530f712c9SDave Chinner 38630f712c9SDave Chinner /* 38730f712c9SDave Chinner * Calculate number of records in an inobt btree block. 38830f712c9SDave Chinner */ 38930f712c9SDave Chinner int 39030f712c9SDave Chinner xfs_inobt_maxrecs( 39130f712c9SDave Chinner struct xfs_mount *mp, 39230f712c9SDave Chinner int blocklen, 39330f712c9SDave Chinner int leaf) 39430f712c9SDave Chinner { 39530f712c9SDave Chinner blocklen -= XFS_INOBT_BLOCK_LEN(mp); 39630f712c9SDave Chinner 39730f712c9SDave Chinner if (leaf) 39830f712c9SDave Chinner return blocklen / sizeof(xfs_inobt_rec_t); 39930f712c9SDave Chinner return blocklen / (sizeof(xfs_inobt_key_t) + sizeof(xfs_inobt_ptr_t)); 40030f712c9SDave Chinner } 4014148c347SBrian Foster 4024148c347SBrian Foster /* 4034148c347SBrian Foster * Convert the inode record holemask to an inode allocation bitmap. The inode 4044148c347SBrian Foster * allocation bitmap is inode granularity and specifies whether an inode is 4054148c347SBrian Foster * physically allocated on disk (not whether the inode is considered allocated 4064148c347SBrian Foster * or free by the fs). 4074148c347SBrian Foster * 4084148c347SBrian Foster * A bit value of 1 means the inode is allocated, a value of 0 means it is free. 4094148c347SBrian Foster */ 4104148c347SBrian Foster uint64_t 4114148c347SBrian Foster xfs_inobt_irec_to_allocmask( 4124148c347SBrian Foster struct xfs_inobt_rec_incore *rec) 4134148c347SBrian Foster { 4144148c347SBrian Foster uint64_t bitmap = 0; 4154148c347SBrian Foster uint64_t inodespbit; 4164148c347SBrian Foster int nextbit; 4174148c347SBrian Foster uint allocbitmap; 4184148c347SBrian Foster 4194148c347SBrian Foster /* 4204148c347SBrian Foster * The holemask has 16-bits for a 64 inode record. Therefore each 4214148c347SBrian Foster * holemask bit represents multiple inodes. Create a mask of bits to set 4224148c347SBrian Foster * in the allocmask for each holemask bit. 4234148c347SBrian Foster */ 4244148c347SBrian Foster inodespbit = (1 << XFS_INODES_PER_HOLEMASK_BIT) - 1; 4254148c347SBrian Foster 4264148c347SBrian Foster /* 4274148c347SBrian Foster * Allocated inodes are represented by 0 bits in holemask. Invert the 0 4284148c347SBrian Foster * bits to 1 and convert to a uint so we can use xfs_next_bit(). Mask 4294148c347SBrian Foster * anything beyond the 16 holemask bits since this casts to a larger 4304148c347SBrian Foster * type. 4314148c347SBrian Foster */ 4324148c347SBrian Foster allocbitmap = ~rec->ir_holemask & ((1 << XFS_INOBT_HOLEMASK_BITS) - 1); 4334148c347SBrian Foster 4344148c347SBrian Foster /* 4354148c347SBrian Foster * allocbitmap is the inverted holemask so every set bit represents 4364148c347SBrian Foster * allocated inodes. To expand from 16-bit holemask granularity to 4374148c347SBrian Foster * 64-bit (e.g., bit-per-inode), set inodespbit bits in the target 4384148c347SBrian Foster * bitmap for every holemask bit. 4394148c347SBrian Foster */ 4404148c347SBrian Foster nextbit = xfs_next_bit(&allocbitmap, 1, 0); 4414148c347SBrian Foster while (nextbit != -1) { 4424148c347SBrian Foster ASSERT(nextbit < (sizeof(rec->ir_holemask) * NBBY)); 4434148c347SBrian Foster 4444148c347SBrian Foster bitmap |= (inodespbit << 4454148c347SBrian Foster (nextbit * XFS_INODES_PER_HOLEMASK_BIT)); 4464148c347SBrian Foster 4474148c347SBrian Foster nextbit = xfs_next_bit(&allocbitmap, 1, nextbit + 1); 4484148c347SBrian Foster } 4494148c347SBrian Foster 4504148c347SBrian Foster return bitmap; 4514148c347SBrian Foster } 45256d1115cSBrian Foster 45356d1115cSBrian Foster #if defined(DEBUG) || defined(XFS_WARN) 45456d1115cSBrian Foster /* 45556d1115cSBrian Foster * Verify that an in-core inode record has a valid inode count. 45656d1115cSBrian Foster */ 45756d1115cSBrian Foster int 45856d1115cSBrian Foster xfs_inobt_rec_check_count( 45956d1115cSBrian Foster struct xfs_mount *mp, 46056d1115cSBrian Foster struct xfs_inobt_rec_incore *rec) 46156d1115cSBrian Foster { 46256d1115cSBrian Foster int inocount = 0; 46356d1115cSBrian Foster int nextbit = 0; 46456d1115cSBrian Foster uint64_t allocbmap; 46556d1115cSBrian Foster int wordsz; 46656d1115cSBrian Foster 46756d1115cSBrian Foster wordsz = sizeof(allocbmap) / sizeof(unsigned int); 46856d1115cSBrian Foster allocbmap = xfs_inobt_irec_to_allocmask(rec); 46956d1115cSBrian Foster 47056d1115cSBrian Foster nextbit = xfs_next_bit((uint *) &allocbmap, wordsz, nextbit); 47156d1115cSBrian Foster while (nextbit != -1) { 47256d1115cSBrian Foster inocount++; 47356d1115cSBrian Foster nextbit = xfs_next_bit((uint *) &allocbmap, wordsz, 47456d1115cSBrian Foster nextbit + 1); 47556d1115cSBrian Foster } 47656d1115cSBrian Foster 47756d1115cSBrian Foster if (inocount != rec->ir_count) 47856d1115cSBrian Foster return -EFSCORRUPTED; 47956d1115cSBrian Foster 48056d1115cSBrian Foster return 0; 48156d1115cSBrian Foster } 48256d1115cSBrian Foster #endif /* DEBUG */ 483