xfs/libxfs/xfs_rmap.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * Copyright (c) 2014 Red Hat, 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_sb.h"
0015 #include "xfs_defer.h"
0016 #include "xfs_btree.h"
0017 #include "xfs_trans.h"
0018 #include "xfs_alloc.h"
0019 #include "xfs_rmap.h"
0020 #include "xfs_rmap_btree.h"
0021 #include "xfs_trace.h"
0022 #include "xfs_errortag.h"
0023 #include "xfs_error.h"
0024 #include "xfs_inode.h"
0025 #include "xfs_ag.h"
0026
0027 struct kmem_cache   *xfs_rmap_intent_cache;
0028
0029 /*
0030  * Lookup the first record less than or equal to [bno, len, owner, offset]
0031  * in the btree given by cur.
0032  */
0033 int
0034 xfs_rmap_lookup_le(
0035     struct xfs_btree_cur    *cur,
0036     xfs_agblock_t       bno,
0037     uint64_t        owner,
0038     uint64_t        offset,
0039     unsigned int        flags,
0040     struct xfs_rmap_irec    *irec,
0041     int         *stat)
0042 {
0043     int         get_stat = 0;
0044     int         error;
0045
0046     cur->bc_rec.r.rm_startblock = bno;
0047     cur->bc_rec.r.rm_blockcount = 0;
0048     cur->bc_rec.r.rm_owner = owner;
0049     cur->bc_rec.r.rm_offset = offset;
0050     cur->bc_rec.r.rm_flags = flags;
0051
0052     error = xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat);
0053     if (error || !(*stat) || !irec)
0054         return error;
0055
0056     error = xfs_rmap_get_rec(cur, irec, &get_stat);
0057     if (error)
0058         return error;
0059     if (!get_stat)
0060         return -EFSCORRUPTED;
0061
0062     return 0;
0063 }
0064
0065 /*
0066  * Lookup the record exactly matching [bno, len, owner, offset]
0067  * in the btree given by cur.
0068  */
0069 int
0070 xfs_rmap_lookup_eq(
0071     struct xfs_btree_cur    *cur,
0072     xfs_agblock_t       bno,
0073     xfs_extlen_t        len,
0074     uint64_t        owner,
0075     uint64_t        offset,
0076     unsigned int        flags,
0077     int         *stat)
0078 {
0079     cur->bc_rec.r.rm_startblock = bno;
0080     cur->bc_rec.r.rm_blockcount = len;
0081     cur->bc_rec.r.rm_owner = owner;
0082     cur->bc_rec.r.rm_offset = offset;
0083     cur->bc_rec.r.rm_flags = flags;
0084     return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat);
0085 }
0086
0087 /*
0088  * Update the record referred to by cur to the value given
0089  * by [bno, len, owner, offset].
0090  * This either works (return 0) or gets an EFSCORRUPTED error.
0091  */
0092 STATIC int
0093 xfs_rmap_update(
0094     struct xfs_btree_cur    *cur,
0095     struct xfs_rmap_irec    *irec)
0096 {
0097     union xfs_btree_rec rec;
0098     int         error;
0099
0100     trace_xfs_rmap_update(cur->bc_mp, cur->bc_ag.pag->pag_agno,
0101             irec->rm_startblock, irec->rm_blockcount,
0102             irec->rm_owner, irec->rm_offset, irec->rm_flags);
0103
0104     rec.rmap.rm_startblock = cpu_to_be32(irec->rm_startblock);
0105     rec.rmap.rm_blockcount = cpu_to_be32(irec->rm_blockcount);
0106     rec.rmap.rm_owner = cpu_to_be64(irec->rm_owner);
0107     rec.rmap.rm_offset = cpu_to_be64(
0108             xfs_rmap_irec_offset_pack(irec));
0109     error = xfs_btree_update(cur, &rec);
0110     if (error)
0111         trace_xfs_rmap_update_error(cur->bc_mp,
0112                 cur->bc_ag.pag->pag_agno, error, _RET_IP_);
0113     return error;
0114 }
0115
0116 int
0117 xfs_rmap_insert(
0118     struct xfs_btree_cur    *rcur,
0119     xfs_agblock_t       agbno,
0120     xfs_extlen_t        len,
0121     uint64_t        owner,
0122     uint64_t        offset,
0123     unsigned int        flags)
0124 {
0125     int         i;
0126     int         error;
0127
0128     trace_xfs_rmap_insert(rcur->bc_mp, rcur->bc_ag.pag->pag_agno, agbno,
0129             len, owner, offset, flags);
0130
0131     error = xfs_rmap_lookup_eq(rcur, agbno, len, owner, offset, flags, &i);
0132     if (error)
0133         goto done;
0134     if (XFS_IS_CORRUPT(rcur->bc_mp, i != 0)) {
0135         error = -EFSCORRUPTED;
0136         goto done;
0137     }
0138
0139     rcur->bc_rec.r.rm_startblock = agbno;
0140     rcur->bc_rec.r.rm_blockcount = len;
0141     rcur->bc_rec.r.rm_owner = owner;
0142     rcur->bc_rec.r.rm_offset = offset;
0143     rcur->bc_rec.r.rm_flags = flags;
0144     error = xfs_btree_insert(rcur, &i);
0145     if (error)
0146         goto done;
0147     if (XFS_IS_CORRUPT(rcur->bc_mp, i != 1)) {
0148         error = -EFSCORRUPTED;
0149         goto done;
0150     }
0151 done:
0152     if (error)
0153         trace_xfs_rmap_insert_error(rcur->bc_mp,
0154                 rcur->bc_ag.pag->pag_agno, error, _RET_IP_);
0155     return error;
0156 }
0157
0158 STATIC int
0159 xfs_rmap_delete(
0160     struct xfs_btree_cur    *rcur,
0161     xfs_agblock_t       agbno,
0162     xfs_extlen_t        len,
0163     uint64_t        owner,
0164     uint64_t        offset,
0165     unsigned int        flags)
0166 {
0167     int         i;
0168     int         error;
0169
0170     trace_xfs_rmap_delete(rcur->bc_mp, rcur->bc_ag.pag->pag_agno, agbno,
0171             len, owner, offset, flags);
0172
0173     error = xfs_rmap_lookup_eq(rcur, agbno, len, owner, offset, flags, &i);
0174     if (error)
0175         goto done;
0176     if (XFS_IS_CORRUPT(rcur->bc_mp, i != 1)) {
0177         error = -EFSCORRUPTED;
0178         goto done;
0179     }
0180
0181     error = xfs_btree_delete(rcur, &i);
0182     if (error)
0183         goto done;
0184     if (XFS_IS_CORRUPT(rcur->bc_mp, i != 1)) {
0185         error = -EFSCORRUPTED;
0186         goto done;
0187     }
0188 done:
0189     if (error)
0190         trace_xfs_rmap_delete_error(rcur->bc_mp,
0191                 rcur->bc_ag.pag->pag_agno, error, _RET_IP_);
0192     return error;
0193 }
0194
0195 /* Convert an internal btree record to an rmap record. */
0196 int
0197 xfs_rmap_btrec_to_irec(
0198     const union xfs_btree_rec   *rec,
0199     struct xfs_rmap_irec        *irec)
0200 {
0201     irec->rm_startblock = be32_to_cpu(rec->rmap.rm_startblock);
0202     irec->rm_blockcount = be32_to_cpu(rec->rmap.rm_blockcount);
0203     irec->rm_owner = be64_to_cpu(rec->rmap.rm_owner);
0204     return xfs_rmap_irec_offset_unpack(be64_to_cpu(rec->rmap.rm_offset),
0205             irec);
0206 }
0207
0208 /*
0209  * Get the data from the pointed-to record.
0210  */
0211 int
0212 xfs_rmap_get_rec(
0213     struct xfs_btree_cur    *cur,
0214     struct xfs_rmap_irec    *irec,
0215     int         *stat)
0216 {
0217     struct xfs_mount    *mp = cur->bc_mp;
0218     struct xfs_perag    *pag = cur->bc_ag.pag;
0219     union xfs_btree_rec *rec;
0220     int         error;
0221
0222     error = xfs_btree_get_rec(cur, &rec, stat);
0223     if (error || !*stat)
0224         return error;
0225
0226     if (xfs_rmap_btrec_to_irec(rec, irec))
0227         goto out_bad_rec;
0228
0229     if (irec->rm_blockcount == 0)
0230         goto out_bad_rec;
0231     if (irec->rm_startblock <= XFS_AGFL_BLOCK(mp)) {
0232         if (irec->rm_owner != XFS_RMAP_OWN_FS)
0233             goto out_bad_rec;
0234         if (irec->rm_blockcount != XFS_AGFL_BLOCK(mp) + 1)
0235             goto out_bad_rec;
0236     } else {
0237         /* check for valid extent range, including overflow */
0238         if (!xfs_verify_agbno(pag, irec->rm_startblock))
0239             goto out_bad_rec;
0240         if (irec->rm_startblock >
0241                 irec->rm_startblock + irec->rm_blockcount)
0242             goto out_bad_rec;
0243         if (!xfs_verify_agbno(pag,
0244                 irec->rm_startblock + irec->rm_blockcount - 1))
0245             goto out_bad_rec;
0246     }
0247
0248     if (!(xfs_verify_ino(mp, irec->rm_owner) ||
0249           (irec->rm_owner <= XFS_RMAP_OWN_FS &&
0250            irec->rm_owner >= XFS_RMAP_OWN_MIN)))
0251         goto out_bad_rec;
0252
0253     return 0;
0254 out_bad_rec:
0255     xfs_warn(mp,
0256         "Reverse Mapping BTree record corruption in AG %d detected!",
0257         pag->pag_agno);
0258     xfs_warn(mp,
0259         "Owner 0x%llx, flags 0x%x, start block 0x%x block count 0x%x",
0260         irec->rm_owner, irec->rm_flags, irec->rm_startblock,
0261         irec->rm_blockcount);
0262     return -EFSCORRUPTED;
0263 }
0264
0265 struct xfs_find_left_neighbor_info {
0266     struct xfs_rmap_irec    high;
0267     struct xfs_rmap_irec    *irec;
0268 };
0269
0270 /* For each rmap given, figure out if it matches the key we want. */
0271 STATIC int
0272 xfs_rmap_find_left_neighbor_helper(
0273     struct xfs_btree_cur        *cur,
0274     const struct xfs_rmap_irec  *rec,
0275     void                *priv)
0276 {
0277     struct xfs_find_left_neighbor_info  *info = priv;
0278
0279     trace_xfs_rmap_find_left_neighbor_candidate(cur->bc_mp,
0280             cur->bc_ag.pag->pag_agno, rec->rm_startblock,
0281             rec->rm_blockcount, rec->rm_owner, rec->rm_offset,
0282             rec->rm_flags);
0283
0284     if (rec->rm_owner != info->high.rm_owner)
0285         return 0;
0286     if (!XFS_RMAP_NON_INODE_OWNER(rec->rm_owner) &&
0287         !(rec->rm_flags & XFS_RMAP_BMBT_BLOCK) &&
0288         rec->rm_offset + rec->rm_blockcount - 1 != info->high.rm_offset)
0289         return 0;
0290
0291     *info->irec = *rec;
0292     return -ECANCELED;
0293 }
0294
0295 /*
0296  * Find the record to the left of the given extent, being careful only to
0297  * return a match with the same owner and adjacent physical and logical
0298  * block ranges.
0299  */
0300 STATIC int
0301 xfs_rmap_find_left_neighbor(
0302     struct xfs_btree_cur    *cur,
0303     xfs_agblock_t       bno,
0304     uint64_t        owner,
0305     uint64_t        offset,
0306     unsigned int        flags,
0307     struct xfs_rmap_irec    *irec,
0308     int         *stat)
0309 {
0310     struct xfs_find_left_neighbor_info  info;
0311     int         found = 0;
0312     int         error;
0313
0314     *stat = 0;
0315     if (bno == 0)
0316         return 0;
0317     info.high.rm_startblock = bno - 1;
0318     info.high.rm_owner = owner;
0319     if (!XFS_RMAP_NON_INODE_OWNER(owner) &&
0320         !(flags & XFS_RMAP_BMBT_BLOCK)) {
0321         if (offset == 0)
0322             return 0;
0323         info.high.rm_offset = offset - 1;
0324     } else
0325         info.high.rm_offset = 0;
0326     info.high.rm_flags = flags;
0327     info.high.rm_blockcount = 0;
0328     info.irec = irec;
0329
0330     trace_xfs_rmap_find_left_neighbor_query(cur->bc_mp,
0331             cur->bc_ag.pag->pag_agno, bno, 0, owner, offset, flags);
0332
0333     /*
0334      * Historically, we always used the range query to walk every reverse
0335      * mapping that could possibly overlap the key that the caller asked
0336      * for, and filter out the ones that don't.  That is very slow when
0337      * there are a lot of records.
0338      *
0339      * However, there are two scenarios where the classic btree search can
0340      * produce correct results -- if the index contains a record that is an
0341      * exact match for the lookup key; and if there are no other records
0342      * between the record we want and the key we supplied.
0343      *
0344      * As an optimization, try a non-overlapped lookup first.  This makes
0345      * extent conversion and remap operations run a bit faster if the
0346      * physical extents aren't being shared.  If we don't find what we
0347      * want, we fall back to the overlapped query.
0348      */
0349     error = xfs_rmap_lookup_le(cur, bno, owner, offset, flags, irec,
0350             &found);
0351     if (error)
0352         return error;
0353     if (found)
0354         error = xfs_rmap_find_left_neighbor_helper(cur, irec, &info);
0355     if (!error)
0356         error = xfs_rmap_query_range(cur, &info.high, &info.high,
0357                 xfs_rmap_find_left_neighbor_helper, &info);
0358     if (error != -ECANCELED)
0359         return error;
0360
0361     *stat = 1;
0362     trace_xfs_rmap_find_left_neighbor_result(cur->bc_mp,
0363             cur->bc_ag.pag->pag_agno, irec->rm_startblock,
0364             irec->rm_blockcount, irec->rm_owner, irec->rm_offset,
0365             irec->rm_flags);
0366     return 0;
0367 }
0368
0369 /* For each rmap given, figure out if it matches the key we want. */
0370 STATIC int
0371 xfs_rmap_lookup_le_range_helper(
0372     struct xfs_btree_cur        *cur,
0373     const struct xfs_rmap_irec  *rec,
0374     void                *priv)
0375 {
0376     struct xfs_find_left_neighbor_info  *info = priv;
0377
0378     trace_xfs_rmap_lookup_le_range_candidate(cur->bc_mp,
0379             cur->bc_ag.pag->pag_agno, rec->rm_startblock,
0380             rec->rm_blockcount, rec->rm_owner, rec->rm_offset,
0381             rec->rm_flags);
0382
0383     if (rec->rm_owner != info->high.rm_owner)
0384         return 0;
0385     if (!XFS_RMAP_NON_INODE_OWNER(rec->rm_owner) &&
0386         !(rec->rm_flags & XFS_RMAP_BMBT_BLOCK) &&
0387         (rec->rm_offset > info->high.rm_offset ||
0388          rec->rm_offset + rec->rm_blockcount <= info->high.rm_offset))
0389         return 0;
0390
0391     *info->irec = *rec;
0392     return -ECANCELED;
0393 }
0394
0395 /*
0396  * Find the record to the left of the given extent, being careful only to
0397  * return a match with the same owner and overlapping physical and logical
0398  * block ranges.  This is the overlapping-interval version of
0399  * xfs_rmap_lookup_le.
0400  */
0401 int
0402 xfs_rmap_lookup_le_range(
0403     struct xfs_btree_cur    *cur,
0404     xfs_agblock_t       bno,
0405     uint64_t        owner,
0406     uint64_t        offset,
0407     unsigned int        flags,
0408     struct xfs_rmap_irec    *irec,
0409     int         *stat)
0410 {
0411     struct xfs_find_left_neighbor_info  info;
0412     int         found = 0;
0413     int         error;
0414
0415     info.high.rm_startblock = bno;
0416     info.high.rm_owner = owner;
0417     if (!XFS_RMAP_NON_INODE_OWNER(owner) && !(flags & XFS_RMAP_BMBT_BLOCK))
0418         info.high.rm_offset = offset;
0419     else
0420         info.high.rm_offset = 0;
0421     info.high.rm_flags = flags;
0422     info.high.rm_blockcount = 0;
0423     *stat = 0;
0424     info.irec = irec;
0425
0426     trace_xfs_rmap_lookup_le_range(cur->bc_mp, cur->bc_ag.pag->pag_agno,
0427             bno, 0, owner, offset, flags);
0428
0429     /*
0430      * Historically, we always used the range query to walk every reverse
0431      * mapping that could possibly overlap the key that the caller asked
0432      * for, and filter out the ones that don't.  That is very slow when
0433      * there are a lot of records.
0434      *
0435      * However, there are two scenarios where the classic btree search can
0436      * produce correct results -- if the index contains a record that is an
0437      * exact match for the lookup key; and if there are no other records
0438      * between the record we want and the key we supplied.
0439      *
0440      * As an optimization, try a non-overlapped lookup first.  This makes
0441      * scrub run much faster on most filesystems because bmbt records are
0442      * usually an exact match for rmap records.  If we don't find what we
0443      * want, we fall back to the overlapped query.
0444      */
0445     error = xfs_rmap_lookup_le(cur, bno, owner, offset, flags, irec,
0446             &found);
0447     if (error)
0448         return error;
0449     if (found)
0450         error = xfs_rmap_lookup_le_range_helper(cur, irec, &info);
0451     if (!error)
0452         error = xfs_rmap_query_range(cur, &info.high, &info.high,
0453                 xfs_rmap_lookup_le_range_helper, &info);
0454     if (error != -ECANCELED)
0455         return error;
0456
0457     *stat = 1;
0458     trace_xfs_rmap_lookup_le_range_result(cur->bc_mp,
0459             cur->bc_ag.pag->pag_agno, irec->rm_startblock,
0460             irec->rm_blockcount, irec->rm_owner, irec->rm_offset,
0461             irec->rm_flags);
0462     return 0;
0463 }
0464
0465 /*
0466  * Perform all the relevant owner checks for a removal op.  If we're doing an
0467  * unknown-owner removal then we have no owner information to check.
0468  */
0469 static int
0470 xfs_rmap_free_check_owner(
0471     struct xfs_mount    *mp,
0472     uint64_t        ltoff,
0473     struct xfs_rmap_irec    *rec,
0474     xfs_filblks_t       len,
0475     uint64_t        owner,
0476     uint64_t        offset,
0477     unsigned int        flags)
0478 {
0479     int         error = 0;
0480
0481     if (owner == XFS_RMAP_OWN_UNKNOWN)
0482         return 0;
0483
0484     /* Make sure the unwritten flag matches. */
0485     if (XFS_IS_CORRUPT(mp,
0486                (flags & XFS_RMAP_UNWRITTEN) !=
0487                (rec->rm_flags & XFS_RMAP_UNWRITTEN))) {
0488         error = -EFSCORRUPTED;
0489         goto out;
0490     }
0491
0492     /* Make sure the owner matches what we expect to find in the tree. */
0493     if (XFS_IS_CORRUPT(mp, owner != rec->rm_owner)) {
0494         error = -EFSCORRUPTED;
0495         goto out;
0496     }
0497
0498     /* Check the offset, if necessary. */
0499     if (XFS_RMAP_NON_INODE_OWNER(owner))
0500         goto out;
0501
0502     if (flags & XFS_RMAP_BMBT_BLOCK) {
0503         if (XFS_IS_CORRUPT(mp,
0504                    !(rec->rm_flags & XFS_RMAP_BMBT_BLOCK))) {
0505             error = -EFSCORRUPTED;
0506             goto out;
0507         }
0508     } else {
0509         if (XFS_IS_CORRUPT(mp, rec->rm_offset > offset)) {
0510             error = -EFSCORRUPTED;
0511             goto out;
0512         }
0513         if (XFS_IS_CORRUPT(mp,
0514                    offset + len > ltoff + rec->rm_blockcount)) {
0515             error = -EFSCORRUPTED;
0516             goto out;
0517         }
0518     }
0519
0520 out:
0521     return error;
0522 }
0523
0524 /*
0525  * Find the extent in the rmap btree and remove it.
0526  *
0527  * The record we find should always be an exact match for the extent that we're
0528  * looking for, since we insert them into the btree without modification.
0529  *
0530  * Special Case #1: when growing the filesystem, we "free" an extent when
0531  * growing the last AG. This extent is new space and so it is not tracked as
0532  * used space in the btree. The growfs code will pass in an owner of
0533  * XFS_RMAP_OWN_NULL to indicate that it expected that there is no owner of this
0534  * extent. We verify that - the extent lookup result in a record that does not
0535  * overlap.
0536  *
0537  * Special Case #2: EFIs do not record the owner of the extent, so when
0538  * recovering EFIs from the log we pass in XFS_RMAP_OWN_UNKNOWN to tell the rmap
0539  * btree to ignore the owner (i.e. wildcard match) so we don't trigger
0540  * corruption checks during log recovery.
0541  */
0542 STATIC int
0543 xfs_rmap_unmap(
0544     struct xfs_btree_cur        *cur,
0545     xfs_agblock_t           bno,
0546     xfs_extlen_t            len,
0547     bool                unwritten,
0548     const struct xfs_owner_info *oinfo)
0549 {
0550     struct xfs_mount        *mp = cur->bc_mp;
0551     struct xfs_rmap_irec        ltrec;
0552     uint64_t            ltoff;
0553     int             error = 0;
0554     int             i;
0555     uint64_t            owner;
0556     uint64_t            offset;
0557     unsigned int            flags;
0558     bool                ignore_off;
0559
0560     xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
0561     ignore_off = XFS_RMAP_NON_INODE_OWNER(owner) ||
0562             (flags & XFS_RMAP_BMBT_BLOCK);
0563     if (unwritten)
0564         flags |= XFS_RMAP_UNWRITTEN;
0565     trace_xfs_rmap_unmap(mp, cur->bc_ag.pag->pag_agno, bno, len,
0566             unwritten, oinfo);
0567
0568     /*
0569      * We should always have a left record because there's a static record
0570      * for the AG headers at rm_startblock == 0 created by mkfs/growfs that
0571      * will not ever be removed from the tree.
0572      */
0573     error = xfs_rmap_lookup_le(cur, bno, owner, offset, flags, &ltrec, &i);
0574     if (error)
0575         goto out_error;
0576     if (XFS_IS_CORRUPT(mp, i != 1)) {
0577         error = -EFSCORRUPTED;
0578         goto out_error;
0579     }
0580
0581     trace_xfs_rmap_lookup_le_range_result(cur->bc_mp,
0582             cur->bc_ag.pag->pag_agno, ltrec.rm_startblock,
0583             ltrec.rm_blockcount, ltrec.rm_owner,
0584             ltrec.rm_offset, ltrec.rm_flags);
0585     ltoff = ltrec.rm_offset;
0586
0587     /*
0588      * For growfs, the incoming extent must be beyond the left record we
0589      * just found as it is new space and won't be used by anyone. This is
0590      * just a corruption check as we don't actually do anything with this
0591      * extent.  Note that we need to use >= instead of > because it might
0592      * be the case that the "left" extent goes all the way to EOFS.
0593      */
0594     if (owner == XFS_RMAP_OWN_NULL) {
0595         if (XFS_IS_CORRUPT(mp,
0596                    bno <
0597                    ltrec.rm_startblock + ltrec.rm_blockcount)) {
0598             error = -EFSCORRUPTED;
0599             goto out_error;
0600         }
0601         goto out_done;
0602     }
0603
0604     /*
0605      * If we're doing an unknown-owner removal for EFI recovery, we expect
0606      * to find the full range in the rmapbt or nothing at all.  If we
0607      * don't find any rmaps overlapping either end of the range, we're
0608      * done.  Hopefully this means that the EFI creator already queued
0609      * (and finished) a RUI to remove the rmap.
0610      */
0611     if (owner == XFS_RMAP_OWN_UNKNOWN &&
0612         ltrec.rm_startblock + ltrec.rm_blockcount <= bno) {
0613         struct xfs_rmap_irec    rtrec;
0614
0615         error = xfs_btree_increment(cur, 0, &i);
0616         if (error)
0617             goto out_error;
0618         if (i == 0)
0619             goto out_done;
0620         error = xfs_rmap_get_rec(cur, &rtrec, &i);
0621         if (error)
0622             goto out_error;
0623         if (XFS_IS_CORRUPT(mp, i != 1)) {
0624             error = -EFSCORRUPTED;
0625             goto out_error;
0626         }
0627         if (rtrec.rm_startblock >= bno + len)
0628             goto out_done;
0629     }
0630
0631     /* Make sure the extent we found covers the entire freeing range. */
0632     if (XFS_IS_CORRUPT(mp,
0633                ltrec.rm_startblock > bno ||
0634                ltrec.rm_startblock + ltrec.rm_blockcount <
0635                bno + len)) {
0636         error = -EFSCORRUPTED;
0637         goto out_error;
0638     }
0639
0640     /* Check owner information. */
0641     error = xfs_rmap_free_check_owner(mp, ltoff, &ltrec, len, owner,
0642             offset, flags);
0643     if (error)
0644         goto out_error;
0645
0646     if (ltrec.rm_startblock == bno && ltrec.rm_blockcount == len) {
0647         /* exact match, simply remove the record from rmap tree */
0648         trace_xfs_rmap_delete(mp, cur->bc_ag.pag->pag_agno,
0649                 ltrec.rm_startblock, ltrec.rm_blockcount,
0650                 ltrec.rm_owner, ltrec.rm_offset,
0651                 ltrec.rm_flags);
0652         error = xfs_btree_delete(cur, &i);
0653         if (error)
0654             goto out_error;
0655         if (XFS_IS_CORRUPT(mp, i != 1)) {
0656             error = -EFSCORRUPTED;
0657             goto out_error;
0658         }
0659     } else if (ltrec.rm_startblock == bno) {
0660         /*
0661          * overlap left hand side of extent: move the start, trim the
0662          * length and update the current record.
0663          *
0664          *       ltbno                ltlen
0665          * Orig:    |oooooooooooooooooooo|
0666          * Freeing: |fffffffff|
0667          * Result:            |rrrrrrrrrr|
0668          *         bno       len
0669          */
0670         ltrec.rm_startblock += len;
0671         ltrec.rm_blockcount -= len;
0672         if (!ignore_off)
0673             ltrec.rm_offset += len;
0674         error = xfs_rmap_update(cur, &ltrec);
0675         if (error)
0676             goto out_error;
0677     } else if (ltrec.rm_startblock + ltrec.rm_blockcount == bno + len) {
0678         /*
0679          * overlap right hand side of extent: trim the length and update
0680          * the current record.
0681          *
0682          *       ltbno                ltlen
0683          * Orig:    |oooooooooooooooooooo|
0684          * Freeing:            |fffffffff|
0685          * Result:  |rrrrrrrrrr|
0686          *                    bno       len
0687          */
0688         ltrec.rm_blockcount -= len;
0689         error = xfs_rmap_update(cur, &ltrec);
0690         if (error)
0691             goto out_error;
0692     } else {
0693
0694         /*
0695          * overlap middle of extent: trim the length of the existing
0696          * record to the length of the new left-extent size, increment
0697          * the insertion position so we can insert a new record
0698          * containing the remaining right-extent space.
0699          *
0700          *       ltbno                ltlen
0701          * Orig:    |oooooooooooooooooooo|
0702          * Freeing:       |fffffffff|
0703          * Result:  |rrrrr|         |rrrr|
0704          *               bno       len
0705          */
0706         xfs_extlen_t    orig_len = ltrec.rm_blockcount;
0707
0708         ltrec.rm_blockcount = bno - ltrec.rm_startblock;
0709         error = xfs_rmap_update(cur, &ltrec);
0710         if (error)
0711             goto out_error;
0712
0713         error = xfs_btree_increment(cur, 0, &i);
0714         if (error)
0715             goto out_error;
0716
0717         cur->bc_rec.r.rm_startblock = bno + len;
0718         cur->bc_rec.r.rm_blockcount = orig_len - len -
0719                              ltrec.rm_blockcount;
0720         cur->bc_rec.r.rm_owner = ltrec.rm_owner;
0721         if (ignore_off)
0722             cur->bc_rec.r.rm_offset = 0;
0723         else
0724             cur->bc_rec.r.rm_offset = offset + len;
0725         cur->bc_rec.r.rm_flags = flags;
0726         trace_xfs_rmap_insert(mp, cur->bc_ag.pag->pag_agno,
0727                 cur->bc_rec.r.rm_startblock,
0728                 cur->bc_rec.r.rm_blockcount,
0729                 cur->bc_rec.r.rm_owner,
0730                 cur->bc_rec.r.rm_offset,
0731                 cur->bc_rec.r.rm_flags);
0732         error = xfs_btree_insert(cur, &i);
0733         if (error)
0734             goto out_error;
0735     }
0736
0737 out_done:
0738     trace_xfs_rmap_unmap_done(mp, cur->bc_ag.pag->pag_agno, bno, len,
0739             unwritten, oinfo);
0740 out_error:
0741     if (error)
0742         trace_xfs_rmap_unmap_error(mp, cur->bc_ag.pag->pag_agno,
0743                 error, _RET_IP_);
0744     return error;
0745 }
0746
0747 /*
0748  * Remove a reference to an extent in the rmap btree.
0749  */
0750 int
0751 xfs_rmap_free(
0752     struct xfs_trans        *tp,
0753     struct xfs_buf          *agbp,
0754     struct xfs_perag        *pag,
0755     xfs_agblock_t           bno,
0756     xfs_extlen_t            len,
0757     const struct xfs_owner_info *oinfo)
0758 {
0759     struct xfs_mount        *mp = tp->t_mountp;
0760     struct xfs_btree_cur        *cur;
0761     int             error;
0762
0763     if (!xfs_has_rmapbt(mp))
0764         return 0;
0765
0766     cur = xfs_rmapbt_init_cursor(mp, tp, agbp, pag);
0767
0768     error = xfs_rmap_unmap(cur, bno, len, false, oinfo);
0769
0770     xfs_btree_del_cursor(cur, error);
0771     return error;
0772 }
0773
0774 /*
0775  * A mergeable rmap must have the same owner and the same values for
0776  * the unwritten, attr_fork, and bmbt flags.  The startblock and
0777  * offset are checked separately.
0778  */
0779 static bool
0780 xfs_rmap_is_mergeable(
0781     struct xfs_rmap_irec    *irec,
0782     uint64_t        owner,
0783     unsigned int        flags)
0784 {
0785     if (irec->rm_owner == XFS_RMAP_OWN_NULL)
0786         return false;
0787     if (irec->rm_owner != owner)
0788         return false;
0789     if ((flags & XFS_RMAP_UNWRITTEN) ^
0790         (irec->rm_flags & XFS_RMAP_UNWRITTEN))
0791         return false;
0792     if ((flags & XFS_RMAP_ATTR_FORK) ^
0793         (irec->rm_flags & XFS_RMAP_ATTR_FORK))
0794         return false;
0795     if ((flags & XFS_RMAP_BMBT_BLOCK) ^
0796         (irec->rm_flags & XFS_RMAP_BMBT_BLOCK))
0797         return false;
0798     return true;
0799 }
0800
0801 /*
0802  * When we allocate a new block, the first thing we do is add a reference to
0803  * the extent in the rmap btree. This takes the form of a [agbno, length,
0804  * owner, offset] record.  Flags are encoded in the high bits of the offset
0805  * field.
0806  */
0807 STATIC int
0808 xfs_rmap_map(
0809     struct xfs_btree_cur        *cur,
0810     xfs_agblock_t           bno,
0811     xfs_extlen_t            len,
0812     bool                unwritten,
0813     const struct xfs_owner_info *oinfo)
0814 {
0815     struct xfs_mount        *mp = cur->bc_mp;
0816     struct xfs_rmap_irec        ltrec;
0817     struct xfs_rmap_irec        gtrec;
0818     int             have_gt;
0819     int             have_lt;
0820     int             error = 0;
0821     int             i;
0822     uint64_t            owner;
0823     uint64_t            offset;
0824     unsigned int            flags = 0;
0825     bool                ignore_off;
0826
0827     xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
0828     ASSERT(owner != 0);
0829     ignore_off = XFS_RMAP_NON_INODE_OWNER(owner) ||
0830             (flags & XFS_RMAP_BMBT_BLOCK);
0831     if (unwritten)
0832         flags |= XFS_RMAP_UNWRITTEN;
0833     trace_xfs_rmap_map(mp, cur->bc_ag.pag->pag_agno, bno, len,
0834             unwritten, oinfo);
0835     ASSERT(!xfs_rmap_should_skip_owner_update(oinfo));
0836
0837     /*
0838      * For the initial lookup, look for an exact match or the left-adjacent
0839      * record for our insertion point. This will also give us the record for
0840      * start block contiguity tests.
0841      */
0842     error = xfs_rmap_lookup_le(cur, bno, owner, offset, flags, &ltrec,
0843             &have_lt);
0844     if (error)
0845         goto out_error;
0846     if (have_lt) {
0847         trace_xfs_rmap_lookup_le_range_result(cur->bc_mp,
0848                 cur->bc_ag.pag->pag_agno, ltrec.rm_startblock,
0849                 ltrec.rm_blockcount, ltrec.rm_owner,
0850                 ltrec.rm_offset, ltrec.rm_flags);
0851
0852         if (!xfs_rmap_is_mergeable(&ltrec, owner, flags))
0853             have_lt = 0;
0854     }
0855
0856     if (XFS_IS_CORRUPT(mp,
0857                have_lt != 0 &&
0858                ltrec.rm_startblock + ltrec.rm_blockcount > bno)) {
0859         error = -EFSCORRUPTED;
0860         goto out_error;
0861     }
0862
0863     /*
0864      * Increment the cursor to see if we have a right-adjacent record to our
0865      * insertion point. This will give us the record for end block
0866      * contiguity tests.
0867      */
0868     error = xfs_btree_increment(cur, 0, &have_gt);
0869     if (error)
0870         goto out_error;
0871     if (have_gt) {
0872         error = xfs_rmap_get_rec(cur, &gtrec, &have_gt);
0873         if (error)
0874             goto out_error;
0875         if (XFS_IS_CORRUPT(mp, have_gt != 1)) {
0876             error = -EFSCORRUPTED;
0877             goto out_error;
0878         }
0879         if (XFS_IS_CORRUPT(mp, bno + len > gtrec.rm_startblock)) {
0880             error = -EFSCORRUPTED;
0881             goto out_error;
0882         }
0883         trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp,
0884             cur->bc_ag.pag->pag_agno, gtrec.rm_startblock,
0885             gtrec.rm_blockcount, gtrec.rm_owner,
0886             gtrec.rm_offset, gtrec.rm_flags);
0887         if (!xfs_rmap_is_mergeable(&gtrec, owner, flags))
0888             have_gt = 0;
0889     }
0890
0891     /*
0892      * Note: cursor currently points one record to the right of ltrec, even
0893      * if there is no record in the tree to the right.
0894      */
0895     if (have_lt &&
0896         ltrec.rm_startblock + ltrec.rm_blockcount == bno &&
0897         (ignore_off || ltrec.rm_offset + ltrec.rm_blockcount == offset)) {
0898         /*
0899          * left edge contiguous, merge into left record.
0900          *
0901          *       ltbno     ltlen
0902          * orig:   |ooooooooo|
0903          * adding:           |aaaaaaaaa|
0904          * result: |rrrrrrrrrrrrrrrrrrr|
0905          *                  bno       len
0906          */
0907         ltrec.rm_blockcount += len;
0908         if (have_gt &&
0909             bno + len == gtrec.rm_startblock &&
0910             (ignore_off || offset + len == gtrec.rm_offset) &&
0911             (unsigned long)ltrec.rm_blockcount + len +
0912                 gtrec.rm_blockcount <= XFS_RMAP_LEN_MAX) {
0913             /*
0914              * right edge also contiguous, delete right record
0915              * and merge into left record.
0916              *
0917              *       ltbno     ltlen    gtbno     gtlen
0918              * orig:   |ooooooooo|         |ooooooooo|
0919              * adding:           |aaaaaaaaa|
0920              * result: |rrrrrrrrrrrrrrrrrrrrrrrrrrrrr|
0921              */
0922             ltrec.rm_blockcount += gtrec.rm_blockcount;
0923             trace_xfs_rmap_delete(mp, cur->bc_ag.pag->pag_agno,
0924                     gtrec.rm_startblock,
0925                     gtrec.rm_blockcount,
0926                     gtrec.rm_owner,
0927                     gtrec.rm_offset,
0928                     gtrec.rm_flags);
0929             error = xfs_btree_delete(cur, &i);
0930             if (error)
0931                 goto out_error;
0932             if (XFS_IS_CORRUPT(mp, i != 1)) {
0933                 error = -EFSCORRUPTED;
0934                 goto out_error;
0935             }
0936         }
0937
0938         /* point the cursor back to the left record and update */
0939         error = xfs_btree_decrement(cur, 0, &have_gt);
0940         if (error)
0941             goto out_error;
0942         error = xfs_rmap_update(cur, &ltrec);
0943         if (error)
0944             goto out_error;
0945     } else if (have_gt &&
0946            bno + len == gtrec.rm_startblock &&
0947            (ignore_off || offset + len == gtrec.rm_offset)) {
0948         /*
0949          * right edge contiguous, merge into right record.
0950          *
0951          *                 gtbno     gtlen
0952          * Orig:             |ooooooooo|
0953          * adding: |aaaaaaaaa|
0954          * Result: |rrrrrrrrrrrrrrrrrrr|
0955          *        bno       len
0956          */
0957         gtrec.rm_startblock = bno;
0958         gtrec.rm_blockcount += len;
0959         if (!ignore_off)
0960             gtrec.rm_offset = offset;
0961         error = xfs_rmap_update(cur, &gtrec);
0962         if (error)
0963             goto out_error;
0964     } else {
0965         /*
0966          * no contiguous edge with identical owner, insert
0967          * new record at current cursor position.
0968          */
0969         cur->bc_rec.r.rm_startblock = bno;
0970         cur->bc_rec.r.rm_blockcount = len;
0971         cur->bc_rec.r.rm_owner = owner;
0972         cur->bc_rec.r.rm_offset = offset;
0973         cur->bc_rec.r.rm_flags = flags;
0974         trace_xfs_rmap_insert(mp, cur->bc_ag.pag->pag_agno, bno, len,
0975             owner, offset, flags);
0976         error = xfs_btree_insert(cur, &i);
0977         if (error)
0978             goto out_error;
0979         if (XFS_IS_CORRUPT(mp, i != 1)) {
0980             error = -EFSCORRUPTED;
0981             goto out_error;
0982         }
0983     }
0984
0985     trace_xfs_rmap_map_done(mp, cur->bc_ag.pag->pag_agno, bno, len,
0986             unwritten, oinfo);
0987 out_error:
0988     if (error)
0989         trace_xfs_rmap_map_error(mp, cur->bc_ag.pag->pag_agno,
0990                 error, _RET_IP_);
0991     return error;
0992 }
0993
0994 /*
0995  * Add a reference to an extent in the rmap btree.
0996  */
0997 int
0998 xfs_rmap_alloc(
0999     struct xfs_trans        *tp,
1000     struct xfs_buf          *agbp,
1001     struct xfs_perag        *pag,
1002     xfs_agblock_t           bno,
1003     xfs_extlen_t            len,
1004     const struct xfs_owner_info *oinfo)
1005 {
1006     struct xfs_mount        *mp = tp->t_mountp;
1007     struct xfs_btree_cur        *cur;
1008     int             error;
1009
1010     if (!xfs_has_rmapbt(mp))
1011         return 0;
1012
1013     cur = xfs_rmapbt_init_cursor(mp, tp, agbp, pag);
1014     error = xfs_rmap_map(cur, bno, len, false, oinfo);
1015
1016     xfs_btree_del_cursor(cur, error);
1017     return error;
1018 }
1019
1020 #define RMAP_LEFT_CONTIG    (1 << 0)
1021 #define RMAP_RIGHT_CONTIG   (1 << 1)
1022 #define RMAP_LEFT_FILLING   (1 << 2)
1023 #define RMAP_RIGHT_FILLING  (1 << 3)
1024 #define RMAP_LEFT_VALID     (1 << 6)
1025 #define RMAP_RIGHT_VALID    (1 << 7)
1026
1027 #define LEFT        r[0]
1028 #define RIGHT       r[1]
1029 #define PREV        r[2]
1030 #define NEW     r[3]
1031
1032 /*
1033  * Convert an unwritten extent to a real extent or vice versa.
1034  * Does not handle overlapping extents.
1035  */
1036 STATIC int
1037 xfs_rmap_convert(
1038     struct xfs_btree_cur        *cur,
1039     xfs_agblock_t           bno,
1040     xfs_extlen_t            len,
1041     bool                unwritten,
1042     const struct xfs_owner_info *oinfo)
1043 {
1044     struct xfs_mount        *mp = cur->bc_mp;
1045     struct xfs_rmap_irec        r[4];   /* neighbor extent entries */
1046                         /* left is 0, right is 1, */
1047                         /* prev is 2, new is 3 */
1048     uint64_t        owner;
1049     uint64_t        offset;
1050     uint64_t        new_endoff;
1051     unsigned int        oldext;
1052     unsigned int        newext;
1053     unsigned int        flags = 0;
1054     int         i;
1055     int         state = 0;
1056     int         error;
1057
1058     xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
1059     ASSERT(!(XFS_RMAP_NON_INODE_OWNER(owner) ||
1060             (flags & (XFS_RMAP_ATTR_FORK | XFS_RMAP_BMBT_BLOCK))));
1061     oldext = unwritten ? XFS_RMAP_UNWRITTEN : 0;
1062     new_endoff = offset + len;
1063     trace_xfs_rmap_convert(mp, cur->bc_ag.pag->pag_agno, bno, len,
1064             unwritten, oinfo);
1065
1066     /*
1067      * For the initial lookup, look for an exact match or the left-adjacent
1068      * record for our insertion point. This will also give us the record for
1069      * start block contiguity tests.
1070      */
1071     error = xfs_rmap_lookup_le(cur, bno, owner, offset, oldext, &PREV, &i);
1072     if (error)
1073         goto done;
1074     if (XFS_IS_CORRUPT(mp, i != 1)) {
1075         error = -EFSCORRUPTED;
1076         goto done;
1077     }
1078
1079     trace_xfs_rmap_lookup_le_range_result(cur->bc_mp,
1080             cur->bc_ag.pag->pag_agno, PREV.rm_startblock,
1081             PREV.rm_blockcount, PREV.rm_owner,
1082             PREV.rm_offset, PREV.rm_flags);
1083
1084     ASSERT(PREV.rm_offset <= offset);
1085     ASSERT(PREV.rm_offset + PREV.rm_blockcount >= new_endoff);
1086     ASSERT((PREV.rm_flags & XFS_RMAP_UNWRITTEN) == oldext);
1087     newext = ~oldext & XFS_RMAP_UNWRITTEN;
1088
1089     /*
1090      * Set flags determining what part of the previous oldext allocation
1091      * extent is being replaced by a newext allocation.
1092      */
1093     if (PREV.rm_offset == offset)
1094         state |= RMAP_LEFT_FILLING;
1095     if (PREV.rm_offset + PREV.rm_blockcount == new_endoff)
1096         state |= RMAP_RIGHT_FILLING;
1097
1098     /*
1099      * Decrement the cursor to see if we have a left-adjacent record to our
1100      * insertion point. This will give us the record for end block
1101      * contiguity tests.
1102      */
1103     error = xfs_btree_decrement(cur, 0, &i);
1104     if (error)
1105         goto done;
1106     if (i) {
1107         state |= RMAP_LEFT_VALID;
1108         error = xfs_rmap_get_rec(cur, &LEFT, &i);
1109         if (error)
1110             goto done;
1111         if (XFS_IS_CORRUPT(mp, i != 1)) {
1112             error = -EFSCORRUPTED;
1113             goto done;
1114         }
1115         if (XFS_IS_CORRUPT(mp,
1116                    LEFT.rm_startblock + LEFT.rm_blockcount >
1117                    bno)) {
1118             error = -EFSCORRUPTED;
1119             goto done;
1120         }
1121         trace_xfs_rmap_find_left_neighbor_result(cur->bc_mp,
1122                 cur->bc_ag.pag->pag_agno, LEFT.rm_startblock,
1123                 LEFT.rm_blockcount, LEFT.rm_owner,
1124                 LEFT.rm_offset, LEFT.rm_flags);
1125         if (LEFT.rm_startblock + LEFT.rm_blockcount == bno &&
1126             LEFT.rm_offset + LEFT.rm_blockcount == offset &&
1127             xfs_rmap_is_mergeable(&LEFT, owner, newext))
1128             state |= RMAP_LEFT_CONTIG;
1129     }
1130
1131     /*
1132      * Increment the cursor to see if we have a right-adjacent record to our
1133      * insertion point. This will give us the record for end block
1134      * contiguity tests.
1135      */
1136     error = xfs_btree_increment(cur, 0, &i);
1137     if (error)
1138         goto done;
1139     if (XFS_IS_CORRUPT(mp, i != 1)) {
1140         error = -EFSCORRUPTED;
1141         goto done;
1142     }
1143     error = xfs_btree_increment(cur, 0, &i);
1144     if (error)
1145         goto done;
1146     if (i) {
1147         state |= RMAP_RIGHT_VALID;
1148         error = xfs_rmap_get_rec(cur, &RIGHT, &i);
1149         if (error)
1150             goto done;
1151         if (XFS_IS_CORRUPT(mp, i != 1)) {
1152             error = -EFSCORRUPTED;
1153             goto done;
1154         }
1155         if (XFS_IS_CORRUPT(mp, bno + len > RIGHT.rm_startblock)) {
1156             error = -EFSCORRUPTED;
1157             goto done;
1158         }
1159         trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp,
1160                 cur->bc_ag.pag->pag_agno, RIGHT.rm_startblock,
1161                 RIGHT.rm_blockcount, RIGHT.rm_owner,
1162                 RIGHT.rm_offset, RIGHT.rm_flags);
1163         if (bno + len == RIGHT.rm_startblock &&
1164             offset + len == RIGHT.rm_offset &&
1165             xfs_rmap_is_mergeable(&RIGHT, owner, newext))
1166             state |= RMAP_RIGHT_CONTIG;
1167     }
1168
1169     /* check that left + prev + right is not too long */
1170     if ((state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1171              RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) ==
1172         (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1173          RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG) &&
1174         (unsigned long)LEFT.rm_blockcount + len +
1175          RIGHT.rm_blockcount > XFS_RMAP_LEN_MAX)
1176         state &= ~RMAP_RIGHT_CONTIG;
1177
1178     trace_xfs_rmap_convert_state(mp, cur->bc_ag.pag->pag_agno, state,
1179             _RET_IP_);
1180
1181     /* reset the cursor back to PREV */
1182     error = xfs_rmap_lookup_le(cur, bno, owner, offset, oldext, NULL, &i);
1183     if (error)
1184         goto done;
1185     if (XFS_IS_CORRUPT(mp, i != 1)) {
1186         error = -EFSCORRUPTED;
1187         goto done;
1188     }
1189
1190     /*
1191      * Switch out based on the FILLING and CONTIG state bits.
1192      */
1193     switch (state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1194              RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) {
1195     case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1196          RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1197         /*
1198          * Setting all of a previous oldext extent to newext.
1199          * The left and right neighbors are both contiguous with new.
1200          */
1201         error = xfs_btree_increment(cur, 0, &i);
1202         if (error)
1203             goto done;
1204         if (XFS_IS_CORRUPT(mp, i != 1)) {
1205             error = -EFSCORRUPTED;
1206             goto done;
1207         }
1208         trace_xfs_rmap_delete(mp, cur->bc_ag.pag->pag_agno,
1209                 RIGHT.rm_startblock, RIGHT.rm_blockcount,
1210                 RIGHT.rm_owner, RIGHT.rm_offset,
1211                 RIGHT.rm_flags);
1212         error = xfs_btree_delete(cur, &i);
1213         if (error)
1214             goto done;
1215         if (XFS_IS_CORRUPT(mp, i != 1)) {
1216             error = -EFSCORRUPTED;
1217             goto done;
1218         }
1219         error = xfs_btree_decrement(cur, 0, &i);
1220         if (error)
1221             goto done;
1222         if (XFS_IS_CORRUPT(mp, i != 1)) {
1223             error = -EFSCORRUPTED;
1224             goto done;
1225         }
1226         trace_xfs_rmap_delete(mp, cur->bc_ag.pag->pag_agno,
1227                 PREV.rm_startblock, PREV.rm_blockcount,
1228                 PREV.rm_owner, PREV.rm_offset,
1229                 PREV.rm_flags);
1230         error = xfs_btree_delete(cur, &i);
1231         if (error)
1232             goto done;
1233         if (XFS_IS_CORRUPT(mp, i != 1)) {
1234             error = -EFSCORRUPTED;
1235             goto done;
1236         }
1237         error = xfs_btree_decrement(cur, 0, &i);
1238         if (error)
1239             goto done;
1240         if (XFS_IS_CORRUPT(mp, i != 1)) {
1241             error = -EFSCORRUPTED;
1242             goto done;
1243         }
1244         NEW = LEFT;
1245         NEW.rm_blockcount += PREV.rm_blockcount + RIGHT.rm_blockcount;
1246         error = xfs_rmap_update(cur, &NEW);
1247         if (error)
1248             goto done;
1249         break;
1250
1251     case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG:
1252         /*
1253          * Setting all of a previous oldext extent to newext.
1254          * The left neighbor is contiguous, the right is not.
1255          */
1256         trace_xfs_rmap_delete(mp, cur->bc_ag.pag->pag_agno,
1257                 PREV.rm_startblock, PREV.rm_blockcount,
1258                 PREV.rm_owner, PREV.rm_offset,
1259                 PREV.rm_flags);
1260         error = xfs_btree_delete(cur, &i);
1261         if (error)
1262             goto done;
1263         if (XFS_IS_CORRUPT(mp, i != 1)) {
1264             error = -EFSCORRUPTED;
1265             goto done;
1266         }
1267         error = xfs_btree_decrement(cur, 0, &i);
1268         if (error)
1269             goto done;
1270         if (XFS_IS_CORRUPT(mp, i != 1)) {
1271             error = -EFSCORRUPTED;
1272             goto done;
1273         }
1274         NEW = LEFT;
1275         NEW.rm_blockcount += PREV.rm_blockcount;
1276         error = xfs_rmap_update(cur, &NEW);
1277         if (error)
1278             goto done;
1279         break;
1280
1281     case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1282         /*
1283          * Setting all of a previous oldext extent to newext.
1284          * The right neighbor is contiguous, the left is not.
1285          */
1286         error = xfs_btree_increment(cur, 0, &i);
1287         if (error)
1288             goto done;
1289         if (XFS_IS_CORRUPT(mp, i != 1)) {
1290             error = -EFSCORRUPTED;
1291             goto done;
1292         }
1293         trace_xfs_rmap_delete(mp, cur->bc_ag.pag->pag_agno,
1294                 RIGHT.rm_startblock, RIGHT.rm_blockcount,
1295                 RIGHT.rm_owner, RIGHT.rm_offset,
1296                 RIGHT.rm_flags);
1297         error = xfs_btree_delete(cur, &i);
1298         if (error)
1299             goto done;
1300         if (XFS_IS_CORRUPT(mp, i != 1)) {
1301             error = -EFSCORRUPTED;
1302             goto done;
1303         }
1304         error = xfs_btree_decrement(cur, 0, &i);
1305         if (error)
1306             goto done;
1307         if (XFS_IS_CORRUPT(mp, i != 1)) {
1308             error = -EFSCORRUPTED;
1309             goto done;
1310         }
1311         NEW = PREV;
1312         NEW.rm_blockcount = len + RIGHT.rm_blockcount;
1313         NEW.rm_flags = newext;
1314         error = xfs_rmap_update(cur, &NEW);
1315         if (error)
1316             goto done;
1317         break;
1318
1319     case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING:
1320         /*
1321          * Setting all of a previous oldext extent to newext.
1322          * Neither the left nor right neighbors are contiguous with
1323          * the new one.
1324          */
1325         NEW = PREV;
1326         NEW.rm_flags = newext;
1327         error = xfs_rmap_update(cur, &NEW);
1328         if (error)
1329             goto done;
1330         break;
1331
1332     case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG:
1333         /*
1334          * Setting the first part of a previous oldext extent to newext.
1335          * The left neighbor is contiguous.
1336          */
1337         NEW = PREV;
1338         NEW.rm_offset += len;
1339         NEW.rm_startblock += len;
1340         NEW.rm_blockcount -= len;
1341         error = xfs_rmap_update(cur, &NEW);
1342         if (error)
1343             goto done;
1344         error = xfs_btree_decrement(cur, 0, &i);
1345         if (error)
1346             goto done;
1347         NEW = LEFT;
1348         NEW.rm_blockcount += len;
1349         error = xfs_rmap_update(cur, &NEW);
1350         if (error)
1351             goto done;
1352         break;
1353
1354     case RMAP_LEFT_FILLING:
1355         /*
1356          * Setting the first part of a previous oldext extent to newext.
1357          * The left neighbor is not contiguous.
1358          */
1359         NEW = PREV;
1360         NEW.rm_startblock += len;
1361         NEW.rm_offset += len;
1362         NEW.rm_blockcount -= len;
1363         error = xfs_rmap_update(cur, &NEW);
1364         if (error)
1365             goto done;
1366         NEW.rm_startblock = bno;
1367         NEW.rm_owner = owner;
1368         NEW.rm_offset = offset;
1369         NEW.rm_blockcount = len;
1370         NEW.rm_flags = newext;
1371         cur->bc_rec.r = NEW;
1372         trace_xfs_rmap_insert(mp, cur->bc_ag.pag->pag_agno, bno,
1373                 len, owner, offset, newext);
1374         error = xfs_btree_insert(cur, &i);
1375         if (error)
1376             goto done;
1377         if (XFS_IS_CORRUPT(mp, i != 1)) {
1378             error = -EFSCORRUPTED;
1379             goto done;
1380         }
1381         break;
1382
1383     case RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1384         /*
1385          * Setting the last part of a previous oldext extent to newext.
1386          * The right neighbor is contiguous with the new allocation.
1387          */
1388         NEW = PREV;
1389         NEW.rm_blockcount -= len;
1390         error = xfs_rmap_update(cur, &NEW);
1391         if (error)
1392             goto done;
1393         error = xfs_btree_increment(cur, 0, &i);
1394         if (error)
1395             goto done;
1396         NEW = RIGHT;
1397         NEW.rm_offset = offset;
1398         NEW.rm_startblock = bno;
1399         NEW.rm_blockcount += len;
1400         error = xfs_rmap_update(cur, &NEW);
1401         if (error)
1402             goto done;
1403         break;
1404
1405     case RMAP_RIGHT_FILLING:
1406         /*
1407          * Setting the last part of a previous oldext extent to newext.
1408          * The right neighbor is not contiguous.
1409          */
1410         NEW = PREV;
1411         NEW.rm_blockcount -= len;
1412         error = xfs_rmap_update(cur, &NEW);
1413         if (error)
1414             goto done;
1415         error = xfs_rmap_lookup_eq(cur, bno, len, owner, offset,
1416                 oldext, &i);
1417         if (error)
1418             goto done;
1419         if (XFS_IS_CORRUPT(mp, i != 0)) {
1420             error = -EFSCORRUPTED;
1421             goto done;
1422         }
1423         NEW.rm_startblock = bno;
1424         NEW.rm_owner = owner;
1425         NEW.rm_offset = offset;
1426         NEW.rm_blockcount = len;
1427         NEW.rm_flags = newext;
1428         cur->bc_rec.r = NEW;
1429         trace_xfs_rmap_insert(mp, cur->bc_ag.pag->pag_agno, bno,
1430                 len, owner, offset, newext);
1431         error = xfs_btree_insert(cur, &i);
1432         if (error)
1433             goto done;
1434         if (XFS_IS_CORRUPT(mp, i != 1)) {
1435             error = -EFSCORRUPTED;
1436             goto done;
1437         }
1438         break;
1439
1440     case 0:
1441         /*
1442          * Setting the middle part of a previous oldext extent to
1443          * newext.  Contiguity is impossible here.
1444          * One extent becomes three extents.
1445          */
1446         /* new right extent - oldext */
1447         NEW.rm_startblock = bno + len;
1448         NEW.rm_owner = owner;
1449         NEW.rm_offset = new_endoff;
1450         NEW.rm_blockcount = PREV.rm_offset + PREV.rm_blockcount -
1451                 new_endoff;
1452         NEW.rm_flags = PREV.rm_flags;
1453         error = xfs_rmap_update(cur, &NEW);
1454         if (error)
1455             goto done;
1456         /* new left extent - oldext */
1457         NEW = PREV;
1458         NEW.rm_blockcount = offset - PREV.rm_offset;
1459         cur->bc_rec.r = NEW;
1460         trace_xfs_rmap_insert(mp, cur->bc_ag.pag->pag_agno,
1461                 NEW.rm_startblock, NEW.rm_blockcount,
1462                 NEW.rm_owner, NEW.rm_offset,
1463                 NEW.rm_flags);
1464         error = xfs_btree_insert(cur, &i);
1465         if (error)
1466             goto done;
1467         if (XFS_IS_CORRUPT(mp, i != 1)) {
1468             error = -EFSCORRUPTED;
1469             goto done;
1470         }
1471         /*
1472          * Reset the cursor to the position of the new extent
1473          * we are about to insert as we can't trust it after
1474          * the previous insert.
1475          */
1476         error = xfs_rmap_lookup_eq(cur, bno, len, owner, offset,
1477                 oldext, &i);
1478         if (error)
1479             goto done;
1480         if (XFS_IS_CORRUPT(mp, i != 0)) {
1481             error = -EFSCORRUPTED;
1482             goto done;
1483         }
1484         /* new middle extent - newext */
1485         cur->bc_rec.r.rm_flags &= ~XFS_RMAP_UNWRITTEN;
1486         cur->bc_rec.r.rm_flags |= newext;
1487         trace_xfs_rmap_insert(mp, cur->bc_ag.pag->pag_agno, bno, len,
1488                 owner, offset, newext);
1489         error = xfs_btree_insert(cur, &i);
1490         if (error)
1491             goto done;
1492         if (XFS_IS_CORRUPT(mp, i != 1)) {
1493             error = -EFSCORRUPTED;
1494             goto done;
1495         }
1496         break;
1497
1498     case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1499     case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1500     case RMAP_LEFT_FILLING | RMAP_RIGHT_CONTIG:
1501     case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG:
1502     case RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1503     case RMAP_LEFT_CONTIG:
1504     case RMAP_RIGHT_CONTIG:
1505         /*
1506          * These cases are all impossible.
1507          */
1508         ASSERT(0);
1509     }
1510
1511     trace_xfs_rmap_convert_done(mp, cur->bc_ag.pag->pag_agno, bno, len,
1512             unwritten, oinfo);
1513 done:
1514     if (error)
1515         trace_xfs_rmap_convert_error(cur->bc_mp,
1516                 cur->bc_ag.pag->pag_agno, error, _RET_IP_);
1517     return error;
1518 }
1519
1520 /*
1521  * Convert an unwritten extent to a real extent or vice versa.  If there is no
1522  * possibility of overlapping extents, delegate to the simpler convert
1523  * function.
1524  */
1525 STATIC int
1526 xfs_rmap_convert_shared(
1527     struct xfs_btree_cur        *cur,
1528     xfs_agblock_t           bno,
1529     xfs_extlen_t            len,
1530     bool                unwritten,
1531     const struct xfs_owner_info *oinfo)
1532 {
1533     struct xfs_mount        *mp = cur->bc_mp;
1534     struct xfs_rmap_irec        r[4];   /* neighbor extent entries */
1535                         /* left is 0, right is 1, */
1536                         /* prev is 2, new is 3 */
1537     uint64_t        owner;
1538     uint64_t        offset;
1539     uint64_t        new_endoff;
1540     unsigned int        oldext;
1541     unsigned int        newext;
1542     unsigned int        flags = 0;
1543     int         i;
1544     int         state = 0;
1545     int         error;
1546
1547     xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
1548     ASSERT(!(XFS_RMAP_NON_INODE_OWNER(owner) ||
1549             (flags & (XFS_RMAP_ATTR_FORK | XFS_RMAP_BMBT_BLOCK))));
1550     oldext = unwritten ? XFS_RMAP_UNWRITTEN : 0;
1551     new_endoff = offset + len;
1552     trace_xfs_rmap_convert(mp, cur->bc_ag.pag->pag_agno, bno, len,
1553             unwritten, oinfo);
1554
1555     /*
1556      * For the initial lookup, look for and exact match or the left-adjacent
1557      * record for our insertion point. This will also give us the record for
1558      * start block contiguity tests.
1559      */
1560     error = xfs_rmap_lookup_le_range(cur, bno, owner, offset, oldext,
1561             &PREV, &i);
1562     if (error)
1563         goto done;
1564     if (XFS_IS_CORRUPT(mp, i != 1)) {
1565         error = -EFSCORRUPTED;
1566         goto done;
1567     }
1568
1569     ASSERT(PREV.rm_offset <= offset);
1570     ASSERT(PREV.rm_offset + PREV.rm_blockcount >= new_endoff);
1571     ASSERT((PREV.rm_flags & XFS_RMAP_UNWRITTEN) == oldext);
1572     newext = ~oldext & XFS_RMAP_UNWRITTEN;
1573
1574     /*
1575      * Set flags determining what part of the previous oldext allocation
1576      * extent is being replaced by a newext allocation.
1577      */
1578     if (PREV.rm_offset == offset)
1579         state |= RMAP_LEFT_FILLING;
1580     if (PREV.rm_offset + PREV.rm_blockcount == new_endoff)
1581         state |= RMAP_RIGHT_FILLING;
1582
1583     /* Is there a left record that abuts our range? */
1584     error = xfs_rmap_find_left_neighbor(cur, bno, owner, offset, newext,
1585             &LEFT, &i);
1586     if (error)
1587         goto done;
1588     if (i) {
1589         state |= RMAP_LEFT_VALID;
1590         if (XFS_IS_CORRUPT(mp,
1591                    LEFT.rm_startblock + LEFT.rm_blockcount >
1592                    bno)) {
1593             error = -EFSCORRUPTED;
1594             goto done;
1595         }
1596         if (xfs_rmap_is_mergeable(&LEFT, owner, newext))
1597             state |= RMAP_LEFT_CONTIG;
1598     }
1599
1600     /* Is there a right record that abuts our range? */
1601     error = xfs_rmap_lookup_eq(cur, bno + len, len, owner, offset + len,
1602             newext, &i);
1603     if (error)
1604         goto done;
1605     if (i) {
1606         state |= RMAP_RIGHT_VALID;
1607         error = xfs_rmap_get_rec(cur, &RIGHT, &i);
1608         if (error)
1609             goto done;
1610         if (XFS_IS_CORRUPT(mp, i != 1)) {
1611             error = -EFSCORRUPTED;
1612             goto done;
1613         }
1614         if (XFS_IS_CORRUPT(mp, bno + len > RIGHT.rm_startblock)) {
1615             error = -EFSCORRUPTED;
1616             goto done;
1617         }
1618         trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp,
1619                 cur->bc_ag.pag->pag_agno, RIGHT.rm_startblock,
1620                 RIGHT.rm_blockcount, RIGHT.rm_owner,
1621                 RIGHT.rm_offset, RIGHT.rm_flags);
1622         if (xfs_rmap_is_mergeable(&RIGHT, owner, newext))
1623             state |= RMAP_RIGHT_CONTIG;
1624     }
1625
1626     /* check that left + prev + right is not too long */
1627     if ((state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1628              RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) ==
1629         (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1630          RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG) &&
1631         (unsigned long)LEFT.rm_blockcount + len +
1632          RIGHT.rm_blockcount > XFS_RMAP_LEN_MAX)
1633         state &= ~RMAP_RIGHT_CONTIG;
1634
1635     trace_xfs_rmap_convert_state(mp, cur->bc_ag.pag->pag_agno, state,
1636             _RET_IP_);
1637     /*
1638      * Switch out based on the FILLING and CONTIG state bits.
1639      */
1640     switch (state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1641              RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) {
1642     case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1643          RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1644         /*
1645          * Setting all of a previous oldext extent to newext.
1646          * The left and right neighbors are both contiguous with new.
1647          */
1648         error = xfs_rmap_delete(cur, RIGHT.rm_startblock,
1649                 RIGHT.rm_blockcount, RIGHT.rm_owner,
1650                 RIGHT.rm_offset, RIGHT.rm_flags);
1651         if (error)
1652             goto done;
1653         error = xfs_rmap_delete(cur, PREV.rm_startblock,
1654                 PREV.rm_blockcount, PREV.rm_owner,
1655                 PREV.rm_offset, PREV.rm_flags);
1656         if (error)
1657             goto done;
1658         NEW = LEFT;
1659         error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1660                 NEW.rm_blockcount, NEW.rm_owner,
1661                 NEW.rm_offset, NEW.rm_flags, &i);
1662         if (error)
1663             goto done;
1664         if (XFS_IS_CORRUPT(mp, i != 1)) {
1665             error = -EFSCORRUPTED;
1666             goto done;
1667         }
1668         NEW.rm_blockcount += PREV.rm_blockcount + RIGHT.rm_blockcount;
1669         error = xfs_rmap_update(cur, &NEW);
1670         if (error)
1671             goto done;
1672         break;
1673
1674     case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG:
1675         /*
1676          * Setting all of a previous oldext extent to newext.
1677          * The left neighbor is contiguous, the right is not.
1678          */
1679         error = xfs_rmap_delete(cur, PREV.rm_startblock,
1680                 PREV.rm_blockcount, PREV.rm_owner,
1681                 PREV.rm_offset, PREV.rm_flags);
1682         if (error)
1683             goto done;
1684         NEW = LEFT;
1685         error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1686                 NEW.rm_blockcount, NEW.rm_owner,
1687                 NEW.rm_offset, NEW.rm_flags, &i);
1688         if (error)
1689             goto done;
1690         if (XFS_IS_CORRUPT(mp, i != 1)) {
1691             error = -EFSCORRUPTED;
1692             goto done;
1693         }
1694         NEW.rm_blockcount += PREV.rm_blockcount;
1695         error = xfs_rmap_update(cur, &NEW);
1696         if (error)
1697             goto done;
1698         break;
1699
1700     case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1701         /*
1702          * Setting all of a previous oldext extent to newext.
1703          * The right neighbor is contiguous, the left is not.
1704          */
1705         error = xfs_rmap_delete(cur, RIGHT.rm_startblock,
1706                 RIGHT.rm_blockcount, RIGHT.rm_owner,
1707                 RIGHT.rm_offset, RIGHT.rm_flags);
1708         if (error)
1709             goto done;
1710         NEW = PREV;
1711         error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1712                 NEW.rm_blockcount, NEW.rm_owner,
1713                 NEW.rm_offset, NEW.rm_flags, &i);
1714         if (error)
1715             goto done;
1716         if (XFS_IS_CORRUPT(mp, i != 1)) {
1717             error = -EFSCORRUPTED;
1718             goto done;
1719         }
1720         NEW.rm_blockcount += RIGHT.rm_blockcount;
1721         NEW.rm_flags = RIGHT.rm_flags;
1722         error = xfs_rmap_update(cur, &NEW);
1723         if (error)
1724             goto done;
1725         break;
1726
1727     case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING:
1728         /*
1729          * Setting all of a previous oldext extent to newext.
1730          * Neither the left nor right neighbors are contiguous with
1731          * the new one.
1732          */
1733         NEW = PREV;
1734         error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1735                 NEW.rm_blockcount, NEW.rm_owner,
1736                 NEW.rm_offset, NEW.rm_flags, &i);
1737         if (error)
1738             goto done;
1739         if (XFS_IS_CORRUPT(mp, i != 1)) {
1740             error = -EFSCORRUPTED;
1741             goto done;
1742         }
1743         NEW.rm_flags = newext;
1744         error = xfs_rmap_update(cur, &NEW);
1745         if (error)
1746             goto done;
1747         break;
1748
1749     case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG:
1750         /*
1751          * Setting the first part of a previous oldext extent to newext.
1752          * The left neighbor is contiguous.
1753          */
1754         NEW = PREV;
1755         error = xfs_rmap_delete(cur, NEW.rm_startblock,
1756                 NEW.rm_blockcount, NEW.rm_owner,
1757                 NEW.rm_offset, NEW.rm_flags);
1758         if (error)
1759             goto done;
1760         NEW.rm_offset += len;
1761         NEW.rm_startblock += len;
1762         NEW.rm_blockcount -= len;
1763         error = xfs_rmap_insert(cur, NEW.rm_startblock,
1764                 NEW.rm_blockcount, NEW.rm_owner,
1765                 NEW.rm_offset, NEW.rm_flags);
1766         if (error)
1767             goto done;
1768         NEW = LEFT;
1769         error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1770                 NEW.rm_blockcount, NEW.rm_owner,
1771                 NEW.rm_offset, NEW.rm_flags, &i);
1772         if (error)
1773             goto done;
1774         if (XFS_IS_CORRUPT(mp, i != 1)) {
1775             error = -EFSCORRUPTED;
1776             goto done;
1777         }
1778         NEW.rm_blockcount += len;
1779         error = xfs_rmap_update(cur, &NEW);
1780         if (error)
1781             goto done;
1782         break;
1783
1784     case RMAP_LEFT_FILLING:
1785         /*
1786          * Setting the first part of a previous oldext extent to newext.
1787          * The left neighbor is not contiguous.
1788          */
1789         NEW = PREV;
1790         error = xfs_rmap_delete(cur, NEW.rm_startblock,
1791                 NEW.rm_blockcount, NEW.rm_owner,
1792                 NEW.rm_offset, NEW.rm_flags);
1793         if (error)
1794             goto done;
1795         NEW.rm_offset += len;
1796         NEW.rm_startblock += len;
1797         NEW.rm_blockcount -= len;
1798         error = xfs_rmap_insert(cur, NEW.rm_startblock,
1799                 NEW.rm_blockcount, NEW.rm_owner,
1800                 NEW.rm_offset, NEW.rm_flags);
1801         if (error)
1802             goto done;
1803         error = xfs_rmap_insert(cur, bno, len, owner, offset, newext);
1804         if (error)
1805             goto done;
1806         break;
1807
1808     case RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1809         /*
1810          * Setting the last part of a previous oldext extent to newext.
1811          * The right neighbor is contiguous with the new allocation.
1812          */
1813         NEW = PREV;
1814         error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1815                 NEW.rm_blockcount, NEW.rm_owner,
1816                 NEW.rm_offset, NEW.rm_flags, &i);
1817         if (error)
1818             goto done;
1819         if (XFS_IS_CORRUPT(mp, i != 1)) {
1820             error = -EFSCORRUPTED;
1821             goto done;
1822         }
1823         NEW.rm_blockcount = offset - NEW.rm_offset;
1824         error = xfs_rmap_update(cur, &NEW);
1825         if (error)
1826             goto done;
1827         NEW = RIGHT;
1828         error = xfs_rmap_delete(cur, NEW.rm_startblock,
1829                 NEW.rm_blockcount, NEW.rm_owner,
1830                 NEW.rm_offset, NEW.rm_flags);
1831         if (error)
1832             goto done;
1833         NEW.rm_offset = offset;
1834         NEW.rm_startblock = bno;
1835         NEW.rm_blockcount += len;
1836         error = xfs_rmap_insert(cur, NEW.rm_startblock,
1837                 NEW.rm_blockcount, NEW.rm_owner,
1838                 NEW.rm_offset, NEW.rm_flags);
1839         if (error)
1840             goto done;
1841         break;
1842
1843     case RMAP_RIGHT_FILLING:
1844         /*
1845          * Setting the last part of a previous oldext extent to newext.
1846          * The right neighbor is not contiguous.
1847          */
1848         NEW = PREV;
1849         error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1850                 NEW.rm_blockcount, NEW.rm_owner,
1851                 NEW.rm_offset, NEW.rm_flags, &i);
1852         if (error)
1853             goto done;
1854         if (XFS_IS_CORRUPT(mp, i != 1)) {
1855             error = -EFSCORRUPTED;
1856             goto done;
1857         }
1858         NEW.rm_blockcount -= len;
1859         error = xfs_rmap_update(cur, &NEW);
1860         if (error)
1861             goto done;
1862         error = xfs_rmap_insert(cur, bno, len, owner, offset, newext);
1863         if (error)
1864             goto done;
1865         break;
1866
1867     case 0:
1868         /*
1869          * Setting the middle part of a previous oldext extent to
1870          * newext.  Contiguity is impossible here.
1871          * One extent becomes three extents.
1872          */
1873         /* new right extent - oldext */
1874         NEW.rm_startblock = bno + len;
1875         NEW.rm_owner = owner;
1876         NEW.rm_offset = new_endoff;
1877         NEW.rm_blockcount = PREV.rm_offset + PREV.rm_blockcount -
1878                 new_endoff;
1879         NEW.rm_flags = PREV.rm_flags;
1880         error = xfs_rmap_insert(cur, NEW.rm_startblock,
1881                 NEW.rm_blockcount, NEW.rm_owner, NEW.rm_offset,
1882                 NEW.rm_flags);
1883         if (error)
1884             goto done;
1885         /* new left extent - oldext */
1886         NEW = PREV;
1887         error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1888                 NEW.rm_blockcount, NEW.rm_owner,
1889                 NEW.rm_offset, NEW.rm_flags, &i);
1890         if (error)
1891             goto done;
1892         if (XFS_IS_CORRUPT(mp, i != 1)) {
1893             error = -EFSCORRUPTED;
1894             goto done;
1895         }
1896         NEW.rm_blockcount = offset - NEW.rm_offset;
1897         error = xfs_rmap_update(cur, &NEW);
1898         if (error)
1899             goto done;
1900         /* new middle extent - newext */
1901         NEW.rm_startblock = bno;
1902         NEW.rm_blockcount = len;
1903         NEW.rm_owner = owner;
1904         NEW.rm_offset = offset;
1905         NEW.rm_flags = newext;
1906         error = xfs_rmap_insert(cur, NEW.rm_startblock,
1907                 NEW.rm_blockcount, NEW.rm_owner, NEW.rm_offset,
1908                 NEW.rm_flags);
1909         if (error)
1910             goto done;
1911         break;
1912
1913     case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1914     case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1915     case RMAP_LEFT_FILLING | RMAP_RIGHT_CONTIG:
1916     case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG:
1917     case RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1918     case RMAP_LEFT_CONTIG:
1919     case RMAP_RIGHT_CONTIG:
1920         /*
1921          * These cases are all impossible.
1922          */
1923         ASSERT(0);
1924     }
1925
1926     trace_xfs_rmap_convert_done(mp, cur->bc_ag.pag->pag_agno, bno, len,
1927             unwritten, oinfo);
1928 done:
1929     if (error)
1930         trace_xfs_rmap_convert_error(cur->bc_mp,
1931                 cur->bc_ag.pag->pag_agno, error, _RET_IP_);
1932     return error;
1933 }
1934
1935 #undef  NEW
1936 #undef  LEFT
1937 #undef  RIGHT
1938 #undef  PREV
1939
1940 /*
1941  * Find an extent in the rmap btree and unmap it.  For rmap extent types that
1942  * can overlap (data fork rmaps on reflink filesystems) we must be careful
1943  * that the prev/next records in the btree might belong to another owner.
1944  * Therefore we must use delete+insert to alter any of the key fields.
1945  *
1946  * For every other situation there can only be one owner for a given extent,
1947  * so we can call the regular _free function.
1948  */
1949 STATIC int
1950 xfs_rmap_unmap_shared(
1951     struct xfs_btree_cur        *cur,
1952     xfs_agblock_t           bno,
1953     xfs_extlen_t            len,
1954     bool                unwritten,
1955     const struct xfs_owner_info *oinfo)
1956 {
1957     struct xfs_mount        *mp = cur->bc_mp;
1958     struct xfs_rmap_irec        ltrec;
1959     uint64_t            ltoff;
1960     int             error = 0;
1961     int             i;
1962     uint64_t            owner;
1963     uint64_t            offset;
1964     unsigned int            flags;
1965
1966     xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
1967     if (unwritten)
1968         flags |= XFS_RMAP_UNWRITTEN;
1969     trace_xfs_rmap_unmap(mp, cur->bc_ag.pag->pag_agno, bno, len,
1970             unwritten, oinfo);
1971
1972     /*
1973      * We should always have a left record because there's a static record
1974      * for the AG headers at rm_startblock == 0 created by mkfs/growfs that
1975      * will not ever be removed from the tree.
1976      */
1977     error = xfs_rmap_lookup_le_range(cur, bno, owner, offset, flags,
1978             &ltrec, &i);
1979     if (error)
1980         goto out_error;
1981     if (XFS_IS_CORRUPT(mp, i != 1)) {
1982         error = -EFSCORRUPTED;
1983         goto out_error;
1984     }
1985     ltoff = ltrec.rm_offset;
1986
1987     /* Make sure the extent we found covers the entire freeing range. */
1988     if (XFS_IS_CORRUPT(mp,
1989                ltrec.rm_startblock > bno ||
1990                ltrec.rm_startblock + ltrec.rm_blockcount <
1991                bno + len)) {
1992         error = -EFSCORRUPTED;
1993         goto out_error;
1994     }
1995
1996     /* Make sure the owner matches what we expect to find in the tree. */
1997     if (XFS_IS_CORRUPT(mp, owner != ltrec.rm_owner)) {
1998         error = -EFSCORRUPTED;
1999         goto out_error;
2000     }
2001
2002     /* Make sure the unwritten flag matches. */
2003     if (XFS_IS_CORRUPT(mp,
2004                (flags & XFS_RMAP_UNWRITTEN) !=
2005                (ltrec.rm_flags & XFS_RMAP_UNWRITTEN))) {
2006         error = -EFSCORRUPTED;
2007         goto out_error;
2008     }
2009
2010     /* Check the offset. */
2011     if (XFS_IS_CORRUPT(mp, ltrec.rm_offset > offset)) {
2012         error = -EFSCORRUPTED;
2013         goto out_error;
2014     }
2015     if (XFS_IS_CORRUPT(mp, offset > ltoff + ltrec.rm_blockcount)) {
2016         error = -EFSCORRUPTED;
2017         goto out_error;
2018     }
2019
2020     if (ltrec.rm_startblock == bno && ltrec.rm_blockcount == len) {
2021         /* Exact match, simply remove the record from rmap tree. */
2022         error = xfs_rmap_delete(cur, ltrec.rm_startblock,
2023                 ltrec.rm_blockcount, ltrec.rm_owner,
2024                 ltrec.rm_offset, ltrec.rm_flags);
2025         if (error)
2026             goto out_error;
2027     } else if (ltrec.rm_startblock == bno) {
2028         /*
2029          * Overlap left hand side of extent: move the start, trim the
2030          * length and update the current record.
2031          *
2032          *       ltbno                ltlen
2033          * Orig:    |oooooooooooooooooooo|
2034          * Freeing: |fffffffff|
2035          * Result:            |rrrrrrrrrr|
2036          *         bno       len
2037          */
2038
2039         /* Delete prev rmap. */
2040         error = xfs_rmap_delete(cur, ltrec.rm_startblock,
2041                 ltrec.rm_blockcount, ltrec.rm_owner,
2042                 ltrec.rm_offset, ltrec.rm_flags);
2043         if (error)
2044             goto out_error;
2045
2046         /* Add an rmap at the new offset. */
2047         ltrec.rm_startblock += len;
2048         ltrec.rm_blockcount -= len;
2049         ltrec.rm_offset += len;
2050         error = xfs_rmap_insert(cur, ltrec.rm_startblock,
2051                 ltrec.rm_blockcount, ltrec.rm_owner,
2052                 ltrec.rm_offset, ltrec.rm_flags);
2053         if (error)
2054             goto out_error;
2055     } else if (ltrec.rm_startblock + ltrec.rm_blockcount == bno + len) {
2056         /*
2057          * Overlap right hand side of extent: trim the length and
2058          * update the current record.
2059          *
2060          *       ltbno                ltlen
2061          * Orig:    |oooooooooooooooooooo|
2062          * Freeing:            |fffffffff|
2063          * Result:  |rrrrrrrrrr|
2064          *                    bno       len
2065          */
2066         error = xfs_rmap_lookup_eq(cur, ltrec.rm_startblock,
2067                 ltrec.rm_blockcount, ltrec.rm_owner,
2068                 ltrec.rm_offset, ltrec.rm_flags, &i);
2069         if (error)
2070             goto out_error;
2071         if (XFS_IS_CORRUPT(mp, i != 1)) {
2072             error = -EFSCORRUPTED;
2073             goto out_error;
2074         }
2075         ltrec.rm_blockcount -= len;
2076         error = xfs_rmap_update(cur, &ltrec);
2077         if (error)
2078             goto out_error;
2079     } else {
2080         /*
2081          * Overlap middle of extent: trim the length of the existing
2082          * record to the length of the new left-extent size, increment
2083          * the insertion position so we can insert a new record
2084          * containing the remaining right-extent space.
2085          *
2086          *       ltbno                ltlen
2087          * Orig:    |oooooooooooooooooooo|
2088          * Freeing:       |fffffffff|
2089          * Result:  |rrrrr|         |rrrr|
2090          *               bno       len
2091          */
2092         xfs_extlen_t    orig_len = ltrec.rm_blockcount;
2093
2094         /* Shrink the left side of the rmap */
2095         error = xfs_rmap_lookup_eq(cur, ltrec.rm_startblock,
2096                 ltrec.rm_blockcount, ltrec.rm_owner,
2097                 ltrec.rm_offset, ltrec.rm_flags, &i);
2098         if (error)
2099             goto out_error;
2100         if (XFS_IS_CORRUPT(mp, i != 1)) {
2101             error = -EFSCORRUPTED;
2102             goto out_error;
2103         }
2104         ltrec.rm_blockcount = bno - ltrec.rm_startblock;
2105         error = xfs_rmap_update(cur, &ltrec);
2106         if (error)
2107             goto out_error;
2108
2109         /* Add an rmap at the new offset */
2110         error = xfs_rmap_insert(cur, bno + len,
2111                 orig_len - len - ltrec.rm_blockcount,
2112                 ltrec.rm_owner, offset + len,
2113                 ltrec.rm_flags);
2114         if (error)
2115             goto out_error;
2116     }
2117
2118     trace_xfs_rmap_unmap_done(mp, cur->bc_ag.pag->pag_agno, bno, len,
2119             unwritten, oinfo);
2120 out_error:
2121     if (error)
2122         trace_xfs_rmap_unmap_error(cur->bc_mp,
2123                 cur->bc_ag.pag->pag_agno, error, _RET_IP_);
2124     return error;
2125 }
2126
2127 /*
2128  * Find an extent in the rmap btree and map it.  For rmap extent types that
2129  * can overlap (data fork rmaps on reflink filesystems) we must be careful
2130  * that the prev/next records in the btree might belong to another owner.
2131  * Therefore we must use delete+insert to alter any of the key fields.
2132  *
2133  * For every other situation there can only be one owner for a given extent,
2134  * so we can call the regular _alloc function.
2135  */
2136 STATIC int
2137 xfs_rmap_map_shared(
2138     struct xfs_btree_cur        *cur,
2139     xfs_agblock_t           bno,
2140     xfs_extlen_t            len,
2141     bool                unwritten,
2142     const struct xfs_owner_info *oinfo)
2143 {
2144     struct xfs_mount        *mp = cur->bc_mp;
2145     struct xfs_rmap_irec        ltrec;
2146     struct xfs_rmap_irec        gtrec;
2147     int             have_gt;
2148     int             have_lt;
2149     int             error = 0;
2150     int             i;
2151     uint64_t            owner;
2152     uint64_t            offset;
2153     unsigned int            flags = 0;
2154
2155     xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
2156     if (unwritten)
2157         flags |= XFS_RMAP_UNWRITTEN;
2158     trace_xfs_rmap_map(mp, cur->bc_ag.pag->pag_agno, bno, len,
2159             unwritten, oinfo);
2160
2161     /* Is there a left record that abuts our range? */
2162     error = xfs_rmap_find_left_neighbor(cur, bno, owner, offset, flags,
2163             &ltrec, &have_lt);
2164     if (error)
2165         goto out_error;
2166     if (have_lt &&
2167         !xfs_rmap_is_mergeable(&ltrec, owner, flags))
2168         have_lt = 0;
2169
2170     /* Is there a right record that abuts our range? */
2171     error = xfs_rmap_lookup_eq(cur, bno + len, len, owner, offset + len,
2172             flags, &have_gt);
2173     if (error)
2174         goto out_error;
2175     if (have_gt) {
2176         error = xfs_rmap_get_rec(cur, &gtrec, &have_gt);
2177         if (error)
2178             goto out_error;
2179         if (XFS_IS_CORRUPT(mp, have_gt != 1)) {
2180             error = -EFSCORRUPTED;
2181             goto out_error;
2182         }
2183         trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp,
2184             cur->bc_ag.pag->pag_agno, gtrec.rm_startblock,
2185             gtrec.rm_blockcount, gtrec.rm_owner,
2186             gtrec.rm_offset, gtrec.rm_flags);
2187
2188         if (!xfs_rmap_is_mergeable(&gtrec, owner, flags))
2189             have_gt = 0;
2190     }
2191
2192     if (have_lt &&
2193         ltrec.rm_startblock + ltrec.rm_blockcount == bno &&
2194         ltrec.rm_offset + ltrec.rm_blockcount == offset) {
2195         /*
2196          * Left edge contiguous, merge into left record.
2197          *
2198          *       ltbno     ltlen
2199          * orig:   |ooooooooo|
2200          * adding:           |aaaaaaaaa|
2201          * result: |rrrrrrrrrrrrrrrrrrr|
2202          *                  bno       len
2203          */
2204         ltrec.rm_blockcount += len;
2205         if (have_gt &&
2206             bno + len == gtrec.rm_startblock &&
2207             offset + len == gtrec.rm_offset) {
2208             /*
2209              * Right edge also contiguous, delete right record
2210              * and merge into left record.
2211              *
2212              *       ltbno     ltlen    gtbno     gtlen
2213              * orig:   |ooooooooo|         |ooooooooo|
2214              * adding:           |aaaaaaaaa|
2215              * result: |rrrrrrrrrrrrrrrrrrrrrrrrrrrrr|
2216              */
2217             ltrec.rm_blockcount += gtrec.rm_blockcount;
2218             error = xfs_rmap_delete(cur, gtrec.rm_startblock,
2219                     gtrec.rm_blockcount, gtrec.rm_owner,
2220                     gtrec.rm_offset, gtrec.rm_flags);
2221             if (error)
2222                 goto out_error;
2223         }
2224
2225         /* Point the cursor back to the left record and update. */
2226         error = xfs_rmap_lookup_eq(cur, ltrec.rm_startblock,
2227                 ltrec.rm_blockcount, ltrec.rm_owner,
2228                 ltrec.rm_offset, ltrec.rm_flags, &i);
2229         if (error)
2230             goto out_error;
2231         if (XFS_IS_CORRUPT(mp, i != 1)) {
2232             error = -EFSCORRUPTED;
2233             goto out_error;
2234         }
2235
2236         error = xfs_rmap_update(cur, &ltrec);
2237         if (error)
2238             goto out_error;
2239     } else if (have_gt &&
2240            bno + len == gtrec.rm_startblock &&
2241            offset + len == gtrec.rm_offset) {
2242         /*
2243          * Right edge contiguous, merge into right record.
2244          *
2245          *                 gtbno     gtlen
2246          * Orig:             |ooooooooo|
2247          * adding: |aaaaaaaaa|
2248          * Result: |rrrrrrrrrrrrrrrrrrr|
2249          *        bno       len
2250          */
2251         /* Delete the old record. */
2252         error = xfs_rmap_delete(cur, gtrec.rm_startblock,
2253                 gtrec.rm_blockcount, gtrec.rm_owner,
2254                 gtrec.rm_offset, gtrec.rm_flags);
2255         if (error)
2256             goto out_error;
2257
2258         /* Move the start and re-add it. */
2259         gtrec.rm_startblock = bno;
2260         gtrec.rm_blockcount += len;
2261         gtrec.rm_offset = offset;
2262         error = xfs_rmap_insert(cur, gtrec.rm_startblock,
2263                 gtrec.rm_blockcount, gtrec.rm_owner,
2264                 gtrec.rm_offset, gtrec.rm_flags);
2265         if (error)
2266             goto out_error;
2267     } else {
2268         /*
2269          * No contiguous edge with identical owner, insert
2270          * new record at current cursor position.
2271          */
2272         error = xfs_rmap_insert(cur, bno, len, owner, offset, flags);
2273         if (error)
2274             goto out_error;
2275     }
2276
2277     trace_xfs_rmap_map_done(mp, cur->bc_ag.pag->pag_agno, bno, len,
2278             unwritten, oinfo);
2279 out_error:
2280     if (error)
2281         trace_xfs_rmap_map_error(cur->bc_mp,
2282                 cur->bc_ag.pag->pag_agno, error, _RET_IP_);
2283     return error;
2284 }
2285
2286 /* Insert a raw rmap into the rmapbt. */
2287 int
2288 xfs_rmap_map_raw(
2289     struct xfs_btree_cur    *cur,
2290     struct xfs_rmap_irec    *rmap)
2291 {
2292     struct xfs_owner_info   oinfo;
2293
2294     oinfo.oi_owner = rmap->rm_owner;
2295     oinfo.oi_offset = rmap->rm_offset;
2296     oinfo.oi_flags = 0;
2297     if (rmap->rm_flags & XFS_RMAP_ATTR_FORK)
2298         oinfo.oi_flags |= XFS_OWNER_INFO_ATTR_FORK;
2299     if (rmap->rm_flags & XFS_RMAP_BMBT_BLOCK)
2300         oinfo.oi_flags |= XFS_OWNER_INFO_BMBT_BLOCK;
2301
2302     if (rmap->rm_flags || XFS_RMAP_NON_INODE_OWNER(rmap->rm_owner))
2303         return xfs_rmap_map(cur, rmap->rm_startblock,
2304                 rmap->rm_blockcount,
2305                 rmap->rm_flags & XFS_RMAP_UNWRITTEN,
2306                 &oinfo);
2307
2308     return xfs_rmap_map_shared(cur, rmap->rm_startblock,
2309             rmap->rm_blockcount,
2310             rmap->rm_flags & XFS_RMAP_UNWRITTEN,
2311             &oinfo);
2312 }
2313
2314 struct xfs_rmap_query_range_info {
2315     xfs_rmap_query_range_fn fn;
2316     void                *priv;
2317 };
2318
2319 /* Format btree record and pass to our callback. */
2320 STATIC int
2321 xfs_rmap_query_range_helper(
2322     struct xfs_btree_cur        *cur,
2323     const union xfs_btree_rec   *rec,
2324     void                *priv)
2325 {
2326     struct xfs_rmap_query_range_info    *query = priv;
2327     struct xfs_rmap_irec            irec;
2328     int                 error;
2329
2330     error = xfs_rmap_btrec_to_irec(rec, &irec);
2331     if (error)
2332         return error;
2333     return query->fn(cur, &irec, query->priv);
2334 }
2335
2336 /* Find all rmaps between two keys. */
2337 int
2338 xfs_rmap_query_range(
2339     struct xfs_btree_cur            *cur,
2340     const struct xfs_rmap_irec      *low_rec,
2341     const struct xfs_rmap_irec      *high_rec,
2342     xfs_rmap_query_range_fn         fn,
2343     void                    *priv)
2344 {
2345     union xfs_btree_irec            low_brec;
2346     union xfs_btree_irec            high_brec;
2347     struct xfs_rmap_query_range_info    query;
2348
2349     low_brec.r = *low_rec;
2350     high_brec.r = *high_rec;
2351     query.priv = priv;
2352     query.fn = fn;
2353     return xfs_btree_query_range(cur, &low_brec, &high_brec,
2354             xfs_rmap_query_range_helper, &query);
2355 }
2356
2357 /* Find all rmaps. */
2358 int
2359 xfs_rmap_query_all(
2360     struct xfs_btree_cur            *cur,
2361     xfs_rmap_query_range_fn         fn,
2362     void                    *priv)
2363 {
2364     struct xfs_rmap_query_range_info    query;
2365
2366     query.priv = priv;
2367     query.fn = fn;
2368     return xfs_btree_query_all(cur, xfs_rmap_query_range_helper, &query);
2369 }
2370
2371 /* Clean up after calling xfs_rmap_finish_one. */
2372 void
2373 xfs_rmap_finish_one_cleanup(
2374     struct xfs_trans    *tp,
2375     struct xfs_btree_cur    *rcur,
2376     int         error)
2377 {
2378     struct xfs_buf      *agbp;
2379
2380     if (rcur == NULL)
2381         return;
2382     agbp = rcur->bc_ag.agbp;
2383     xfs_btree_del_cursor(rcur, error);
2384     if (error)
2385         xfs_trans_brelse(tp, agbp);
2386 }
2387
2388 /*
2389  * Process one of the deferred rmap operations.  We pass back the
2390  * btree cursor to maintain our lock on the rmapbt between calls.
2391  * This saves time and eliminates a buffer deadlock between the
2392  * superblock and the AGF because we'll always grab them in the same
2393  * order.
2394  */
2395 int
2396 xfs_rmap_finish_one(
2397     struct xfs_trans        *tp,
2398     enum xfs_rmap_intent_type   type,
2399     uint64_t            owner,
2400     int             whichfork,
2401     xfs_fileoff_t           startoff,
2402     xfs_fsblock_t           startblock,
2403     xfs_filblks_t           blockcount,
2404     xfs_exntst_t            state,
2405     struct xfs_btree_cur        **pcur)
2406 {
2407     struct xfs_mount        *mp = tp->t_mountp;
2408     struct xfs_perag        *pag;
2409     struct xfs_btree_cur        *rcur;
2410     struct xfs_buf          *agbp = NULL;
2411     int             error = 0;
2412     struct xfs_owner_info       oinfo;
2413     xfs_agblock_t           bno;
2414     bool                unwritten;
2415
2416     pag = xfs_perag_get(mp, XFS_FSB_TO_AGNO(mp, startblock));
2417     bno = XFS_FSB_TO_AGBNO(mp, startblock);
2418
2419     trace_xfs_rmap_deferred(mp, pag->pag_agno, type, bno, owner, whichfork,
2420             startoff, blockcount, state);
2421
2422     if (XFS_TEST_ERROR(false, mp, XFS_ERRTAG_RMAP_FINISH_ONE)) {
2423         error = -EIO;
2424         goto out_drop;
2425     }
2426
2427
2428     /*
2429      * If we haven't gotten a cursor or the cursor AG doesn't match
2430      * the startblock, get one now.
2431      */
2432     rcur = *pcur;
2433     if (rcur != NULL && rcur->bc_ag.pag != pag) {
2434         xfs_rmap_finish_one_cleanup(tp, rcur, 0);
2435         rcur = NULL;
2436         *pcur = NULL;
2437     }
2438     if (rcur == NULL) {
2439         /*
2440          * Refresh the freelist before we start changing the
2441          * rmapbt, because a shape change could cause us to
2442          * allocate blocks.
2443          */
2444         error = xfs_free_extent_fix_freelist(tp, pag, &agbp);
2445         if (error)
2446             goto out_drop;
2447         if (XFS_IS_CORRUPT(tp->t_mountp, !agbp)) {
2448             error = -EFSCORRUPTED;
2449             goto out_drop;
2450         }
2451
2452         rcur = xfs_rmapbt_init_cursor(mp, tp, agbp, pag);
2453     }
2454     *pcur = rcur;
2455
2456     xfs_rmap_ino_owner(&oinfo, owner, whichfork, startoff);
2457     unwritten = state == XFS_EXT_UNWRITTEN;
2458     bno = XFS_FSB_TO_AGBNO(rcur->bc_mp, startblock);
2459
2460     switch (type) {
2461     case XFS_RMAP_ALLOC:
2462     case XFS_RMAP_MAP:
2463         error = xfs_rmap_map(rcur, bno, blockcount, unwritten, &oinfo);
2464         break;
2465     case XFS_RMAP_MAP_SHARED:
2466         error = xfs_rmap_map_shared(rcur, bno, blockcount, unwritten,
2467                 &oinfo);
2468         break;
2469     case XFS_RMAP_FREE:
2470     case XFS_RMAP_UNMAP:
2471         error = xfs_rmap_unmap(rcur, bno, blockcount, unwritten,
2472                 &oinfo);
2473         break;
2474     case XFS_RMAP_UNMAP_SHARED:
2475         error = xfs_rmap_unmap_shared(rcur, bno, blockcount, unwritten,
2476                 &oinfo);
2477         break;
2478     case XFS_RMAP_CONVERT:
2479         error = xfs_rmap_convert(rcur, bno, blockcount, !unwritten,
2480                 &oinfo);
2481         break;
2482     case XFS_RMAP_CONVERT_SHARED:
2483         error = xfs_rmap_convert_shared(rcur, bno, blockcount,
2484                 !unwritten, &oinfo);
2485         break;
2486     default:
2487         ASSERT(0);
2488         error = -EFSCORRUPTED;
2489     }
2490 out_drop:
2491     xfs_perag_put(pag);
2492     return error;
2493 }
2494
2495 /*
2496  * Don't defer an rmap if we aren't an rmap filesystem.
2497  */
2498 static bool
2499 xfs_rmap_update_is_needed(
2500     struct xfs_mount    *mp,
2501     int         whichfork)
2502 {
2503     return xfs_has_rmapbt(mp) && whichfork != XFS_COW_FORK;
2504 }
2505
2506 /*
2507  * Record a rmap intent; the list is kept sorted first by AG and then by
2508  * increasing age.
2509  */
2510 static void
2511 __xfs_rmap_add(
2512     struct xfs_trans        *tp,
2513     enum xfs_rmap_intent_type   type,
2514     uint64_t            owner,
2515     int             whichfork,
2516     struct xfs_bmbt_irec        *bmap)
2517 {
2518     struct xfs_rmap_intent      *ri;
2519
2520     trace_xfs_rmap_defer(tp->t_mountp,
2521             XFS_FSB_TO_AGNO(tp->t_mountp, bmap->br_startblock),
2522             type,
2523             XFS_FSB_TO_AGBNO(tp->t_mountp, bmap->br_startblock),
2524             owner, whichfork,
2525             bmap->br_startoff,
2526             bmap->br_blockcount,
2527             bmap->br_state);
2528
2529     ri = kmem_cache_alloc(xfs_rmap_intent_cache, GFP_NOFS | __GFP_NOFAIL);
2530     INIT_LIST_HEAD(&ri->ri_list);
2531     ri->ri_type = type;
2532     ri->ri_owner = owner;
2533     ri->ri_whichfork = whichfork;
2534     ri->ri_bmap = *bmap;
2535
2536     xfs_defer_add(tp, XFS_DEFER_OPS_TYPE_RMAP, &ri->ri_list);
2537 }
2538
2539 /* Map an extent into a file. */
2540 void
2541 xfs_rmap_map_extent(
2542     struct xfs_trans    *tp,
2543     struct xfs_inode    *ip,
2544     int         whichfork,
2545     struct xfs_bmbt_irec    *PREV)
2546 {
2547     enum xfs_rmap_intent_type type = XFS_RMAP_MAP;
2548
2549     if (!xfs_rmap_update_is_needed(tp->t_mountp, whichfork))
2550         return;
2551
2552     if (whichfork != XFS_ATTR_FORK && xfs_is_reflink_inode(ip))
2553         type = XFS_RMAP_MAP_SHARED;
2554
2555     __xfs_rmap_add(tp, type, ip->i_ino, whichfork, PREV);
2556 }
2557
2558 /* Unmap an extent out of a file. */
2559 void
2560 xfs_rmap_unmap_extent(
2561     struct xfs_trans    *tp,
2562     struct xfs_inode    *ip,
2563     int         whichfork,
2564     struct xfs_bmbt_irec    *PREV)
2565 {
2566     enum xfs_rmap_intent_type type = XFS_RMAP_UNMAP;
2567
2568     if (!xfs_rmap_update_is_needed(tp->t_mountp, whichfork))
2569         return;
2570
2571     if (whichfork != XFS_ATTR_FORK && xfs_is_reflink_inode(ip))
2572         type = XFS_RMAP_UNMAP_SHARED;
2573
2574     __xfs_rmap_add(tp, type, ip->i_ino, whichfork, PREV);
2575 }
2576
2577 /*
2578  * Convert a data fork extent from unwritten to real or vice versa.
2579  *
2580  * Note that tp can be NULL here as no transaction is used for COW fork
2581  * unwritten conversion.
2582  */
2583 void
2584 xfs_rmap_convert_extent(
2585     struct xfs_mount    *mp,
2586     struct xfs_trans    *tp,
2587     struct xfs_inode    *ip,
2588     int         whichfork,
2589     struct xfs_bmbt_irec    *PREV)
2590 {
2591     enum xfs_rmap_intent_type type = XFS_RMAP_CONVERT;
2592
2593     if (!xfs_rmap_update_is_needed(mp, whichfork))
2594         return;
2595
2596     if (whichfork != XFS_ATTR_FORK && xfs_is_reflink_inode(ip))
2597         type = XFS_RMAP_CONVERT_SHARED;
2598
2599     __xfs_rmap_add(tp, type, ip->i_ino, whichfork, PREV);
2600 }
2601
2602 /* Schedule the creation of an rmap for non-file data. */
2603 void
2604 xfs_rmap_alloc_extent(
2605     struct xfs_trans    *tp,
2606     xfs_agnumber_t      agno,
2607     xfs_agblock_t       bno,
2608     xfs_extlen_t        len,
2609     uint64_t        owner)
2610 {
2611     struct xfs_bmbt_irec    bmap;
2612
2613     if (!xfs_rmap_update_is_needed(tp->t_mountp, XFS_DATA_FORK))
2614         return;
2615
2616     bmap.br_startblock = XFS_AGB_TO_FSB(tp->t_mountp, agno, bno);
2617     bmap.br_blockcount = len;
2618     bmap.br_startoff = 0;
2619     bmap.br_state = XFS_EXT_NORM;
2620
2621     __xfs_rmap_add(tp, XFS_RMAP_ALLOC, owner, XFS_DATA_FORK, &bmap);
2622 }
2623
2624 /* Schedule the deletion of an rmap for non-file data. */
2625 void
2626 xfs_rmap_free_extent(
2627     struct xfs_trans    *tp,
2628     xfs_agnumber_t      agno,
2629     xfs_agblock_t       bno,
2630     xfs_extlen_t        len,
2631     uint64_t        owner)
2632 {
2633     struct xfs_bmbt_irec    bmap;
2634
2635     if (!xfs_rmap_update_is_needed(tp->t_mountp, XFS_DATA_FORK))
2636         return;
2637
2638     bmap.br_startblock = XFS_AGB_TO_FSB(tp->t_mountp, agno, bno);
2639     bmap.br_blockcount = len;
2640     bmap.br_startoff = 0;
2641     bmap.br_state = XFS_EXT_NORM;
2642
2643     __xfs_rmap_add(tp, XFS_RMAP_FREE, owner, XFS_DATA_FORK, &bmap);
2644 }
2645
2646 /* Compare rmap records.  Returns -1 if a < b, 1 if a > b, and 0 if equal. */
2647 int
2648 xfs_rmap_compare(
2649     const struct xfs_rmap_irec  *a,
2650     const struct xfs_rmap_irec  *b)
2651 {
2652     __u64               oa;
2653     __u64               ob;
2654
2655     oa = xfs_rmap_irec_offset_pack(a);
2656     ob = xfs_rmap_irec_offset_pack(b);
2657
2658     if (a->rm_startblock < b->rm_startblock)
2659         return -1;
2660     else if (a->rm_startblock > b->rm_startblock)
2661         return 1;
2662     else if (a->rm_owner < b->rm_owner)
2663         return -1;
2664     else if (a->rm_owner > b->rm_owner)
2665         return 1;
2666     else if (oa < ob)
2667         return -1;
2668     else if (oa > ob)
2669         return 1;
2670     else
2671         return 0;
2672 }
2673
2674 /* Is there a record covering a given extent? */
2675 int
2676 xfs_rmap_has_record(
2677     struct xfs_btree_cur    *cur,
2678     xfs_agblock_t       bno,
2679     xfs_extlen_t        len,
2680     bool            *exists)
2681 {
2682     union xfs_btree_irec    low;
2683     union xfs_btree_irec    high;
2684
2685     memset(&low, 0, sizeof(low));
2686     low.r.rm_startblock = bno;
2687     memset(&high, 0xFF, sizeof(high));
2688     high.r.rm_startblock = bno + len - 1;
2689
2690     return xfs_btree_has_record(cur, &low, &high, exists);
2691 }
2692
2693 /*
2694  * Is there a record for this owner completely covering a given physical
2695  * extent?  If so, *has_rmap will be set to true.  If there is no record
2696  * or the record only covers part of the range, we set *has_rmap to false.
2697  * This function doesn't perform range lookups or offset checks, so it is
2698  * not suitable for checking data fork blocks.
2699  */
2700 int
2701 xfs_rmap_record_exists(
2702     struct xfs_btree_cur        *cur,
2703     xfs_agblock_t           bno,
2704     xfs_extlen_t            len,
2705     const struct xfs_owner_info *oinfo,
2706     bool                *has_rmap)
2707 {
2708     uint64_t            owner;
2709     uint64_t            offset;
2710     unsigned int            flags;
2711     int             has_record;
2712     struct xfs_rmap_irec        irec;
2713     int             error;
2714
2715     xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
2716     ASSERT(XFS_RMAP_NON_INODE_OWNER(owner) ||
2717            (flags & XFS_RMAP_BMBT_BLOCK));
2718
2719     error = xfs_rmap_lookup_le(cur, bno, owner, offset, flags, &irec,
2720             &has_record);
2721     if (error)
2722         return error;
2723     if (!has_record) {
2724         *has_rmap = false;
2725         return 0;
2726     }
2727
2728     *has_rmap = (irec.rm_owner == owner && irec.rm_startblock <= bno &&
2729              irec.rm_startblock + irec.rm_blockcount >= bno + len);
2730     return 0;
2731 }
2732
2733 struct xfs_rmap_key_state {
2734     uint64_t            owner;
2735     uint64_t            offset;
2736     unsigned int            flags;
2737 };
2738
2739 /* For each rmap given, figure out if it doesn't match the key we want. */
2740 STATIC int
2741 xfs_rmap_has_other_keys_helper(
2742     struct xfs_btree_cur        *cur,
2743     const struct xfs_rmap_irec  *rec,
2744     void                *priv)
2745 {
2746     struct xfs_rmap_key_state   *rks = priv;
2747
2748     if (rks->owner == rec->rm_owner && rks->offset == rec->rm_offset &&
2749         ((rks->flags & rec->rm_flags) & XFS_RMAP_KEY_FLAGS) == rks->flags)
2750         return 0;
2751     return -ECANCELED;
2752 }
2753
2754 /*
2755  * Given an extent and some owner info, can we find records overlapping
2756  * the extent whose owner info does not match the given owner?
2757  */
2758 int
2759 xfs_rmap_has_other_keys(
2760     struct xfs_btree_cur        *cur,
2761     xfs_agblock_t           bno,
2762     xfs_extlen_t            len,
2763     const struct xfs_owner_info *oinfo,
2764     bool                *has_rmap)
2765 {
2766     struct xfs_rmap_irec        low = {0};
2767     struct xfs_rmap_irec        high;
2768     struct xfs_rmap_key_state   rks;
2769     int             error;
2770
2771     xfs_owner_info_unpack(oinfo, &rks.owner, &rks.offset, &rks.flags);
2772     *has_rmap = false;
2773
2774     low.rm_startblock = bno;
2775     memset(&high, 0xFF, sizeof(high));
2776     high.rm_startblock = bno + len - 1;
2777
2778     error = xfs_rmap_query_range(cur, &low, &high,
2779             xfs_rmap_has_other_keys_helper, &rks);
2780     if (error == -ECANCELED) {
2781         *has_rmap = true;
2782         return 0;
2783     }
2784
2785     return error;
2786 }
2787
2788 const struct xfs_owner_info XFS_RMAP_OINFO_SKIP_UPDATE = {
2789     .oi_owner = XFS_RMAP_OWN_NULL,
2790 };
2791 const struct xfs_owner_info XFS_RMAP_OINFO_ANY_OWNER = {
2792     .oi_owner = XFS_RMAP_OWN_UNKNOWN,
2793 };
2794 const struct xfs_owner_info XFS_RMAP_OINFO_FS = {
2795     .oi_owner = XFS_RMAP_OWN_FS,
2796 };
2797 const struct xfs_owner_info XFS_RMAP_OINFO_LOG = {
2798     .oi_owner = XFS_RMAP_OWN_LOG,
2799 };
2800 const struct xfs_owner_info XFS_RMAP_OINFO_AG = {
2801     .oi_owner = XFS_RMAP_OWN_AG,
2802 };
2803 const struct xfs_owner_info XFS_RMAP_OINFO_INOBT = {
2804     .oi_owner = XFS_RMAP_OWN_INOBT,
2805 };
2806 const struct xfs_owner_info XFS_RMAP_OINFO_INODES = {
2807     .oi_owner = XFS_RMAP_OWN_INODES,
2808 };
2809 const struct xfs_owner_info XFS_RMAP_OINFO_REFC = {
2810     .oi_owner = XFS_RMAP_OWN_REFC,
2811 };
2812 const struct xfs_owner_info XFS_RMAP_OINFO_COW = {
2813     .oi_owner = XFS_RMAP_OWN_COW,
2814 };
2815
2816 int __init
2817 xfs_rmap_intent_init_cache(void)
2818 {
2819     xfs_rmap_intent_cache = kmem_cache_create("xfs_rmap_intent",
2820             sizeof(struct xfs_rmap_intent),
2821             0, 0, NULL);
2822
2823     return xfs_rmap_intent_cache != NULL ? 0 : -ENOMEM;
2824 }
2825
2826 void
2827 xfs_rmap_intent_destroy_cache(void)
2828 {
2829     kmem_cache_destroy(xfs_rmap_intent_cache);
2830     xfs_rmap_intent_cache = NULL;
2831 }