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_mount.h" 1330f712c9SDave Chinner #include "xfs_btree.h" 14e6eb33d9SDarrick J. Wong #include "xfs_btree_staging.h" 1530f712c9SDave Chinner #include "xfs_alloc_btree.h" 1630f712c9SDave Chinner #include "xfs_alloc.h" 1730f712c9SDave Chinner #include "xfs_extent_busy.h" 1830f712c9SDave Chinner #include "xfs_error.h" 1930f712c9SDave Chinner #include "xfs_trace.h" 2030f712c9SDave Chinner #include "xfs_trans.h" 219bbafc71SDave Chinner #include "xfs_ag.h" 2230f712c9SDave Chinner 2330f712c9SDave Chinner 2430f712c9SDave Chinner STATIC struct xfs_btree_cur * 2530f712c9SDave Chinner xfs_allocbt_dup_cursor( 2630f712c9SDave Chinner struct xfs_btree_cur *cur) 2730f712c9SDave Chinner { 2830f712c9SDave Chinner return xfs_allocbt_init_cursor(cur->bc_mp, cur->bc_tp, 29289d38d2SDave Chinner cur->bc_ag.agbp, cur->bc_ag.pag, cur->bc_btnum); 3030f712c9SDave Chinner } 3130f712c9SDave Chinner 3230f712c9SDave Chinner STATIC void 3330f712c9SDave Chinner xfs_allocbt_set_root( 3430f712c9SDave Chinner struct xfs_btree_cur *cur, 35b5a6e5feSDarrick J. Wong const union xfs_btree_ptr *ptr, 3630f712c9SDave Chinner int inc) 3730f712c9SDave Chinner { 38576af732SDave Chinner struct xfs_buf *agbp = cur->bc_ag.agbp; 399798f615SChristoph Hellwig struct xfs_agf *agf = agbp->b_addr; 4030f712c9SDave Chinner int btnum = cur->bc_btnum; 4130f712c9SDave Chinner 4230f712c9SDave Chinner ASSERT(ptr->s != 0); 4330f712c9SDave Chinner 4430f712c9SDave Chinner agf->agf_roots[btnum] = ptr->s; 4530f712c9SDave Chinner be32_add_cpu(&agf->agf_levels[btnum], inc); 46289d38d2SDave Chinner cur->bc_ag.pag->pagf_levels[btnum] += inc; 4730f712c9SDave Chinner 4830f712c9SDave Chinner xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS); 4930f712c9SDave Chinner } 5030f712c9SDave Chinner 5130f712c9SDave Chinner STATIC int 5230f712c9SDave Chinner xfs_allocbt_alloc_block( 5330f712c9SDave Chinner struct xfs_btree_cur *cur, 54deb06b9aSDarrick J. Wong const union xfs_btree_ptr *start, 5530f712c9SDave Chinner union xfs_btree_ptr *new, 5630f712c9SDave Chinner int *stat) 5730f712c9SDave Chinner { 5830f712c9SDave Chinner int error; 5930f712c9SDave Chinner xfs_agblock_t bno; 6030f712c9SDave Chinner 6130f712c9SDave Chinner /* Allocate the new block from the freelist. If we can't, give up. */ 62576af732SDave Chinner error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_ag.agbp, 6330f712c9SDave Chinner &bno, 1); 64e157ebdcSCarlos Maiolino if (error) 6530f712c9SDave Chinner return error; 6630f712c9SDave Chinner 6730f712c9SDave Chinner if (bno == NULLAGBLOCK) { 6830f712c9SDave Chinner *stat = 0; 6930f712c9SDave Chinner return 0; 7030f712c9SDave Chinner } 7130f712c9SDave Chinner 7216eaab83SBrian Foster atomic64_inc(&cur->bc_mp->m_allocbt_blks); 7345d06621SDave Chinner xfs_extent_busy_reuse(cur->bc_mp, cur->bc_ag.agbp->b_pag, bno, 1, false); 7430f712c9SDave Chinner 7530f712c9SDave Chinner new->s = cpu_to_be32(bno); 7630f712c9SDave Chinner 7730f712c9SDave Chinner *stat = 1; 7830f712c9SDave Chinner return 0; 7930f712c9SDave Chinner } 8030f712c9SDave Chinner 8130f712c9SDave Chinner STATIC int 8230f712c9SDave Chinner xfs_allocbt_free_block( 8330f712c9SDave Chinner struct xfs_btree_cur *cur, 8430f712c9SDave Chinner struct xfs_buf *bp) 8530f712c9SDave Chinner { 86576af732SDave Chinner struct xfs_buf *agbp = cur->bc_ag.agbp; 8730f712c9SDave Chinner xfs_agblock_t bno; 8830f712c9SDave Chinner int error; 8930f712c9SDave Chinner 9004fcad80SDave Chinner bno = xfs_daddr_to_agbno(cur->bc_mp, xfs_buf_daddr(bp)); 9130f712c9SDave Chinner error = xfs_alloc_put_freelist(cur->bc_tp, agbp, NULL, bno, 1); 9230f712c9SDave Chinner if (error) 9330f712c9SDave Chinner return error; 9430f712c9SDave Chinner 9516eaab83SBrian Foster atomic64_dec(&cur->bc_mp->m_allocbt_blks); 9645d06621SDave Chinner xfs_extent_busy_insert(cur->bc_tp, agbp->b_pag, bno, 1, 9730f712c9SDave Chinner XFS_EXTENT_BUSY_SKIP_DISCARD); 9830f712c9SDave Chinner return 0; 9930f712c9SDave Chinner } 10030f712c9SDave Chinner 10130f712c9SDave Chinner /* 10230f712c9SDave Chinner * Update the longest extent in the AGF 10330f712c9SDave Chinner */ 10430f712c9SDave Chinner STATIC void 10530f712c9SDave Chinner xfs_allocbt_update_lastrec( 10630f712c9SDave Chinner struct xfs_btree_cur *cur, 10760e265f7SDarrick J. Wong const struct xfs_btree_block *block, 10860e265f7SDarrick J. Wong const union xfs_btree_rec *rec, 10930f712c9SDave Chinner int ptr, 11030f712c9SDave Chinner int reason) 11130f712c9SDave Chinner { 112576af732SDave Chinner struct xfs_agf *agf = cur->bc_ag.agbp->b_addr; 11330f712c9SDave Chinner struct xfs_perag *pag; 11430f712c9SDave Chinner __be32 len; 11530f712c9SDave Chinner int numrecs; 11630f712c9SDave Chinner 11730f712c9SDave Chinner ASSERT(cur->bc_btnum == XFS_BTNUM_CNT); 11830f712c9SDave Chinner 11930f712c9SDave Chinner switch (reason) { 12030f712c9SDave Chinner case LASTREC_UPDATE: 12130f712c9SDave Chinner /* 12230f712c9SDave Chinner * If this is the last leaf block and it's the last record, 12330f712c9SDave Chinner * then update the size of the longest extent in the AG. 12430f712c9SDave Chinner */ 12530f712c9SDave Chinner if (ptr != xfs_btree_get_numrecs(block)) 12630f712c9SDave Chinner return; 12730f712c9SDave Chinner len = rec->alloc.ar_blockcount; 12830f712c9SDave Chinner break; 12930f712c9SDave Chinner case LASTREC_INSREC: 13030f712c9SDave Chinner if (be32_to_cpu(rec->alloc.ar_blockcount) <= 13130f712c9SDave Chinner be32_to_cpu(agf->agf_longest)) 13230f712c9SDave Chinner return; 13330f712c9SDave Chinner len = rec->alloc.ar_blockcount; 13430f712c9SDave Chinner break; 13530f712c9SDave Chinner case LASTREC_DELREC: 13630f712c9SDave Chinner numrecs = xfs_btree_get_numrecs(block); 13730f712c9SDave Chinner if (ptr <= numrecs) 13830f712c9SDave Chinner return; 13930f712c9SDave Chinner ASSERT(ptr == numrecs + 1); 14030f712c9SDave Chinner 14130f712c9SDave Chinner if (numrecs) { 14230f712c9SDave Chinner xfs_alloc_rec_t *rrp; 14330f712c9SDave Chinner 14430f712c9SDave Chinner rrp = XFS_ALLOC_REC_ADDR(cur->bc_mp, block, numrecs); 14530f712c9SDave Chinner len = rrp->ar_blockcount; 14630f712c9SDave Chinner } else { 14730f712c9SDave Chinner len = 0; 14830f712c9SDave Chinner } 14930f712c9SDave Chinner 15030f712c9SDave Chinner break; 15130f712c9SDave Chinner default: 15230f712c9SDave Chinner ASSERT(0); 15330f712c9SDave Chinner return; 15430f712c9SDave Chinner } 15530f712c9SDave Chinner 15630f712c9SDave Chinner agf->agf_longest = len; 15792a00544SGao Xiang pag = cur->bc_ag.agbp->b_pag; 15830f712c9SDave Chinner pag->pagf_longest = be32_to_cpu(len); 159576af732SDave Chinner xfs_alloc_log_agf(cur->bc_tp, cur->bc_ag.agbp, XFS_AGF_LONGEST); 16030f712c9SDave Chinner } 16130f712c9SDave Chinner 16230f712c9SDave Chinner STATIC int 16330f712c9SDave Chinner xfs_allocbt_get_minrecs( 16430f712c9SDave Chinner struct xfs_btree_cur *cur, 16530f712c9SDave Chinner int level) 16630f712c9SDave Chinner { 16730f712c9SDave Chinner return cur->bc_mp->m_alloc_mnr[level != 0]; 16830f712c9SDave Chinner } 16930f712c9SDave Chinner 17030f712c9SDave Chinner STATIC int 17130f712c9SDave Chinner xfs_allocbt_get_maxrecs( 17230f712c9SDave Chinner struct xfs_btree_cur *cur, 17330f712c9SDave Chinner int level) 17430f712c9SDave Chinner { 17530f712c9SDave Chinner return cur->bc_mp->m_alloc_mxr[level != 0]; 17630f712c9SDave Chinner } 17730f712c9SDave Chinner 17830f712c9SDave Chinner STATIC void 17930f712c9SDave Chinner xfs_allocbt_init_key_from_rec( 18030f712c9SDave Chinner union xfs_btree_key *key, 18123825cd1SDarrick J. Wong const union xfs_btree_rec *rec) 18230f712c9SDave Chinner { 18330f712c9SDave Chinner key->alloc.ar_startblock = rec->alloc.ar_startblock; 18430f712c9SDave Chinner key->alloc.ar_blockcount = rec->alloc.ar_blockcount; 18530f712c9SDave Chinner } 18630f712c9SDave Chinner 18730f712c9SDave Chinner STATIC void 18808438b1eSDarrick J. Wong xfs_bnobt_init_high_key_from_rec( 18908438b1eSDarrick J. Wong union xfs_btree_key *key, 19023825cd1SDarrick J. Wong const union xfs_btree_rec *rec) 19108438b1eSDarrick J. Wong { 19208438b1eSDarrick J. Wong __u32 x; 19308438b1eSDarrick J. Wong 19408438b1eSDarrick J. Wong x = be32_to_cpu(rec->alloc.ar_startblock); 19508438b1eSDarrick J. Wong x += be32_to_cpu(rec->alloc.ar_blockcount) - 1; 19608438b1eSDarrick J. Wong key->alloc.ar_startblock = cpu_to_be32(x); 19708438b1eSDarrick J. Wong key->alloc.ar_blockcount = 0; 19808438b1eSDarrick J. Wong } 19908438b1eSDarrick J. Wong 20008438b1eSDarrick J. Wong STATIC void 20108438b1eSDarrick J. Wong xfs_cntbt_init_high_key_from_rec( 20208438b1eSDarrick J. Wong union xfs_btree_key *key, 20323825cd1SDarrick J. Wong const union xfs_btree_rec *rec) 20408438b1eSDarrick J. Wong { 20508438b1eSDarrick J. Wong key->alloc.ar_blockcount = rec->alloc.ar_blockcount; 20608438b1eSDarrick J. Wong key->alloc.ar_startblock = 0; 20708438b1eSDarrick J. Wong } 20808438b1eSDarrick J. Wong 20908438b1eSDarrick J. Wong STATIC void 21030f712c9SDave Chinner xfs_allocbt_init_rec_from_cur( 21130f712c9SDave Chinner struct xfs_btree_cur *cur, 21230f712c9SDave Chinner union xfs_btree_rec *rec) 21330f712c9SDave Chinner { 21430f712c9SDave Chinner rec->alloc.ar_startblock = cpu_to_be32(cur->bc_rec.a.ar_startblock); 21530f712c9SDave Chinner rec->alloc.ar_blockcount = cpu_to_be32(cur->bc_rec.a.ar_blockcount); 21630f712c9SDave Chinner } 21730f712c9SDave Chinner 21830f712c9SDave Chinner STATIC void 21930f712c9SDave Chinner xfs_allocbt_init_ptr_from_cur( 22030f712c9SDave Chinner struct xfs_btree_cur *cur, 22130f712c9SDave Chinner union xfs_btree_ptr *ptr) 22230f712c9SDave Chinner { 223576af732SDave Chinner struct xfs_agf *agf = cur->bc_ag.agbp->b_addr; 22430f712c9SDave Chinner 225289d38d2SDave Chinner ASSERT(cur->bc_ag.pag->pag_agno == be32_to_cpu(agf->agf_seqno)); 22630f712c9SDave Chinner 22730f712c9SDave Chinner ptr->s = agf->agf_roots[cur->bc_btnum]; 22830f712c9SDave Chinner } 22930f712c9SDave Chinner 230c8ce540dSDarrick J. Wong STATIC int64_t 23108438b1eSDarrick J. Wong xfs_bnobt_key_diff( 23208438b1eSDarrick J. Wong struct xfs_btree_cur *cur, 233d29d5577SDarrick J. Wong const union xfs_btree_key *key) 23408438b1eSDarrick J. Wong { 235d29d5577SDarrick J. Wong struct xfs_alloc_rec_incore *rec = &cur->bc_rec.a; 236d29d5577SDarrick J. Wong const struct xfs_alloc_rec *kp = &key->alloc; 23708438b1eSDarrick J. Wong 238c8ce540dSDarrick J. Wong return (int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock; 23908438b1eSDarrick J. Wong } 24008438b1eSDarrick J. Wong 241c8ce540dSDarrick J. Wong STATIC int64_t 24208438b1eSDarrick J. Wong xfs_cntbt_key_diff( 24330f712c9SDave Chinner struct xfs_btree_cur *cur, 244d29d5577SDarrick J. Wong const union xfs_btree_key *key) 24530f712c9SDave Chinner { 246d29d5577SDarrick J. Wong struct xfs_alloc_rec_incore *rec = &cur->bc_rec.a; 247d29d5577SDarrick J. Wong const struct xfs_alloc_rec *kp = &key->alloc; 248c8ce540dSDarrick J. Wong int64_t diff; 24930f712c9SDave Chinner 250c8ce540dSDarrick J. Wong diff = (int64_t)be32_to_cpu(kp->ar_blockcount) - rec->ar_blockcount; 25130f712c9SDave Chinner if (diff) 25230f712c9SDave Chinner return diff; 25330f712c9SDave Chinner 254c8ce540dSDarrick J. Wong return (int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock; 25530f712c9SDave Chinner } 25630f712c9SDave Chinner 257c8ce540dSDarrick J. Wong STATIC int64_t 25808438b1eSDarrick J. Wong xfs_bnobt_diff_two_keys( 25908438b1eSDarrick J. Wong struct xfs_btree_cur *cur, 260d29d5577SDarrick J. Wong const union xfs_btree_key *k1, 261d29d5577SDarrick J. Wong const union xfs_btree_key *k2) 26208438b1eSDarrick J. Wong { 263c8ce540dSDarrick J. Wong return (int64_t)be32_to_cpu(k1->alloc.ar_startblock) - 26408438b1eSDarrick J. Wong be32_to_cpu(k2->alloc.ar_startblock); 26508438b1eSDarrick J. Wong } 26608438b1eSDarrick J. Wong 267c8ce540dSDarrick J. Wong STATIC int64_t 26808438b1eSDarrick J. Wong xfs_cntbt_diff_two_keys( 26908438b1eSDarrick J. Wong struct xfs_btree_cur *cur, 270d29d5577SDarrick J. Wong const union xfs_btree_key *k1, 271d29d5577SDarrick J. Wong const union xfs_btree_key *k2) 27208438b1eSDarrick J. Wong { 273c8ce540dSDarrick J. Wong int64_t diff; 27408438b1eSDarrick J. Wong 27508438b1eSDarrick J. Wong diff = be32_to_cpu(k1->alloc.ar_blockcount) - 27608438b1eSDarrick J. Wong be32_to_cpu(k2->alloc.ar_blockcount); 27708438b1eSDarrick J. Wong if (diff) 27808438b1eSDarrick J. Wong return diff; 27908438b1eSDarrick J. Wong 28008438b1eSDarrick J. Wong return be32_to_cpu(k1->alloc.ar_startblock) - 28108438b1eSDarrick J. Wong be32_to_cpu(k2->alloc.ar_startblock); 28208438b1eSDarrick J. Wong } 28308438b1eSDarrick J. Wong 284a6a781a5SDarrick J. Wong static xfs_failaddr_t 28530f712c9SDave Chinner xfs_allocbt_verify( 28630f712c9SDave Chinner struct xfs_buf *bp) 28730f712c9SDave Chinner { 288dbd329f1SChristoph Hellwig struct xfs_mount *mp = bp->b_mount; 28930f712c9SDave Chinner struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); 29030f712c9SDave Chinner struct xfs_perag *pag = bp->b_pag; 291a6a781a5SDarrick J. Wong xfs_failaddr_t fa; 29230f712c9SDave Chinner unsigned int level; 293b8f89801SBrian Foster xfs_btnum_t btnum = XFS_BTNUM_BNOi; 294b8f89801SBrian Foster 295b8f89801SBrian Foster if (!xfs_verify_magic(bp, block->bb_magic)) 296b8f89801SBrian Foster return __this_address; 297b8f89801SBrian Foster 298ebd9027dSDave Chinner if (xfs_has_crc(mp)) { 299b8f89801SBrian Foster fa = xfs_btree_sblock_v5hdr_verify(bp); 300b8f89801SBrian Foster if (fa) 301b8f89801SBrian Foster return fa; 302b8f89801SBrian Foster } 30330f712c9SDave Chinner 30430f712c9SDave Chinner /* 305b8f89801SBrian Foster * The perag may not be attached during grow operations or fully 306b8f89801SBrian Foster * initialized from the AGF during log recovery. Therefore we can only 307b8f89801SBrian Foster * check against maximum tree depth from those contexts. 30830f712c9SDave Chinner * 309b8f89801SBrian Foster * Otherwise check against the per-tree limit. Peek at one of the 310b8f89801SBrian Foster * verifier magic values to determine the type of tree we're verifying 311b8f89801SBrian Foster * against. 31230f712c9SDave Chinner */ 31330f712c9SDave Chinner level = be16_to_cpu(block->bb_level); 314b8f89801SBrian Foster if (bp->b_ops->magic[0] == cpu_to_be32(XFS_ABTC_MAGIC)) 315b8f89801SBrian Foster btnum = XFS_BTNUM_CNTi; 31630f712c9SDave Chinner if (pag && pag->pagf_init) { 317b8f89801SBrian Foster if (level >= pag->pagf_levels[btnum]) 318a6a781a5SDarrick J. Wong return __this_address; 319*7cb3efb4SDarrick J. Wong } else if (level >= mp->m_alloc_maxlevels) 320a6a781a5SDarrick J. Wong return __this_address; 32130f712c9SDave Chinner 322c5ab131bSDarrick J. Wong return xfs_btree_sblock_verify(bp, mp->m_alloc_mxr[level != 0]); 32330f712c9SDave Chinner } 32430f712c9SDave Chinner 32530f712c9SDave Chinner static void 32630f712c9SDave Chinner xfs_allocbt_read_verify( 32730f712c9SDave Chinner struct xfs_buf *bp) 32830f712c9SDave Chinner { 329bc1a09b8SDarrick J. Wong xfs_failaddr_t fa; 330bc1a09b8SDarrick J. Wong 33130f712c9SDave Chinner if (!xfs_btree_sblock_verify_crc(bp)) 332bc1a09b8SDarrick J. Wong xfs_verifier_error(bp, -EFSBADCRC, __this_address); 333bc1a09b8SDarrick J. Wong else { 334bc1a09b8SDarrick J. Wong fa = xfs_allocbt_verify(bp); 335bc1a09b8SDarrick J. Wong if (fa) 336bc1a09b8SDarrick J. Wong xfs_verifier_error(bp, -EFSCORRUPTED, fa); 337bc1a09b8SDarrick J. Wong } 33830f712c9SDave Chinner 33931ca03c9SDarrick J. Wong if (bp->b_error) 34030f712c9SDave Chinner trace_xfs_btree_corrupt(bp, _RET_IP_); 34130f712c9SDave Chinner } 34230f712c9SDave Chinner 34330f712c9SDave Chinner static void 34430f712c9SDave Chinner xfs_allocbt_write_verify( 34530f712c9SDave Chinner struct xfs_buf *bp) 34630f712c9SDave Chinner { 347bc1a09b8SDarrick J. Wong xfs_failaddr_t fa; 348bc1a09b8SDarrick J. Wong 349bc1a09b8SDarrick J. Wong fa = xfs_allocbt_verify(bp); 350bc1a09b8SDarrick J. Wong if (fa) { 35130f712c9SDave Chinner trace_xfs_btree_corrupt(bp, _RET_IP_); 352bc1a09b8SDarrick J. Wong xfs_verifier_error(bp, -EFSCORRUPTED, fa); 35330f712c9SDave Chinner return; 35430f712c9SDave Chinner } 35530f712c9SDave Chinner xfs_btree_sblock_calc_crc(bp); 35630f712c9SDave Chinner 35730f712c9SDave Chinner } 35830f712c9SDave Chinner 35927df4f50SBrian Foster const struct xfs_buf_ops xfs_bnobt_buf_ops = { 36027df4f50SBrian Foster .name = "xfs_bnobt", 361b8f89801SBrian Foster .magic = { cpu_to_be32(XFS_ABTB_MAGIC), 362b8f89801SBrian Foster cpu_to_be32(XFS_ABTB_CRC_MAGIC) }, 36330f712c9SDave Chinner .verify_read = xfs_allocbt_read_verify, 36430f712c9SDave Chinner .verify_write = xfs_allocbt_write_verify, 365b5572597SDarrick J. Wong .verify_struct = xfs_allocbt_verify, 36630f712c9SDave Chinner }; 36730f712c9SDave Chinner 36827df4f50SBrian Foster const struct xfs_buf_ops xfs_cntbt_buf_ops = { 36927df4f50SBrian Foster .name = "xfs_cntbt", 370b8f89801SBrian Foster .magic = { cpu_to_be32(XFS_ABTC_MAGIC), 371b8f89801SBrian Foster cpu_to_be32(XFS_ABTC_CRC_MAGIC) }, 37227df4f50SBrian Foster .verify_read = xfs_allocbt_read_verify, 37327df4f50SBrian Foster .verify_write = xfs_allocbt_write_verify, 37427df4f50SBrian Foster .verify_struct = xfs_allocbt_verify, 37527df4f50SBrian Foster }; 37630f712c9SDave Chinner 37730f712c9SDave Chinner STATIC int 37808438b1eSDarrick J. Wong xfs_bnobt_keys_inorder( 37930f712c9SDave Chinner struct xfs_btree_cur *cur, 3808e38dc88SDarrick J. Wong const union xfs_btree_key *k1, 3818e38dc88SDarrick J. Wong const union xfs_btree_key *k2) 38230f712c9SDave Chinner { 38330f712c9SDave Chinner return be32_to_cpu(k1->alloc.ar_startblock) < 38430f712c9SDave Chinner be32_to_cpu(k2->alloc.ar_startblock); 38508438b1eSDarrick J. Wong } 38608438b1eSDarrick J. Wong 38708438b1eSDarrick J. Wong STATIC int 38808438b1eSDarrick J. Wong xfs_bnobt_recs_inorder( 38908438b1eSDarrick J. Wong struct xfs_btree_cur *cur, 3908e38dc88SDarrick J. Wong const union xfs_btree_rec *r1, 3918e38dc88SDarrick J. Wong const union xfs_btree_rec *r2) 39208438b1eSDarrick J. Wong { 39308438b1eSDarrick J. Wong return be32_to_cpu(r1->alloc.ar_startblock) + 39408438b1eSDarrick J. Wong be32_to_cpu(r1->alloc.ar_blockcount) <= 39508438b1eSDarrick J. Wong be32_to_cpu(r2->alloc.ar_startblock); 39608438b1eSDarrick J. Wong } 39708438b1eSDarrick J. Wong 39808438b1eSDarrick J. Wong STATIC int 39908438b1eSDarrick J. Wong xfs_cntbt_keys_inorder( 40008438b1eSDarrick J. Wong struct xfs_btree_cur *cur, 4018e38dc88SDarrick J. Wong const union xfs_btree_key *k1, 4028e38dc88SDarrick J. Wong const union xfs_btree_key *k2) 40308438b1eSDarrick J. Wong { 40430f712c9SDave Chinner return be32_to_cpu(k1->alloc.ar_blockcount) < 40530f712c9SDave Chinner be32_to_cpu(k2->alloc.ar_blockcount) || 40630f712c9SDave Chinner (k1->alloc.ar_blockcount == k2->alloc.ar_blockcount && 40730f712c9SDave Chinner be32_to_cpu(k1->alloc.ar_startblock) < 40830f712c9SDave Chinner be32_to_cpu(k2->alloc.ar_startblock)); 40930f712c9SDave Chinner } 41030f712c9SDave Chinner 41130f712c9SDave Chinner STATIC int 41208438b1eSDarrick J. Wong xfs_cntbt_recs_inorder( 41330f712c9SDave Chinner struct xfs_btree_cur *cur, 4148e38dc88SDarrick J. Wong const union xfs_btree_rec *r1, 4158e38dc88SDarrick J. Wong const union xfs_btree_rec *r2) 41630f712c9SDave Chinner { 41730f712c9SDave Chinner return be32_to_cpu(r1->alloc.ar_blockcount) < 41830f712c9SDave Chinner be32_to_cpu(r2->alloc.ar_blockcount) || 41930f712c9SDave Chinner (r1->alloc.ar_blockcount == r2->alloc.ar_blockcount && 42030f712c9SDave Chinner be32_to_cpu(r1->alloc.ar_startblock) < 42130f712c9SDave Chinner be32_to_cpu(r2->alloc.ar_startblock)); 42230f712c9SDave Chinner } 42330f712c9SDave Chinner 42408438b1eSDarrick J. Wong static const struct xfs_btree_ops xfs_bnobt_ops = { 42530f712c9SDave Chinner .rec_len = sizeof(xfs_alloc_rec_t), 42630f712c9SDave Chinner .key_len = sizeof(xfs_alloc_key_t), 42730f712c9SDave Chinner 42830f712c9SDave Chinner .dup_cursor = xfs_allocbt_dup_cursor, 42930f712c9SDave Chinner .set_root = xfs_allocbt_set_root, 43030f712c9SDave Chinner .alloc_block = xfs_allocbt_alloc_block, 43130f712c9SDave Chinner .free_block = xfs_allocbt_free_block, 43230f712c9SDave Chinner .update_lastrec = xfs_allocbt_update_lastrec, 43330f712c9SDave Chinner .get_minrecs = xfs_allocbt_get_minrecs, 43430f712c9SDave Chinner .get_maxrecs = xfs_allocbt_get_maxrecs, 43530f712c9SDave Chinner .init_key_from_rec = xfs_allocbt_init_key_from_rec, 43608438b1eSDarrick J. Wong .init_high_key_from_rec = xfs_bnobt_init_high_key_from_rec, 43730f712c9SDave Chinner .init_rec_from_cur = xfs_allocbt_init_rec_from_cur, 43830f712c9SDave Chinner .init_ptr_from_cur = xfs_allocbt_init_ptr_from_cur, 43908438b1eSDarrick J. Wong .key_diff = xfs_bnobt_key_diff, 44027df4f50SBrian Foster .buf_ops = &xfs_bnobt_buf_ops, 44108438b1eSDarrick J. Wong .diff_two_keys = xfs_bnobt_diff_two_keys, 44208438b1eSDarrick J. Wong .keys_inorder = xfs_bnobt_keys_inorder, 44308438b1eSDarrick J. Wong .recs_inorder = xfs_bnobt_recs_inorder, 44408438b1eSDarrick J. Wong }; 44508438b1eSDarrick J. Wong 44608438b1eSDarrick J. Wong static const struct xfs_btree_ops xfs_cntbt_ops = { 44708438b1eSDarrick J. Wong .rec_len = sizeof(xfs_alloc_rec_t), 44808438b1eSDarrick J. Wong .key_len = sizeof(xfs_alloc_key_t), 44908438b1eSDarrick J. Wong 45008438b1eSDarrick J. Wong .dup_cursor = xfs_allocbt_dup_cursor, 45108438b1eSDarrick J. Wong .set_root = xfs_allocbt_set_root, 45208438b1eSDarrick J. Wong .alloc_block = xfs_allocbt_alloc_block, 45308438b1eSDarrick J. Wong .free_block = xfs_allocbt_free_block, 45408438b1eSDarrick J. Wong .update_lastrec = xfs_allocbt_update_lastrec, 45508438b1eSDarrick J. Wong .get_minrecs = xfs_allocbt_get_minrecs, 45608438b1eSDarrick J. Wong .get_maxrecs = xfs_allocbt_get_maxrecs, 45708438b1eSDarrick J. Wong .init_key_from_rec = xfs_allocbt_init_key_from_rec, 45808438b1eSDarrick J. Wong .init_high_key_from_rec = xfs_cntbt_init_high_key_from_rec, 45908438b1eSDarrick J. Wong .init_rec_from_cur = xfs_allocbt_init_rec_from_cur, 46008438b1eSDarrick J. Wong .init_ptr_from_cur = xfs_allocbt_init_ptr_from_cur, 46108438b1eSDarrick J. Wong .key_diff = xfs_cntbt_key_diff, 46227df4f50SBrian Foster .buf_ops = &xfs_cntbt_buf_ops, 46308438b1eSDarrick J. Wong .diff_two_keys = xfs_cntbt_diff_two_keys, 46408438b1eSDarrick J. Wong .keys_inorder = xfs_cntbt_keys_inorder, 46508438b1eSDarrick J. Wong .recs_inorder = xfs_cntbt_recs_inorder, 46630f712c9SDave Chinner }; 46730f712c9SDave Chinner 468e6eb33d9SDarrick J. Wong /* Allocate most of a new allocation btree cursor. */ 469e6eb33d9SDarrick J. Wong STATIC struct xfs_btree_cur * 470e6eb33d9SDarrick J. Wong xfs_allocbt_init_common( 471e6eb33d9SDarrick J. Wong struct xfs_mount *mp, 472e6eb33d9SDarrick J. Wong struct xfs_trans *tp, 473be9fb17dSDave Chinner struct xfs_perag *pag, 474e6eb33d9SDarrick J. Wong xfs_btnum_t btnum) 475e6eb33d9SDarrick J. Wong { 476e6eb33d9SDarrick J. Wong struct xfs_btree_cur *cur; 477e6eb33d9SDarrick J. Wong 478e6eb33d9SDarrick J. Wong ASSERT(btnum == XFS_BTNUM_BNO || btnum == XFS_BTNUM_CNT); 479e6eb33d9SDarrick J. Wong 480*7cb3efb4SDarrick J. Wong cur = xfs_btree_alloc_cursor(mp, tp, btnum, mp->m_alloc_maxlevels); 481289d38d2SDave Chinner cur->bc_ag.abt.active = false; 482e6eb33d9SDarrick J. Wong 483e6eb33d9SDarrick J. Wong if (btnum == XFS_BTNUM_CNT) { 484e6eb33d9SDarrick J. Wong cur->bc_ops = &xfs_cntbt_ops; 485e6eb33d9SDarrick J. Wong cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_abtc_2); 486e6eb33d9SDarrick J. Wong cur->bc_flags = XFS_BTREE_LASTREC_UPDATE; 487e6eb33d9SDarrick J. Wong } else { 488e6eb33d9SDarrick J. Wong cur->bc_ops = &xfs_bnobt_ops; 489e6eb33d9SDarrick J. Wong cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_abtb_2); 490e6eb33d9SDarrick J. Wong } 491e6eb33d9SDarrick J. Wong 492be9fb17dSDave Chinner /* take a reference for the cursor */ 493be9fb17dSDave Chinner atomic_inc(&pag->pag_ref); 494be9fb17dSDave Chinner cur->bc_ag.pag = pag; 495e6eb33d9SDarrick J. Wong 49638c26bfdSDave Chinner if (xfs_has_crc(mp)) 497e6eb33d9SDarrick J. Wong cur->bc_flags |= XFS_BTREE_CRC_BLOCKS; 498e6eb33d9SDarrick J. Wong 499e6eb33d9SDarrick J. Wong return cur; 500e6eb33d9SDarrick J. Wong } 501e6eb33d9SDarrick J. Wong 50230f712c9SDave Chinner /* 50330f712c9SDave Chinner * Allocate a new allocation btree cursor. 50430f712c9SDave Chinner */ 50530f712c9SDave Chinner struct xfs_btree_cur * /* new alloc btree cursor */ 50630f712c9SDave Chinner xfs_allocbt_init_cursor( 50730f712c9SDave Chinner struct xfs_mount *mp, /* file system mount point */ 50830f712c9SDave Chinner struct xfs_trans *tp, /* transaction pointer */ 50930f712c9SDave Chinner struct xfs_buf *agbp, /* buffer for agf structure */ 510be9fb17dSDave Chinner struct xfs_perag *pag, 51130f712c9SDave Chinner xfs_btnum_t btnum) /* btree identifier */ 51230f712c9SDave Chinner { 5139798f615SChristoph Hellwig struct xfs_agf *agf = agbp->b_addr; 51430f712c9SDave Chinner struct xfs_btree_cur *cur; 51530f712c9SDave Chinner 516289d38d2SDave Chinner cur = xfs_allocbt_init_common(mp, tp, pag, btnum); 517e6eb33d9SDarrick J. Wong if (btnum == XFS_BTNUM_CNT) 51830f712c9SDave Chinner cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]); 519e6eb33d9SDarrick J. Wong else 52030f712c9SDave Chinner cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]); 52130f712c9SDave Chinner 522576af732SDave Chinner cur->bc_ag.agbp = agbp; 52330f712c9SDave Chinner 52430f712c9SDave Chinner return cur; 52530f712c9SDave Chinner } 52630f712c9SDave Chinner 527e6eb33d9SDarrick J. Wong /* Create a free space btree cursor with a fake root for staging. */ 528e6eb33d9SDarrick J. Wong struct xfs_btree_cur * 529e6eb33d9SDarrick J. Wong xfs_allocbt_stage_cursor( 530e6eb33d9SDarrick J. Wong struct xfs_mount *mp, 531e6eb33d9SDarrick J. Wong struct xbtree_afakeroot *afake, 532289d38d2SDave Chinner struct xfs_perag *pag, 533e6eb33d9SDarrick J. Wong xfs_btnum_t btnum) 534e6eb33d9SDarrick J. Wong { 535e6eb33d9SDarrick J. Wong struct xfs_btree_cur *cur; 536e6eb33d9SDarrick J. Wong 537289d38d2SDave Chinner cur = xfs_allocbt_init_common(mp, NULL, pag, btnum); 538e6eb33d9SDarrick J. Wong xfs_btree_stage_afakeroot(cur, afake); 539e6eb33d9SDarrick J. Wong return cur; 540e6eb33d9SDarrick J. Wong } 541e6eb33d9SDarrick J. Wong 542e6eb33d9SDarrick J. Wong /* 543e6eb33d9SDarrick J. Wong * Install a new free space btree root. Caller is responsible for invalidating 544e6eb33d9SDarrick J. Wong * and freeing the old btree blocks. 545e6eb33d9SDarrick J. Wong */ 546e6eb33d9SDarrick J. Wong void 547e6eb33d9SDarrick J. Wong xfs_allocbt_commit_staged_btree( 548e6eb33d9SDarrick J. Wong struct xfs_btree_cur *cur, 549e6eb33d9SDarrick J. Wong struct xfs_trans *tp, 550e6eb33d9SDarrick J. Wong struct xfs_buf *agbp) 551e6eb33d9SDarrick J. Wong { 552e6eb33d9SDarrick J. Wong struct xfs_agf *agf = agbp->b_addr; 553e6eb33d9SDarrick J. Wong struct xbtree_afakeroot *afake = cur->bc_ag.afake; 554e6eb33d9SDarrick J. Wong 555e6eb33d9SDarrick J. Wong ASSERT(cur->bc_flags & XFS_BTREE_STAGING); 556e6eb33d9SDarrick J. Wong 557e6eb33d9SDarrick J. Wong agf->agf_roots[cur->bc_btnum] = cpu_to_be32(afake->af_root); 558e6eb33d9SDarrick J. Wong agf->agf_levels[cur->bc_btnum] = cpu_to_be32(afake->af_levels); 559e6eb33d9SDarrick J. Wong xfs_alloc_log_agf(tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS); 560e6eb33d9SDarrick J. Wong 561e6eb33d9SDarrick J. Wong if (cur->bc_btnum == XFS_BTNUM_BNO) { 562e6eb33d9SDarrick J. Wong xfs_btree_commit_afakeroot(cur, tp, agbp, &xfs_bnobt_ops); 563e6eb33d9SDarrick J. Wong } else { 564e6eb33d9SDarrick J. Wong cur->bc_flags |= XFS_BTREE_LASTREC_UPDATE; 565e6eb33d9SDarrick J. Wong xfs_btree_commit_afakeroot(cur, tp, agbp, &xfs_cntbt_ops); 566e6eb33d9SDarrick J. Wong } 567e6eb33d9SDarrick J. Wong } 568e6eb33d9SDarrick J. Wong 56930f712c9SDave Chinner /* 57030f712c9SDave Chinner * Calculate number of records in an alloc btree block. 57130f712c9SDave Chinner */ 57230f712c9SDave Chinner int 57330f712c9SDave Chinner xfs_allocbt_maxrecs( 57430f712c9SDave Chinner struct xfs_mount *mp, 57530f712c9SDave Chinner int blocklen, 57630f712c9SDave Chinner int leaf) 57730f712c9SDave Chinner { 57830f712c9SDave Chinner blocklen -= XFS_ALLOC_BLOCK_LEN(mp); 57930f712c9SDave Chinner 58030f712c9SDave Chinner if (leaf) 58130f712c9SDave Chinner return blocklen / sizeof(xfs_alloc_rec_t); 58230f712c9SDave Chinner return blocklen / (sizeof(xfs_alloc_key_t) + sizeof(xfs_alloc_ptr_t)); 58330f712c9SDave Chinner } 58414861c47SDarrick J. Wong 58514861c47SDarrick J. Wong /* Calculate the freespace btree size for some records. */ 58614861c47SDarrick J. Wong xfs_extlen_t 58714861c47SDarrick J. Wong xfs_allocbt_calc_size( 58814861c47SDarrick J. Wong struct xfs_mount *mp, 58914861c47SDarrick J. Wong unsigned long long len) 59014861c47SDarrick J. Wong { 59114861c47SDarrick J. Wong return xfs_btree_calc_size(mp->m_alloc_mnr, len); 59214861c47SDarrick J. Wong } 593