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_sb.h" 1330f712c9SDave Chinner #include "xfs_mount.h" 1430f712c9SDave Chinner #include "xfs_btree.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" 2130f712c9SDave Chinner 2230f712c9SDave Chinner 2330f712c9SDave Chinner STATIC struct xfs_btree_cur * 2430f712c9SDave Chinner xfs_allocbt_dup_cursor( 2530f712c9SDave Chinner struct xfs_btree_cur *cur) 2630f712c9SDave Chinner { 2730f712c9SDave Chinner return xfs_allocbt_init_cursor(cur->bc_mp, cur->bc_tp, 28576af732SDave Chinner cur->bc_ag.agbp, cur->bc_ag.agno, 2930f712c9SDave Chinner cur->bc_btnum); 3030f712c9SDave Chinner } 3130f712c9SDave Chinner 3230f712c9SDave Chinner STATIC void 3330f712c9SDave Chinner xfs_allocbt_set_root( 3430f712c9SDave Chinner struct xfs_btree_cur *cur, 3530f712c9SDave Chinner 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 xfs_agnumber_t seqno = be32_to_cpu(agf->agf_seqno); 4130f712c9SDave Chinner int btnum = cur->bc_btnum; 4230f712c9SDave Chinner struct xfs_perag *pag = xfs_perag_get(cur->bc_mp, seqno); 4330f712c9SDave Chinner 4430f712c9SDave Chinner ASSERT(ptr->s != 0); 4530f712c9SDave Chinner 4630f712c9SDave Chinner agf->agf_roots[btnum] = ptr->s; 4730f712c9SDave Chinner be32_add_cpu(&agf->agf_levels[btnum], inc); 4830f712c9SDave Chinner pag->pagf_levels[btnum] += inc; 4930f712c9SDave Chinner xfs_perag_put(pag); 5030f712c9SDave Chinner 5130f712c9SDave Chinner xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS); 5230f712c9SDave Chinner } 5330f712c9SDave Chinner 5430f712c9SDave Chinner STATIC int 5530f712c9SDave Chinner xfs_allocbt_alloc_block( 5630f712c9SDave Chinner struct xfs_btree_cur *cur, 5730f712c9SDave Chinner union xfs_btree_ptr *start, 5830f712c9SDave Chinner union xfs_btree_ptr *new, 5930f712c9SDave Chinner int *stat) 6030f712c9SDave Chinner { 6130f712c9SDave Chinner int error; 6230f712c9SDave Chinner xfs_agblock_t bno; 6330f712c9SDave Chinner 6430f712c9SDave Chinner /* Allocate the new block from the freelist. If we can't, give up. */ 65576af732SDave Chinner error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_ag.agbp, 6630f712c9SDave Chinner &bno, 1); 67e157ebdcSCarlos Maiolino if (error) 6830f712c9SDave Chinner return error; 6930f712c9SDave Chinner 7030f712c9SDave Chinner if (bno == NULLAGBLOCK) { 7130f712c9SDave Chinner *stat = 0; 7230f712c9SDave Chinner return 0; 7330f712c9SDave Chinner } 7430f712c9SDave Chinner 75576af732SDave Chinner xfs_extent_busy_reuse(cur->bc_mp, cur->bc_ag.agno, bno, 1, false); 7630f712c9SDave Chinner 7730f712c9SDave Chinner xfs_trans_agbtree_delta(cur->bc_tp, 1); 7830f712c9SDave Chinner new->s = cpu_to_be32(bno); 7930f712c9SDave Chinner 8030f712c9SDave Chinner *stat = 1; 8130f712c9SDave Chinner return 0; 8230f712c9SDave Chinner } 8330f712c9SDave Chinner 8430f712c9SDave Chinner STATIC int 8530f712c9SDave Chinner xfs_allocbt_free_block( 8630f712c9SDave Chinner struct xfs_btree_cur *cur, 8730f712c9SDave Chinner struct xfs_buf *bp) 8830f712c9SDave Chinner { 89576af732SDave Chinner struct xfs_buf *agbp = cur->bc_ag.agbp; 909798f615SChristoph Hellwig struct xfs_agf *agf = agbp->b_addr; 9130f712c9SDave Chinner xfs_agblock_t bno; 9230f712c9SDave Chinner int error; 9330f712c9SDave Chinner 9430f712c9SDave Chinner bno = xfs_daddr_to_agbno(cur->bc_mp, XFS_BUF_ADDR(bp)); 9530f712c9SDave Chinner error = xfs_alloc_put_freelist(cur->bc_tp, agbp, NULL, bno, 1); 9630f712c9SDave Chinner if (error) 9730f712c9SDave Chinner return error; 9830f712c9SDave Chinner 9930f712c9SDave Chinner xfs_extent_busy_insert(cur->bc_tp, be32_to_cpu(agf->agf_seqno), bno, 1, 10030f712c9SDave Chinner XFS_EXTENT_BUSY_SKIP_DISCARD); 10130f712c9SDave Chinner xfs_trans_agbtree_delta(cur->bc_tp, -1); 10230f712c9SDave Chinner return 0; 10330f712c9SDave Chinner } 10430f712c9SDave Chinner 10530f712c9SDave Chinner /* 10630f712c9SDave Chinner * Update the longest extent in the AGF 10730f712c9SDave Chinner */ 10830f712c9SDave Chinner STATIC void 10930f712c9SDave Chinner xfs_allocbt_update_lastrec( 11030f712c9SDave Chinner struct xfs_btree_cur *cur, 11130f712c9SDave Chinner struct xfs_btree_block *block, 11230f712c9SDave Chinner union xfs_btree_rec *rec, 11330f712c9SDave Chinner int ptr, 11430f712c9SDave Chinner int reason) 11530f712c9SDave Chinner { 116576af732SDave Chinner struct xfs_agf *agf = cur->bc_ag.agbp->b_addr; 11730f712c9SDave Chinner xfs_agnumber_t seqno = be32_to_cpu(agf->agf_seqno); 11830f712c9SDave Chinner struct xfs_perag *pag; 11930f712c9SDave Chinner __be32 len; 12030f712c9SDave Chinner int numrecs; 12130f712c9SDave Chinner 12230f712c9SDave Chinner ASSERT(cur->bc_btnum == XFS_BTNUM_CNT); 12330f712c9SDave Chinner 12430f712c9SDave Chinner switch (reason) { 12530f712c9SDave Chinner case LASTREC_UPDATE: 12630f712c9SDave Chinner /* 12730f712c9SDave Chinner * If this is the last leaf block and it's the last record, 12830f712c9SDave Chinner * then update the size of the longest extent in the AG. 12930f712c9SDave Chinner */ 13030f712c9SDave Chinner if (ptr != xfs_btree_get_numrecs(block)) 13130f712c9SDave Chinner return; 13230f712c9SDave Chinner len = rec->alloc.ar_blockcount; 13330f712c9SDave Chinner break; 13430f712c9SDave Chinner case LASTREC_INSREC: 13530f712c9SDave Chinner if (be32_to_cpu(rec->alloc.ar_blockcount) <= 13630f712c9SDave Chinner be32_to_cpu(agf->agf_longest)) 13730f712c9SDave Chinner return; 13830f712c9SDave Chinner len = rec->alloc.ar_blockcount; 13930f712c9SDave Chinner break; 14030f712c9SDave Chinner case LASTREC_DELREC: 14130f712c9SDave Chinner numrecs = xfs_btree_get_numrecs(block); 14230f712c9SDave Chinner if (ptr <= numrecs) 14330f712c9SDave Chinner return; 14430f712c9SDave Chinner ASSERT(ptr == numrecs + 1); 14530f712c9SDave Chinner 14630f712c9SDave Chinner if (numrecs) { 14730f712c9SDave Chinner xfs_alloc_rec_t *rrp; 14830f712c9SDave Chinner 14930f712c9SDave Chinner rrp = XFS_ALLOC_REC_ADDR(cur->bc_mp, block, numrecs); 15030f712c9SDave Chinner len = rrp->ar_blockcount; 15130f712c9SDave Chinner } else { 15230f712c9SDave Chinner len = 0; 15330f712c9SDave Chinner } 15430f712c9SDave Chinner 15530f712c9SDave Chinner break; 15630f712c9SDave Chinner default: 15730f712c9SDave Chinner ASSERT(0); 15830f712c9SDave Chinner return; 15930f712c9SDave Chinner } 16030f712c9SDave Chinner 16130f712c9SDave Chinner agf->agf_longest = len; 16230f712c9SDave Chinner pag = xfs_perag_get(cur->bc_mp, seqno); 16330f712c9SDave Chinner pag->pagf_longest = be32_to_cpu(len); 16430f712c9SDave Chinner xfs_perag_put(pag); 165576af732SDave Chinner xfs_alloc_log_agf(cur->bc_tp, cur->bc_ag.agbp, XFS_AGF_LONGEST); 16630f712c9SDave Chinner } 16730f712c9SDave Chinner 16830f712c9SDave Chinner STATIC int 16930f712c9SDave Chinner xfs_allocbt_get_minrecs( 17030f712c9SDave Chinner struct xfs_btree_cur *cur, 17130f712c9SDave Chinner int level) 17230f712c9SDave Chinner { 17330f712c9SDave Chinner return cur->bc_mp->m_alloc_mnr[level != 0]; 17430f712c9SDave Chinner } 17530f712c9SDave Chinner 17630f712c9SDave Chinner STATIC int 17730f712c9SDave Chinner xfs_allocbt_get_maxrecs( 17830f712c9SDave Chinner struct xfs_btree_cur *cur, 17930f712c9SDave Chinner int level) 18030f712c9SDave Chinner { 18130f712c9SDave Chinner return cur->bc_mp->m_alloc_mxr[level != 0]; 18230f712c9SDave Chinner } 18330f712c9SDave Chinner 18430f712c9SDave Chinner STATIC void 18530f712c9SDave Chinner xfs_allocbt_init_key_from_rec( 18630f712c9SDave Chinner union xfs_btree_key *key, 18730f712c9SDave Chinner union xfs_btree_rec *rec) 18830f712c9SDave Chinner { 18930f712c9SDave Chinner key->alloc.ar_startblock = rec->alloc.ar_startblock; 19030f712c9SDave Chinner key->alloc.ar_blockcount = rec->alloc.ar_blockcount; 19130f712c9SDave Chinner } 19230f712c9SDave Chinner 19330f712c9SDave Chinner STATIC void 19408438b1eSDarrick J. Wong xfs_bnobt_init_high_key_from_rec( 19508438b1eSDarrick J. Wong union xfs_btree_key *key, 19608438b1eSDarrick J. Wong union xfs_btree_rec *rec) 19708438b1eSDarrick J. Wong { 19808438b1eSDarrick J. Wong __u32 x; 19908438b1eSDarrick J. Wong 20008438b1eSDarrick J. Wong x = be32_to_cpu(rec->alloc.ar_startblock); 20108438b1eSDarrick J. Wong x += be32_to_cpu(rec->alloc.ar_blockcount) - 1; 20208438b1eSDarrick J. Wong key->alloc.ar_startblock = cpu_to_be32(x); 20308438b1eSDarrick J. Wong key->alloc.ar_blockcount = 0; 20408438b1eSDarrick J. Wong } 20508438b1eSDarrick J. Wong 20608438b1eSDarrick J. Wong STATIC void 20708438b1eSDarrick J. Wong xfs_cntbt_init_high_key_from_rec( 20808438b1eSDarrick J. Wong union xfs_btree_key *key, 20908438b1eSDarrick J. Wong union xfs_btree_rec *rec) 21008438b1eSDarrick J. Wong { 21108438b1eSDarrick J. Wong key->alloc.ar_blockcount = rec->alloc.ar_blockcount; 21208438b1eSDarrick J. Wong key->alloc.ar_startblock = 0; 21308438b1eSDarrick J. Wong } 21408438b1eSDarrick J. Wong 21508438b1eSDarrick J. Wong STATIC void 21630f712c9SDave Chinner xfs_allocbt_init_rec_from_cur( 21730f712c9SDave Chinner struct xfs_btree_cur *cur, 21830f712c9SDave Chinner union xfs_btree_rec *rec) 21930f712c9SDave Chinner { 22030f712c9SDave Chinner rec->alloc.ar_startblock = cpu_to_be32(cur->bc_rec.a.ar_startblock); 22130f712c9SDave Chinner rec->alloc.ar_blockcount = cpu_to_be32(cur->bc_rec.a.ar_blockcount); 22230f712c9SDave Chinner } 22330f712c9SDave Chinner 22430f712c9SDave Chinner STATIC void 22530f712c9SDave Chinner xfs_allocbt_init_ptr_from_cur( 22630f712c9SDave Chinner struct xfs_btree_cur *cur, 22730f712c9SDave Chinner union xfs_btree_ptr *ptr) 22830f712c9SDave Chinner { 229576af732SDave Chinner struct xfs_agf *agf = cur->bc_ag.agbp->b_addr; 23030f712c9SDave Chinner 231576af732SDave Chinner ASSERT(cur->bc_ag.agno == be32_to_cpu(agf->agf_seqno)); 23230f712c9SDave Chinner 23330f712c9SDave Chinner ptr->s = agf->agf_roots[cur->bc_btnum]; 23430f712c9SDave Chinner } 23530f712c9SDave Chinner 236c8ce540dSDarrick J. Wong STATIC int64_t 23708438b1eSDarrick J. Wong xfs_bnobt_key_diff( 23808438b1eSDarrick J. Wong struct xfs_btree_cur *cur, 23908438b1eSDarrick J. Wong union xfs_btree_key *key) 24008438b1eSDarrick J. Wong { 24108438b1eSDarrick J. Wong xfs_alloc_rec_incore_t *rec = &cur->bc_rec.a; 24208438b1eSDarrick J. Wong xfs_alloc_key_t *kp = &key->alloc; 24308438b1eSDarrick J. Wong 244c8ce540dSDarrick J. Wong return (int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock; 24508438b1eSDarrick J. Wong } 24608438b1eSDarrick J. Wong 247c8ce540dSDarrick J. Wong STATIC int64_t 24808438b1eSDarrick J. Wong xfs_cntbt_key_diff( 24930f712c9SDave Chinner struct xfs_btree_cur *cur, 25030f712c9SDave Chinner union xfs_btree_key *key) 25130f712c9SDave Chinner { 25230f712c9SDave Chinner xfs_alloc_rec_incore_t *rec = &cur->bc_rec.a; 25330f712c9SDave Chinner xfs_alloc_key_t *kp = &key->alloc; 254c8ce540dSDarrick J. Wong int64_t diff; 25530f712c9SDave Chinner 256c8ce540dSDarrick J. Wong diff = (int64_t)be32_to_cpu(kp->ar_blockcount) - rec->ar_blockcount; 25730f712c9SDave Chinner if (diff) 25830f712c9SDave Chinner return diff; 25930f712c9SDave Chinner 260c8ce540dSDarrick J. Wong return (int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock; 26130f712c9SDave Chinner } 26230f712c9SDave Chinner 263c8ce540dSDarrick J. Wong STATIC int64_t 26408438b1eSDarrick J. Wong xfs_bnobt_diff_two_keys( 26508438b1eSDarrick J. Wong struct xfs_btree_cur *cur, 26608438b1eSDarrick J. Wong union xfs_btree_key *k1, 26708438b1eSDarrick J. Wong union xfs_btree_key *k2) 26808438b1eSDarrick J. Wong { 269c8ce540dSDarrick J. Wong return (int64_t)be32_to_cpu(k1->alloc.ar_startblock) - 27008438b1eSDarrick J. Wong be32_to_cpu(k2->alloc.ar_startblock); 27108438b1eSDarrick J. Wong } 27208438b1eSDarrick J. Wong 273c8ce540dSDarrick J. Wong STATIC int64_t 27408438b1eSDarrick J. Wong xfs_cntbt_diff_two_keys( 27508438b1eSDarrick J. Wong struct xfs_btree_cur *cur, 27608438b1eSDarrick J. Wong union xfs_btree_key *k1, 27708438b1eSDarrick J. Wong union xfs_btree_key *k2) 27808438b1eSDarrick J. Wong { 279c8ce540dSDarrick J. Wong int64_t diff; 28008438b1eSDarrick J. Wong 28108438b1eSDarrick J. Wong diff = be32_to_cpu(k1->alloc.ar_blockcount) - 28208438b1eSDarrick J. Wong be32_to_cpu(k2->alloc.ar_blockcount); 28308438b1eSDarrick J. Wong if (diff) 28408438b1eSDarrick J. Wong return diff; 28508438b1eSDarrick J. Wong 28608438b1eSDarrick J. Wong return be32_to_cpu(k1->alloc.ar_startblock) - 28708438b1eSDarrick J. Wong be32_to_cpu(k2->alloc.ar_startblock); 28808438b1eSDarrick J. Wong } 28908438b1eSDarrick J. Wong 290a6a781a5SDarrick J. Wong static xfs_failaddr_t 29130f712c9SDave Chinner xfs_allocbt_verify( 29230f712c9SDave Chinner struct xfs_buf *bp) 29330f712c9SDave Chinner { 294dbd329f1SChristoph Hellwig struct xfs_mount *mp = bp->b_mount; 29530f712c9SDave Chinner struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); 29630f712c9SDave Chinner struct xfs_perag *pag = bp->b_pag; 297a6a781a5SDarrick J. Wong xfs_failaddr_t fa; 29830f712c9SDave Chinner unsigned int level; 299b8f89801SBrian Foster xfs_btnum_t btnum = XFS_BTNUM_BNOi; 300b8f89801SBrian Foster 301b8f89801SBrian Foster if (!xfs_verify_magic(bp, block->bb_magic)) 302b8f89801SBrian Foster return __this_address; 303b8f89801SBrian Foster 304b8f89801SBrian Foster if (xfs_sb_version_hascrc(&mp->m_sb)) { 305b8f89801SBrian Foster fa = xfs_btree_sblock_v5hdr_verify(bp); 306b8f89801SBrian Foster if (fa) 307b8f89801SBrian Foster return fa; 308b8f89801SBrian Foster } 30930f712c9SDave Chinner 31030f712c9SDave Chinner /* 311b8f89801SBrian Foster * The perag may not be attached during grow operations or fully 312b8f89801SBrian Foster * initialized from the AGF during log recovery. Therefore we can only 313b8f89801SBrian Foster * check against maximum tree depth from those contexts. 31430f712c9SDave Chinner * 315b8f89801SBrian Foster * Otherwise check against the per-tree limit. Peek at one of the 316b8f89801SBrian Foster * verifier magic values to determine the type of tree we're verifying 317b8f89801SBrian Foster * against. 31830f712c9SDave Chinner */ 31930f712c9SDave Chinner level = be16_to_cpu(block->bb_level); 320b8f89801SBrian Foster if (bp->b_ops->magic[0] == cpu_to_be32(XFS_ABTC_MAGIC)) 321b8f89801SBrian Foster btnum = XFS_BTNUM_CNTi; 32230f712c9SDave Chinner if (pag && pag->pagf_init) { 323b8f89801SBrian Foster if (level >= pag->pagf_levels[btnum]) 324a6a781a5SDarrick J. Wong return __this_address; 32530f712c9SDave Chinner } else if (level >= mp->m_ag_maxlevels) 326a6a781a5SDarrick J. Wong return __this_address; 32730f712c9SDave Chinner 328c5ab131bSDarrick J. Wong return xfs_btree_sblock_verify(bp, mp->m_alloc_mxr[level != 0]); 32930f712c9SDave Chinner } 33030f712c9SDave Chinner 33130f712c9SDave Chinner static void 33230f712c9SDave Chinner xfs_allocbt_read_verify( 33330f712c9SDave Chinner struct xfs_buf *bp) 33430f712c9SDave Chinner { 335bc1a09b8SDarrick J. Wong xfs_failaddr_t fa; 336bc1a09b8SDarrick J. Wong 33730f712c9SDave Chinner if (!xfs_btree_sblock_verify_crc(bp)) 338bc1a09b8SDarrick J. Wong xfs_verifier_error(bp, -EFSBADCRC, __this_address); 339bc1a09b8SDarrick J. Wong else { 340bc1a09b8SDarrick J. Wong fa = xfs_allocbt_verify(bp); 341bc1a09b8SDarrick J. Wong if (fa) 342bc1a09b8SDarrick J. Wong xfs_verifier_error(bp, -EFSCORRUPTED, fa); 343bc1a09b8SDarrick J. Wong } 34430f712c9SDave Chinner 34531ca03c9SDarrick J. Wong if (bp->b_error) 34630f712c9SDave Chinner trace_xfs_btree_corrupt(bp, _RET_IP_); 34730f712c9SDave Chinner } 34830f712c9SDave Chinner 34930f712c9SDave Chinner static void 35030f712c9SDave Chinner xfs_allocbt_write_verify( 35130f712c9SDave Chinner struct xfs_buf *bp) 35230f712c9SDave Chinner { 353bc1a09b8SDarrick J. Wong xfs_failaddr_t fa; 354bc1a09b8SDarrick J. Wong 355bc1a09b8SDarrick J. Wong fa = xfs_allocbt_verify(bp); 356bc1a09b8SDarrick J. Wong if (fa) { 35730f712c9SDave Chinner trace_xfs_btree_corrupt(bp, _RET_IP_); 358bc1a09b8SDarrick J. Wong xfs_verifier_error(bp, -EFSCORRUPTED, fa); 35930f712c9SDave Chinner return; 36030f712c9SDave Chinner } 36130f712c9SDave Chinner xfs_btree_sblock_calc_crc(bp); 36230f712c9SDave Chinner 36330f712c9SDave Chinner } 36430f712c9SDave Chinner 36527df4f50SBrian Foster const struct xfs_buf_ops xfs_bnobt_buf_ops = { 36627df4f50SBrian Foster .name = "xfs_bnobt", 367b8f89801SBrian Foster .magic = { cpu_to_be32(XFS_ABTB_MAGIC), 368b8f89801SBrian Foster cpu_to_be32(XFS_ABTB_CRC_MAGIC) }, 36930f712c9SDave Chinner .verify_read = xfs_allocbt_read_verify, 37030f712c9SDave Chinner .verify_write = xfs_allocbt_write_verify, 371b5572597SDarrick J. Wong .verify_struct = xfs_allocbt_verify, 37230f712c9SDave Chinner }; 37330f712c9SDave Chinner 37427df4f50SBrian Foster const struct xfs_buf_ops xfs_cntbt_buf_ops = { 37527df4f50SBrian Foster .name = "xfs_cntbt", 376b8f89801SBrian Foster .magic = { cpu_to_be32(XFS_ABTC_MAGIC), 377b8f89801SBrian Foster cpu_to_be32(XFS_ABTC_CRC_MAGIC) }, 37827df4f50SBrian Foster .verify_read = xfs_allocbt_read_verify, 37927df4f50SBrian Foster .verify_write = xfs_allocbt_write_verify, 38027df4f50SBrian Foster .verify_struct = xfs_allocbt_verify, 38127df4f50SBrian Foster }; 38230f712c9SDave Chinner 38330f712c9SDave Chinner STATIC int 38408438b1eSDarrick J. Wong xfs_bnobt_keys_inorder( 38530f712c9SDave Chinner struct xfs_btree_cur *cur, 38630f712c9SDave Chinner union xfs_btree_key *k1, 38730f712c9SDave Chinner union xfs_btree_key *k2) 38830f712c9SDave Chinner { 38930f712c9SDave Chinner return be32_to_cpu(k1->alloc.ar_startblock) < 39030f712c9SDave Chinner be32_to_cpu(k2->alloc.ar_startblock); 39108438b1eSDarrick J. Wong } 39208438b1eSDarrick J. Wong 39308438b1eSDarrick J. Wong STATIC int 39408438b1eSDarrick J. Wong xfs_bnobt_recs_inorder( 39508438b1eSDarrick J. Wong struct xfs_btree_cur *cur, 39608438b1eSDarrick J. Wong union xfs_btree_rec *r1, 39708438b1eSDarrick J. Wong union xfs_btree_rec *r2) 39808438b1eSDarrick J. Wong { 39908438b1eSDarrick J. Wong return be32_to_cpu(r1->alloc.ar_startblock) + 40008438b1eSDarrick J. Wong be32_to_cpu(r1->alloc.ar_blockcount) <= 40108438b1eSDarrick J. Wong be32_to_cpu(r2->alloc.ar_startblock); 40208438b1eSDarrick J. Wong } 40308438b1eSDarrick J. Wong 40408438b1eSDarrick J. Wong STATIC int 40508438b1eSDarrick J. Wong xfs_cntbt_keys_inorder( 40608438b1eSDarrick J. Wong struct xfs_btree_cur *cur, 40708438b1eSDarrick J. Wong union xfs_btree_key *k1, 40808438b1eSDarrick J. Wong union xfs_btree_key *k2) 40908438b1eSDarrick J. Wong { 41030f712c9SDave Chinner return be32_to_cpu(k1->alloc.ar_blockcount) < 41130f712c9SDave Chinner be32_to_cpu(k2->alloc.ar_blockcount) || 41230f712c9SDave Chinner (k1->alloc.ar_blockcount == k2->alloc.ar_blockcount && 41330f712c9SDave Chinner be32_to_cpu(k1->alloc.ar_startblock) < 41430f712c9SDave Chinner be32_to_cpu(k2->alloc.ar_startblock)); 41530f712c9SDave Chinner } 41630f712c9SDave Chinner 41730f712c9SDave Chinner STATIC int 41808438b1eSDarrick J. Wong xfs_cntbt_recs_inorder( 41930f712c9SDave Chinner struct xfs_btree_cur *cur, 42030f712c9SDave Chinner union xfs_btree_rec *r1, 42130f712c9SDave Chinner union xfs_btree_rec *r2) 42230f712c9SDave Chinner { 42330f712c9SDave Chinner return be32_to_cpu(r1->alloc.ar_blockcount) < 42430f712c9SDave Chinner be32_to_cpu(r2->alloc.ar_blockcount) || 42530f712c9SDave Chinner (r1->alloc.ar_blockcount == r2->alloc.ar_blockcount && 42630f712c9SDave Chinner be32_to_cpu(r1->alloc.ar_startblock) < 42730f712c9SDave Chinner be32_to_cpu(r2->alloc.ar_startblock)); 42830f712c9SDave Chinner } 42930f712c9SDave Chinner 43008438b1eSDarrick J. Wong static const struct xfs_btree_ops xfs_bnobt_ops = { 43130f712c9SDave Chinner .rec_len = sizeof(xfs_alloc_rec_t), 43230f712c9SDave Chinner .key_len = sizeof(xfs_alloc_key_t), 43330f712c9SDave Chinner 43430f712c9SDave Chinner .dup_cursor = xfs_allocbt_dup_cursor, 43530f712c9SDave Chinner .set_root = xfs_allocbt_set_root, 43630f712c9SDave Chinner .alloc_block = xfs_allocbt_alloc_block, 43730f712c9SDave Chinner .free_block = xfs_allocbt_free_block, 43830f712c9SDave Chinner .update_lastrec = xfs_allocbt_update_lastrec, 43930f712c9SDave Chinner .get_minrecs = xfs_allocbt_get_minrecs, 44030f712c9SDave Chinner .get_maxrecs = xfs_allocbt_get_maxrecs, 44130f712c9SDave Chinner .init_key_from_rec = xfs_allocbt_init_key_from_rec, 44208438b1eSDarrick J. Wong .init_high_key_from_rec = xfs_bnobt_init_high_key_from_rec, 44330f712c9SDave Chinner .init_rec_from_cur = xfs_allocbt_init_rec_from_cur, 44430f712c9SDave Chinner .init_ptr_from_cur = xfs_allocbt_init_ptr_from_cur, 44508438b1eSDarrick J. Wong .key_diff = xfs_bnobt_key_diff, 44627df4f50SBrian Foster .buf_ops = &xfs_bnobt_buf_ops, 44708438b1eSDarrick J. Wong .diff_two_keys = xfs_bnobt_diff_two_keys, 44808438b1eSDarrick J. Wong .keys_inorder = xfs_bnobt_keys_inorder, 44908438b1eSDarrick J. Wong .recs_inorder = xfs_bnobt_recs_inorder, 45008438b1eSDarrick J. Wong }; 45108438b1eSDarrick J. Wong 45208438b1eSDarrick J. Wong static const struct xfs_btree_ops xfs_cntbt_ops = { 45308438b1eSDarrick J. Wong .rec_len = sizeof(xfs_alloc_rec_t), 45408438b1eSDarrick J. Wong .key_len = sizeof(xfs_alloc_key_t), 45508438b1eSDarrick J. Wong 45608438b1eSDarrick J. Wong .dup_cursor = xfs_allocbt_dup_cursor, 45708438b1eSDarrick J. Wong .set_root = xfs_allocbt_set_root, 45808438b1eSDarrick J. Wong .alloc_block = xfs_allocbt_alloc_block, 45908438b1eSDarrick J. Wong .free_block = xfs_allocbt_free_block, 46008438b1eSDarrick J. Wong .update_lastrec = xfs_allocbt_update_lastrec, 46108438b1eSDarrick J. Wong .get_minrecs = xfs_allocbt_get_minrecs, 46208438b1eSDarrick J. Wong .get_maxrecs = xfs_allocbt_get_maxrecs, 46308438b1eSDarrick J. Wong .init_key_from_rec = xfs_allocbt_init_key_from_rec, 46408438b1eSDarrick J. Wong .init_high_key_from_rec = xfs_cntbt_init_high_key_from_rec, 46508438b1eSDarrick J. Wong .init_rec_from_cur = xfs_allocbt_init_rec_from_cur, 46608438b1eSDarrick J. Wong .init_ptr_from_cur = xfs_allocbt_init_ptr_from_cur, 46708438b1eSDarrick J. Wong .key_diff = xfs_cntbt_key_diff, 46827df4f50SBrian Foster .buf_ops = &xfs_cntbt_buf_ops, 46908438b1eSDarrick J. Wong .diff_two_keys = xfs_cntbt_diff_two_keys, 47008438b1eSDarrick J. Wong .keys_inorder = xfs_cntbt_keys_inorder, 47108438b1eSDarrick J. Wong .recs_inorder = xfs_cntbt_recs_inorder, 47230f712c9SDave Chinner }; 47330f712c9SDave Chinner 47430f712c9SDave Chinner /* 47530f712c9SDave Chinner * Allocate a new allocation btree cursor. 47630f712c9SDave Chinner */ 47730f712c9SDave Chinner struct xfs_btree_cur * /* new alloc btree cursor */ 47830f712c9SDave Chinner xfs_allocbt_init_cursor( 47930f712c9SDave Chinner struct xfs_mount *mp, /* file system mount point */ 48030f712c9SDave Chinner struct xfs_trans *tp, /* transaction pointer */ 48130f712c9SDave Chinner struct xfs_buf *agbp, /* buffer for agf structure */ 48230f712c9SDave Chinner xfs_agnumber_t agno, /* allocation group number */ 48330f712c9SDave Chinner xfs_btnum_t btnum) /* btree identifier */ 48430f712c9SDave Chinner { 4859798f615SChristoph Hellwig struct xfs_agf *agf = agbp->b_addr; 48630f712c9SDave Chinner struct xfs_btree_cur *cur; 48730f712c9SDave Chinner 48830f712c9SDave Chinner ASSERT(btnum == XFS_BTNUM_BNO || btnum == XFS_BTNUM_CNT); 48930f712c9SDave Chinner 490b24a978cSDarrick J. Wong cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_NOFS); 49130f712c9SDave Chinner 49230f712c9SDave Chinner cur->bc_tp = tp; 49330f712c9SDave Chinner cur->bc_mp = mp; 49430f712c9SDave Chinner cur->bc_btnum = btnum; 49530f712c9SDave Chinner cur->bc_blocklog = mp->m_sb.sb_blocklog; 49630f712c9SDave Chinner 49730f712c9SDave Chinner if (btnum == XFS_BTNUM_CNT) { 49808438b1eSDarrick J. Wong cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_abtc_2); 49908438b1eSDarrick J. Wong cur->bc_ops = &xfs_cntbt_ops; 50030f712c9SDave Chinner cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]); 50130f712c9SDave Chinner cur->bc_flags = XFS_BTREE_LASTREC_UPDATE; 50230f712c9SDave Chinner } else { 50308438b1eSDarrick J. Wong cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_abtb_2); 50408438b1eSDarrick J. Wong cur->bc_ops = &xfs_bnobt_ops; 50530f712c9SDave Chinner cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]); 50630f712c9SDave Chinner } 50730f712c9SDave Chinner 508576af732SDave Chinner cur->bc_ag.agbp = agbp; 509576af732SDave Chinner cur->bc_ag.agno = agno; 510576af732SDave Chinner cur->bc_ag.priv.abt.active = false; 51130f712c9SDave Chinner 51230f712c9SDave Chinner if (xfs_sb_version_hascrc(&mp->m_sb)) 51330f712c9SDave Chinner cur->bc_flags |= XFS_BTREE_CRC_BLOCKS; 51430f712c9SDave Chinner 51530f712c9SDave Chinner return cur; 51630f712c9SDave Chinner } 51730f712c9SDave Chinner 51830f712c9SDave Chinner /* 51930f712c9SDave Chinner * Calculate number of records in an alloc btree block. 52030f712c9SDave Chinner */ 52130f712c9SDave Chinner int 52230f712c9SDave Chinner xfs_allocbt_maxrecs( 52330f712c9SDave Chinner struct xfs_mount *mp, 52430f712c9SDave Chinner int blocklen, 52530f712c9SDave Chinner int leaf) 52630f712c9SDave Chinner { 52730f712c9SDave Chinner blocklen -= XFS_ALLOC_BLOCK_LEN(mp); 52830f712c9SDave Chinner 52930f712c9SDave Chinner if (leaf) 53030f712c9SDave Chinner return blocklen / sizeof(xfs_alloc_rec_t); 53130f712c9SDave Chinner return blocklen / (sizeof(xfs_alloc_key_t) + sizeof(xfs_alloc_ptr_t)); 53230f712c9SDave Chinner } 53314861c47SDarrick J. Wong 53414861c47SDarrick J. Wong /* Calculate the freespace btree size for some records. */ 53514861c47SDarrick J. Wong xfs_extlen_t 53614861c47SDarrick J. Wong xfs_allocbt_calc_size( 53714861c47SDarrick J. Wong struct xfs_mount *mp, 53814861c47SDarrick J. Wong unsigned long long len) 53914861c47SDarrick J. Wong { 54014861c47SDarrick J. Wong return xfs_btree_calc_size(mp->m_alloc_mnr, len); 54114861c47SDarrick J. Wong } 542