xfs/libxfs/xfs_bmap_btree.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * Copyright (c) 2000-2003,2005 Silicon Graphics, Inc.
0004  * All Rights Reserved.
0005  */
0006 #include "xfs.h"
0007 #include "xfs_fs.h"
0008 #include "xfs_shared.h"
0009 #include "xfs_format.h"
0010 #include "xfs_log_format.h"
0011 #include "xfs_trans_resv.h"
0012 #include "xfs_bit.h"
0013 #include "xfs_mount.h"
0014 #include "xfs_inode.h"
0015 #include "xfs_trans.h"
0016 #include "xfs_alloc.h"
0017 #include "xfs_btree.h"
0018 #include "xfs_bmap_btree.h"
0019 #include "xfs_bmap.h"
0020 #include "xfs_error.h"
0021 #include "xfs_quota.h"
0022 #include "xfs_trace.h"
0023 #include "xfs_rmap.h"
0024
0025 static struct kmem_cache    *xfs_bmbt_cur_cache;
0026
0027 /*
0028  * Convert on-disk form of btree root to in-memory form.
0029  */
0030 void
0031 xfs_bmdr_to_bmbt(
0032     struct xfs_inode    *ip,
0033     xfs_bmdr_block_t    *dblock,
0034     int         dblocklen,
0035     struct xfs_btree_block  *rblock,
0036     int         rblocklen)
0037 {
0038     struct xfs_mount    *mp = ip->i_mount;
0039     int         dmxr;
0040     xfs_bmbt_key_t      *fkp;
0041     __be64          *fpp;
0042     xfs_bmbt_key_t      *tkp;
0043     __be64          *tpp;
0044
0045     xfs_btree_init_block_int(mp, rblock, XFS_BUF_DADDR_NULL,
0046                  XFS_BTNUM_BMAP, 0, 0, ip->i_ino,
0047                  XFS_BTREE_LONG_PTRS);
0048     rblock->bb_level = dblock->bb_level;
0049     ASSERT(be16_to_cpu(rblock->bb_level) > 0);
0050     rblock->bb_numrecs = dblock->bb_numrecs;
0051     dmxr = xfs_bmdr_maxrecs(dblocklen, 0);
0052     fkp = XFS_BMDR_KEY_ADDR(dblock, 1);
0053     tkp = XFS_BMBT_KEY_ADDR(mp, rblock, 1);
0054     fpp = XFS_BMDR_PTR_ADDR(dblock, 1, dmxr);
0055     tpp = XFS_BMAP_BROOT_PTR_ADDR(mp, rblock, 1, rblocklen);
0056     dmxr = be16_to_cpu(dblock->bb_numrecs);
0057     memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
0058     memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
0059 }
0060
0061 void
0062 xfs_bmbt_disk_get_all(
0063     const struct xfs_bmbt_rec *rec,
0064     struct xfs_bmbt_irec    *irec)
0065 {
0066     uint64_t        l0 = get_unaligned_be64(&rec->l0);
0067     uint64_t        l1 = get_unaligned_be64(&rec->l1);
0068
0069     irec->br_startoff = (l0 & xfs_mask64lo(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
0070     irec->br_startblock = ((l0 & xfs_mask64lo(9)) << 43) | (l1 >> 21);
0071     irec->br_blockcount = l1 & xfs_mask64lo(21);
0072     if (l0 >> (64 - BMBT_EXNTFLAG_BITLEN))
0073         irec->br_state = XFS_EXT_UNWRITTEN;
0074     else
0075         irec->br_state = XFS_EXT_NORM;
0076 }
0077
0078 /*
0079  * Extract the blockcount field from an on disk bmap extent record.
0080  */
0081 xfs_filblks_t
0082 xfs_bmbt_disk_get_blockcount(
0083     const struct xfs_bmbt_rec   *r)
0084 {
0085     return (xfs_filblks_t)(be64_to_cpu(r->l1) & xfs_mask64lo(21));
0086 }
0087
0088 /*
0089  * Extract the startoff field from a disk format bmap extent record.
0090  */
0091 xfs_fileoff_t
0092 xfs_bmbt_disk_get_startoff(
0093     const struct xfs_bmbt_rec   *r)
0094 {
0095     return ((xfs_fileoff_t)be64_to_cpu(r->l0) &
0096          xfs_mask64lo(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
0097 }
0098
0099 /*
0100  * Set all the fields in a bmap extent record from the uncompressed form.
0101  */
0102 void
0103 xfs_bmbt_disk_set_all(
0104     struct xfs_bmbt_rec *r,
0105     struct xfs_bmbt_irec    *s)
0106 {
0107     int         extent_flag = (s->br_state != XFS_EXT_NORM);
0108
0109     ASSERT(s->br_state == XFS_EXT_NORM || s->br_state == XFS_EXT_UNWRITTEN);
0110     ASSERT(!(s->br_startoff & xfs_mask64hi(64-BMBT_STARTOFF_BITLEN)));
0111     ASSERT(!(s->br_blockcount & xfs_mask64hi(64-BMBT_BLOCKCOUNT_BITLEN)));
0112     ASSERT(!(s->br_startblock & xfs_mask64hi(64-BMBT_STARTBLOCK_BITLEN)));
0113
0114     put_unaligned_be64(
0115         ((xfs_bmbt_rec_base_t)extent_flag << 63) |
0116          ((xfs_bmbt_rec_base_t)s->br_startoff << 9) |
0117          ((xfs_bmbt_rec_base_t)s->br_startblock >> 43), &r->l0);
0118     put_unaligned_be64(
0119         ((xfs_bmbt_rec_base_t)s->br_startblock << 21) |
0120          ((xfs_bmbt_rec_base_t)s->br_blockcount &
0121           (xfs_bmbt_rec_base_t)xfs_mask64lo(21)), &r->l1);
0122 }
0123
0124 /*
0125  * Convert in-memory form of btree root to on-disk form.
0126  */
0127 void
0128 xfs_bmbt_to_bmdr(
0129     struct xfs_mount    *mp,
0130     struct xfs_btree_block  *rblock,
0131     int         rblocklen,
0132     xfs_bmdr_block_t    *dblock,
0133     int         dblocklen)
0134 {
0135     int         dmxr;
0136     xfs_bmbt_key_t      *fkp;
0137     __be64          *fpp;
0138     xfs_bmbt_key_t      *tkp;
0139     __be64          *tpp;
0140
0141     if (xfs_has_crc(mp)) {
0142         ASSERT(rblock->bb_magic == cpu_to_be32(XFS_BMAP_CRC_MAGIC));
0143         ASSERT(uuid_equal(&rblock->bb_u.l.bb_uuid,
0144                &mp->m_sb.sb_meta_uuid));
0145         ASSERT(rblock->bb_u.l.bb_blkno ==
0146                cpu_to_be64(XFS_BUF_DADDR_NULL));
0147     } else
0148         ASSERT(rblock->bb_magic == cpu_to_be32(XFS_BMAP_MAGIC));
0149     ASSERT(rblock->bb_u.l.bb_leftsib == cpu_to_be64(NULLFSBLOCK));
0150     ASSERT(rblock->bb_u.l.bb_rightsib == cpu_to_be64(NULLFSBLOCK));
0151     ASSERT(rblock->bb_level != 0);
0152     dblock->bb_level = rblock->bb_level;
0153     dblock->bb_numrecs = rblock->bb_numrecs;
0154     dmxr = xfs_bmdr_maxrecs(dblocklen, 0);
0155     fkp = XFS_BMBT_KEY_ADDR(mp, rblock, 1);
0156     tkp = XFS_BMDR_KEY_ADDR(dblock, 1);
0157     fpp = XFS_BMAP_BROOT_PTR_ADDR(mp, rblock, 1, rblocklen);
0158     tpp = XFS_BMDR_PTR_ADDR(dblock, 1, dmxr);
0159     dmxr = be16_to_cpu(dblock->bb_numrecs);
0160     memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
0161     memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
0162 }
0163
0164 STATIC struct xfs_btree_cur *
0165 xfs_bmbt_dup_cursor(
0166     struct xfs_btree_cur    *cur)
0167 {
0168     struct xfs_btree_cur    *new;
0169
0170     new = xfs_bmbt_init_cursor(cur->bc_mp, cur->bc_tp,
0171             cur->bc_ino.ip, cur->bc_ino.whichfork);
0172
0173     /*
0174      * Copy the firstblock, dfops, and flags values,
0175      * since init cursor doesn't get them.
0176      */
0177     new->bc_ino.flags = cur->bc_ino.flags;
0178
0179     return new;
0180 }
0181
0182 STATIC void
0183 xfs_bmbt_update_cursor(
0184     struct xfs_btree_cur    *src,
0185     struct xfs_btree_cur    *dst)
0186 {
0187     ASSERT((dst->bc_tp->t_firstblock != NULLFSBLOCK) ||
0188            (dst->bc_ino.ip->i_diflags & XFS_DIFLAG_REALTIME));
0189
0190     dst->bc_ino.allocated += src->bc_ino.allocated;
0191     dst->bc_tp->t_firstblock = src->bc_tp->t_firstblock;
0192
0193     src->bc_ino.allocated = 0;
0194 }
0195
0196 STATIC int
0197 xfs_bmbt_alloc_block(
0198     struct xfs_btree_cur        *cur,
0199     const union xfs_btree_ptr   *start,
0200     union xfs_btree_ptr     *new,
0201     int             *stat)
0202 {
0203     xfs_alloc_arg_t     args;       /* block allocation args */
0204     int         error;      /* error return value */
0205
0206     memset(&args, 0, sizeof(args));
0207     args.tp = cur->bc_tp;
0208     args.mp = cur->bc_mp;
0209     args.fsbno = cur->bc_tp->t_firstblock;
0210     xfs_rmap_ino_bmbt_owner(&args.oinfo, cur->bc_ino.ip->i_ino,
0211             cur->bc_ino.whichfork);
0212
0213     if (args.fsbno == NULLFSBLOCK) {
0214         args.fsbno = be64_to_cpu(start->l);
0215         args.type = XFS_ALLOCTYPE_START_BNO;
0216         /*
0217          * Make sure there is sufficient room left in the AG to
0218          * complete a full tree split for an extent insert.  If
0219          * we are converting the middle part of an extent then
0220          * we may need space for two tree splits.
0221          *
0222          * We are relying on the caller to make the correct block
0223          * reservation for this operation to succeed.  If the
0224          * reservation amount is insufficient then we may fail a
0225          * block allocation here and corrupt the filesystem.
0226          */
0227         args.minleft = args.tp->t_blk_res;
0228     } else if (cur->bc_tp->t_flags & XFS_TRANS_LOWMODE) {
0229         args.type = XFS_ALLOCTYPE_START_BNO;
0230     } else {
0231         args.type = XFS_ALLOCTYPE_NEAR_BNO;
0232     }
0233
0234     args.minlen = args.maxlen = args.prod = 1;
0235     args.wasdel = cur->bc_ino.flags & XFS_BTCUR_BMBT_WASDEL;
0236     if (!args.wasdel && args.tp->t_blk_res == 0) {
0237         error = -ENOSPC;
0238         goto error0;
0239     }
0240     error = xfs_alloc_vextent(&args);
0241     if (error)
0242         goto error0;
0243
0244     if (args.fsbno == NULLFSBLOCK && args.minleft) {
0245         /*
0246          * Could not find an AG with enough free space to satisfy
0247          * a full btree split.  Try again and if
0248          * successful activate the lowspace algorithm.
0249          */
0250         args.fsbno = 0;
0251         args.type = XFS_ALLOCTYPE_FIRST_AG;
0252         error = xfs_alloc_vextent(&args);
0253         if (error)
0254             goto error0;
0255         cur->bc_tp->t_flags |= XFS_TRANS_LOWMODE;
0256     }
0257     if (WARN_ON_ONCE(args.fsbno == NULLFSBLOCK)) {
0258         *stat = 0;
0259         return 0;
0260     }
0261
0262     ASSERT(args.len == 1);
0263     cur->bc_tp->t_firstblock = args.fsbno;
0264     cur->bc_ino.allocated++;
0265     cur->bc_ino.ip->i_nblocks++;
0266     xfs_trans_log_inode(args.tp, cur->bc_ino.ip, XFS_ILOG_CORE);
0267     xfs_trans_mod_dquot_byino(args.tp, cur->bc_ino.ip,
0268             XFS_TRANS_DQ_BCOUNT, 1L);
0269
0270     new->l = cpu_to_be64(args.fsbno);
0271
0272     *stat = 1;
0273     return 0;
0274
0275  error0:
0276     return error;
0277 }
0278
0279 STATIC int
0280 xfs_bmbt_free_block(
0281     struct xfs_btree_cur    *cur,
0282     struct xfs_buf      *bp)
0283 {
0284     struct xfs_mount    *mp = cur->bc_mp;
0285     struct xfs_inode    *ip = cur->bc_ino.ip;
0286     struct xfs_trans    *tp = cur->bc_tp;
0287     xfs_fsblock_t       fsbno = XFS_DADDR_TO_FSB(mp, xfs_buf_daddr(bp));
0288     struct xfs_owner_info   oinfo;
0289
0290     xfs_rmap_ino_bmbt_owner(&oinfo, ip->i_ino, cur->bc_ino.whichfork);
0291     xfs_free_extent_later(cur->bc_tp, fsbno, 1, &oinfo);
0292     ip->i_nblocks--;
0293
0294     xfs_trans_log_inode(tp, ip, XFS_ILOG_CORE);
0295     xfs_trans_mod_dquot_byino(tp, ip, XFS_TRANS_DQ_BCOUNT, -1L);
0296     return 0;
0297 }
0298
0299 STATIC int
0300 xfs_bmbt_get_minrecs(
0301     struct xfs_btree_cur    *cur,
0302     int         level)
0303 {
0304     if (level == cur->bc_nlevels - 1) {
0305         struct xfs_ifork    *ifp;
0306
0307         ifp = xfs_ifork_ptr(cur->bc_ino.ip,
0308                     cur->bc_ino.whichfork);
0309
0310         return xfs_bmbt_maxrecs(cur->bc_mp,
0311                     ifp->if_broot_bytes, level == 0) / 2;
0312     }
0313
0314     return cur->bc_mp->m_bmap_dmnr[level != 0];
0315 }
0316
0317 int
0318 xfs_bmbt_get_maxrecs(
0319     struct xfs_btree_cur    *cur,
0320     int         level)
0321 {
0322     if (level == cur->bc_nlevels - 1) {
0323         struct xfs_ifork    *ifp;
0324
0325         ifp = xfs_ifork_ptr(cur->bc_ino.ip,
0326                     cur->bc_ino.whichfork);
0327
0328         return xfs_bmbt_maxrecs(cur->bc_mp,
0329                     ifp->if_broot_bytes, level == 0);
0330     }
0331
0332     return cur->bc_mp->m_bmap_dmxr[level != 0];
0333
0334 }
0335
0336 /*
0337  * Get the maximum records we could store in the on-disk format.
0338  *
0339  * For non-root nodes this is equivalent to xfs_bmbt_get_maxrecs, but
0340  * for the root node this checks the available space in the dinode fork
0341  * so that we can resize the in-memory buffer to match it.  After a
0342  * resize to the maximum size this function returns the same value
0343  * as xfs_bmbt_get_maxrecs for the root node, too.
0344  */
0345 STATIC int
0346 xfs_bmbt_get_dmaxrecs(
0347     struct xfs_btree_cur    *cur,
0348     int         level)
0349 {
0350     if (level != cur->bc_nlevels - 1)
0351         return cur->bc_mp->m_bmap_dmxr[level != 0];
0352     return xfs_bmdr_maxrecs(cur->bc_ino.forksize, level == 0);
0353 }
0354
0355 STATIC void
0356 xfs_bmbt_init_key_from_rec(
0357     union xfs_btree_key     *key,
0358     const union xfs_btree_rec   *rec)
0359 {
0360     key->bmbt.br_startoff =
0361         cpu_to_be64(xfs_bmbt_disk_get_startoff(&rec->bmbt));
0362 }
0363
0364 STATIC void
0365 xfs_bmbt_init_high_key_from_rec(
0366     union xfs_btree_key     *key,
0367     const union xfs_btree_rec   *rec)
0368 {
0369     key->bmbt.br_startoff = cpu_to_be64(
0370             xfs_bmbt_disk_get_startoff(&rec->bmbt) +
0371             xfs_bmbt_disk_get_blockcount(&rec->bmbt) - 1);
0372 }
0373
0374 STATIC void
0375 xfs_bmbt_init_rec_from_cur(
0376     struct xfs_btree_cur    *cur,
0377     union xfs_btree_rec *rec)
0378 {
0379     xfs_bmbt_disk_set_all(&rec->bmbt, &cur->bc_rec.b);
0380 }
0381
0382 STATIC void
0383 xfs_bmbt_init_ptr_from_cur(
0384     struct xfs_btree_cur    *cur,
0385     union xfs_btree_ptr *ptr)
0386 {
0387     ptr->l = 0;
0388 }
0389
0390 STATIC int64_t
0391 xfs_bmbt_key_diff(
0392     struct xfs_btree_cur        *cur,
0393     const union xfs_btree_key   *key)
0394 {
0395     return (int64_t)be64_to_cpu(key->bmbt.br_startoff) -
0396                       cur->bc_rec.b.br_startoff;
0397 }
0398
0399 STATIC int64_t
0400 xfs_bmbt_diff_two_keys(
0401     struct xfs_btree_cur        *cur,
0402     const union xfs_btree_key   *k1,
0403     const union xfs_btree_key   *k2)
0404 {
0405     uint64_t            a = be64_to_cpu(k1->bmbt.br_startoff);
0406     uint64_t            b = be64_to_cpu(k2->bmbt.br_startoff);
0407
0408     /*
0409      * Note: This routine previously casted a and b to int64 and subtracted
0410      * them to generate a result.  This lead to problems if b was the
0411      * "maximum" key value (all ones) being signed incorrectly, hence this
0412      * somewhat less efficient version.
0413      */
0414     if (a > b)
0415         return 1;
0416     if (b > a)
0417         return -1;
0418     return 0;
0419 }
0420
0421 static xfs_failaddr_t
0422 xfs_bmbt_verify(
0423     struct xfs_buf      *bp)
0424 {
0425     struct xfs_mount    *mp = bp->b_mount;
0426     struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
0427     xfs_failaddr_t      fa;
0428     unsigned int        level;
0429
0430     if (!xfs_verify_magic(bp, block->bb_magic))
0431         return __this_address;
0432
0433     if (xfs_has_crc(mp)) {
0434         /*
0435          * XXX: need a better way of verifying the owner here. Right now
0436          * just make sure there has been one set.
0437          */
0438         fa = xfs_btree_lblock_v5hdr_verify(bp, XFS_RMAP_OWN_UNKNOWN);
0439         if (fa)
0440             return fa;
0441     }
0442
0443     /*
0444      * numrecs and level verification.
0445      *
0446      * We don't know what fork we belong to, so just verify that the level
0447      * is less than the maximum of the two. Later checks will be more
0448      * precise.
0449      */
0450     level = be16_to_cpu(block->bb_level);
0451     if (level > max(mp->m_bm_maxlevels[0], mp->m_bm_maxlevels[1]))
0452         return __this_address;
0453
0454     return xfs_btree_lblock_verify(bp, mp->m_bmap_dmxr[level != 0]);
0455 }
0456
0457 static void
0458 xfs_bmbt_read_verify(
0459     struct xfs_buf  *bp)
0460 {
0461     xfs_failaddr_t  fa;
0462
0463     if (!xfs_btree_lblock_verify_crc(bp))
0464         xfs_verifier_error(bp, -EFSBADCRC, __this_address);
0465     else {
0466         fa = xfs_bmbt_verify(bp);
0467         if (fa)
0468             xfs_verifier_error(bp, -EFSCORRUPTED, fa);
0469     }
0470
0471     if (bp->b_error)
0472         trace_xfs_btree_corrupt(bp, _RET_IP_);
0473 }
0474
0475 static void
0476 xfs_bmbt_write_verify(
0477     struct xfs_buf  *bp)
0478 {
0479     xfs_failaddr_t  fa;
0480
0481     fa = xfs_bmbt_verify(bp);
0482     if (fa) {
0483         trace_xfs_btree_corrupt(bp, _RET_IP_);
0484         xfs_verifier_error(bp, -EFSCORRUPTED, fa);
0485         return;
0486     }
0487     xfs_btree_lblock_calc_crc(bp);
0488 }
0489
0490 const struct xfs_buf_ops xfs_bmbt_buf_ops = {
0491     .name = "xfs_bmbt",
0492     .magic = { cpu_to_be32(XFS_BMAP_MAGIC),
0493            cpu_to_be32(XFS_BMAP_CRC_MAGIC) },
0494     .verify_read = xfs_bmbt_read_verify,
0495     .verify_write = xfs_bmbt_write_verify,
0496     .verify_struct = xfs_bmbt_verify,
0497 };
0498
0499
0500 STATIC int
0501 xfs_bmbt_keys_inorder(
0502     struct xfs_btree_cur        *cur,
0503     const union xfs_btree_key   *k1,
0504     const union xfs_btree_key   *k2)
0505 {
0506     return be64_to_cpu(k1->bmbt.br_startoff) <
0507         be64_to_cpu(k2->bmbt.br_startoff);
0508 }
0509
0510 STATIC int
0511 xfs_bmbt_recs_inorder(
0512     struct xfs_btree_cur        *cur,
0513     const union xfs_btree_rec   *r1,
0514     const union xfs_btree_rec   *r2)
0515 {
0516     return xfs_bmbt_disk_get_startoff(&r1->bmbt) +
0517         xfs_bmbt_disk_get_blockcount(&r1->bmbt) <=
0518         xfs_bmbt_disk_get_startoff(&r2->bmbt);
0519 }
0520
0521 static const struct xfs_btree_ops xfs_bmbt_ops = {
0522     .rec_len        = sizeof(xfs_bmbt_rec_t),
0523     .key_len        = sizeof(xfs_bmbt_key_t),
0524
0525     .dup_cursor     = xfs_bmbt_dup_cursor,
0526     .update_cursor      = xfs_bmbt_update_cursor,
0527     .alloc_block        = xfs_bmbt_alloc_block,
0528     .free_block     = xfs_bmbt_free_block,
0529     .get_maxrecs        = xfs_bmbt_get_maxrecs,
0530     .get_minrecs        = xfs_bmbt_get_minrecs,
0531     .get_dmaxrecs       = xfs_bmbt_get_dmaxrecs,
0532     .init_key_from_rec  = xfs_bmbt_init_key_from_rec,
0533     .init_high_key_from_rec = xfs_bmbt_init_high_key_from_rec,
0534     .init_rec_from_cur  = xfs_bmbt_init_rec_from_cur,
0535     .init_ptr_from_cur  = xfs_bmbt_init_ptr_from_cur,
0536     .key_diff       = xfs_bmbt_key_diff,
0537     .diff_two_keys      = xfs_bmbt_diff_two_keys,
0538     .buf_ops        = &xfs_bmbt_buf_ops,
0539     .keys_inorder       = xfs_bmbt_keys_inorder,
0540     .recs_inorder       = xfs_bmbt_recs_inorder,
0541 };
0542
0543 /*
0544  * Allocate a new bmap btree cursor.
0545  */
0546 struct xfs_btree_cur *              /* new bmap btree cursor */
0547 xfs_bmbt_init_cursor(
0548     struct xfs_mount    *mp,        /* file system mount point */
0549     struct xfs_trans    *tp,        /* transaction pointer */
0550     struct xfs_inode    *ip,        /* inode owning the btree */
0551     int         whichfork)  /* data or attr fork */
0552 {
0553     struct xfs_ifork    *ifp = xfs_ifork_ptr(ip, whichfork);
0554     struct xfs_btree_cur    *cur;
0555     ASSERT(whichfork != XFS_COW_FORK);
0556
0557     cur = xfs_btree_alloc_cursor(mp, tp, XFS_BTNUM_BMAP,
0558             mp->m_bm_maxlevels[whichfork], xfs_bmbt_cur_cache);
0559     cur->bc_nlevels = be16_to_cpu(ifp->if_broot->bb_level) + 1;
0560     cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_bmbt_2);
0561
0562     cur->bc_ops = &xfs_bmbt_ops;
0563     cur->bc_flags = XFS_BTREE_LONG_PTRS | XFS_BTREE_ROOT_IN_INODE;
0564     if (xfs_has_crc(mp))
0565         cur->bc_flags |= XFS_BTREE_CRC_BLOCKS;
0566
0567     cur->bc_ino.forksize = xfs_inode_fork_size(ip, whichfork);
0568     cur->bc_ino.ip = ip;
0569     cur->bc_ino.allocated = 0;
0570     cur->bc_ino.flags = 0;
0571     cur->bc_ino.whichfork = whichfork;
0572
0573     return cur;
0574 }
0575
0576 /* Calculate number of records in a block mapping btree block. */
0577 static inline unsigned int
0578 xfs_bmbt_block_maxrecs(
0579     unsigned int        blocklen,
0580     bool            leaf)
0581 {
0582     if (leaf)
0583         return blocklen / sizeof(xfs_bmbt_rec_t);
0584     return blocklen / (sizeof(xfs_bmbt_key_t) + sizeof(xfs_bmbt_ptr_t));
0585 }
0586
0587 /*
0588  * Calculate number of records in a bmap btree block.
0589  */
0590 int
0591 xfs_bmbt_maxrecs(
0592     struct xfs_mount    *mp,
0593     int         blocklen,
0594     int         leaf)
0595 {
0596     blocklen -= XFS_BMBT_BLOCK_LEN(mp);
0597     return xfs_bmbt_block_maxrecs(blocklen, leaf);
0598 }
0599
0600 /*
0601  * Calculate the maximum possible height of the btree that the on-disk format
0602  * supports. This is used for sizing structures large enough to support every
0603  * possible configuration of a filesystem that might get mounted.
0604  */
0605 unsigned int
0606 xfs_bmbt_maxlevels_ondisk(void)
0607 {
0608     unsigned int        minrecs[2];
0609     unsigned int        blocklen;
0610
0611     blocklen = min(XFS_MIN_BLOCKSIZE - XFS_BTREE_SBLOCK_LEN,
0612                XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN);
0613
0614     minrecs[0] = xfs_bmbt_block_maxrecs(blocklen, true) / 2;
0615     minrecs[1] = xfs_bmbt_block_maxrecs(blocklen, false) / 2;
0616
0617     /* One extra level for the inode root. */
0618     return xfs_btree_compute_maxlevels(minrecs,
0619             XFS_MAX_EXTCNT_DATA_FORK_LARGE) + 1;
0620 }
0621
0622 /*
0623  * Calculate number of records in a bmap btree inode root.
0624  */
0625 int
0626 xfs_bmdr_maxrecs(
0627     int         blocklen,
0628     int         leaf)
0629 {
0630     blocklen -= sizeof(xfs_bmdr_block_t);
0631
0632     if (leaf)
0633         return blocklen / sizeof(xfs_bmdr_rec_t);
0634     return blocklen / (sizeof(xfs_bmdr_key_t) + sizeof(xfs_bmdr_ptr_t));
0635 }
0636
0637 /*
0638  * Change the owner of a btree format fork fo the inode passed in. Change it to
0639  * the owner of that is passed in so that we can change owners before or after
0640  * we switch forks between inodes. The operation that the caller is doing will
0641  * determine whether is needs to change owner before or after the switch.
0642  *
0643  * For demand paged transactional modification, the fork switch should be done
0644  * after reading in all the blocks, modifying them and pinning them in the
0645  * transaction. For modification when the buffers are already pinned in memory,
0646  * the fork switch can be done before changing the owner as we won't need to
0647  * validate the owner until the btree buffers are unpinned and writes can occur
0648  * again.
0649  *
0650  * For recovery based ownership change, there is no transactional context and
0651  * so a buffer list must be supplied so that we can record the buffers that we
0652  * modified for the caller to issue IO on.
0653  */
0654 int
0655 xfs_bmbt_change_owner(
0656     struct xfs_trans    *tp,
0657     struct xfs_inode    *ip,
0658     int         whichfork,
0659     xfs_ino_t       new_owner,
0660     struct list_head    *buffer_list)
0661 {
0662     struct xfs_btree_cur    *cur;
0663     int         error;
0664
0665     ASSERT(tp || buffer_list);
0666     ASSERT(!(tp && buffer_list));
0667     ASSERT(xfs_ifork_ptr(ip, whichfork)->if_format == XFS_DINODE_FMT_BTREE);
0668
0669     cur = xfs_bmbt_init_cursor(ip->i_mount, tp, ip, whichfork);
0670     cur->bc_ino.flags |= XFS_BTCUR_BMBT_INVALID_OWNER;
0671
0672     error = xfs_btree_change_owner(cur, new_owner, buffer_list);
0673     xfs_btree_del_cursor(cur, error);
0674     return error;
0675 }
0676
0677 /* Calculate the bmap btree size for some records. */
0678 unsigned long long
0679 xfs_bmbt_calc_size(
0680     struct xfs_mount    *mp,
0681     unsigned long long  len)
0682 {
0683     return xfs_btree_calc_size(mp->m_bmap_dmnr, len);
0684 }
0685
0686 int __init
0687 xfs_bmbt_init_cur_cache(void)
0688 {
0689     xfs_bmbt_cur_cache = kmem_cache_create("xfs_bmbt_cur",
0690             xfs_btree_cur_sizeof(xfs_bmbt_maxlevels_ondisk()),
0691             0, 0, NULL);
0692
0693     if (!xfs_bmbt_cur_cache)
0694         return -ENOMEM;
0695     return 0;
0696 }
0697
0698 void
0699 xfs_bmbt_destroy_cur_cache(void)
0700 {
0701     kmem_cache_destroy(xfs_bmbt_cur_cache);
0702     xfs_bmbt_cur_cache = NULL;
0703 }