10b61f8a4SDave Chinner // SPDX-License-Identifier: GPL-2.0 230f712c9SDave Chinner /* 330f712c9SDave Chinner * Copyright (c) 2000-2003,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_inode.h" 1530f712c9SDave Chinner #include "xfs_trans.h" 1630f712c9SDave Chinner #include "xfs_alloc.h" 1730f712c9SDave Chinner #include "xfs_btree.h" 1830f712c9SDave Chinner #include "xfs_bmap_btree.h" 1930f712c9SDave Chinner #include "xfs_bmap.h" 2030f712c9SDave Chinner #include "xfs_error.h" 2130f712c9SDave Chinner #include "xfs_quota.h" 2230f712c9SDave Chinner #include "xfs_trace.h" 23340785ccSDarrick J. Wong #include "xfs_rmap.h" 2430f712c9SDave Chinner 25e7720afaSDarrick J. Wong static struct kmem_cache *xfs_bmbt_cur_cache; 269fa47bdcSDarrick J. Wong 2730f712c9SDave Chinner /* 2830f712c9SDave Chinner * Convert on-disk form of btree root to in-memory form. 2930f712c9SDave Chinner */ 3030f712c9SDave Chinner void 3130f712c9SDave Chinner xfs_bmdr_to_bmbt( 3230f712c9SDave Chinner struct xfs_inode *ip, 3330f712c9SDave Chinner xfs_bmdr_block_t *dblock, 3430f712c9SDave Chinner int dblocklen, 3530f712c9SDave Chinner struct xfs_btree_block *rblock, 3630f712c9SDave Chinner int rblocklen) 3730f712c9SDave Chinner { 3830f712c9SDave Chinner struct xfs_mount *mp = ip->i_mount; 3930f712c9SDave Chinner int dmxr; 4030f712c9SDave Chinner xfs_bmbt_key_t *fkp; 4130f712c9SDave Chinner __be64 *fpp; 4230f712c9SDave Chinner xfs_bmbt_key_t *tkp; 4330f712c9SDave Chinner __be64 *tpp; 4430f712c9SDave Chinner 4530f712c9SDave Chinner xfs_btree_init_block_int(mp, rblock, XFS_BUF_DADDR_NULL, 46b6f41e44SEric Sandeen XFS_BTNUM_BMAP, 0, 0, ip->i_ino, 47f88ae46bSEric Sandeen XFS_BTREE_LONG_PTRS); 4830f712c9SDave Chinner rblock->bb_level = dblock->bb_level; 4930f712c9SDave Chinner ASSERT(be16_to_cpu(rblock->bb_level) > 0); 5030f712c9SDave Chinner rblock->bb_numrecs = dblock->bb_numrecs; 5130f712c9SDave Chinner dmxr = xfs_bmdr_maxrecs(dblocklen, 0); 5230f712c9SDave Chinner fkp = XFS_BMDR_KEY_ADDR(dblock, 1); 5330f712c9SDave Chinner tkp = XFS_BMBT_KEY_ADDR(mp, rblock, 1); 5430f712c9SDave Chinner fpp = XFS_BMDR_PTR_ADDR(dblock, 1, dmxr); 5530f712c9SDave Chinner tpp = XFS_BMAP_BROOT_PTR_ADDR(mp, rblock, 1, rblocklen); 5630f712c9SDave Chinner dmxr = be16_to_cpu(dblock->bb_numrecs); 5730f712c9SDave Chinner memcpy(tkp, fkp, sizeof(*fkp) * dmxr); 5830f712c9SDave Chinner memcpy(tpp, fpp, sizeof(*fpp) * dmxr); 5930f712c9SDave Chinner } 6030f712c9SDave Chinner 6130f712c9SDave Chinner void 626bdcf26aSChristoph Hellwig xfs_bmbt_disk_get_all( 6322ece4e8SDarrick J. Wong const struct xfs_bmbt_rec *rec, 646bdcf26aSChristoph Hellwig struct xfs_bmbt_irec *irec) 6530f712c9SDave Chinner { 666bdcf26aSChristoph Hellwig uint64_t l0 = get_unaligned_be64(&rec->l0); 676bdcf26aSChristoph Hellwig uint64_t l1 = get_unaligned_be64(&rec->l1); 6830f712c9SDave Chinner 696bdcf26aSChristoph Hellwig irec->br_startoff = (l0 & xfs_mask64lo(64 - BMBT_EXNTFLAG_BITLEN)) >> 9; 706bdcf26aSChristoph Hellwig irec->br_startblock = ((l0 & xfs_mask64lo(9)) << 43) | (l1 >> 21); 716bdcf26aSChristoph Hellwig irec->br_blockcount = l1 & xfs_mask64lo(21); 726bdcf26aSChristoph Hellwig if (l0 >> (64 - BMBT_EXNTFLAG_BITLEN)) 736bdcf26aSChristoph Hellwig irec->br_state = XFS_EXT_UNWRITTEN; 746bdcf26aSChristoph Hellwig else 756bdcf26aSChristoph Hellwig irec->br_state = XFS_EXT_NORM; 7630f712c9SDave Chinner } 7730f712c9SDave Chinner 7830f712c9SDave Chinner /* 7930f712c9SDave Chinner * Extract the blockcount field from an on disk bmap extent record. 8030f712c9SDave Chinner */ 8130f712c9SDave Chinner xfs_filblks_t 8230f712c9SDave Chinner xfs_bmbt_disk_get_blockcount( 8323825cd1SDarrick J. Wong const struct xfs_bmbt_rec *r) 8430f712c9SDave Chinner { 8530f712c9SDave Chinner return (xfs_filblks_t)(be64_to_cpu(r->l1) & xfs_mask64lo(21)); 8630f712c9SDave Chinner } 8730f712c9SDave Chinner 8830f712c9SDave Chinner /* 8930f712c9SDave Chinner * Extract the startoff field from a disk format bmap extent record. 9030f712c9SDave Chinner */ 9130f712c9SDave Chinner xfs_fileoff_t 9230f712c9SDave Chinner xfs_bmbt_disk_get_startoff( 9323825cd1SDarrick J. Wong const struct xfs_bmbt_rec *r) 9430f712c9SDave Chinner { 9530f712c9SDave Chinner return ((xfs_fileoff_t)be64_to_cpu(r->l0) & 9630f712c9SDave Chinner xfs_mask64lo(64 - BMBT_EXNTFLAG_BITLEN)) >> 9; 9730f712c9SDave Chinner } 9830f712c9SDave Chinner 9930f712c9SDave Chinner /* 10030f712c9SDave Chinner * Set all the fields in a bmap extent record from the uncompressed form. 10130f712c9SDave Chinner */ 10230f712c9SDave Chinner void 10330f712c9SDave Chinner xfs_bmbt_disk_set_all( 104a67d00a5SChristoph Hellwig struct xfs_bmbt_rec *r, 105a67d00a5SChristoph Hellwig struct xfs_bmbt_irec *s) 10630f712c9SDave Chinner { 107a67d00a5SChristoph Hellwig int extent_flag = (s->br_state != XFS_EXT_NORM); 108a67d00a5SChristoph Hellwig 109a67d00a5SChristoph Hellwig ASSERT(s->br_state == XFS_EXT_NORM || s->br_state == XFS_EXT_UNWRITTEN); 110a67d00a5SChristoph Hellwig ASSERT(!(s->br_startoff & xfs_mask64hi(64-BMBT_STARTOFF_BITLEN))); 111a67d00a5SChristoph Hellwig ASSERT(!(s->br_blockcount & xfs_mask64hi(64-BMBT_BLOCKCOUNT_BITLEN))); 112a67d00a5SChristoph Hellwig ASSERT(!(s->br_startblock & xfs_mask64hi(64-BMBT_STARTBLOCK_BITLEN))); 113a67d00a5SChristoph Hellwig 114135dcc10SChristoph Hellwig put_unaligned_be64( 115a67d00a5SChristoph Hellwig ((xfs_bmbt_rec_base_t)extent_flag << 63) | 116a67d00a5SChristoph Hellwig ((xfs_bmbt_rec_base_t)s->br_startoff << 9) | 117135dcc10SChristoph Hellwig ((xfs_bmbt_rec_base_t)s->br_startblock >> 43), &r->l0); 118135dcc10SChristoph Hellwig put_unaligned_be64( 119a67d00a5SChristoph Hellwig ((xfs_bmbt_rec_base_t)s->br_startblock << 21) | 120a67d00a5SChristoph Hellwig ((xfs_bmbt_rec_base_t)s->br_blockcount & 121135dcc10SChristoph Hellwig (xfs_bmbt_rec_base_t)xfs_mask64lo(21)), &r->l1); 12230f712c9SDave Chinner } 12330f712c9SDave Chinner 12430f712c9SDave Chinner /* 12530f712c9SDave Chinner * Convert in-memory form of btree root to on-disk form. 12630f712c9SDave Chinner */ 12730f712c9SDave Chinner void 12830f712c9SDave Chinner xfs_bmbt_to_bmdr( 12930f712c9SDave Chinner struct xfs_mount *mp, 13030f712c9SDave Chinner struct xfs_btree_block *rblock, 13130f712c9SDave Chinner int rblocklen, 13230f712c9SDave Chinner xfs_bmdr_block_t *dblock, 13330f712c9SDave Chinner int dblocklen) 13430f712c9SDave Chinner { 13530f712c9SDave Chinner int dmxr; 13630f712c9SDave Chinner xfs_bmbt_key_t *fkp; 13730f712c9SDave Chinner __be64 *fpp; 13830f712c9SDave Chinner xfs_bmbt_key_t *tkp; 13930f712c9SDave Chinner __be64 *tpp; 14030f712c9SDave Chinner 14138c26bfdSDave Chinner if (xfs_has_crc(mp)) { 14230f712c9SDave Chinner ASSERT(rblock->bb_magic == cpu_to_be32(XFS_BMAP_CRC_MAGIC)); 143ce748eaaSEric Sandeen ASSERT(uuid_equal(&rblock->bb_u.l.bb_uuid, 144ce748eaaSEric Sandeen &mp->m_sb.sb_meta_uuid)); 14530f712c9SDave Chinner ASSERT(rblock->bb_u.l.bb_blkno == 14630f712c9SDave Chinner cpu_to_be64(XFS_BUF_DADDR_NULL)); 14730f712c9SDave Chinner } else 14830f712c9SDave Chinner ASSERT(rblock->bb_magic == cpu_to_be32(XFS_BMAP_MAGIC)); 149d5cf09baSChristoph Hellwig ASSERT(rblock->bb_u.l.bb_leftsib == cpu_to_be64(NULLFSBLOCK)); 150d5cf09baSChristoph Hellwig ASSERT(rblock->bb_u.l.bb_rightsib == cpu_to_be64(NULLFSBLOCK)); 15130f712c9SDave Chinner ASSERT(rblock->bb_level != 0); 15230f712c9SDave Chinner dblock->bb_level = rblock->bb_level; 15330f712c9SDave Chinner dblock->bb_numrecs = rblock->bb_numrecs; 15430f712c9SDave Chinner dmxr = xfs_bmdr_maxrecs(dblocklen, 0); 15530f712c9SDave Chinner fkp = XFS_BMBT_KEY_ADDR(mp, rblock, 1); 15630f712c9SDave Chinner tkp = XFS_BMDR_KEY_ADDR(dblock, 1); 15730f712c9SDave Chinner fpp = XFS_BMAP_BROOT_PTR_ADDR(mp, rblock, 1, rblocklen); 15830f712c9SDave Chinner tpp = XFS_BMDR_PTR_ADDR(dblock, 1, dmxr); 15930f712c9SDave Chinner dmxr = be16_to_cpu(dblock->bb_numrecs); 16030f712c9SDave Chinner memcpy(tkp, fkp, sizeof(*fkp) * dmxr); 16130f712c9SDave Chinner memcpy(tpp, fpp, sizeof(*fpp) * dmxr); 16230f712c9SDave Chinner } 16330f712c9SDave Chinner 16430f712c9SDave Chinner STATIC struct xfs_btree_cur * 16530f712c9SDave Chinner xfs_bmbt_dup_cursor( 16630f712c9SDave Chinner struct xfs_btree_cur *cur) 16730f712c9SDave Chinner { 16830f712c9SDave Chinner struct xfs_btree_cur *new; 16930f712c9SDave Chinner 17030f712c9SDave Chinner new = xfs_bmbt_init_cursor(cur->bc_mp, cur->bc_tp, 17192219c29SDave Chinner cur->bc_ino.ip, cur->bc_ino.whichfork); 17230f712c9SDave Chinner 17330f712c9SDave Chinner /* 1742c3234d1SDarrick J. Wong * Copy the firstblock, dfops, and flags values, 17530f712c9SDave Chinner * since init cursor doesn't get them. 17630f712c9SDave Chinner */ 17792219c29SDave Chinner new->bc_ino.flags = cur->bc_ino.flags; 17830f712c9SDave Chinner 17930f712c9SDave Chinner return new; 18030f712c9SDave Chinner } 18130f712c9SDave Chinner 18230f712c9SDave Chinner STATIC void 18330f712c9SDave Chinner xfs_bmbt_update_cursor( 18430f712c9SDave Chinner struct xfs_btree_cur *src, 18530f712c9SDave Chinner struct xfs_btree_cur *dst) 18630f712c9SDave Chinner { 187cf612de7SBrian Foster ASSERT((dst->bc_tp->t_firstblock != NULLFSBLOCK) || 188db07349dSChristoph Hellwig (dst->bc_ino.ip->i_diflags & XFS_DIFLAG_REALTIME)); 18930f712c9SDave Chinner 19092219c29SDave Chinner dst->bc_ino.allocated += src->bc_ino.allocated; 191cf612de7SBrian Foster dst->bc_tp->t_firstblock = src->bc_tp->t_firstblock; 19230f712c9SDave Chinner 19392219c29SDave Chinner src->bc_ino.allocated = 0; 19430f712c9SDave Chinner } 19530f712c9SDave Chinner 19630f712c9SDave Chinner STATIC int 19730f712c9SDave Chinner xfs_bmbt_alloc_block( 19830f712c9SDave Chinner struct xfs_btree_cur *cur, 199deb06b9aSDarrick J. Wong const union xfs_btree_ptr *start, 20030f712c9SDave Chinner union xfs_btree_ptr *new, 20130f712c9SDave Chinner int *stat) 20230f712c9SDave Chinner { 20330f712c9SDave Chinner xfs_alloc_arg_t args; /* block allocation args */ 20430f712c9SDave Chinner int error; /* error return value */ 20530f712c9SDave Chinner 20630f712c9SDave Chinner memset(&args, 0, sizeof(args)); 20730f712c9SDave Chinner args.tp = cur->bc_tp; 20830f712c9SDave Chinner args.mp = cur->bc_mp; 209cf612de7SBrian Foster args.fsbno = cur->bc_tp->t_firstblock; 21092219c29SDave Chinner xfs_rmap_ino_bmbt_owner(&args.oinfo, cur->bc_ino.ip->i_ino, 21192219c29SDave Chinner cur->bc_ino.whichfork); 21230f712c9SDave Chinner 21330f712c9SDave Chinner if (args.fsbno == NULLFSBLOCK) { 21430f712c9SDave Chinner args.fsbno = be64_to_cpu(start->l); 21530f712c9SDave Chinner args.type = XFS_ALLOCTYPE_START_BNO; 21630f712c9SDave Chinner /* 21730f712c9SDave Chinner * Make sure there is sufficient room left in the AG to 21830f712c9SDave Chinner * complete a full tree split for an extent insert. If 21930f712c9SDave Chinner * we are converting the middle part of an extent then 22030f712c9SDave Chinner * we may need space for two tree splits. 22130f712c9SDave Chinner * 22230f712c9SDave Chinner * We are relying on the caller to make the correct block 22330f712c9SDave Chinner * reservation for this operation to succeed. If the 22430f712c9SDave Chinner * reservation amount is insufficient then we may fail a 22530f712c9SDave Chinner * block allocation here and corrupt the filesystem. 22630f712c9SDave Chinner */ 227a7e5d03bSChristoph Hellwig args.minleft = args.tp->t_blk_res; 2281214f1cfSBrian Foster } else if (cur->bc_tp->t_flags & XFS_TRANS_LOWMODE) { 22930f712c9SDave Chinner args.type = XFS_ALLOCTYPE_START_BNO; 23030f712c9SDave Chinner } else { 23130f712c9SDave Chinner args.type = XFS_ALLOCTYPE_NEAR_BNO; 23230f712c9SDave Chinner } 23330f712c9SDave Chinner 23430f712c9SDave Chinner args.minlen = args.maxlen = args.prod = 1; 2358ef54797SDave Chinner args.wasdel = cur->bc_ino.flags & XFS_BTCUR_BMBT_WASDEL; 236a7e5d03bSChristoph Hellwig if (!args.wasdel && args.tp->t_blk_res == 0) { 2372451337dSDave Chinner error = -ENOSPC; 23830f712c9SDave Chinner goto error0; 23930f712c9SDave Chinner } 24030f712c9SDave Chinner error = xfs_alloc_vextent(&args); 24130f712c9SDave Chinner if (error) 24230f712c9SDave Chinner goto error0; 24330f712c9SDave Chinner 24430f712c9SDave Chinner if (args.fsbno == NULLFSBLOCK && args.minleft) { 24530f712c9SDave Chinner /* 24630f712c9SDave Chinner * Could not find an AG with enough free space to satisfy 247255c5162SChristoph Hellwig * a full btree split. Try again and if 24830f712c9SDave Chinner * successful activate the lowspace algorithm. 24930f712c9SDave Chinner */ 25030f712c9SDave Chinner args.fsbno = 0; 25130f712c9SDave Chinner args.type = XFS_ALLOCTYPE_FIRST_AG; 25230f712c9SDave Chinner error = xfs_alloc_vextent(&args); 25330f712c9SDave Chinner if (error) 25430f712c9SDave Chinner goto error0; 2551214f1cfSBrian Foster cur->bc_tp->t_flags |= XFS_TRANS_LOWMODE; 25630f712c9SDave Chinner } 2572fcc319dSChristoph Hellwig if (WARN_ON_ONCE(args.fsbno == NULLFSBLOCK)) { 25830f712c9SDave Chinner *stat = 0; 25930f712c9SDave Chinner return 0; 26030f712c9SDave Chinner } 261e157ebdcSCarlos Maiolino 26230f712c9SDave Chinner ASSERT(args.len == 1); 263cf612de7SBrian Foster cur->bc_tp->t_firstblock = args.fsbno; 26492219c29SDave Chinner cur->bc_ino.allocated++; 2656e73a545SChristoph Hellwig cur->bc_ino.ip->i_nblocks++; 26692219c29SDave Chinner xfs_trans_log_inode(args.tp, cur->bc_ino.ip, XFS_ILOG_CORE); 26792219c29SDave Chinner xfs_trans_mod_dquot_byino(args.tp, cur->bc_ino.ip, 26830f712c9SDave Chinner XFS_TRANS_DQ_BCOUNT, 1L); 26930f712c9SDave Chinner 27030f712c9SDave Chinner new->l = cpu_to_be64(args.fsbno); 27130f712c9SDave Chinner 27230f712c9SDave Chinner *stat = 1; 27330f712c9SDave Chinner return 0; 27430f712c9SDave Chinner 27530f712c9SDave Chinner error0: 27630f712c9SDave Chinner return error; 27730f712c9SDave Chinner } 27830f712c9SDave Chinner 27930f712c9SDave Chinner STATIC int 28030f712c9SDave Chinner xfs_bmbt_free_block( 28130f712c9SDave Chinner struct xfs_btree_cur *cur, 28230f712c9SDave Chinner struct xfs_buf *bp) 28330f712c9SDave Chinner { 28430f712c9SDave Chinner struct xfs_mount *mp = cur->bc_mp; 28592219c29SDave Chinner struct xfs_inode *ip = cur->bc_ino.ip; 28630f712c9SDave Chinner struct xfs_trans *tp = cur->bc_tp; 28704fcad80SDave Chinner xfs_fsblock_t fsbno = XFS_DADDR_TO_FSB(mp, xfs_buf_daddr(bp)); 288340785ccSDarrick J. Wong struct xfs_owner_info oinfo; 28930f712c9SDave Chinner 29092219c29SDave Chinner xfs_rmap_ino_bmbt_owner(&oinfo, ip->i_ino, cur->bc_ino.whichfork); 291c201d9caSDarrick J. Wong xfs_free_extent_later(cur->bc_tp, fsbno, 1, &oinfo); 2926e73a545SChristoph Hellwig ip->i_nblocks--; 29330f712c9SDave Chinner 29430f712c9SDave Chinner xfs_trans_log_inode(tp, ip, XFS_ILOG_CORE); 29530f712c9SDave Chinner xfs_trans_mod_dquot_byino(tp, ip, XFS_TRANS_DQ_BCOUNT, -1L); 29630f712c9SDave Chinner return 0; 29730f712c9SDave Chinner } 29830f712c9SDave Chinner 29930f712c9SDave Chinner STATIC int 30030f712c9SDave Chinner xfs_bmbt_get_minrecs( 30130f712c9SDave Chinner struct xfs_btree_cur *cur, 30230f712c9SDave Chinner int level) 30330f712c9SDave Chinner { 30430f712c9SDave Chinner if (level == cur->bc_nlevels - 1) { 30530f712c9SDave Chinner struct xfs_ifork *ifp; 30630f712c9SDave Chinner 307*732436efSDarrick J. Wong ifp = xfs_ifork_ptr(cur->bc_ino.ip, 30892219c29SDave Chinner cur->bc_ino.whichfork); 30930f712c9SDave Chinner 31030f712c9SDave Chinner return xfs_bmbt_maxrecs(cur->bc_mp, 31130f712c9SDave Chinner ifp->if_broot_bytes, level == 0) / 2; 31230f712c9SDave Chinner } 31330f712c9SDave Chinner 31430f712c9SDave Chinner return cur->bc_mp->m_bmap_dmnr[level != 0]; 31530f712c9SDave Chinner } 31630f712c9SDave Chinner 31730f712c9SDave Chinner int 31830f712c9SDave Chinner xfs_bmbt_get_maxrecs( 31930f712c9SDave Chinner struct xfs_btree_cur *cur, 32030f712c9SDave Chinner int level) 32130f712c9SDave Chinner { 32230f712c9SDave Chinner if (level == cur->bc_nlevels - 1) { 32330f712c9SDave Chinner struct xfs_ifork *ifp; 32430f712c9SDave Chinner 325*732436efSDarrick J. Wong ifp = xfs_ifork_ptr(cur->bc_ino.ip, 32692219c29SDave Chinner cur->bc_ino.whichfork); 32730f712c9SDave Chinner 32830f712c9SDave Chinner return xfs_bmbt_maxrecs(cur->bc_mp, 32930f712c9SDave Chinner ifp->if_broot_bytes, level == 0); 33030f712c9SDave Chinner } 33130f712c9SDave Chinner 33230f712c9SDave Chinner return cur->bc_mp->m_bmap_dmxr[level != 0]; 33330f712c9SDave Chinner 33430f712c9SDave Chinner } 33530f712c9SDave Chinner 33630f712c9SDave Chinner /* 33730f712c9SDave Chinner * Get the maximum records we could store in the on-disk format. 33830f712c9SDave Chinner * 33930f712c9SDave Chinner * For non-root nodes this is equivalent to xfs_bmbt_get_maxrecs, but 34030f712c9SDave Chinner * for the root node this checks the available space in the dinode fork 34130f712c9SDave Chinner * so that we can resize the in-memory buffer to match it. After a 34230f712c9SDave Chinner * resize to the maximum size this function returns the same value 34330f712c9SDave Chinner * as xfs_bmbt_get_maxrecs for the root node, too. 34430f712c9SDave Chinner */ 34530f712c9SDave Chinner STATIC int 34630f712c9SDave Chinner xfs_bmbt_get_dmaxrecs( 34730f712c9SDave Chinner struct xfs_btree_cur *cur, 34830f712c9SDave Chinner int level) 34930f712c9SDave Chinner { 35030f712c9SDave Chinner if (level != cur->bc_nlevels - 1) 35130f712c9SDave Chinner return cur->bc_mp->m_bmap_dmxr[level != 0]; 35292219c29SDave Chinner return xfs_bmdr_maxrecs(cur->bc_ino.forksize, level == 0); 35330f712c9SDave Chinner } 35430f712c9SDave Chinner 35530f712c9SDave Chinner STATIC void 35630f712c9SDave Chinner xfs_bmbt_init_key_from_rec( 35730f712c9SDave Chinner union xfs_btree_key *key, 35823825cd1SDarrick J. Wong const union xfs_btree_rec *rec) 35930f712c9SDave Chinner { 36030f712c9SDave Chinner key->bmbt.br_startoff = 36130f712c9SDave Chinner cpu_to_be64(xfs_bmbt_disk_get_startoff(&rec->bmbt)); 36230f712c9SDave Chinner } 36330f712c9SDave Chinner 36430f712c9SDave Chinner STATIC void 365118bb47eSDarrick J. Wong xfs_bmbt_init_high_key_from_rec( 366118bb47eSDarrick J. Wong union xfs_btree_key *key, 36723825cd1SDarrick J. Wong const union xfs_btree_rec *rec) 368118bb47eSDarrick J. Wong { 369118bb47eSDarrick J. Wong key->bmbt.br_startoff = cpu_to_be64( 370118bb47eSDarrick J. Wong xfs_bmbt_disk_get_startoff(&rec->bmbt) + 371118bb47eSDarrick J. Wong xfs_bmbt_disk_get_blockcount(&rec->bmbt) - 1); 372118bb47eSDarrick J. Wong } 373118bb47eSDarrick J. Wong 374118bb47eSDarrick J. Wong STATIC void 37530f712c9SDave Chinner xfs_bmbt_init_rec_from_cur( 37630f712c9SDave Chinner struct xfs_btree_cur *cur, 37730f712c9SDave Chinner union xfs_btree_rec *rec) 37830f712c9SDave Chinner { 37930f712c9SDave Chinner xfs_bmbt_disk_set_all(&rec->bmbt, &cur->bc_rec.b); 38030f712c9SDave Chinner } 38130f712c9SDave Chinner 38230f712c9SDave Chinner STATIC void 38330f712c9SDave Chinner xfs_bmbt_init_ptr_from_cur( 38430f712c9SDave Chinner struct xfs_btree_cur *cur, 38530f712c9SDave Chinner union xfs_btree_ptr *ptr) 38630f712c9SDave Chinner { 38730f712c9SDave Chinner ptr->l = 0; 38830f712c9SDave Chinner } 38930f712c9SDave Chinner 390c8ce540dSDarrick J. Wong STATIC int64_t 39130f712c9SDave Chinner xfs_bmbt_key_diff( 39230f712c9SDave Chinner struct xfs_btree_cur *cur, 393d29d5577SDarrick J. Wong const union xfs_btree_key *key) 39430f712c9SDave Chinner { 395c8ce540dSDarrick J. Wong return (int64_t)be64_to_cpu(key->bmbt.br_startoff) - 39630f712c9SDave Chinner cur->bc_rec.b.br_startoff; 39730f712c9SDave Chinner } 39830f712c9SDave Chinner 399118bb47eSDarrick J. Wong STATIC int64_t 400118bb47eSDarrick J. Wong xfs_bmbt_diff_two_keys( 401118bb47eSDarrick J. Wong struct xfs_btree_cur *cur, 402d29d5577SDarrick J. Wong const union xfs_btree_key *k1, 403d29d5577SDarrick J. Wong const union xfs_btree_key *k2) 404118bb47eSDarrick J. Wong { 405b521c890SDarrick J. Wong uint64_t a = be64_to_cpu(k1->bmbt.br_startoff); 406b521c890SDarrick J. Wong uint64_t b = be64_to_cpu(k2->bmbt.br_startoff); 407b521c890SDarrick J. Wong 408b521c890SDarrick J. Wong /* 409b521c890SDarrick J. Wong * Note: This routine previously casted a and b to int64 and subtracted 410b521c890SDarrick J. Wong * them to generate a result. This lead to problems if b was the 411b521c890SDarrick J. Wong * "maximum" key value (all ones) being signed incorrectly, hence this 412b521c890SDarrick J. Wong * somewhat less efficient version. 413b521c890SDarrick J. Wong */ 414b521c890SDarrick J. Wong if (a > b) 415b521c890SDarrick J. Wong return 1; 416b521c890SDarrick J. Wong if (b > a) 417b521c890SDarrick J. Wong return -1; 418b521c890SDarrick J. Wong return 0; 419118bb47eSDarrick J. Wong } 420118bb47eSDarrick J. Wong 421a6a781a5SDarrick J. Wong static xfs_failaddr_t 42230f712c9SDave Chinner xfs_bmbt_verify( 42330f712c9SDave Chinner struct xfs_buf *bp) 42430f712c9SDave Chinner { 425dbd329f1SChristoph Hellwig struct xfs_mount *mp = bp->b_mount; 42630f712c9SDave Chinner struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); 427a6a781a5SDarrick J. Wong xfs_failaddr_t fa; 42830f712c9SDave Chinner unsigned int level; 42930f712c9SDave Chinner 43039708c20SBrian Foster if (!xfs_verify_magic(bp, block->bb_magic)) 43139708c20SBrian Foster return __this_address; 43239708c20SBrian Foster 433ebd9027dSDave Chinner if (xfs_has_crc(mp)) { 43430f712c9SDave Chinner /* 43530f712c9SDave Chinner * XXX: need a better way of verifying the owner here. Right now 43630f712c9SDave Chinner * just make sure there has been one set. 43730f712c9SDave Chinner */ 438a6a781a5SDarrick J. Wong fa = xfs_btree_lblock_v5hdr_verify(bp, XFS_RMAP_OWN_UNKNOWN); 439a6a781a5SDarrick J. Wong if (fa) 440a6a781a5SDarrick J. Wong return fa; 44130f712c9SDave Chinner } 44230f712c9SDave Chinner 44330f712c9SDave Chinner /* 44430f712c9SDave Chinner * numrecs and level verification. 44530f712c9SDave Chinner * 44630f712c9SDave Chinner * We don't know what fork we belong to, so just verify that the level 44730f712c9SDave Chinner * is less than the maximum of the two. Later checks will be more 44830f712c9SDave Chinner * precise. 44930f712c9SDave Chinner */ 45030f712c9SDave Chinner level = be16_to_cpu(block->bb_level); 45130f712c9SDave Chinner if (level > max(mp->m_bm_maxlevels[0], mp->m_bm_maxlevels[1])) 452a6a781a5SDarrick J. Wong return __this_address; 45330f712c9SDave Chinner 4548368a601SDarrick J. Wong return xfs_btree_lblock_verify(bp, mp->m_bmap_dmxr[level != 0]); 45530f712c9SDave Chinner } 45630f712c9SDave Chinner 45730f712c9SDave Chinner static void 45830f712c9SDave Chinner xfs_bmbt_read_verify( 45930f712c9SDave Chinner struct xfs_buf *bp) 46030f712c9SDave Chinner { 461bc1a09b8SDarrick J. Wong xfs_failaddr_t fa; 462bc1a09b8SDarrick J. Wong 46330f712c9SDave Chinner if (!xfs_btree_lblock_verify_crc(bp)) 464bc1a09b8SDarrick J. Wong xfs_verifier_error(bp, -EFSBADCRC, __this_address); 465bc1a09b8SDarrick J. Wong else { 466bc1a09b8SDarrick J. Wong fa = xfs_bmbt_verify(bp); 467bc1a09b8SDarrick J. Wong if (fa) 468bc1a09b8SDarrick J. Wong xfs_verifier_error(bp, -EFSCORRUPTED, fa); 469bc1a09b8SDarrick J. Wong } 47030f712c9SDave Chinner 47131ca03c9SDarrick J. Wong if (bp->b_error) 47230f712c9SDave Chinner trace_xfs_btree_corrupt(bp, _RET_IP_); 47330f712c9SDave Chinner } 47430f712c9SDave Chinner 47530f712c9SDave Chinner static void 47630f712c9SDave Chinner xfs_bmbt_write_verify( 47730f712c9SDave Chinner struct xfs_buf *bp) 47830f712c9SDave Chinner { 479bc1a09b8SDarrick J. Wong xfs_failaddr_t fa; 480bc1a09b8SDarrick J. Wong 481bc1a09b8SDarrick J. Wong fa = xfs_bmbt_verify(bp); 482bc1a09b8SDarrick J. Wong if (fa) { 48330f712c9SDave Chinner trace_xfs_btree_corrupt(bp, _RET_IP_); 484bc1a09b8SDarrick J. Wong xfs_verifier_error(bp, -EFSCORRUPTED, fa); 48530f712c9SDave Chinner return; 48630f712c9SDave Chinner } 48730f712c9SDave Chinner xfs_btree_lblock_calc_crc(bp); 48830f712c9SDave Chinner } 48930f712c9SDave Chinner 49030f712c9SDave Chinner const struct xfs_buf_ops xfs_bmbt_buf_ops = { 491233135b7SEric Sandeen .name = "xfs_bmbt", 49239708c20SBrian Foster .magic = { cpu_to_be32(XFS_BMAP_MAGIC), 49339708c20SBrian Foster cpu_to_be32(XFS_BMAP_CRC_MAGIC) }, 49430f712c9SDave Chinner .verify_read = xfs_bmbt_read_verify, 49530f712c9SDave Chinner .verify_write = xfs_bmbt_write_verify, 496b5572597SDarrick J. Wong .verify_struct = xfs_bmbt_verify, 49730f712c9SDave Chinner }; 49830f712c9SDave Chinner 49930f712c9SDave Chinner 50030f712c9SDave Chinner STATIC int 50130f712c9SDave Chinner xfs_bmbt_keys_inorder( 50230f712c9SDave Chinner struct xfs_btree_cur *cur, 5038e38dc88SDarrick J. Wong const union xfs_btree_key *k1, 5048e38dc88SDarrick J. Wong const union xfs_btree_key *k2) 50530f712c9SDave Chinner { 50630f712c9SDave Chinner return be64_to_cpu(k1->bmbt.br_startoff) < 50730f712c9SDave Chinner be64_to_cpu(k2->bmbt.br_startoff); 50830f712c9SDave Chinner } 50930f712c9SDave Chinner 51030f712c9SDave Chinner STATIC int 51130f712c9SDave Chinner xfs_bmbt_recs_inorder( 51230f712c9SDave Chinner struct xfs_btree_cur *cur, 5138e38dc88SDarrick J. Wong const union xfs_btree_rec *r1, 5148e38dc88SDarrick J. Wong const union xfs_btree_rec *r2) 51530f712c9SDave Chinner { 51630f712c9SDave Chinner return xfs_bmbt_disk_get_startoff(&r1->bmbt) + 51730f712c9SDave Chinner xfs_bmbt_disk_get_blockcount(&r1->bmbt) <= 51830f712c9SDave Chinner xfs_bmbt_disk_get_startoff(&r2->bmbt); 51930f712c9SDave Chinner } 52030f712c9SDave Chinner 52130f712c9SDave Chinner static const struct xfs_btree_ops xfs_bmbt_ops = { 52230f712c9SDave Chinner .rec_len = sizeof(xfs_bmbt_rec_t), 52330f712c9SDave Chinner .key_len = sizeof(xfs_bmbt_key_t), 52430f712c9SDave Chinner 52530f712c9SDave Chinner .dup_cursor = xfs_bmbt_dup_cursor, 52630f712c9SDave Chinner .update_cursor = xfs_bmbt_update_cursor, 52730f712c9SDave Chinner .alloc_block = xfs_bmbt_alloc_block, 52830f712c9SDave Chinner .free_block = xfs_bmbt_free_block, 52930f712c9SDave Chinner .get_maxrecs = xfs_bmbt_get_maxrecs, 53030f712c9SDave Chinner .get_minrecs = xfs_bmbt_get_minrecs, 53130f712c9SDave Chinner .get_dmaxrecs = xfs_bmbt_get_dmaxrecs, 53230f712c9SDave Chinner .init_key_from_rec = xfs_bmbt_init_key_from_rec, 533118bb47eSDarrick J. Wong .init_high_key_from_rec = xfs_bmbt_init_high_key_from_rec, 53430f712c9SDave Chinner .init_rec_from_cur = xfs_bmbt_init_rec_from_cur, 53530f712c9SDave Chinner .init_ptr_from_cur = xfs_bmbt_init_ptr_from_cur, 53630f712c9SDave Chinner .key_diff = xfs_bmbt_key_diff, 537118bb47eSDarrick J. Wong .diff_two_keys = xfs_bmbt_diff_two_keys, 53830f712c9SDave Chinner .buf_ops = &xfs_bmbt_buf_ops, 53930f712c9SDave Chinner .keys_inorder = xfs_bmbt_keys_inorder, 54030f712c9SDave Chinner .recs_inorder = xfs_bmbt_recs_inorder, 54130f712c9SDave Chinner }; 54230f712c9SDave Chinner 54330f712c9SDave Chinner /* 54430f712c9SDave Chinner * Allocate a new bmap btree cursor. 54530f712c9SDave Chinner */ 54630f712c9SDave Chinner struct xfs_btree_cur * /* new bmap btree cursor */ 54730f712c9SDave Chinner xfs_bmbt_init_cursor( 54830f712c9SDave Chinner struct xfs_mount *mp, /* file system mount point */ 54930f712c9SDave Chinner struct xfs_trans *tp, /* transaction pointer */ 55030f712c9SDave Chinner struct xfs_inode *ip, /* inode owning the btree */ 55130f712c9SDave Chinner int whichfork) /* data or attr fork */ 55230f712c9SDave Chinner { 553*732436efSDarrick J. Wong struct xfs_ifork *ifp = xfs_ifork_ptr(ip, whichfork); 55430f712c9SDave Chinner struct xfs_btree_cur *cur; 5553993baebSDarrick J. Wong ASSERT(whichfork != XFS_COW_FORK); 55630f712c9SDave Chinner 557c940a0c5SDarrick J. Wong cur = xfs_btree_alloc_cursor(mp, tp, XFS_BTNUM_BMAP, 5589fa47bdcSDarrick J. Wong mp->m_bm_maxlevels[whichfork], xfs_bmbt_cur_cache); 55930f712c9SDave Chinner cur->bc_nlevels = be16_to_cpu(ifp->if_broot->bb_level) + 1; 56011ef38afSDave Chinner cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_bmbt_2); 56130f712c9SDave Chinner 56230f712c9SDave Chinner cur->bc_ops = &xfs_bmbt_ops; 56330f712c9SDave Chinner cur->bc_flags = XFS_BTREE_LONG_PTRS | XFS_BTREE_ROOT_IN_INODE; 56438c26bfdSDave Chinner if (xfs_has_crc(mp)) 56530f712c9SDave Chinner cur->bc_flags |= XFS_BTREE_CRC_BLOCKS; 56630f712c9SDave Chinner 56792219c29SDave Chinner cur->bc_ino.forksize = XFS_IFORK_SIZE(ip, whichfork); 56892219c29SDave Chinner cur->bc_ino.ip = ip; 56992219c29SDave Chinner cur->bc_ino.allocated = 0; 57092219c29SDave Chinner cur->bc_ino.flags = 0; 57192219c29SDave Chinner cur->bc_ino.whichfork = whichfork; 57230f712c9SDave Chinner 57330f712c9SDave Chinner return cur; 57430f712c9SDave Chinner } 57530f712c9SDave Chinner 5760ed5f735SDarrick J. Wong /* Calculate number of records in a block mapping btree block. */ 5770ed5f735SDarrick J. Wong static inline unsigned int 5780ed5f735SDarrick J. Wong xfs_bmbt_block_maxrecs( 5790ed5f735SDarrick J. Wong unsigned int blocklen, 5800ed5f735SDarrick J. Wong bool leaf) 5810ed5f735SDarrick J. Wong { 5820ed5f735SDarrick J. Wong if (leaf) 5830ed5f735SDarrick J. Wong return blocklen / sizeof(xfs_bmbt_rec_t); 5840ed5f735SDarrick J. Wong return blocklen / (sizeof(xfs_bmbt_key_t) + sizeof(xfs_bmbt_ptr_t)); 5850ed5f735SDarrick J. Wong } 5860ed5f735SDarrick J. Wong 58730f712c9SDave Chinner /* 58830f712c9SDave Chinner * Calculate number of records in a bmap btree block. 58930f712c9SDave Chinner */ 59030f712c9SDave Chinner int 59130f712c9SDave Chinner xfs_bmbt_maxrecs( 59230f712c9SDave Chinner struct xfs_mount *mp, 59330f712c9SDave Chinner int blocklen, 59430f712c9SDave Chinner int leaf) 59530f712c9SDave Chinner { 59630f712c9SDave Chinner blocklen -= XFS_BMBT_BLOCK_LEN(mp); 5970ed5f735SDarrick J. Wong return xfs_bmbt_block_maxrecs(blocklen, leaf); 5980ed5f735SDarrick J. Wong } 59930f712c9SDave Chinner 600df9ad5ccSChandan Babu R /* 601df9ad5ccSChandan Babu R * Calculate the maximum possible height of the btree that the on-disk format 602df9ad5ccSChandan Babu R * supports. This is used for sizing structures large enough to support every 603df9ad5ccSChandan Babu R * possible configuration of a filesystem that might get mounted. 604df9ad5ccSChandan Babu R */ 6050ed5f735SDarrick J. Wong unsigned int 6060ed5f735SDarrick J. Wong xfs_bmbt_maxlevels_ondisk(void) 6070ed5f735SDarrick J. Wong { 6080ed5f735SDarrick J. Wong unsigned int minrecs[2]; 6090ed5f735SDarrick J. Wong unsigned int blocklen; 6100ed5f735SDarrick J. Wong 6110ed5f735SDarrick J. Wong blocklen = min(XFS_MIN_BLOCKSIZE - XFS_BTREE_SBLOCK_LEN, 6120ed5f735SDarrick J. Wong XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN); 6130ed5f735SDarrick J. Wong 6140ed5f735SDarrick J. Wong minrecs[0] = xfs_bmbt_block_maxrecs(blocklen, true) / 2; 6150ed5f735SDarrick J. Wong minrecs[1] = xfs_bmbt_block_maxrecs(blocklen, false) / 2; 6160ed5f735SDarrick J. Wong 6170ed5f735SDarrick J. Wong /* One extra level for the inode root. */ 618df9ad5ccSChandan Babu R return xfs_btree_compute_maxlevels(minrecs, 619df9ad5ccSChandan Babu R XFS_MAX_EXTCNT_DATA_FORK_LARGE) + 1; 62030f712c9SDave Chinner } 62130f712c9SDave Chinner 62230f712c9SDave Chinner /* 62330f712c9SDave Chinner * Calculate number of records in a bmap btree inode root. 62430f712c9SDave Chinner */ 62530f712c9SDave Chinner int 62630f712c9SDave Chinner xfs_bmdr_maxrecs( 62730f712c9SDave Chinner int blocklen, 62830f712c9SDave Chinner int leaf) 62930f712c9SDave Chinner { 63030f712c9SDave Chinner blocklen -= sizeof(xfs_bmdr_block_t); 63130f712c9SDave Chinner 63230f712c9SDave Chinner if (leaf) 63330f712c9SDave Chinner return blocklen / sizeof(xfs_bmdr_rec_t); 63430f712c9SDave Chinner return blocklen / (sizeof(xfs_bmdr_key_t) + sizeof(xfs_bmdr_ptr_t)); 63530f712c9SDave Chinner } 63630f712c9SDave Chinner 63730f712c9SDave Chinner /* 63830f712c9SDave Chinner * Change the owner of a btree format fork fo the inode passed in. Change it to 63930f712c9SDave Chinner * the owner of that is passed in so that we can change owners before or after 64030f712c9SDave Chinner * we switch forks between inodes. The operation that the caller is doing will 64130f712c9SDave Chinner * determine whether is needs to change owner before or after the switch. 64230f712c9SDave Chinner * 64330f712c9SDave Chinner * For demand paged transactional modification, the fork switch should be done 64430f712c9SDave Chinner * after reading in all the blocks, modifying them and pinning them in the 64530f712c9SDave Chinner * transaction. For modification when the buffers are already pinned in memory, 64630f712c9SDave Chinner * the fork switch can be done before changing the owner as we won't need to 64730f712c9SDave Chinner * validate the owner until the btree buffers are unpinned and writes can occur 64830f712c9SDave Chinner * again. 64930f712c9SDave Chinner * 65030f712c9SDave Chinner * For recovery based ownership change, there is no transactional context and 65130f712c9SDave Chinner * so a buffer list must be supplied so that we can record the buffers that we 65230f712c9SDave Chinner * modified for the caller to issue IO on. 65330f712c9SDave Chinner */ 65430f712c9SDave Chinner int 65530f712c9SDave Chinner xfs_bmbt_change_owner( 65630f712c9SDave Chinner struct xfs_trans *tp, 65730f712c9SDave Chinner struct xfs_inode *ip, 65830f712c9SDave Chinner int whichfork, 65930f712c9SDave Chinner xfs_ino_t new_owner, 66030f712c9SDave Chinner struct list_head *buffer_list) 66130f712c9SDave Chinner { 66230f712c9SDave Chinner struct xfs_btree_cur *cur; 66330f712c9SDave Chinner int error; 66430f712c9SDave Chinner 66530f712c9SDave Chinner ASSERT(tp || buffer_list); 66630f712c9SDave Chinner ASSERT(!(tp && buffer_list)); 667*732436efSDarrick J. Wong ASSERT(xfs_ifork_ptr(ip, whichfork)->if_format == XFS_DINODE_FMT_BTREE); 66830f712c9SDave Chinner 66930f712c9SDave Chinner cur = xfs_bmbt_init_cursor(ip->i_mount, tp, ip, whichfork); 6708ef54797SDave Chinner cur->bc_ino.flags |= XFS_BTCUR_BMBT_INVALID_OWNER; 67130f712c9SDave Chinner 67230f712c9SDave Chinner error = xfs_btree_change_owner(cur, new_owner, buffer_list); 6730b04b6b8SDarrick J. Wong xfs_btree_del_cursor(cur, error); 67430f712c9SDave Chinner return error; 67530f712c9SDave Chinner } 67614861c47SDarrick J. Wong 67714861c47SDarrick J. Wong /* Calculate the bmap btree size for some records. */ 67814861c47SDarrick J. Wong unsigned long long 67914861c47SDarrick J. Wong xfs_bmbt_calc_size( 68014861c47SDarrick J. Wong struct xfs_mount *mp, 68114861c47SDarrick J. Wong unsigned long long len) 68214861c47SDarrick J. Wong { 68314861c47SDarrick J. Wong return xfs_btree_calc_size(mp->m_bmap_dmnr, len); 68414861c47SDarrick J. Wong } 6859fa47bdcSDarrick J. Wong 6869fa47bdcSDarrick J. Wong int __init 6879fa47bdcSDarrick J. Wong xfs_bmbt_init_cur_cache(void) 6889fa47bdcSDarrick J. Wong { 6899fa47bdcSDarrick J. Wong xfs_bmbt_cur_cache = kmem_cache_create("xfs_bmbt_cur", 6909fa47bdcSDarrick J. Wong xfs_btree_cur_sizeof(xfs_bmbt_maxlevels_ondisk()), 6919fa47bdcSDarrick J. Wong 0, 0, NULL); 6929fa47bdcSDarrick J. Wong 6939fa47bdcSDarrick J. Wong if (!xfs_bmbt_cur_cache) 6949fa47bdcSDarrick J. Wong return -ENOMEM; 6959fa47bdcSDarrick J. Wong return 0; 6969fa47bdcSDarrick J. Wong } 6979fa47bdcSDarrick J. Wong 6989fa47bdcSDarrick J. Wong void 6999fa47bdcSDarrick J. Wong xfs_bmbt_destroy_cur_cache(void) 7009fa47bdcSDarrick J. Wong { 7019fa47bdcSDarrick J. Wong kmem_cache_destroy(xfs_bmbt_cur_cache); 7029fa47bdcSDarrick J. Wong xfs_bmbt_cur_cache = NULL; 7039fa47bdcSDarrick J. Wong } 704