130f712c9SDave Chinner /* 230f712c9SDave Chinner * Copyright (c) 2000-2003,2005 Silicon Graphics, Inc. 330f712c9SDave Chinner * All Rights Reserved. 430f712c9SDave Chinner * 530f712c9SDave Chinner * This program is free software; you can redistribute it and/or 630f712c9SDave Chinner * modify it under the terms of the GNU General Public License as 730f712c9SDave Chinner * published by the Free Software Foundation. 830f712c9SDave Chinner * 930f712c9SDave Chinner * This program is distributed in the hope that it would be useful, 1030f712c9SDave Chinner * but WITHOUT ANY WARRANTY; without even the implied warranty of 1130f712c9SDave Chinner * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1230f712c9SDave Chinner * GNU General Public License for more details. 1330f712c9SDave Chinner * 1430f712c9SDave Chinner * You should have received a copy of the GNU General Public License 1530f712c9SDave Chinner * along with this program; if not, write the Free Software Foundation, 1630f712c9SDave Chinner * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 1730f712c9SDave Chinner */ 1830f712c9SDave Chinner #include "xfs.h" 1930f712c9SDave Chinner #include "xfs_fs.h" 2030f712c9SDave Chinner #include "xfs_shared.h" 2130f712c9SDave Chinner #include "xfs_format.h" 2230f712c9SDave Chinner #include "xfs_log_format.h" 2330f712c9SDave Chinner #include "xfs_trans_resv.h" 2430f712c9SDave Chinner #include "xfs_bit.h" 2530f712c9SDave Chinner #include "xfs_mount.h" 263ab78df2SDarrick J. Wong #include "xfs_defer.h" 2730f712c9SDave Chinner #include "xfs_inode.h" 2830f712c9SDave Chinner #include "xfs_trans.h" 2930f712c9SDave Chinner #include "xfs_inode_item.h" 3030f712c9SDave Chinner #include "xfs_alloc.h" 3130f712c9SDave Chinner #include "xfs_btree.h" 3230f712c9SDave Chinner #include "xfs_bmap_btree.h" 3330f712c9SDave Chinner #include "xfs_bmap.h" 3430f712c9SDave Chinner #include "xfs_error.h" 3530f712c9SDave Chinner #include "xfs_quota.h" 3630f712c9SDave Chinner #include "xfs_trace.h" 3730f712c9SDave Chinner #include "xfs_cksum.h" 38340785ccSDarrick J. Wong #include "xfs_rmap.h" 3930f712c9SDave Chinner 4030f712c9SDave Chinner /* 4130f712c9SDave Chinner * Convert on-disk form of btree root to in-memory form. 4230f712c9SDave Chinner */ 4330f712c9SDave Chinner void 4430f712c9SDave Chinner xfs_bmdr_to_bmbt( 4530f712c9SDave Chinner struct xfs_inode *ip, 4630f712c9SDave Chinner xfs_bmdr_block_t *dblock, 4730f712c9SDave Chinner int dblocklen, 4830f712c9SDave Chinner struct xfs_btree_block *rblock, 4930f712c9SDave Chinner int rblocklen) 5030f712c9SDave Chinner { 5130f712c9SDave Chinner struct xfs_mount *mp = ip->i_mount; 5230f712c9SDave Chinner int dmxr; 5330f712c9SDave Chinner xfs_bmbt_key_t *fkp; 5430f712c9SDave Chinner __be64 *fpp; 5530f712c9SDave Chinner xfs_bmbt_key_t *tkp; 5630f712c9SDave Chinner __be64 *tpp; 5730f712c9SDave Chinner 5830f712c9SDave Chinner xfs_btree_init_block_int(mp, rblock, XFS_BUF_DADDR_NULL, 59b6f41e44SEric Sandeen XFS_BTNUM_BMAP, 0, 0, ip->i_ino, 60f88ae46bSEric Sandeen XFS_BTREE_LONG_PTRS); 6130f712c9SDave Chinner rblock->bb_level = dblock->bb_level; 6230f712c9SDave Chinner ASSERT(be16_to_cpu(rblock->bb_level) > 0); 6330f712c9SDave Chinner rblock->bb_numrecs = dblock->bb_numrecs; 6430f712c9SDave Chinner dmxr = xfs_bmdr_maxrecs(dblocklen, 0); 6530f712c9SDave Chinner fkp = XFS_BMDR_KEY_ADDR(dblock, 1); 6630f712c9SDave Chinner tkp = XFS_BMBT_KEY_ADDR(mp, rblock, 1); 6730f712c9SDave Chinner fpp = XFS_BMDR_PTR_ADDR(dblock, 1, dmxr); 6830f712c9SDave Chinner tpp = XFS_BMAP_BROOT_PTR_ADDR(mp, rblock, 1, rblocklen); 6930f712c9SDave Chinner dmxr = be16_to_cpu(dblock->bb_numrecs); 7030f712c9SDave Chinner memcpy(tkp, fkp, sizeof(*fkp) * dmxr); 7130f712c9SDave Chinner memcpy(tpp, fpp, sizeof(*fpp) * dmxr); 7230f712c9SDave Chinner } 7330f712c9SDave Chinner 7430f712c9SDave Chinner void 756bdcf26aSChristoph Hellwig xfs_bmbt_disk_get_all( 766bdcf26aSChristoph Hellwig struct xfs_bmbt_rec *rec, 776bdcf26aSChristoph Hellwig struct xfs_bmbt_irec *irec) 7830f712c9SDave Chinner { 796bdcf26aSChristoph Hellwig uint64_t l0 = get_unaligned_be64(&rec->l0); 806bdcf26aSChristoph Hellwig uint64_t l1 = get_unaligned_be64(&rec->l1); 8130f712c9SDave Chinner 826bdcf26aSChristoph Hellwig irec->br_startoff = (l0 & xfs_mask64lo(64 - BMBT_EXNTFLAG_BITLEN)) >> 9; 836bdcf26aSChristoph Hellwig irec->br_startblock = ((l0 & xfs_mask64lo(9)) << 43) | (l1 >> 21); 846bdcf26aSChristoph Hellwig irec->br_blockcount = l1 & xfs_mask64lo(21); 856bdcf26aSChristoph Hellwig if (l0 >> (64 - BMBT_EXNTFLAG_BITLEN)) 866bdcf26aSChristoph Hellwig irec->br_state = XFS_EXT_UNWRITTEN; 876bdcf26aSChristoph Hellwig else 886bdcf26aSChristoph Hellwig irec->br_state = XFS_EXT_NORM; 8930f712c9SDave Chinner } 9030f712c9SDave Chinner 9130f712c9SDave Chinner /* 9230f712c9SDave Chinner * Extract the blockcount field from an on disk bmap extent record. 9330f712c9SDave Chinner */ 9430f712c9SDave Chinner xfs_filblks_t 9530f712c9SDave Chinner xfs_bmbt_disk_get_blockcount( 9630f712c9SDave Chinner xfs_bmbt_rec_t *r) 9730f712c9SDave Chinner { 9830f712c9SDave Chinner return (xfs_filblks_t)(be64_to_cpu(r->l1) & xfs_mask64lo(21)); 9930f712c9SDave Chinner } 10030f712c9SDave Chinner 10130f712c9SDave Chinner /* 10230f712c9SDave Chinner * Extract the startoff field from a disk format bmap extent record. 10330f712c9SDave Chinner */ 10430f712c9SDave Chinner xfs_fileoff_t 10530f712c9SDave Chinner xfs_bmbt_disk_get_startoff( 10630f712c9SDave Chinner xfs_bmbt_rec_t *r) 10730f712c9SDave Chinner { 10830f712c9SDave Chinner return ((xfs_fileoff_t)be64_to_cpu(r->l0) & 10930f712c9SDave Chinner xfs_mask64lo(64 - BMBT_EXNTFLAG_BITLEN)) >> 9; 11030f712c9SDave Chinner } 11130f712c9SDave Chinner 11230f712c9SDave Chinner /* 11330f712c9SDave Chinner * Set all the fields in a bmap extent record from the uncompressed form. 11430f712c9SDave Chinner */ 11530f712c9SDave Chinner void 11630f712c9SDave Chinner xfs_bmbt_disk_set_all( 117a67d00a5SChristoph Hellwig struct xfs_bmbt_rec *r, 118a67d00a5SChristoph Hellwig struct xfs_bmbt_irec *s) 11930f712c9SDave Chinner { 120a67d00a5SChristoph Hellwig int extent_flag = (s->br_state != XFS_EXT_NORM); 121a67d00a5SChristoph Hellwig 122a67d00a5SChristoph Hellwig ASSERT(s->br_state == XFS_EXT_NORM || s->br_state == XFS_EXT_UNWRITTEN); 123a67d00a5SChristoph Hellwig ASSERT(!(s->br_startoff & xfs_mask64hi(64-BMBT_STARTOFF_BITLEN))); 124a67d00a5SChristoph Hellwig ASSERT(!(s->br_blockcount & xfs_mask64hi(64-BMBT_BLOCKCOUNT_BITLEN))); 125a67d00a5SChristoph Hellwig ASSERT(!(s->br_startblock & xfs_mask64hi(64-BMBT_STARTBLOCK_BITLEN))); 126a67d00a5SChristoph Hellwig 127135dcc10SChristoph Hellwig put_unaligned_be64( 128a67d00a5SChristoph Hellwig ((xfs_bmbt_rec_base_t)extent_flag << 63) | 129a67d00a5SChristoph Hellwig ((xfs_bmbt_rec_base_t)s->br_startoff << 9) | 130135dcc10SChristoph Hellwig ((xfs_bmbt_rec_base_t)s->br_startblock >> 43), &r->l0); 131135dcc10SChristoph Hellwig put_unaligned_be64( 132a67d00a5SChristoph Hellwig ((xfs_bmbt_rec_base_t)s->br_startblock << 21) | 133a67d00a5SChristoph Hellwig ((xfs_bmbt_rec_base_t)s->br_blockcount & 134135dcc10SChristoph Hellwig (xfs_bmbt_rec_base_t)xfs_mask64lo(21)), &r->l1); 13530f712c9SDave Chinner } 13630f712c9SDave Chinner 13730f712c9SDave Chinner /* 13830f712c9SDave Chinner * Convert in-memory form of btree root to on-disk form. 13930f712c9SDave Chinner */ 14030f712c9SDave Chinner void 14130f712c9SDave Chinner xfs_bmbt_to_bmdr( 14230f712c9SDave Chinner struct xfs_mount *mp, 14330f712c9SDave Chinner struct xfs_btree_block *rblock, 14430f712c9SDave Chinner int rblocklen, 14530f712c9SDave Chinner xfs_bmdr_block_t *dblock, 14630f712c9SDave Chinner int dblocklen) 14730f712c9SDave Chinner { 14830f712c9SDave Chinner int dmxr; 14930f712c9SDave Chinner xfs_bmbt_key_t *fkp; 15030f712c9SDave Chinner __be64 *fpp; 15130f712c9SDave Chinner xfs_bmbt_key_t *tkp; 15230f712c9SDave Chinner __be64 *tpp; 15330f712c9SDave Chinner 15430f712c9SDave Chinner if (xfs_sb_version_hascrc(&mp->m_sb)) { 15530f712c9SDave Chinner ASSERT(rblock->bb_magic == cpu_to_be32(XFS_BMAP_CRC_MAGIC)); 156ce748eaaSEric Sandeen ASSERT(uuid_equal(&rblock->bb_u.l.bb_uuid, 157ce748eaaSEric Sandeen &mp->m_sb.sb_meta_uuid)); 15830f712c9SDave Chinner ASSERT(rblock->bb_u.l.bb_blkno == 15930f712c9SDave Chinner cpu_to_be64(XFS_BUF_DADDR_NULL)); 16030f712c9SDave Chinner } else 16130f712c9SDave Chinner ASSERT(rblock->bb_magic == cpu_to_be32(XFS_BMAP_MAGIC)); 162d5cf09baSChristoph Hellwig ASSERT(rblock->bb_u.l.bb_leftsib == cpu_to_be64(NULLFSBLOCK)); 163d5cf09baSChristoph Hellwig ASSERT(rblock->bb_u.l.bb_rightsib == cpu_to_be64(NULLFSBLOCK)); 16430f712c9SDave Chinner ASSERT(rblock->bb_level != 0); 16530f712c9SDave Chinner dblock->bb_level = rblock->bb_level; 16630f712c9SDave Chinner dblock->bb_numrecs = rblock->bb_numrecs; 16730f712c9SDave Chinner dmxr = xfs_bmdr_maxrecs(dblocklen, 0); 16830f712c9SDave Chinner fkp = XFS_BMBT_KEY_ADDR(mp, rblock, 1); 16930f712c9SDave Chinner tkp = XFS_BMDR_KEY_ADDR(dblock, 1); 17030f712c9SDave Chinner fpp = XFS_BMAP_BROOT_PTR_ADDR(mp, rblock, 1, rblocklen); 17130f712c9SDave Chinner tpp = XFS_BMDR_PTR_ADDR(dblock, 1, dmxr); 17230f712c9SDave Chinner dmxr = be16_to_cpu(dblock->bb_numrecs); 17330f712c9SDave Chinner memcpy(tkp, fkp, sizeof(*fkp) * dmxr); 17430f712c9SDave Chinner memcpy(tpp, fpp, sizeof(*fpp) * dmxr); 17530f712c9SDave Chinner } 17630f712c9SDave Chinner 17730f712c9SDave Chinner STATIC struct xfs_btree_cur * 17830f712c9SDave Chinner xfs_bmbt_dup_cursor( 17930f712c9SDave Chinner struct xfs_btree_cur *cur) 18030f712c9SDave Chinner { 18130f712c9SDave Chinner struct xfs_btree_cur *new; 18230f712c9SDave Chinner 18330f712c9SDave Chinner new = xfs_bmbt_init_cursor(cur->bc_mp, cur->bc_tp, 18430f712c9SDave Chinner cur->bc_private.b.ip, cur->bc_private.b.whichfork); 18530f712c9SDave Chinner 18630f712c9SDave Chinner /* 1872c3234d1SDarrick J. Wong * Copy the firstblock, dfops, and flags values, 18830f712c9SDave Chinner * since init cursor doesn't get them. 18930f712c9SDave Chinner */ 19030f712c9SDave Chinner new->bc_private.b.firstblock = cur->bc_private.b.firstblock; 1912c3234d1SDarrick J. Wong new->bc_private.b.dfops = cur->bc_private.b.dfops; 19230f712c9SDave Chinner new->bc_private.b.flags = cur->bc_private.b.flags; 19330f712c9SDave Chinner 19430f712c9SDave Chinner return new; 19530f712c9SDave Chinner } 19630f712c9SDave Chinner 19730f712c9SDave Chinner STATIC void 19830f712c9SDave Chinner xfs_bmbt_update_cursor( 19930f712c9SDave Chinner struct xfs_btree_cur *src, 20030f712c9SDave Chinner struct xfs_btree_cur *dst) 20130f712c9SDave Chinner { 20230f712c9SDave Chinner ASSERT((dst->bc_private.b.firstblock != NULLFSBLOCK) || 20330f712c9SDave Chinner (dst->bc_private.b.ip->i_d.di_flags & XFS_DIFLAG_REALTIME)); 2042c3234d1SDarrick J. Wong ASSERT(dst->bc_private.b.dfops == src->bc_private.b.dfops); 20530f712c9SDave Chinner 20630f712c9SDave Chinner dst->bc_private.b.allocated += src->bc_private.b.allocated; 20730f712c9SDave Chinner dst->bc_private.b.firstblock = src->bc_private.b.firstblock; 20830f712c9SDave Chinner 20930f712c9SDave Chinner src->bc_private.b.allocated = 0; 21030f712c9SDave Chinner } 21130f712c9SDave Chinner 21230f712c9SDave Chinner STATIC int 21330f712c9SDave Chinner xfs_bmbt_alloc_block( 21430f712c9SDave Chinner struct xfs_btree_cur *cur, 21530f712c9SDave Chinner union xfs_btree_ptr *start, 21630f712c9SDave Chinner union xfs_btree_ptr *new, 21730f712c9SDave Chinner int *stat) 21830f712c9SDave Chinner { 21930f712c9SDave Chinner xfs_alloc_arg_t args; /* block allocation args */ 22030f712c9SDave Chinner int error; /* error return value */ 22130f712c9SDave Chinner 22230f712c9SDave Chinner memset(&args, 0, sizeof(args)); 22330f712c9SDave Chinner args.tp = cur->bc_tp; 22430f712c9SDave Chinner args.mp = cur->bc_mp; 22530f712c9SDave Chinner args.fsbno = cur->bc_private.b.firstblock; 22630f712c9SDave Chinner args.firstblock = args.fsbno; 227340785ccSDarrick J. Wong xfs_rmap_ino_bmbt_owner(&args.oinfo, cur->bc_private.b.ip->i_ino, 228340785ccSDarrick J. Wong cur->bc_private.b.whichfork); 22930f712c9SDave Chinner 23030f712c9SDave Chinner if (args.fsbno == NULLFSBLOCK) { 23130f712c9SDave Chinner args.fsbno = be64_to_cpu(start->l); 23230f712c9SDave Chinner args.type = XFS_ALLOCTYPE_START_BNO; 23330f712c9SDave Chinner /* 23430f712c9SDave Chinner * Make sure there is sufficient room left in the AG to 23530f712c9SDave Chinner * complete a full tree split for an extent insert. If 23630f712c9SDave Chinner * we are converting the middle part of an extent then 23730f712c9SDave Chinner * we may need space for two tree splits. 23830f712c9SDave Chinner * 23930f712c9SDave Chinner * We are relying on the caller to make the correct block 24030f712c9SDave Chinner * reservation for this operation to succeed. If the 24130f712c9SDave Chinner * reservation amount is insufficient then we may fail a 24230f712c9SDave Chinner * block allocation here and corrupt the filesystem. 24330f712c9SDave Chinner */ 244a7e5d03bSChristoph Hellwig args.minleft = args.tp->t_blk_res; 2452c3234d1SDarrick J. Wong } else if (cur->bc_private.b.dfops->dop_low) { 24630f712c9SDave Chinner args.type = XFS_ALLOCTYPE_START_BNO; 24730f712c9SDave Chinner } else { 24830f712c9SDave Chinner args.type = XFS_ALLOCTYPE_NEAR_BNO; 24930f712c9SDave Chinner } 25030f712c9SDave Chinner 25130f712c9SDave Chinner args.minlen = args.maxlen = args.prod = 1; 25230f712c9SDave Chinner args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL; 253a7e5d03bSChristoph Hellwig if (!args.wasdel && args.tp->t_blk_res == 0) { 2542451337dSDave Chinner error = -ENOSPC; 25530f712c9SDave Chinner goto error0; 25630f712c9SDave Chinner } 25730f712c9SDave Chinner error = xfs_alloc_vextent(&args); 25830f712c9SDave Chinner if (error) 25930f712c9SDave Chinner goto error0; 26030f712c9SDave Chinner 26130f712c9SDave Chinner if (args.fsbno == NULLFSBLOCK && args.minleft) { 26230f712c9SDave Chinner /* 26330f712c9SDave Chinner * Could not find an AG with enough free space to satisfy 264255c5162SChristoph Hellwig * a full btree split. Try again and if 26530f712c9SDave Chinner * successful activate the lowspace algorithm. 26630f712c9SDave Chinner */ 26730f712c9SDave Chinner args.fsbno = 0; 26830f712c9SDave Chinner args.type = XFS_ALLOCTYPE_FIRST_AG; 26930f712c9SDave Chinner error = xfs_alloc_vextent(&args); 27030f712c9SDave Chinner if (error) 27130f712c9SDave Chinner goto error0; 2722c3234d1SDarrick J. Wong cur->bc_private.b.dfops->dop_low = true; 27330f712c9SDave Chinner } 2742fcc319dSChristoph Hellwig if (WARN_ON_ONCE(args.fsbno == NULLFSBLOCK)) { 27530f712c9SDave Chinner *stat = 0; 27630f712c9SDave Chinner return 0; 27730f712c9SDave Chinner } 278e157ebdcSCarlos Maiolino 27930f712c9SDave Chinner ASSERT(args.len == 1); 28030f712c9SDave Chinner cur->bc_private.b.firstblock = args.fsbno; 28130f712c9SDave Chinner cur->bc_private.b.allocated++; 28230f712c9SDave Chinner cur->bc_private.b.ip->i_d.di_nblocks++; 28330f712c9SDave Chinner xfs_trans_log_inode(args.tp, cur->bc_private.b.ip, XFS_ILOG_CORE); 28430f712c9SDave Chinner xfs_trans_mod_dquot_byino(args.tp, cur->bc_private.b.ip, 28530f712c9SDave Chinner XFS_TRANS_DQ_BCOUNT, 1L); 28630f712c9SDave Chinner 28730f712c9SDave Chinner new->l = cpu_to_be64(args.fsbno); 28830f712c9SDave Chinner 28930f712c9SDave Chinner *stat = 1; 29030f712c9SDave Chinner return 0; 29130f712c9SDave Chinner 29230f712c9SDave Chinner error0: 29330f712c9SDave Chinner return error; 29430f712c9SDave Chinner } 29530f712c9SDave Chinner 29630f712c9SDave Chinner STATIC int 29730f712c9SDave Chinner xfs_bmbt_free_block( 29830f712c9SDave Chinner struct xfs_btree_cur *cur, 29930f712c9SDave Chinner struct xfs_buf *bp) 30030f712c9SDave Chinner { 30130f712c9SDave Chinner struct xfs_mount *mp = cur->bc_mp; 30230f712c9SDave Chinner struct xfs_inode *ip = cur->bc_private.b.ip; 30330f712c9SDave Chinner struct xfs_trans *tp = cur->bc_tp; 30430f712c9SDave Chinner xfs_fsblock_t fsbno = XFS_DADDR_TO_FSB(mp, XFS_BUF_ADDR(bp)); 305340785ccSDarrick J. Wong struct xfs_owner_info oinfo; 30630f712c9SDave Chinner 307340785ccSDarrick J. Wong xfs_rmap_ino_bmbt_owner(&oinfo, ip->i_ino, cur->bc_private.b.whichfork); 308340785ccSDarrick J. Wong xfs_bmap_add_free(mp, cur->bc_private.b.dfops, fsbno, 1, &oinfo); 30930f712c9SDave Chinner ip->i_d.di_nblocks--; 31030f712c9SDave Chinner 31130f712c9SDave Chinner xfs_trans_log_inode(tp, ip, XFS_ILOG_CORE); 31230f712c9SDave Chinner xfs_trans_mod_dquot_byino(tp, ip, XFS_TRANS_DQ_BCOUNT, -1L); 31330f712c9SDave Chinner return 0; 31430f712c9SDave Chinner } 31530f712c9SDave Chinner 31630f712c9SDave Chinner STATIC int 31730f712c9SDave Chinner xfs_bmbt_get_minrecs( 31830f712c9SDave Chinner struct xfs_btree_cur *cur, 31930f712c9SDave Chinner int level) 32030f712c9SDave Chinner { 32130f712c9SDave Chinner if (level == cur->bc_nlevels - 1) { 32230f712c9SDave Chinner struct xfs_ifork *ifp; 32330f712c9SDave Chinner 32430f712c9SDave Chinner ifp = XFS_IFORK_PTR(cur->bc_private.b.ip, 32530f712c9SDave Chinner cur->bc_private.b.whichfork); 32630f712c9SDave Chinner 32730f712c9SDave Chinner return xfs_bmbt_maxrecs(cur->bc_mp, 32830f712c9SDave Chinner ifp->if_broot_bytes, level == 0) / 2; 32930f712c9SDave Chinner } 33030f712c9SDave Chinner 33130f712c9SDave Chinner return cur->bc_mp->m_bmap_dmnr[level != 0]; 33230f712c9SDave Chinner } 33330f712c9SDave Chinner 33430f712c9SDave Chinner int 33530f712c9SDave Chinner xfs_bmbt_get_maxrecs( 33630f712c9SDave Chinner struct xfs_btree_cur *cur, 33730f712c9SDave Chinner int level) 33830f712c9SDave Chinner { 33930f712c9SDave Chinner if (level == cur->bc_nlevels - 1) { 34030f712c9SDave Chinner struct xfs_ifork *ifp; 34130f712c9SDave Chinner 34230f712c9SDave Chinner ifp = XFS_IFORK_PTR(cur->bc_private.b.ip, 34330f712c9SDave Chinner cur->bc_private.b.whichfork); 34430f712c9SDave Chinner 34530f712c9SDave Chinner return xfs_bmbt_maxrecs(cur->bc_mp, 34630f712c9SDave Chinner ifp->if_broot_bytes, level == 0); 34730f712c9SDave Chinner } 34830f712c9SDave Chinner 34930f712c9SDave Chinner return cur->bc_mp->m_bmap_dmxr[level != 0]; 35030f712c9SDave Chinner 35130f712c9SDave Chinner } 35230f712c9SDave Chinner 35330f712c9SDave Chinner /* 35430f712c9SDave Chinner * Get the maximum records we could store in the on-disk format. 35530f712c9SDave Chinner * 35630f712c9SDave Chinner * For non-root nodes this is equivalent to xfs_bmbt_get_maxrecs, but 35730f712c9SDave Chinner * for the root node this checks the available space in the dinode fork 35830f712c9SDave Chinner * so that we can resize the in-memory buffer to match it. After a 35930f712c9SDave Chinner * resize to the maximum size this function returns the same value 36030f712c9SDave Chinner * as xfs_bmbt_get_maxrecs for the root node, too. 36130f712c9SDave Chinner */ 36230f712c9SDave Chinner STATIC int 36330f712c9SDave Chinner xfs_bmbt_get_dmaxrecs( 36430f712c9SDave Chinner struct xfs_btree_cur *cur, 36530f712c9SDave Chinner int level) 36630f712c9SDave Chinner { 36730f712c9SDave Chinner if (level != cur->bc_nlevels - 1) 36830f712c9SDave Chinner return cur->bc_mp->m_bmap_dmxr[level != 0]; 36930f712c9SDave Chinner return xfs_bmdr_maxrecs(cur->bc_private.b.forksize, level == 0); 37030f712c9SDave Chinner } 37130f712c9SDave Chinner 37230f712c9SDave Chinner STATIC void 37330f712c9SDave Chinner xfs_bmbt_init_key_from_rec( 37430f712c9SDave Chinner union xfs_btree_key *key, 37530f712c9SDave Chinner union xfs_btree_rec *rec) 37630f712c9SDave Chinner { 37730f712c9SDave Chinner key->bmbt.br_startoff = 37830f712c9SDave Chinner cpu_to_be64(xfs_bmbt_disk_get_startoff(&rec->bmbt)); 37930f712c9SDave Chinner } 38030f712c9SDave Chinner 38130f712c9SDave Chinner STATIC void 382118bb47eSDarrick J. Wong xfs_bmbt_init_high_key_from_rec( 383118bb47eSDarrick J. Wong union xfs_btree_key *key, 384118bb47eSDarrick J. Wong union xfs_btree_rec *rec) 385118bb47eSDarrick J. Wong { 386118bb47eSDarrick J. Wong key->bmbt.br_startoff = cpu_to_be64( 387118bb47eSDarrick J. Wong xfs_bmbt_disk_get_startoff(&rec->bmbt) + 388118bb47eSDarrick J. Wong xfs_bmbt_disk_get_blockcount(&rec->bmbt) - 1); 389118bb47eSDarrick J. Wong } 390118bb47eSDarrick J. Wong 391118bb47eSDarrick J. Wong STATIC void 39230f712c9SDave Chinner xfs_bmbt_init_rec_from_cur( 39330f712c9SDave Chinner struct xfs_btree_cur *cur, 39430f712c9SDave Chinner union xfs_btree_rec *rec) 39530f712c9SDave Chinner { 39630f712c9SDave Chinner xfs_bmbt_disk_set_all(&rec->bmbt, &cur->bc_rec.b); 39730f712c9SDave Chinner } 39830f712c9SDave Chinner 39930f712c9SDave Chinner STATIC void 40030f712c9SDave Chinner xfs_bmbt_init_ptr_from_cur( 40130f712c9SDave Chinner struct xfs_btree_cur *cur, 40230f712c9SDave Chinner union xfs_btree_ptr *ptr) 40330f712c9SDave Chinner { 40430f712c9SDave Chinner ptr->l = 0; 40530f712c9SDave Chinner } 40630f712c9SDave Chinner 407c8ce540dSDarrick J. Wong STATIC int64_t 40830f712c9SDave Chinner xfs_bmbt_key_diff( 40930f712c9SDave Chinner struct xfs_btree_cur *cur, 41030f712c9SDave Chinner union xfs_btree_key *key) 41130f712c9SDave Chinner { 412c8ce540dSDarrick J. Wong return (int64_t)be64_to_cpu(key->bmbt.br_startoff) - 41330f712c9SDave Chinner cur->bc_rec.b.br_startoff; 41430f712c9SDave Chinner } 41530f712c9SDave Chinner 416118bb47eSDarrick J. Wong STATIC int64_t 417118bb47eSDarrick J. Wong xfs_bmbt_diff_two_keys( 418118bb47eSDarrick J. Wong struct xfs_btree_cur *cur, 419118bb47eSDarrick J. Wong union xfs_btree_key *k1, 420118bb47eSDarrick J. Wong union xfs_btree_key *k2) 421118bb47eSDarrick J. Wong { 422118bb47eSDarrick J. Wong return (int64_t)be64_to_cpu(k1->bmbt.br_startoff) - 423118bb47eSDarrick J. Wong be64_to_cpu(k2->bmbt.br_startoff); 424118bb47eSDarrick J. Wong } 425118bb47eSDarrick J. Wong 426a6a781a5SDarrick J. Wong static xfs_failaddr_t 42730f712c9SDave Chinner xfs_bmbt_verify( 42830f712c9SDave Chinner struct xfs_buf *bp) 42930f712c9SDave Chinner { 43030f712c9SDave Chinner struct xfs_mount *mp = bp->b_target->bt_mount; 43130f712c9SDave Chinner struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); 432a6a781a5SDarrick J. Wong xfs_failaddr_t fa; 43330f712c9SDave Chinner unsigned int level; 43430f712c9SDave Chinner 43530f712c9SDave Chinner switch (block->bb_magic) { 43630f712c9SDave Chinner case cpu_to_be32(XFS_BMAP_CRC_MAGIC): 43730f712c9SDave Chinner /* 43830f712c9SDave Chinner * XXX: need a better way of verifying the owner here. Right now 43930f712c9SDave Chinner * just make sure there has been one set. 44030f712c9SDave Chinner */ 441a6a781a5SDarrick J. Wong fa = xfs_btree_lblock_v5hdr_verify(bp, XFS_RMAP_OWN_UNKNOWN); 442a6a781a5SDarrick J. Wong if (fa) 443a6a781a5SDarrick J. Wong return fa; 44430f712c9SDave Chinner /* fall through */ 44530f712c9SDave Chinner case cpu_to_be32(XFS_BMAP_MAGIC): 44630f712c9SDave Chinner break; 44730f712c9SDave Chinner default: 448a6a781a5SDarrick J. Wong return __this_address; 44930f712c9SDave Chinner } 45030f712c9SDave Chinner 45130f712c9SDave Chinner /* 45230f712c9SDave Chinner * numrecs and level verification. 45330f712c9SDave Chinner * 45430f712c9SDave Chinner * We don't know what fork we belong to, so just verify that the level 45530f712c9SDave Chinner * is less than the maximum of the two. Later checks will be more 45630f712c9SDave Chinner * precise. 45730f712c9SDave Chinner */ 45830f712c9SDave Chinner level = be16_to_cpu(block->bb_level); 45930f712c9SDave Chinner if (level > max(mp->m_bm_maxlevels[0], mp->m_bm_maxlevels[1])) 460a6a781a5SDarrick J. Wong return __this_address; 46130f712c9SDave Chinner 4628368a601SDarrick J. Wong return xfs_btree_lblock_verify(bp, mp->m_bmap_dmxr[level != 0]); 46330f712c9SDave Chinner } 46430f712c9SDave Chinner 46530f712c9SDave Chinner static void 46630f712c9SDave Chinner xfs_bmbt_read_verify( 46730f712c9SDave Chinner struct xfs_buf *bp) 46830f712c9SDave Chinner { 469bc1a09b8SDarrick J. Wong xfs_failaddr_t fa; 470bc1a09b8SDarrick J. Wong 47130f712c9SDave Chinner if (!xfs_btree_lblock_verify_crc(bp)) 472bc1a09b8SDarrick J. Wong xfs_verifier_error(bp, -EFSBADCRC, __this_address); 473bc1a09b8SDarrick J. Wong else { 474bc1a09b8SDarrick J. Wong fa = xfs_bmbt_verify(bp); 475bc1a09b8SDarrick J. Wong if (fa) 476bc1a09b8SDarrick J. Wong xfs_verifier_error(bp, -EFSCORRUPTED, fa); 477bc1a09b8SDarrick J. Wong } 47830f712c9SDave Chinner 47931ca03c9SDarrick J. Wong if (bp->b_error) 48030f712c9SDave Chinner trace_xfs_btree_corrupt(bp, _RET_IP_); 48130f712c9SDave Chinner } 48230f712c9SDave Chinner 48330f712c9SDave Chinner static void 48430f712c9SDave Chinner xfs_bmbt_write_verify( 48530f712c9SDave Chinner struct xfs_buf *bp) 48630f712c9SDave Chinner { 487bc1a09b8SDarrick J. Wong xfs_failaddr_t fa; 488bc1a09b8SDarrick J. Wong 489bc1a09b8SDarrick J. Wong fa = xfs_bmbt_verify(bp); 490bc1a09b8SDarrick J. Wong if (fa) { 49130f712c9SDave Chinner trace_xfs_btree_corrupt(bp, _RET_IP_); 492bc1a09b8SDarrick J. Wong xfs_verifier_error(bp, -EFSCORRUPTED, fa); 49330f712c9SDave Chinner return; 49430f712c9SDave Chinner } 49530f712c9SDave Chinner xfs_btree_lblock_calc_crc(bp); 49630f712c9SDave Chinner } 49730f712c9SDave Chinner 49830f712c9SDave Chinner const struct xfs_buf_ops xfs_bmbt_buf_ops = { 499233135b7SEric Sandeen .name = "xfs_bmbt", 50030f712c9SDave Chinner .verify_read = xfs_bmbt_read_verify, 50130f712c9SDave Chinner .verify_write = xfs_bmbt_write_verify, 502b5572597SDarrick J. Wong .verify_struct = xfs_bmbt_verify, 50330f712c9SDave Chinner }; 50430f712c9SDave Chinner 50530f712c9SDave Chinner 50630f712c9SDave Chinner STATIC int 50730f712c9SDave Chinner xfs_bmbt_keys_inorder( 50830f712c9SDave Chinner struct xfs_btree_cur *cur, 50930f712c9SDave Chinner union xfs_btree_key *k1, 51030f712c9SDave Chinner union xfs_btree_key *k2) 51130f712c9SDave Chinner { 51230f712c9SDave Chinner return be64_to_cpu(k1->bmbt.br_startoff) < 51330f712c9SDave Chinner be64_to_cpu(k2->bmbt.br_startoff); 51430f712c9SDave Chinner } 51530f712c9SDave Chinner 51630f712c9SDave Chinner STATIC int 51730f712c9SDave Chinner xfs_bmbt_recs_inorder( 51830f712c9SDave Chinner struct xfs_btree_cur *cur, 51930f712c9SDave Chinner union xfs_btree_rec *r1, 52030f712c9SDave Chinner union xfs_btree_rec *r2) 52130f712c9SDave Chinner { 52230f712c9SDave Chinner return xfs_bmbt_disk_get_startoff(&r1->bmbt) + 52330f712c9SDave Chinner xfs_bmbt_disk_get_blockcount(&r1->bmbt) <= 52430f712c9SDave Chinner xfs_bmbt_disk_get_startoff(&r2->bmbt); 52530f712c9SDave Chinner } 52630f712c9SDave Chinner 52730f712c9SDave Chinner static const struct xfs_btree_ops xfs_bmbt_ops = { 52830f712c9SDave Chinner .rec_len = sizeof(xfs_bmbt_rec_t), 52930f712c9SDave Chinner .key_len = sizeof(xfs_bmbt_key_t), 53030f712c9SDave Chinner 53130f712c9SDave Chinner .dup_cursor = xfs_bmbt_dup_cursor, 53230f712c9SDave Chinner .update_cursor = xfs_bmbt_update_cursor, 53330f712c9SDave Chinner .alloc_block = xfs_bmbt_alloc_block, 53430f712c9SDave Chinner .free_block = xfs_bmbt_free_block, 53530f712c9SDave Chinner .get_maxrecs = xfs_bmbt_get_maxrecs, 53630f712c9SDave Chinner .get_minrecs = xfs_bmbt_get_minrecs, 53730f712c9SDave Chinner .get_dmaxrecs = xfs_bmbt_get_dmaxrecs, 53830f712c9SDave Chinner .init_key_from_rec = xfs_bmbt_init_key_from_rec, 539118bb47eSDarrick J. Wong .init_high_key_from_rec = xfs_bmbt_init_high_key_from_rec, 54030f712c9SDave Chinner .init_rec_from_cur = xfs_bmbt_init_rec_from_cur, 54130f712c9SDave Chinner .init_ptr_from_cur = xfs_bmbt_init_ptr_from_cur, 54230f712c9SDave Chinner .key_diff = xfs_bmbt_key_diff, 543118bb47eSDarrick J. Wong .diff_two_keys = xfs_bmbt_diff_two_keys, 54430f712c9SDave Chinner .buf_ops = &xfs_bmbt_buf_ops, 54530f712c9SDave Chinner .keys_inorder = xfs_bmbt_keys_inorder, 54630f712c9SDave Chinner .recs_inorder = xfs_bmbt_recs_inorder, 54730f712c9SDave Chinner }; 54830f712c9SDave Chinner 54930f712c9SDave Chinner /* 55030f712c9SDave Chinner * Allocate a new bmap btree cursor. 55130f712c9SDave Chinner */ 55230f712c9SDave Chinner struct xfs_btree_cur * /* new bmap btree cursor */ 55330f712c9SDave Chinner xfs_bmbt_init_cursor( 55430f712c9SDave Chinner struct xfs_mount *mp, /* file system mount point */ 55530f712c9SDave Chinner struct xfs_trans *tp, /* transaction pointer */ 55630f712c9SDave Chinner struct xfs_inode *ip, /* inode owning the btree */ 55730f712c9SDave Chinner int whichfork) /* data or attr fork */ 55830f712c9SDave Chinner { 55930f712c9SDave Chinner struct xfs_ifork *ifp = XFS_IFORK_PTR(ip, whichfork); 56030f712c9SDave Chinner struct xfs_btree_cur *cur; 5613993baebSDarrick J. Wong ASSERT(whichfork != XFS_COW_FORK); 56230f712c9SDave Chinner 563b24a978cSDarrick J. Wong cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_NOFS); 56430f712c9SDave Chinner 56530f712c9SDave Chinner cur->bc_tp = tp; 56630f712c9SDave Chinner cur->bc_mp = mp; 56730f712c9SDave Chinner cur->bc_nlevels = be16_to_cpu(ifp->if_broot->bb_level) + 1; 56830f712c9SDave Chinner cur->bc_btnum = XFS_BTNUM_BMAP; 56930f712c9SDave Chinner cur->bc_blocklog = mp->m_sb.sb_blocklog; 57011ef38afSDave Chinner cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_bmbt_2); 57130f712c9SDave Chinner 57230f712c9SDave Chinner cur->bc_ops = &xfs_bmbt_ops; 57330f712c9SDave Chinner cur->bc_flags = XFS_BTREE_LONG_PTRS | XFS_BTREE_ROOT_IN_INODE; 57430f712c9SDave Chinner if (xfs_sb_version_hascrc(&mp->m_sb)) 57530f712c9SDave Chinner cur->bc_flags |= XFS_BTREE_CRC_BLOCKS; 57630f712c9SDave Chinner 57730f712c9SDave Chinner cur->bc_private.b.forksize = XFS_IFORK_SIZE(ip, whichfork); 57830f712c9SDave Chinner cur->bc_private.b.ip = ip; 57930f712c9SDave Chinner cur->bc_private.b.firstblock = NULLFSBLOCK; 5802c3234d1SDarrick J. Wong cur->bc_private.b.dfops = NULL; 58130f712c9SDave Chinner cur->bc_private.b.allocated = 0; 58230f712c9SDave Chinner cur->bc_private.b.flags = 0; 58330f712c9SDave Chinner cur->bc_private.b.whichfork = whichfork; 58430f712c9SDave Chinner 58530f712c9SDave Chinner return cur; 58630f712c9SDave Chinner } 58730f712c9SDave Chinner 58830f712c9SDave Chinner /* 58930f712c9SDave Chinner * Calculate number of records in a bmap btree block. 59030f712c9SDave Chinner */ 59130f712c9SDave Chinner int 59230f712c9SDave Chinner xfs_bmbt_maxrecs( 59330f712c9SDave Chinner struct xfs_mount *mp, 59430f712c9SDave Chinner int blocklen, 59530f712c9SDave Chinner int leaf) 59630f712c9SDave Chinner { 59730f712c9SDave Chinner blocklen -= XFS_BMBT_BLOCK_LEN(mp); 59830f712c9SDave Chinner 59930f712c9SDave Chinner if (leaf) 60030f712c9SDave Chinner return blocklen / sizeof(xfs_bmbt_rec_t); 60130f712c9SDave Chinner return blocklen / (sizeof(xfs_bmbt_key_t) + sizeof(xfs_bmbt_ptr_t)); 60230f712c9SDave Chinner } 60330f712c9SDave Chinner 60430f712c9SDave Chinner /* 60530f712c9SDave Chinner * Calculate number of records in a bmap btree inode root. 60630f712c9SDave Chinner */ 60730f712c9SDave Chinner int 60830f712c9SDave Chinner xfs_bmdr_maxrecs( 60930f712c9SDave Chinner int blocklen, 61030f712c9SDave Chinner int leaf) 61130f712c9SDave Chinner { 61230f712c9SDave Chinner blocklen -= sizeof(xfs_bmdr_block_t); 61330f712c9SDave Chinner 61430f712c9SDave Chinner if (leaf) 61530f712c9SDave Chinner return blocklen / sizeof(xfs_bmdr_rec_t); 61630f712c9SDave Chinner return blocklen / (sizeof(xfs_bmdr_key_t) + sizeof(xfs_bmdr_ptr_t)); 61730f712c9SDave Chinner } 61830f712c9SDave Chinner 61930f712c9SDave Chinner /* 62030f712c9SDave Chinner * Change the owner of a btree format fork fo the inode passed in. Change it to 62130f712c9SDave Chinner * the owner of that is passed in so that we can change owners before or after 62230f712c9SDave Chinner * we switch forks between inodes. The operation that the caller is doing will 62330f712c9SDave Chinner * determine whether is needs to change owner before or after the switch. 62430f712c9SDave Chinner * 62530f712c9SDave Chinner * For demand paged transactional modification, the fork switch should be done 62630f712c9SDave Chinner * after reading in all the blocks, modifying them and pinning them in the 62730f712c9SDave Chinner * transaction. For modification when the buffers are already pinned in memory, 62830f712c9SDave Chinner * the fork switch can be done before changing the owner as we won't need to 62930f712c9SDave Chinner * validate the owner until the btree buffers are unpinned and writes can occur 63030f712c9SDave Chinner * again. 63130f712c9SDave Chinner * 63230f712c9SDave Chinner * For recovery based ownership change, there is no transactional context and 63330f712c9SDave Chinner * so a buffer list must be supplied so that we can record the buffers that we 63430f712c9SDave Chinner * modified for the caller to issue IO on. 63530f712c9SDave Chinner */ 63630f712c9SDave Chinner int 63730f712c9SDave Chinner xfs_bmbt_change_owner( 63830f712c9SDave Chinner struct xfs_trans *tp, 63930f712c9SDave Chinner struct xfs_inode *ip, 64030f712c9SDave Chinner int whichfork, 64130f712c9SDave Chinner xfs_ino_t new_owner, 64230f712c9SDave Chinner struct list_head *buffer_list) 64330f712c9SDave Chinner { 64430f712c9SDave Chinner struct xfs_btree_cur *cur; 64530f712c9SDave Chinner int error; 64630f712c9SDave Chinner 64730f712c9SDave Chinner ASSERT(tp || buffer_list); 64830f712c9SDave Chinner ASSERT(!(tp && buffer_list)); 64930f712c9SDave Chinner if (whichfork == XFS_DATA_FORK) 65030f712c9SDave Chinner ASSERT(ip->i_d.di_format == XFS_DINODE_FMT_BTREE); 65130f712c9SDave Chinner else 65230f712c9SDave Chinner ASSERT(ip->i_d.di_aformat == XFS_DINODE_FMT_BTREE); 65330f712c9SDave Chinner 65430f712c9SDave Chinner cur = xfs_bmbt_init_cursor(ip->i_mount, tp, ip, whichfork); 65530f712c9SDave Chinner if (!cur) 6562451337dSDave Chinner return -ENOMEM; 65799c794c6SBrian Foster cur->bc_private.b.flags |= XFS_BTCUR_BPRV_INVALID_OWNER; 65830f712c9SDave Chinner 65930f712c9SDave Chinner error = xfs_btree_change_owner(cur, new_owner, buffer_list); 66030f712c9SDave Chinner xfs_btree_del_cursor(cur, error ? XFS_BTREE_ERROR : XFS_BTREE_NOERROR); 66130f712c9SDave Chinner return error; 66230f712c9SDave Chinner } 66314861c47SDarrick J. Wong 66414861c47SDarrick J. Wong /* Calculate the bmap btree size for some records. */ 66514861c47SDarrick J. Wong unsigned long long 66614861c47SDarrick J. Wong xfs_bmbt_calc_size( 66714861c47SDarrick J. Wong struct xfs_mount *mp, 66814861c47SDarrick J. Wong unsigned long long len) 66914861c47SDarrick J. Wong { 67014861c47SDarrick J. Wong return xfs_btree_calc_size(mp->m_bmap_dmnr, len); 67114861c47SDarrick J. Wong } 672