10b61f8a4SDave Chinner // SPDX-License-Identifier: GPL-2.0
230f712c9SDave Chinner /*
330f712c9SDave Chinner * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
430f712c9SDave Chinner * All Rights Reserved.
530f712c9SDave Chinner */
630f712c9SDave Chinner #include "xfs.h"
730f712c9SDave Chinner #include "xfs_fs.h"
830f712c9SDave Chinner #include "xfs_shared.h"
930f712c9SDave Chinner #include "xfs_format.h"
1030f712c9SDave Chinner #include "xfs_log_format.h"
1130f712c9SDave Chinner #include "xfs_trans_resv.h"
1230f712c9SDave Chinner #include "xfs_bit.h"
1330f712c9SDave Chinner #include "xfs_mount.h"
1430f712c9SDave Chinner #include "xfs_btree.h"
15c29ce8f4SDarrick J. Wong #include "xfs_btree_staging.h"
1630f712c9SDave Chinner #include "xfs_ialloc.h"
1730f712c9SDave Chinner #include "xfs_ialloc_btree.h"
1830f712c9SDave Chinner #include "xfs_alloc.h"
1930f712c9SDave Chinner #include "xfs_error.h"
2030f712c9SDave Chinner #include "xfs_trace.h"
2130f712c9SDave Chinner #include "xfs_trans.h"
22340785ccSDarrick J. Wong #include "xfs_rmap.h"
2330933120SDave Chinner #include "xfs_ag.h"
2430f712c9SDave Chinner
25e7720afaSDarrick J. Wong static struct kmem_cache *xfs_inobt_cur_cache;
269fa47bdcSDarrick J. Wong
2730f712c9SDave Chinner STATIC int
xfs_inobt_get_minrecs(struct xfs_btree_cur * cur,int level)2830f712c9SDave Chinner xfs_inobt_get_minrecs(
2930f712c9SDave Chinner struct xfs_btree_cur *cur,
3030f712c9SDave Chinner int level)
3130f712c9SDave Chinner {
32ef325959SDarrick J. Wong return M_IGEO(cur->bc_mp)->inobt_mnr[level != 0];
3330f712c9SDave Chinner }
3430f712c9SDave Chinner
3530f712c9SDave Chinner STATIC struct xfs_btree_cur *
xfs_inobt_dup_cursor(struct xfs_btree_cur * cur)3630f712c9SDave Chinner xfs_inobt_dup_cursor(
3730f712c9SDave Chinner struct xfs_btree_cur *cur)
3830f712c9SDave Chinner {
39bab8b795SDave Chinner return xfs_inobt_init_cursor(cur->bc_ag.pag, cur->bc_tp,
40bab8b795SDave Chinner cur->bc_ag.agbp, cur->bc_btnum);
4130f712c9SDave Chinner }
4230f712c9SDave Chinner
4330f712c9SDave Chinner STATIC void
xfs_inobt_set_root(struct xfs_btree_cur * cur,const union xfs_btree_ptr * nptr,int inc)4430f712c9SDave Chinner xfs_inobt_set_root(
4530f712c9SDave Chinner struct xfs_btree_cur *cur,
46b5a6e5feSDarrick J. Wong const union xfs_btree_ptr *nptr,
4730f712c9SDave Chinner int inc) /* level change */
4830f712c9SDave Chinner {
49576af732SDave Chinner struct xfs_buf *agbp = cur->bc_ag.agbp;
50370c782bSChristoph Hellwig struct xfs_agi *agi = agbp->b_addr;
5130f712c9SDave Chinner
5230f712c9SDave Chinner agi->agi_root = nptr->s;
5330f712c9SDave Chinner be32_add_cpu(&agi->agi_level, inc);
5430f712c9SDave Chinner xfs_ialloc_log_agi(cur->bc_tp, agbp, XFS_AGI_ROOT | XFS_AGI_LEVEL);
5530f712c9SDave Chinner }
5630f712c9SDave Chinner
5730f712c9SDave Chinner STATIC void
xfs_finobt_set_root(struct xfs_btree_cur * cur,const union xfs_btree_ptr * nptr,int inc)5830f712c9SDave Chinner xfs_finobt_set_root(
5930f712c9SDave Chinner struct xfs_btree_cur *cur,
60b5a6e5feSDarrick J. Wong const union xfs_btree_ptr *nptr,
6130f712c9SDave Chinner int inc) /* level change */
6230f712c9SDave Chinner {
63576af732SDave Chinner struct xfs_buf *agbp = cur->bc_ag.agbp;
64370c782bSChristoph Hellwig struct xfs_agi *agi = agbp->b_addr;
6530f712c9SDave Chinner
6630f712c9SDave Chinner agi->agi_free_root = nptr->s;
6730f712c9SDave Chinner be32_add_cpu(&agi->agi_free_level, inc);
6830f712c9SDave Chinner xfs_ialloc_log_agi(cur->bc_tp, agbp,
6930f712c9SDave Chinner XFS_AGI_FREE_ROOT | XFS_AGI_FREE_LEVEL);
7030f712c9SDave Chinner }
7130f712c9SDave Chinner
722a39946cSDarrick J. Wong /* Update the inode btree block counter for this btree. */
732a39946cSDarrick J. Wong static inline void
xfs_inobt_mod_blockcount(struct xfs_btree_cur * cur,int howmuch)742a39946cSDarrick J. Wong xfs_inobt_mod_blockcount(
752a39946cSDarrick J. Wong struct xfs_btree_cur *cur,
762a39946cSDarrick J. Wong int howmuch)
772a39946cSDarrick J. Wong {
782a39946cSDarrick J. Wong struct xfs_buf *agbp = cur->bc_ag.agbp;
792a39946cSDarrick J. Wong struct xfs_agi *agi = agbp->b_addr;
802a39946cSDarrick J. Wong
81ebd9027dSDave Chinner if (!xfs_has_inobtcounts(cur->bc_mp))
822a39946cSDarrick J. Wong return;
832a39946cSDarrick J. Wong
842a39946cSDarrick J. Wong if (cur->bc_btnum == XFS_BTNUM_FINO)
852a39946cSDarrick J. Wong be32_add_cpu(&agi->agi_fblocks, howmuch);
862a39946cSDarrick J. Wong else if (cur->bc_btnum == XFS_BTNUM_INO)
872a39946cSDarrick J. Wong be32_add_cpu(&agi->agi_iblocks, howmuch);
882a39946cSDarrick J. Wong xfs_ialloc_log_agi(cur->bc_tp, agbp, XFS_AGI_IBLOCKS);
892a39946cSDarrick J. Wong }
902a39946cSDarrick J. Wong
9130f712c9SDave Chinner STATIC int
__xfs_inobt_alloc_block(struct xfs_btree_cur * cur,const union xfs_btree_ptr * start,union xfs_btree_ptr * new,int * stat,enum xfs_ag_resv_type resv)9276d771b4SChristoph Hellwig __xfs_inobt_alloc_block(
9330f712c9SDave Chinner struct xfs_btree_cur *cur,
94deb06b9aSDarrick J. Wong const union xfs_btree_ptr *start,
9530f712c9SDave Chinner union xfs_btree_ptr *new,
9676d771b4SChristoph Hellwig int *stat,
9776d771b4SChristoph Hellwig enum xfs_ag_resv_type resv)
9830f712c9SDave Chinner {
9930f712c9SDave Chinner xfs_alloc_arg_t args; /* block allocation args */
10030f712c9SDave Chinner int error; /* error return value */
10130f712c9SDave Chinner xfs_agblock_t sbno = be32_to_cpu(start->s);
10230f712c9SDave Chinner
10330f712c9SDave Chinner memset(&args, 0, sizeof(args));
10430f712c9SDave Chinner args.tp = cur->bc_tp;
10530f712c9SDave Chinner args.mp = cur->bc_mp;
10674c36a86SDave Chinner args.pag = cur->bc_ag.pag;
1077280fedaSDarrick J. Wong args.oinfo = XFS_RMAP_OINFO_INOBT;
10830f712c9SDave Chinner args.minlen = 1;
10930f712c9SDave Chinner args.maxlen = 1;
11030f712c9SDave Chinner args.prod = 1;
11176d771b4SChristoph Hellwig args.resv = resv;
11230f712c9SDave Chinner
113db4710fdSDave Chinner error = xfs_alloc_vextent_near_bno(&args,
114db4710fdSDave Chinner XFS_AGB_TO_FSB(args.mp, args.pag->pag_agno, sbno));
115e157ebdcSCarlos Maiolino if (error)
11630f712c9SDave Chinner return error;
117e157ebdcSCarlos Maiolino
11830f712c9SDave Chinner if (args.fsbno == NULLFSBLOCK) {
11930f712c9SDave Chinner *stat = 0;
12030f712c9SDave Chinner return 0;
12130f712c9SDave Chinner }
12230f712c9SDave Chinner ASSERT(args.len == 1);
12330f712c9SDave Chinner
12430f712c9SDave Chinner new->s = cpu_to_be32(XFS_FSB_TO_AGBNO(args.mp, args.fsbno));
12530f712c9SDave Chinner *stat = 1;
1262a39946cSDarrick J. Wong xfs_inobt_mod_blockcount(cur, 1);
12730f712c9SDave Chinner return 0;
12830f712c9SDave Chinner }
12930f712c9SDave Chinner
13030f712c9SDave Chinner STATIC int
xfs_inobt_alloc_block(struct xfs_btree_cur * cur,const union xfs_btree_ptr * start,union xfs_btree_ptr * new,int * stat)13176d771b4SChristoph Hellwig xfs_inobt_alloc_block(
13276d771b4SChristoph Hellwig struct xfs_btree_cur *cur,
133deb06b9aSDarrick J. Wong const union xfs_btree_ptr *start,
13476d771b4SChristoph Hellwig union xfs_btree_ptr *new,
13576d771b4SChristoph Hellwig int *stat)
13676d771b4SChristoph Hellwig {
13776d771b4SChristoph Hellwig return __xfs_inobt_alloc_block(cur, start, new, stat, XFS_AG_RESV_NONE);
13876d771b4SChristoph Hellwig }
13976d771b4SChristoph Hellwig
14076d771b4SChristoph Hellwig STATIC int
xfs_finobt_alloc_block(struct xfs_btree_cur * cur,const union xfs_btree_ptr * start,union xfs_btree_ptr * new,int * stat)14176d771b4SChristoph Hellwig xfs_finobt_alloc_block(
14276d771b4SChristoph Hellwig struct xfs_btree_cur *cur,
143deb06b9aSDarrick J. Wong const union xfs_btree_ptr *start,
14476d771b4SChristoph Hellwig union xfs_btree_ptr *new,
14576d771b4SChristoph Hellwig int *stat)
14676d771b4SChristoph Hellwig {
147e1f6ca11SDarrick J. Wong if (cur->bc_mp->m_finobt_nores)
148ad90bb58SBrian Foster return xfs_inobt_alloc_block(cur, start, new, stat);
14976d771b4SChristoph Hellwig return __xfs_inobt_alloc_block(cur, start, new, stat,
15076d771b4SChristoph Hellwig XFS_AG_RESV_METADATA);
15176d771b4SChristoph Hellwig }
15276d771b4SChristoph Hellwig
15376d771b4SChristoph Hellwig STATIC int
__xfs_inobt_free_block(struct xfs_btree_cur * cur,struct xfs_buf * bp,enum xfs_ag_resv_type resv)154ad90bb58SBrian Foster __xfs_inobt_free_block(
155ad90bb58SBrian Foster struct xfs_btree_cur *cur,
156ad90bb58SBrian Foster struct xfs_buf *bp,
157ad90bb58SBrian Foster enum xfs_ag_resv_type resv)
158ad90bb58SBrian Foster {
159b2ccab31SDarrick J. Wong xfs_fsblock_t fsbno;
160b2ccab31SDarrick J. Wong
1612a39946cSDarrick J. Wong xfs_inobt_mod_blockcount(cur, -1);
162b2ccab31SDarrick J. Wong fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, xfs_buf_daddr(bp));
163b2ccab31SDarrick J. Wong return xfs_free_extent_later(cur->bc_tp, fsbno, 1,
164b2ccab31SDarrick J. Wong &XFS_RMAP_OINFO_INOBT, resv);
1657280fedaSDarrick J. Wong }
166ad90bb58SBrian Foster
167ad90bb58SBrian Foster STATIC int
xfs_inobt_free_block(struct xfs_btree_cur * cur,struct xfs_buf * bp)168ad90bb58SBrian Foster xfs_inobt_free_block(
16930f712c9SDave Chinner struct xfs_btree_cur *cur,
17030f712c9SDave Chinner struct xfs_buf *bp)
17130f712c9SDave Chinner {
17230f712c9SDave Chinner return __xfs_inobt_free_block(cur, bp, XFS_AG_RESV_NONE);
173ad90bb58SBrian Foster }
174ad90bb58SBrian Foster
175340785ccSDarrick J. Wong STATIC int
xfs_finobt_free_block(struct xfs_btree_cur * cur,struct xfs_buf * bp)176ad90bb58SBrian Foster xfs_finobt_free_block(
177ad90bb58SBrian Foster struct xfs_btree_cur *cur,
178ad90bb58SBrian Foster struct xfs_buf *bp)
179ad90bb58SBrian Foster {
180ad90bb58SBrian Foster if (cur->bc_mp->m_finobt_nores)
181e1f6ca11SDarrick J. Wong return xfs_inobt_free_block(cur, bp);
182ad90bb58SBrian Foster return __xfs_inobt_free_block(cur, bp, XFS_AG_RESV_METADATA);
183ad90bb58SBrian Foster }
18430f712c9SDave Chinner
18530f712c9SDave Chinner STATIC int
xfs_inobt_get_maxrecs(struct xfs_btree_cur * cur,int level)18630f712c9SDave Chinner xfs_inobt_get_maxrecs(
18730f712c9SDave Chinner struct xfs_btree_cur *cur,
18830f712c9SDave Chinner int level)
18930f712c9SDave Chinner {
19030f712c9SDave Chinner return M_IGEO(cur->bc_mp)->inobt_mxr[level != 0];
191ef325959SDarrick J. Wong }
19230f712c9SDave Chinner
19330f712c9SDave Chinner STATIC void
xfs_inobt_init_key_from_rec(union xfs_btree_key * key,const union xfs_btree_rec * rec)19430f712c9SDave Chinner xfs_inobt_init_key_from_rec(
19530f712c9SDave Chinner union xfs_btree_key *key,
19630f712c9SDave Chinner const union xfs_btree_rec *rec)
19723825cd1SDarrick J. Wong {
19830f712c9SDave Chinner key->inobt.ir_startino = rec->inobt.ir_startino;
19930f712c9SDave Chinner }
20030f712c9SDave Chinner
20130f712c9SDave Chinner STATIC void
xfs_inobt_init_high_key_from_rec(union xfs_btree_key * key,const union xfs_btree_rec * rec)20230f712c9SDave Chinner xfs_inobt_init_high_key_from_rec(
203118bb47eSDarrick J. Wong union xfs_btree_key *key,
204118bb47eSDarrick J. Wong const union xfs_btree_rec *rec)
20523825cd1SDarrick J. Wong {
206118bb47eSDarrick J. Wong __u32 x;
207118bb47eSDarrick J. Wong
208118bb47eSDarrick J. Wong x = be32_to_cpu(rec->inobt.ir_startino);
209118bb47eSDarrick J. Wong x += XFS_INODES_PER_CHUNK - 1;
210118bb47eSDarrick J. Wong key->inobt.ir_startino = cpu_to_be32(x);
211118bb47eSDarrick J. Wong }
212118bb47eSDarrick J. Wong
213118bb47eSDarrick J. Wong STATIC void
xfs_inobt_init_rec_from_cur(struct xfs_btree_cur * cur,union xfs_btree_rec * rec)214118bb47eSDarrick J. Wong xfs_inobt_init_rec_from_cur(
21530f712c9SDave Chinner struct xfs_btree_cur *cur,
21630f712c9SDave Chinner union xfs_btree_rec *rec)
21730f712c9SDave Chinner {
21830f712c9SDave Chinner rec->inobt.ir_startino = cpu_to_be32(cur->bc_rec.i.ir_startino);
21930f712c9SDave Chinner if (xfs_has_sparseinodes(cur->bc_mp)) {
22038c26bfdSDave Chinner rec->inobt.ir_u.sp.ir_holemask =
2215419040fSBrian Foster cpu_to_be16(cur->bc_rec.i.ir_holemask);
2225419040fSBrian Foster rec->inobt.ir_u.sp.ir_count = cur->bc_rec.i.ir_count;
2235419040fSBrian Foster rec->inobt.ir_u.sp.ir_freecount = cur->bc_rec.i.ir_freecount;
2245419040fSBrian Foster } else {
2255419040fSBrian Foster /* ir_holemask/ir_count not supported on-disk */
2265419040fSBrian Foster rec->inobt.ir_u.f.ir_freecount =
2275419040fSBrian Foster cpu_to_be32(cur->bc_rec.i.ir_freecount);
2285419040fSBrian Foster }
2295419040fSBrian Foster rec->inobt.ir_free = cpu_to_be64(cur->bc_rec.i.ir_free);
23030f712c9SDave Chinner }
23130f712c9SDave Chinner
23230f712c9SDave Chinner /*
23330f712c9SDave Chinner * initial value of ptr for lookup
23430f712c9SDave Chinner */
23530f712c9SDave Chinner STATIC void
xfs_inobt_init_ptr_from_cur(struct xfs_btree_cur * cur,union xfs_btree_ptr * ptr)23630f712c9SDave Chinner xfs_inobt_init_ptr_from_cur(
23730f712c9SDave Chinner struct xfs_btree_cur *cur,
23830f712c9SDave Chinner union xfs_btree_ptr *ptr)
23930f712c9SDave Chinner {
24030f712c9SDave Chinner struct xfs_agi *agi = cur->bc_ag.agbp->b_addr;
241576af732SDave Chinner
24230f712c9SDave Chinner ASSERT(cur->bc_ag.pag->pag_agno == be32_to_cpu(agi->agi_seqno));
24350f02fe3SDave Chinner
24430f712c9SDave Chinner ptr->s = agi->agi_root;
24530f712c9SDave Chinner }
24630f712c9SDave Chinner
24730f712c9SDave Chinner STATIC void
xfs_finobt_init_ptr_from_cur(struct xfs_btree_cur * cur,union xfs_btree_ptr * ptr)24830f712c9SDave Chinner xfs_finobt_init_ptr_from_cur(
24930f712c9SDave Chinner struct xfs_btree_cur *cur,
25030f712c9SDave Chinner union xfs_btree_ptr *ptr)
25130f712c9SDave Chinner {
25230f712c9SDave Chinner struct xfs_agi *agi = cur->bc_ag.agbp->b_addr;
253576af732SDave Chinner
25430f712c9SDave Chinner ASSERT(cur->bc_ag.pag->pag_agno == be32_to_cpu(agi->agi_seqno));
25550f02fe3SDave Chinner ptr->s = agi->agi_free_root;
25630f712c9SDave Chinner }
25730f712c9SDave Chinner
25830f712c9SDave Chinner STATIC int64_t
xfs_inobt_key_diff(struct xfs_btree_cur * cur,const union xfs_btree_key * key)259c8ce540dSDarrick J. Wong xfs_inobt_key_diff(
26030f712c9SDave Chinner struct xfs_btree_cur *cur,
26130f712c9SDave Chinner const union xfs_btree_key *key)
262d29d5577SDarrick J. Wong {
26330f712c9SDave Chinner return (int64_t)be32_to_cpu(key->inobt.ir_startino) -
264c8ce540dSDarrick J. Wong cur->bc_rec.i.ir_startino;
26530f712c9SDave Chinner }
26630f712c9SDave Chinner
26730f712c9SDave Chinner STATIC int64_t
xfs_inobt_diff_two_keys(struct xfs_btree_cur * cur,const union xfs_btree_key * k1,const union xfs_btree_key * k2,const union xfs_btree_key * mask)268118bb47eSDarrick J. Wong xfs_inobt_diff_two_keys(
269118bb47eSDarrick J. Wong struct xfs_btree_cur *cur,
270118bb47eSDarrick J. Wong const union xfs_btree_key *k1,
271d29d5577SDarrick J. Wong const union xfs_btree_key *k2,
272*4a200a09SDarrick J. Wong const union xfs_btree_key *mask)
273*4a200a09SDarrick J. Wong {
274118bb47eSDarrick J. Wong ASSERT(!mask || mask->inobt.ir_startino);
275*4a200a09SDarrick J. Wong
276*4a200a09SDarrick J. Wong return (int64_t)be32_to_cpu(k1->inobt.ir_startino) -
277118bb47eSDarrick J. Wong be32_to_cpu(k2->inobt.ir_startino);
278118bb47eSDarrick J. Wong }
279118bb47eSDarrick J. Wong
280118bb47eSDarrick J. Wong static xfs_failaddr_t
xfs_inobt_verify(struct xfs_buf * bp)281a6a781a5SDarrick J. Wong xfs_inobt_verify(
28230f712c9SDave Chinner struct xfs_buf *bp)
28330f712c9SDave Chinner {
28430f712c9SDave Chinner struct xfs_mount *mp = bp->b_mount;
285dbd329f1SChristoph Hellwig struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
28630f712c9SDave Chinner xfs_failaddr_t fa;
287a6a781a5SDarrick J. Wong unsigned int level;
28830f712c9SDave Chinner
28930f712c9SDave Chinner if (!xfs_verify_magic(bp, block->bb_magic))
2908473fee3SBrian Foster return __this_address;
2918473fee3SBrian Foster
2928473fee3SBrian Foster /*
29330f712c9SDave Chinner * During growfs operations, we can't verify the exact owner as the
29430f712c9SDave Chinner * perag is not fully initialised and hence not attached to the buffer.
29530f712c9SDave Chinner *
29630f712c9SDave Chinner * Similarly, during log recovery we will have a perag structure
29730f712c9SDave Chinner * attached, but the agi information will not yet have been initialised
29830f712c9SDave Chinner * from the on disk AGI. We don't currently use any of this information,
29930f712c9SDave Chinner * but beware of the landmine (i.e. need to check
3007ac2ff8bSDave Chinner * xfs_perag_initialised_agi(pag)) if we ever do.
3017ac2ff8bSDave Chinner */
30230f712c9SDave Chinner if (xfs_has_crc(mp)) {
303ebd9027dSDave Chinner fa = xfs_btree_sblock_v5hdr_verify(bp);
304a6a781a5SDarrick J. Wong if (fa)
305a6a781a5SDarrick J. Wong return fa;
306a6a781a5SDarrick J. Wong }
30730f712c9SDave Chinner
30830f712c9SDave Chinner /* level verification */
309c5ab131bSDarrick J. Wong level = be16_to_cpu(block->bb_level);
31030f712c9SDave Chinner if (level >= M_IGEO(mp)->inobt_maxlevels)
311ef325959SDarrick J. Wong return __this_address;
312a6a781a5SDarrick J. Wong
31330f712c9SDave Chinner return xfs_btree_sblock_verify(bp,
314ef325959SDarrick J. Wong M_IGEO(mp)->inobt_mxr[level != 0]);
315ef325959SDarrick J. Wong }
31630f712c9SDave Chinner
31730f712c9SDave Chinner static void
xfs_inobt_read_verify(struct xfs_buf * bp)31830f712c9SDave Chinner xfs_inobt_read_verify(
31930f712c9SDave Chinner struct xfs_buf *bp)
32030f712c9SDave Chinner {
32130f712c9SDave Chinner xfs_failaddr_t fa;
322bc1a09b8SDarrick J. Wong
323bc1a09b8SDarrick J. Wong if (!xfs_btree_sblock_verify_crc(bp))
32430f712c9SDave Chinner xfs_verifier_error(bp, -EFSBADCRC, __this_address);
325bc1a09b8SDarrick J. Wong else {
326bc1a09b8SDarrick J. Wong fa = xfs_inobt_verify(bp);
327bc1a09b8SDarrick J. Wong if (fa)
328bc1a09b8SDarrick J. Wong xfs_verifier_error(bp, -EFSCORRUPTED, fa);
329bc1a09b8SDarrick J. Wong }
330bc1a09b8SDarrick J. Wong
33130f712c9SDave Chinner if (bp->b_error)
33231ca03c9SDarrick J. Wong trace_xfs_btree_corrupt(bp, _RET_IP_);
33330f712c9SDave Chinner }
33430f712c9SDave Chinner
33530f712c9SDave Chinner static void
xfs_inobt_write_verify(struct xfs_buf * bp)33630f712c9SDave Chinner xfs_inobt_write_verify(
33730f712c9SDave Chinner struct xfs_buf *bp)
33830f712c9SDave Chinner {
33930f712c9SDave Chinner xfs_failaddr_t fa;
340bc1a09b8SDarrick J. Wong
341bc1a09b8SDarrick J. Wong fa = xfs_inobt_verify(bp);
342bc1a09b8SDarrick J. Wong if (fa) {
343bc1a09b8SDarrick J. Wong trace_xfs_btree_corrupt(bp, _RET_IP_);
34430f712c9SDave Chinner xfs_verifier_error(bp, -EFSCORRUPTED, fa);
345bc1a09b8SDarrick J. Wong return;
34630f712c9SDave Chinner }
34730f712c9SDave Chinner xfs_btree_sblock_calc_crc(bp);
34830f712c9SDave Chinner
34930f712c9SDave Chinner }
35030f712c9SDave Chinner
35130f712c9SDave Chinner const struct xfs_buf_ops xfs_inobt_buf_ops = {
35230f712c9SDave Chinner .name = "xfs_inobt",
353233135b7SEric Sandeen .magic = { cpu_to_be32(XFS_IBT_MAGIC), cpu_to_be32(XFS_IBT_CRC_MAGIC) },
3548473fee3SBrian Foster .verify_read = xfs_inobt_read_verify,
35530f712c9SDave Chinner .verify_write = xfs_inobt_write_verify,
35630f712c9SDave Chinner .verify_struct = xfs_inobt_verify,
357b5572597SDarrick J. Wong };
35830f712c9SDave Chinner
35930f712c9SDave Chinner const struct xfs_buf_ops xfs_finobt_buf_ops = {
36001e68f40SBrian Foster .name = "xfs_finobt",
36101e68f40SBrian Foster .magic = { cpu_to_be32(XFS_FIBT_MAGIC),
3628473fee3SBrian Foster cpu_to_be32(XFS_FIBT_CRC_MAGIC) },
3638473fee3SBrian Foster .verify_read = xfs_inobt_read_verify,
36401e68f40SBrian Foster .verify_write = xfs_inobt_write_verify,
36501e68f40SBrian Foster .verify_struct = xfs_inobt_verify,
36601e68f40SBrian Foster };
36701e68f40SBrian Foster
36801e68f40SBrian Foster STATIC int
xfs_inobt_keys_inorder(struct xfs_btree_cur * cur,const union xfs_btree_key * k1,const union xfs_btree_key * k2)36930f712c9SDave Chinner xfs_inobt_keys_inorder(
37030f712c9SDave Chinner struct xfs_btree_cur *cur,
37130f712c9SDave Chinner const union xfs_btree_key *k1,
3728e38dc88SDarrick J. Wong const union xfs_btree_key *k2)
3738e38dc88SDarrick J. Wong {
37430f712c9SDave Chinner return be32_to_cpu(k1->inobt.ir_startino) <
37530f712c9SDave Chinner be32_to_cpu(k2->inobt.ir_startino);
37630f712c9SDave Chinner }
37730f712c9SDave Chinner
37830f712c9SDave Chinner STATIC int
xfs_inobt_recs_inorder(struct xfs_btree_cur * cur,const union xfs_btree_rec * r1,const union xfs_btree_rec * r2)37930f712c9SDave Chinner xfs_inobt_recs_inorder(
38030f712c9SDave Chinner struct xfs_btree_cur *cur,
38130f712c9SDave Chinner const union xfs_btree_rec *r1,
3828e38dc88SDarrick J. Wong const union xfs_btree_rec *r2)
3838e38dc88SDarrick J. Wong {
38430f712c9SDave Chinner return be32_to_cpu(r1->inobt.ir_startino) + XFS_INODES_PER_CHUNK <=
38530f712c9SDave Chinner be32_to_cpu(r2->inobt.ir_startino);
38630f712c9SDave Chinner }
38730f712c9SDave Chinner
38830f712c9SDave Chinner STATIC enum xbtree_key_contig
xfs_inobt_keys_contiguous(struct xfs_btree_cur * cur,const union xfs_btree_key * key1,const union xfs_btree_key * key2,const union xfs_btree_key * mask)3896abc7aefSDarrick J. Wong xfs_inobt_keys_contiguous(
3906abc7aefSDarrick J. Wong struct xfs_btree_cur *cur,
3916abc7aefSDarrick J. Wong const union xfs_btree_key *key1,
3926abc7aefSDarrick J. Wong const union xfs_btree_key *key2,
393*4a200a09SDarrick J. Wong const union xfs_btree_key *mask)
394*4a200a09SDarrick J. Wong {
3956abc7aefSDarrick J. Wong ASSERT(!mask || mask->inobt.ir_startino);
396*4a200a09SDarrick J. Wong
397*4a200a09SDarrick J. Wong return xbtree_key_contig(be32_to_cpu(key1->inobt.ir_startino),
3986abc7aefSDarrick J. Wong be32_to_cpu(key2->inobt.ir_startino));
3996abc7aefSDarrick J. Wong }
4006abc7aefSDarrick J. Wong
4016abc7aefSDarrick J. Wong static const struct xfs_btree_ops xfs_inobt_ops = {
40230f712c9SDave Chinner .rec_len = sizeof(xfs_inobt_rec_t),
40330f712c9SDave Chinner .key_len = sizeof(xfs_inobt_key_t),
40430f712c9SDave Chinner
40530f712c9SDave Chinner .dup_cursor = xfs_inobt_dup_cursor,
40630f712c9SDave Chinner .set_root = xfs_inobt_set_root,
40730f712c9SDave Chinner .alloc_block = xfs_inobt_alloc_block,
40830f712c9SDave Chinner .free_block = xfs_inobt_free_block,
40930f712c9SDave Chinner .get_minrecs = xfs_inobt_get_minrecs,
41030f712c9SDave Chinner .get_maxrecs = xfs_inobt_get_maxrecs,
41130f712c9SDave Chinner .init_key_from_rec = xfs_inobt_init_key_from_rec,
41230f712c9SDave Chinner .init_high_key_from_rec = xfs_inobt_init_high_key_from_rec,
413118bb47eSDarrick J. Wong .init_rec_from_cur = xfs_inobt_init_rec_from_cur,
41430f712c9SDave Chinner .init_ptr_from_cur = xfs_inobt_init_ptr_from_cur,
41530f712c9SDave Chinner .key_diff = xfs_inobt_key_diff,
41630f712c9SDave Chinner .buf_ops = &xfs_inobt_buf_ops,
41730f712c9SDave Chinner .diff_two_keys = xfs_inobt_diff_two_keys,
418118bb47eSDarrick J. Wong .keys_inorder = xfs_inobt_keys_inorder,
41930f712c9SDave Chinner .recs_inorder = xfs_inobt_recs_inorder,
42030f712c9SDave Chinner .keys_contiguous = xfs_inobt_keys_contiguous,
4216abc7aefSDarrick J. Wong };
42230f712c9SDave Chinner
42330f712c9SDave Chinner static const struct xfs_btree_ops xfs_finobt_ops = {
42430f712c9SDave Chinner .rec_len = sizeof(xfs_inobt_rec_t),
42530f712c9SDave Chinner .key_len = sizeof(xfs_inobt_key_t),
42630f712c9SDave Chinner
42730f712c9SDave Chinner .dup_cursor = xfs_inobt_dup_cursor,
42830f712c9SDave Chinner .set_root = xfs_finobt_set_root,
42930f712c9SDave Chinner .alloc_block = xfs_finobt_alloc_block,
43076d771b4SChristoph Hellwig .free_block = xfs_finobt_free_block,
431ad90bb58SBrian Foster .get_minrecs = xfs_inobt_get_minrecs,
43230f712c9SDave Chinner .get_maxrecs = xfs_inobt_get_maxrecs,
43330f712c9SDave Chinner .init_key_from_rec = xfs_inobt_init_key_from_rec,
43430f712c9SDave Chinner .init_high_key_from_rec = xfs_inobt_init_high_key_from_rec,
435118bb47eSDarrick J. Wong .init_rec_from_cur = xfs_inobt_init_rec_from_cur,
43630f712c9SDave Chinner .init_ptr_from_cur = xfs_finobt_init_ptr_from_cur,
43730f712c9SDave Chinner .key_diff = xfs_inobt_key_diff,
43830f712c9SDave Chinner .buf_ops = &xfs_finobt_buf_ops,
43901e68f40SBrian Foster .diff_two_keys = xfs_inobt_diff_two_keys,
440118bb47eSDarrick J. Wong .keys_inorder = xfs_inobt_keys_inorder,
44130f712c9SDave Chinner .recs_inorder = xfs_inobt_recs_inorder,
44230f712c9SDave Chinner .keys_contiguous = xfs_inobt_keys_contiguous,
4436abc7aefSDarrick J. Wong };
44430f712c9SDave Chinner
44530f712c9SDave Chinner /*
44630f712c9SDave Chinner * Initialize a new inode btree cursor.
447c29ce8f4SDarrick J. Wong */
44830f712c9SDave Chinner static struct xfs_btree_cur *
xfs_inobt_init_common(struct xfs_perag * pag,struct xfs_trans * tp,xfs_btnum_t btnum)449c29ce8f4SDarrick J. Wong xfs_inobt_init_common(
450c29ce8f4SDarrick J. Wong struct xfs_perag *pag,
451be9fb17dSDave Chinner struct xfs_trans *tp, /* transaction pointer */
452bab8b795SDave Chinner xfs_btnum_t btnum) /* ialloc or free ino btree */
45330f712c9SDave Chinner {
45430f712c9SDave Chinner struct xfs_mount *mp = pag->pag_mount;
455bab8b795SDave Chinner struct xfs_btree_cur *cur;
45630f712c9SDave Chinner
45730f712c9SDave Chinner cur = xfs_btree_alloc_cursor(mp, tp, btnum,
458c940a0c5SDarrick J. Wong M_IGEO(mp)->inobt_maxlevels, xfs_inobt_cur_cache);
4599fa47bdcSDarrick J. Wong if (btnum == XFS_BTNUM_INO) {
46030f712c9SDave Chinner cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_ibt_2);
46111ef38afSDave Chinner cur->bc_ops = &xfs_inobt_ops;
462c29ce8f4SDarrick J. Wong } else {
46330f712c9SDave Chinner cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_fibt_2);
46411ef38afSDave Chinner cur->bc_ops = &xfs_finobt_ops;
465c29ce8f4SDarrick J. Wong }
46630f712c9SDave Chinner
46730f712c9SDave Chinner if (xfs_has_crc(mp))
46838c26bfdSDave Chinner cur->bc_flags |= XFS_BTREE_CRC_BLOCKS;
46930f712c9SDave Chinner
47030f712c9SDave Chinner cur->bc_ag.pag = xfs_perag_hold(pag);
4719b2e5a23SDarrick J. Wong return cur;
47230f712c9SDave Chinner }
47330f712c9SDave Chinner
47430f712c9SDave Chinner /* Create an inode btree cursor. */
475c29ce8f4SDarrick J. Wong struct xfs_btree_cur *
xfs_inobt_init_cursor(struct xfs_perag * pag,struct xfs_trans * tp,struct xfs_buf * agbp,xfs_btnum_t btnum)476c29ce8f4SDarrick J. Wong xfs_inobt_init_cursor(
477c29ce8f4SDarrick J. Wong struct xfs_perag *pag,
478bab8b795SDave Chinner struct xfs_trans *tp,
479c29ce8f4SDarrick J. Wong struct xfs_buf *agbp,
480c29ce8f4SDarrick J. Wong xfs_btnum_t btnum)
481c29ce8f4SDarrick J. Wong {
482c29ce8f4SDarrick J. Wong struct xfs_btree_cur *cur;
483c29ce8f4SDarrick J. Wong struct xfs_agi *agi = agbp->b_addr;
484c29ce8f4SDarrick J. Wong
485c29ce8f4SDarrick J. Wong cur = xfs_inobt_init_common(pag, tp, btnum);
486bab8b795SDave Chinner if (btnum == XFS_BTNUM_INO)
487c29ce8f4SDarrick J. Wong cur->bc_nlevels = be32_to_cpu(agi->agi_level);
488c29ce8f4SDarrick J. Wong else
489c29ce8f4SDarrick J. Wong cur->bc_nlevels = be32_to_cpu(agi->agi_free_level);
490c29ce8f4SDarrick J. Wong cur->bc_ag.agbp = agbp;
491c29ce8f4SDarrick J. Wong return cur;
492c29ce8f4SDarrick J. Wong }
493c29ce8f4SDarrick J. Wong
494c29ce8f4SDarrick J. Wong /* Create an inode btree cursor with a fake root for staging. */
495c29ce8f4SDarrick J. Wong struct xfs_btree_cur *
xfs_inobt_stage_cursor(struct xfs_perag * pag,struct xbtree_afakeroot * afake,xfs_btnum_t btnum)496c29ce8f4SDarrick J. Wong xfs_inobt_stage_cursor(
497c29ce8f4SDarrick J. Wong struct xfs_perag *pag,
4987b13c515SDave Chinner struct xbtree_afakeroot *afake,
499bab8b795SDave Chinner xfs_btnum_t btnum)
500c29ce8f4SDarrick J. Wong {
501c29ce8f4SDarrick J. Wong struct xfs_btree_cur *cur;
502c29ce8f4SDarrick J. Wong
503c29ce8f4SDarrick J. Wong cur = xfs_inobt_init_common(pag, NULL, btnum);
504bab8b795SDave Chinner xfs_btree_stage_afakeroot(cur, afake);
505c29ce8f4SDarrick J. Wong return cur;
506c29ce8f4SDarrick J. Wong }
507c29ce8f4SDarrick J. Wong
508c29ce8f4SDarrick J. Wong /*
509c29ce8f4SDarrick J. Wong * Install a new inobt btree root. Caller is responsible for invalidating
510c29ce8f4SDarrick J. Wong * and freeing the old btree blocks.
511c29ce8f4SDarrick J. Wong */
512c29ce8f4SDarrick J. Wong void
xfs_inobt_commit_staged_btree(struct xfs_btree_cur * cur,struct xfs_trans * tp,struct xfs_buf * agbp)513c29ce8f4SDarrick J. Wong xfs_inobt_commit_staged_btree(
514c29ce8f4SDarrick J. Wong struct xfs_btree_cur *cur,
515c29ce8f4SDarrick J. Wong struct xfs_trans *tp,
516c29ce8f4SDarrick J. Wong struct xfs_buf *agbp)
517c29ce8f4SDarrick J. Wong {
518c29ce8f4SDarrick J. Wong struct xfs_agi *agi = agbp->b_addr;
519c29ce8f4SDarrick J. Wong struct xbtree_afakeroot *afake = cur->bc_ag.afake;
520c29ce8f4SDarrick J. Wong int fields;
52111f74423SDarrick J. Wong
522c29ce8f4SDarrick J. Wong ASSERT(cur->bc_flags & XFS_BTREE_STAGING);
523c29ce8f4SDarrick J. Wong
524c29ce8f4SDarrick J. Wong if (cur->bc_btnum == XFS_BTNUM_INO) {
525c29ce8f4SDarrick J. Wong fields = XFS_AGI_ROOT | XFS_AGI_LEVEL;
52611f74423SDarrick J. Wong agi->agi_root = cpu_to_be32(afake->af_root);
527c29ce8f4SDarrick J. Wong agi->agi_level = cpu_to_be32(afake->af_levels);
528c29ce8f4SDarrick J. Wong if (xfs_has_inobtcounts(cur->bc_mp)) {
529ebd9027dSDave Chinner agi->agi_iblocks = cpu_to_be32(afake->af_blocks);
53011f74423SDarrick J. Wong fields |= XFS_AGI_IBLOCKS;
53111f74423SDarrick J. Wong }
53211f74423SDarrick J. Wong xfs_ialloc_log_agi(tp, agbp, fields);
53311f74423SDarrick J. Wong xfs_btree_commit_afakeroot(cur, tp, agbp, &xfs_inobt_ops);
534c29ce8f4SDarrick J. Wong } else {
535c29ce8f4SDarrick J. Wong fields = XFS_AGI_FREE_ROOT | XFS_AGI_FREE_LEVEL;
53611f74423SDarrick J. Wong agi->agi_free_root = cpu_to_be32(afake->af_root);
537c29ce8f4SDarrick J. Wong agi->agi_free_level = cpu_to_be32(afake->af_levels);
538c29ce8f4SDarrick J. Wong if (xfs_has_inobtcounts(cur->bc_mp)) {
539ebd9027dSDave Chinner agi->agi_fblocks = cpu_to_be32(afake->af_blocks);
54011f74423SDarrick J. Wong fields |= XFS_AGI_IBLOCKS;
54111f74423SDarrick J. Wong }
54211f74423SDarrick J. Wong xfs_ialloc_log_agi(tp, agbp, fields);
54311f74423SDarrick J. Wong xfs_btree_commit_afakeroot(cur, tp, agbp, &xfs_finobt_ops);
544c29ce8f4SDarrick J. Wong }
545c29ce8f4SDarrick J. Wong }
546c29ce8f4SDarrick J. Wong
547c29ce8f4SDarrick J. Wong /* Calculate number of records in an inode btree block. */
5480ed5f735SDarrick J. Wong static inline unsigned int
xfs_inobt_block_maxrecs(unsigned int blocklen,bool leaf)5490ed5f735SDarrick J. Wong xfs_inobt_block_maxrecs(
5500ed5f735SDarrick J. Wong unsigned int blocklen,
5510ed5f735SDarrick J. Wong bool leaf)
5520ed5f735SDarrick J. Wong {
5530ed5f735SDarrick J. Wong if (leaf)
5540ed5f735SDarrick J. Wong return blocklen / sizeof(xfs_inobt_rec_t);
5550ed5f735SDarrick J. Wong return blocklen / (sizeof(xfs_inobt_key_t) + sizeof(xfs_inobt_ptr_t));
5560ed5f735SDarrick J. Wong }
5570ed5f735SDarrick J. Wong
5580ed5f735SDarrick J. Wong /*
55930f712c9SDave Chinner * Calculate number of records in an inobt btree block.
56030f712c9SDave Chinner */
56130f712c9SDave Chinner int
xfs_inobt_maxrecs(struct xfs_mount * mp,int blocklen,int leaf)56230f712c9SDave Chinner xfs_inobt_maxrecs(
56330f712c9SDave Chinner struct xfs_mount *mp,
56430f712c9SDave Chinner int blocklen,
56530f712c9SDave Chinner int leaf)
56630f712c9SDave Chinner {
56730f712c9SDave Chinner blocklen -= XFS_INOBT_BLOCK_LEN(mp);
56830f712c9SDave Chinner return xfs_inobt_block_maxrecs(blocklen, leaf);
5690ed5f735SDarrick J. Wong }
5700ed5f735SDarrick J. Wong
57130f712c9SDave Chinner /*
5720ed5f735SDarrick J. Wong * Maximum number of inode btree records per AG. Pretend that we can fill an
5730ed5f735SDarrick J. Wong * entire AG completely full of inodes except for the AG headers.
5740ed5f735SDarrick J. Wong */
5750ed5f735SDarrick J. Wong #define XFS_MAX_INODE_RECORDS \
5760ed5f735SDarrick J. Wong ((XFS_MAX_AG_BYTES - (4 * BBSIZE)) / XFS_DINODE_MIN_SIZE) / \
5770ed5f735SDarrick J. Wong XFS_INODES_PER_CHUNK
5780ed5f735SDarrick J. Wong
5790ed5f735SDarrick J. Wong /* Compute the max possible height for the inode btree. */
5800ed5f735SDarrick J. Wong static inline unsigned int
xfs_inobt_maxlevels_ondisk(void)5810ed5f735SDarrick J. Wong xfs_inobt_maxlevels_ondisk(void)
5820ed5f735SDarrick J. Wong {
5830ed5f735SDarrick J. Wong unsigned int minrecs[2];
5840ed5f735SDarrick J. Wong unsigned int blocklen;
5850ed5f735SDarrick J. Wong
5860ed5f735SDarrick J. Wong blocklen = min(XFS_MIN_BLOCKSIZE - XFS_BTREE_SBLOCK_LEN,
5870ed5f735SDarrick J. Wong XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN);
5880ed5f735SDarrick J. Wong
5890ed5f735SDarrick J. Wong minrecs[0] = xfs_inobt_block_maxrecs(blocklen, true) / 2;
5900ed5f735SDarrick J. Wong minrecs[1] = xfs_inobt_block_maxrecs(blocklen, false) / 2;
5910ed5f735SDarrick J. Wong
5920ed5f735SDarrick J. Wong return xfs_btree_compute_maxlevels(minrecs, XFS_MAX_INODE_RECORDS);
5930ed5f735SDarrick J. Wong }
5940ed5f735SDarrick J. Wong
5950ed5f735SDarrick J. Wong /* Compute the max possible height for the free inode btree. */
5960ed5f735SDarrick J. Wong static inline unsigned int
xfs_finobt_maxlevels_ondisk(void)5970ed5f735SDarrick J. Wong xfs_finobt_maxlevels_ondisk(void)
5980ed5f735SDarrick J. Wong {
5990ed5f735SDarrick J. Wong unsigned int minrecs[2];
6000ed5f735SDarrick J. Wong unsigned int blocklen;
6010ed5f735SDarrick J. Wong
6020ed5f735SDarrick J. Wong blocklen = XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN;
6030ed5f735SDarrick J. Wong
6040ed5f735SDarrick J. Wong minrecs[0] = xfs_inobt_block_maxrecs(blocklen, true) / 2;
6050ed5f735SDarrick J. Wong minrecs[1] = xfs_inobt_block_maxrecs(blocklen, false) / 2;
6060ed5f735SDarrick J. Wong
6070ed5f735SDarrick J. Wong return xfs_btree_compute_maxlevels(minrecs, XFS_MAX_INODE_RECORDS);
6080ed5f735SDarrick J. Wong }
6090ed5f735SDarrick J. Wong
6100ed5f735SDarrick J. Wong /* Compute the max possible height for either inode btree. */
6110ed5f735SDarrick J. Wong unsigned int
xfs_iallocbt_maxlevels_ondisk(void)6120ed5f735SDarrick J. Wong xfs_iallocbt_maxlevels_ondisk(void)
6130ed5f735SDarrick J. Wong {
6140ed5f735SDarrick J. Wong return max(xfs_inobt_maxlevels_ondisk(),
6150ed5f735SDarrick J. Wong xfs_finobt_maxlevels_ondisk());
6160ed5f735SDarrick J. Wong }
61730f712c9SDave Chinner
6184148c347SBrian Foster /*
6194148c347SBrian Foster * Convert the inode record holemask to an inode allocation bitmap. The inode
6204148c347SBrian Foster * allocation bitmap is inode granularity and specifies whether an inode is
6214148c347SBrian Foster * physically allocated on disk (not whether the inode is considered allocated
6224148c347SBrian Foster * or free by the fs).
6234148c347SBrian Foster *
6244148c347SBrian Foster * A bit value of 1 means the inode is allocated, a value of 0 means it is free.
6254148c347SBrian Foster */
6264148c347SBrian Foster uint64_t
xfs_inobt_irec_to_allocmask(const struct xfs_inobt_rec_incore * rec)6274148c347SBrian Foster xfs_inobt_irec_to_allocmask(
6284148c347SBrian Foster const struct xfs_inobt_rec_incore *rec)
629366a0b8dSDarrick J. Wong {
6304148c347SBrian Foster uint64_t bitmap = 0;
6314148c347SBrian Foster uint64_t inodespbit;
6324148c347SBrian Foster int nextbit;
6334148c347SBrian Foster uint allocbitmap;
6344148c347SBrian Foster
6354148c347SBrian Foster /*
6364148c347SBrian Foster * The holemask has 16-bits for a 64 inode record. Therefore each
6374148c347SBrian Foster * holemask bit represents multiple inodes. Create a mask of bits to set
6384148c347SBrian Foster * in the allocmask for each holemask bit.
6394148c347SBrian Foster */
6404148c347SBrian Foster inodespbit = (1 << XFS_INODES_PER_HOLEMASK_BIT) - 1;
6414148c347SBrian Foster
6424148c347SBrian Foster /*
6434148c347SBrian Foster * Allocated inodes are represented by 0 bits in holemask. Invert the 0
6444148c347SBrian Foster * bits to 1 and convert to a uint so we can use xfs_next_bit(). Mask
6454148c347SBrian Foster * anything beyond the 16 holemask bits since this casts to a larger
6464148c347SBrian Foster * type.
6474148c347SBrian Foster */
6484148c347SBrian Foster allocbitmap = ~rec->ir_holemask & ((1 << XFS_INOBT_HOLEMASK_BITS) - 1);
6494148c347SBrian Foster
6504148c347SBrian Foster /*
6514148c347SBrian Foster * allocbitmap is the inverted holemask so every set bit represents
6524148c347SBrian Foster * allocated inodes. To expand from 16-bit holemask granularity to
6534148c347SBrian Foster * 64-bit (e.g., bit-per-inode), set inodespbit bits in the target
6544148c347SBrian Foster * bitmap for every holemask bit.
6554148c347SBrian Foster */
6564148c347SBrian Foster nextbit = xfs_next_bit(&allocbitmap, 1, 0);
6574148c347SBrian Foster while (nextbit != -1) {
6584148c347SBrian Foster ASSERT(nextbit < (sizeof(rec->ir_holemask) * NBBY));
6594148c347SBrian Foster
6604148c347SBrian Foster bitmap |= (inodespbit <<
6614148c347SBrian Foster (nextbit * XFS_INODES_PER_HOLEMASK_BIT));
6624148c347SBrian Foster
6634148c347SBrian Foster nextbit = xfs_next_bit(&allocbitmap, 1, nextbit + 1);
6644148c347SBrian Foster }
6654148c347SBrian Foster
6664148c347SBrian Foster return bitmap;
6674148c347SBrian Foster }
6684148c347SBrian Foster
66956d1115cSBrian Foster #if defined(DEBUG) || defined(XFS_WARN)
67056d1115cSBrian Foster /*
67156d1115cSBrian Foster * Verify that an in-core inode record has a valid inode count.
67256d1115cSBrian Foster */
67356d1115cSBrian Foster int
xfs_inobt_rec_check_count(struct xfs_mount * mp,struct xfs_inobt_rec_incore * rec)67456d1115cSBrian Foster xfs_inobt_rec_check_count(
67556d1115cSBrian Foster struct xfs_mount *mp,
67656d1115cSBrian Foster struct xfs_inobt_rec_incore *rec)
67756d1115cSBrian Foster {
67856d1115cSBrian Foster int inocount = 0;
67956d1115cSBrian Foster int nextbit = 0;
68056d1115cSBrian Foster uint64_t allocbmap;
68156d1115cSBrian Foster int wordsz;
68256d1115cSBrian Foster
68356d1115cSBrian Foster wordsz = sizeof(allocbmap) / sizeof(unsigned int);
68456d1115cSBrian Foster allocbmap = xfs_inobt_irec_to_allocmask(rec);
68556d1115cSBrian Foster
68656d1115cSBrian Foster nextbit = xfs_next_bit((uint *) &allocbmap, wordsz, nextbit);
68756d1115cSBrian Foster while (nextbit != -1) {
68856d1115cSBrian Foster inocount++;
68956d1115cSBrian Foster nextbit = xfs_next_bit((uint *) &allocbmap, wordsz,
69056d1115cSBrian Foster nextbit + 1);
69156d1115cSBrian Foster }
69256d1115cSBrian Foster
69356d1115cSBrian Foster if (inocount != rec->ir_count)
69456d1115cSBrian Foster return -EFSCORRUPTED;
69556d1115cSBrian Foster
69656d1115cSBrian Foster return 0;
69756d1115cSBrian Foster }
69856d1115cSBrian Foster #endif /* DEBUG */
69956d1115cSBrian Foster
70076d771b4SChristoph Hellwig static xfs_extlen_t
xfs_inobt_max_size(struct xfs_perag * pag)70176d771b4SChristoph Hellwig xfs_inobt_max_size(
70276d771b4SChristoph Hellwig struct xfs_perag *pag)
7033829c9a1SDave Chinner {
70476d771b4SChristoph Hellwig struct xfs_mount *mp = pag->pag_mount;
7053829c9a1SDave Chinner xfs_agblock_t agblocks = pag->block_count;
7063829c9a1SDave Chinner
707c0876897SDave Chinner /* Bail out if we're uninitialized, which can happen in mkfs. */
70876d771b4SChristoph Hellwig if (M_IGEO(mp)->inobt_mxr[0] == 0)
709ef325959SDarrick J. Wong return 0;
71076d771b4SChristoph Hellwig
71176d771b4SChristoph Hellwig /*
7125cd213b0SDarrick J. Wong * The log is permanently allocated, so the space it occupies will
7135cd213b0SDarrick J. Wong * never be available for the kinds of things that would require btree
7145cd213b0SDarrick J. Wong * expansion. We therefore can pretend the space isn't there.
7155cd213b0SDarrick J. Wong */
7165cd213b0SDarrick J. Wong if (xfs_ag_contains_log(mp, pag->pag_agno))
71736029deeSDave Chinner agblocks -= mp->m_sb.sb_logblocks;
7185cd213b0SDarrick J. Wong
7195cd213b0SDarrick J. Wong return xfs_btree_calc_size(M_IGEO(mp)->inobt_mnr,
720ef325959SDarrick J. Wong (uint64_t)agblocks * mp->m_sb.sb_inopblock /
721c0876897SDave Chinner XFS_INODES_PER_CHUNK);
72276d771b4SChristoph Hellwig }
72376d771b4SChristoph Hellwig
72476d771b4SChristoph Hellwig /* Read AGI and create inobt cursor. */
725a211432cSDarrick J. Wong int
xfs_inobt_cur(struct xfs_perag * pag,struct xfs_trans * tp,xfs_btnum_t which,struct xfs_btree_cur ** curpp,struct xfs_buf ** agi_bpp)726a211432cSDarrick J. Wong xfs_inobt_cur(
727a211432cSDarrick J. Wong struct xfs_perag *pag,
7287b13c515SDave Chinner struct xfs_trans *tp,
729bab8b795SDave Chinner xfs_btnum_t which,
730a211432cSDarrick J. Wong struct xfs_btree_cur **curpp,
731a211432cSDarrick J. Wong struct xfs_buf **agi_bpp)
732a211432cSDarrick J. Wong {
733a211432cSDarrick J. Wong struct xfs_btree_cur *cur;
734a211432cSDarrick J. Wong int error;
735a211432cSDarrick J. Wong
736a211432cSDarrick J. Wong ASSERT(*agi_bpp == NULL);
737a211432cSDarrick J. Wong ASSERT(*curpp == NULL);
738a211432cSDarrick J. Wong
739a211432cSDarrick J. Wong error = xfs_ialloc_read_agi(pag, tp, agi_bpp);
74099b13c7fSDave Chinner if (error)
741a211432cSDarrick J. Wong return error;
742a211432cSDarrick J. Wong
743a211432cSDarrick J. Wong cur = xfs_inobt_init_cursor(pag, tp, *agi_bpp, which);
744bab8b795SDave Chinner *curpp = cur;
745a211432cSDarrick J. Wong return 0;
746a211432cSDarrick J. Wong }
747a211432cSDarrick J. Wong
748a211432cSDarrick J. Wong static int
xfs_inobt_count_blocks(struct xfs_perag * pag,struct xfs_trans * tp,xfs_btnum_t btnum,xfs_extlen_t * tree_blocks)74976d771b4SChristoph Hellwig xfs_inobt_count_blocks(
75076d771b4SChristoph Hellwig struct xfs_perag *pag,
75130933120SDave Chinner struct xfs_trans *tp,
752bab8b795SDave Chinner xfs_btnum_t btnum,
75376d771b4SChristoph Hellwig xfs_extlen_t *tree_blocks)
75476d771b4SChristoph Hellwig {
75576d771b4SChristoph Hellwig struct xfs_buf *agbp = NULL;
756a211432cSDarrick J. Wong struct xfs_btree_cur *cur = NULL;
757a211432cSDarrick J. Wong int error;
75876d771b4SChristoph Hellwig
75976d771b4SChristoph Hellwig error = xfs_inobt_cur(pag, tp, btnum, &cur, &agbp);
760bab8b795SDave Chinner if (error)
76176d771b4SChristoph Hellwig return error;
76276d771b4SChristoph Hellwig
76376d771b4SChristoph Hellwig error = xfs_btree_count_blocks(cur, tree_blocks);
76476d771b4SChristoph Hellwig xfs_btree_del_cursor(cur, error);
7650b04b6b8SDarrick J. Wong xfs_trans_brelse(tp, agbp);
766ebcbef3aSDarrick J. Wong
76776d771b4SChristoph Hellwig return error;
76876d771b4SChristoph Hellwig }
76976d771b4SChristoph Hellwig
77076d771b4SChristoph Hellwig /* Read finobt block count from AGI header. */
7711ac35f06SDarrick J. Wong static int
xfs_finobt_read_blocks(struct xfs_perag * pag,struct xfs_trans * tp,xfs_extlen_t * tree_blocks)7721ac35f06SDarrick J. Wong xfs_finobt_read_blocks(
7731ac35f06SDarrick J. Wong struct xfs_perag *pag,
77430933120SDave Chinner struct xfs_trans *tp,
77599b13c7fSDave Chinner xfs_extlen_t *tree_blocks)
7761ac35f06SDarrick J. Wong {
7771ac35f06SDarrick J. Wong struct xfs_buf *agbp;
7781ac35f06SDarrick J. Wong struct xfs_agi *agi;
7791ac35f06SDarrick J. Wong int error;
7801ac35f06SDarrick J. Wong
7811ac35f06SDarrick J. Wong error = xfs_ialloc_read_agi(pag, tp, &agbp);
78299b13c7fSDave Chinner if (error)
7831ac35f06SDarrick J. Wong return error;
7841ac35f06SDarrick J. Wong
7851ac35f06SDarrick J. Wong agi = agbp->b_addr;
7861ac35f06SDarrick J. Wong *tree_blocks = be32_to_cpu(agi->agi_fblocks);
7871ac35f06SDarrick J. Wong xfs_trans_brelse(tp, agbp);
7881ac35f06SDarrick J. Wong return 0;
7891ac35f06SDarrick J. Wong }
7901ac35f06SDarrick J. Wong
7911ac35f06SDarrick J. Wong /*
79276d771b4SChristoph Hellwig * Figure out how many blocks to reserve and how many are used by this btree.
79376d771b4SChristoph Hellwig */
79476d771b4SChristoph Hellwig int
xfs_finobt_calc_reserves(struct xfs_perag * pag,struct xfs_trans * tp,xfs_extlen_t * ask,xfs_extlen_t * used)79576d771b4SChristoph Hellwig xfs_finobt_calc_reserves(
79676d771b4SChristoph Hellwig struct xfs_perag *pag,
79730933120SDave Chinner struct xfs_trans *tp,
798bab8b795SDave Chinner xfs_extlen_t *ask,
79976d771b4SChristoph Hellwig xfs_extlen_t *used)
80076d771b4SChristoph Hellwig {
80176d771b4SChristoph Hellwig xfs_extlen_t tree_len = 0;
80276d771b4SChristoph Hellwig int error;
80376d771b4SChristoph Hellwig
80476d771b4SChristoph Hellwig if (!xfs_has_finobt(pag->pag_mount))
805bab8b795SDave Chinner return 0;
80676d771b4SChristoph Hellwig
80776d771b4SChristoph Hellwig if (xfs_has_inobtcounts(pag->pag_mount))
808bab8b795SDave Chinner error = xfs_finobt_read_blocks(pag, tp, &tree_len);
80999b13c7fSDave Chinner else
8101ac35f06SDarrick J. Wong error = xfs_inobt_count_blocks(pag, tp, XFS_BTNUM_FINO,
811bab8b795SDave Chinner &tree_len);
8121ac35f06SDarrick J. Wong if (error)
81376d771b4SChristoph Hellwig return error;
81476d771b4SChristoph Hellwig
81576d771b4SChristoph Hellwig *ask += xfs_inobt_max_size(pag);
8163829c9a1SDave Chinner *used += tree_len;
81776d771b4SChristoph Hellwig return 0;
81876d771b4SChristoph Hellwig }
81976d771b4SChristoph Hellwig
82014861c47SDarrick J. Wong /* Calculate the inobt btree size for some records. */
82114861c47SDarrick J. Wong xfs_extlen_t
xfs_iallocbt_calc_size(struct xfs_mount * mp,unsigned long long len)82214861c47SDarrick J. Wong xfs_iallocbt_calc_size(
82314861c47SDarrick J. Wong struct xfs_mount *mp,
82414861c47SDarrick J. Wong unsigned long long len)
82514861c47SDarrick J. Wong {
82614861c47SDarrick J. Wong return xfs_btree_calc_size(M_IGEO(mp)->inobt_mnr, len);
827ef325959SDarrick J. Wong }
82814861c47SDarrick J. Wong
8299fa47bdcSDarrick J. Wong int __init
xfs_inobt_init_cur_cache(void)8309fa47bdcSDarrick J. Wong xfs_inobt_init_cur_cache(void)
8319fa47bdcSDarrick J. Wong {
8329fa47bdcSDarrick J. Wong xfs_inobt_cur_cache = kmem_cache_create("xfs_inobt_cur",
8339fa47bdcSDarrick J. Wong xfs_btree_cur_sizeof(xfs_inobt_maxlevels_ondisk()),
8349fa47bdcSDarrick J. Wong 0, 0, NULL);
8359fa47bdcSDarrick J. Wong
8369fa47bdcSDarrick J. Wong if (!xfs_inobt_cur_cache)
8379fa47bdcSDarrick J. Wong return -ENOMEM;
8389fa47bdcSDarrick J. Wong return 0;
8399fa47bdcSDarrick J. Wong }
8409fa47bdcSDarrick J. Wong
8419fa47bdcSDarrick J. Wong void
xfs_inobt_destroy_cur_cache(void)8429fa47bdcSDarrick J. Wong xfs_inobt_destroy_cur_cache(void)
8439fa47bdcSDarrick J. Wong {
8449fa47bdcSDarrick J. Wong kmem_cache_destroy(xfs_inobt_cur_cache);
8459fa47bdcSDarrick J. Wong xfs_inobt_cur_cache = NULL;
8469fa47bdcSDarrick J. Wong }
8479fa47bdcSDarrick J. Wong