Back to home page

OSCL-LXR
 
 

     

0001 // SPDX-License-Identifier: GPL-2.0+
0002 /*
0003  * Copyright (C) 2016 Oracle.  All Rights Reserved.
0004  * Author: Darrick J. Wong <darrick.wong@oracle.com>
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_mount.h"
0013 #include "xfs_defer.h"
0014 #include "xfs_btree.h"
0015 #include "xfs_bmap.h"
0016 #include "xfs_refcount_btree.h"
0017 #include "xfs_alloc.h"
0018 #include "xfs_errortag.h"
0019 #include "xfs_error.h"
0020 #include "xfs_trace.h"
0021 #include "xfs_trans.h"
0022 #include "xfs_bit.h"
0023 #include "xfs_refcount.h"
0024 #include "xfs_rmap.h"
0025 #include "xfs_ag.h"
0026 
0027 struct kmem_cache   *xfs_refcount_intent_cache;
0028 
0029 /* Allowable refcount adjustment amounts. */
0030 enum xfs_refc_adjust_op {
0031     XFS_REFCOUNT_ADJUST_INCREASE    = 1,
0032     XFS_REFCOUNT_ADJUST_DECREASE    = -1,
0033     XFS_REFCOUNT_ADJUST_COW_ALLOC   = 0,
0034     XFS_REFCOUNT_ADJUST_COW_FREE    = -1,
0035 };
0036 
0037 STATIC int __xfs_refcount_cow_alloc(struct xfs_btree_cur *rcur,
0038         xfs_agblock_t agbno, xfs_extlen_t aglen);
0039 STATIC int __xfs_refcount_cow_free(struct xfs_btree_cur *rcur,
0040         xfs_agblock_t agbno, xfs_extlen_t aglen);
0041 
0042 /*
0043  * Look up the first record less than or equal to [bno, len] in the btree
0044  * given by cur.
0045  */
0046 int
0047 xfs_refcount_lookup_le(
0048     struct xfs_btree_cur    *cur,
0049     xfs_agblock_t       bno,
0050     int         *stat)
0051 {
0052     trace_xfs_refcount_lookup(cur->bc_mp, cur->bc_ag.pag->pag_agno, bno,
0053             XFS_LOOKUP_LE);
0054     cur->bc_rec.rc.rc_startblock = bno;
0055     cur->bc_rec.rc.rc_blockcount = 0;
0056     return xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat);
0057 }
0058 
0059 /*
0060  * Look up the first record greater than or equal to [bno, len] in the btree
0061  * given by cur.
0062  */
0063 int
0064 xfs_refcount_lookup_ge(
0065     struct xfs_btree_cur    *cur,
0066     xfs_agblock_t       bno,
0067     int         *stat)
0068 {
0069     trace_xfs_refcount_lookup(cur->bc_mp, cur->bc_ag.pag->pag_agno, bno,
0070             XFS_LOOKUP_GE);
0071     cur->bc_rec.rc.rc_startblock = bno;
0072     cur->bc_rec.rc.rc_blockcount = 0;
0073     return xfs_btree_lookup(cur, XFS_LOOKUP_GE, stat);
0074 }
0075 
0076 /*
0077  * Look up the first record equal to [bno, len] in the btree
0078  * given by cur.
0079  */
0080 int
0081 xfs_refcount_lookup_eq(
0082     struct xfs_btree_cur    *cur,
0083     xfs_agblock_t       bno,
0084     int         *stat)
0085 {
0086     trace_xfs_refcount_lookup(cur->bc_mp, cur->bc_ag.pag->pag_agno, bno,
0087             XFS_LOOKUP_LE);
0088     cur->bc_rec.rc.rc_startblock = bno;
0089     cur->bc_rec.rc.rc_blockcount = 0;
0090     return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat);
0091 }
0092 
0093 /* Convert on-disk record to in-core format. */
0094 void
0095 xfs_refcount_btrec_to_irec(
0096     const union xfs_btree_rec   *rec,
0097     struct xfs_refcount_irec    *irec)
0098 {
0099     irec->rc_startblock = be32_to_cpu(rec->refc.rc_startblock);
0100     irec->rc_blockcount = be32_to_cpu(rec->refc.rc_blockcount);
0101     irec->rc_refcount = be32_to_cpu(rec->refc.rc_refcount);
0102 }
0103 
0104 /*
0105  * Get the data from the pointed-to record.
0106  */
0107 int
0108 xfs_refcount_get_rec(
0109     struct xfs_btree_cur        *cur,
0110     struct xfs_refcount_irec    *irec,
0111     int             *stat)
0112 {
0113     struct xfs_mount        *mp = cur->bc_mp;
0114     struct xfs_perag        *pag = cur->bc_ag.pag;
0115     union xfs_btree_rec     *rec;
0116     int             error;
0117     xfs_agblock_t           realstart;
0118 
0119     error = xfs_btree_get_rec(cur, &rec, stat);
0120     if (error || !*stat)
0121         return error;
0122 
0123     xfs_refcount_btrec_to_irec(rec, irec);
0124     if (irec->rc_blockcount == 0 || irec->rc_blockcount > MAXREFCEXTLEN)
0125         goto out_bad_rec;
0126 
0127     /* handle special COW-staging state */
0128     realstart = irec->rc_startblock;
0129     if (realstart & XFS_REFC_COW_START) {
0130         if (irec->rc_refcount != 1)
0131             goto out_bad_rec;
0132         realstart &= ~XFS_REFC_COW_START;
0133     } else if (irec->rc_refcount < 2) {
0134         goto out_bad_rec;
0135     }
0136 
0137     /* check for valid extent range, including overflow */
0138     if (!xfs_verify_agbno(pag, realstart))
0139         goto out_bad_rec;
0140     if (realstart > realstart + irec->rc_blockcount)
0141         goto out_bad_rec;
0142     if (!xfs_verify_agbno(pag, realstart + irec->rc_blockcount - 1))
0143         goto out_bad_rec;
0144 
0145     if (irec->rc_refcount == 0 || irec->rc_refcount > MAXREFCOUNT)
0146         goto out_bad_rec;
0147 
0148     trace_xfs_refcount_get(cur->bc_mp, pag->pag_agno, irec);
0149     return 0;
0150 
0151 out_bad_rec:
0152     xfs_warn(mp,
0153         "Refcount BTree record corruption in AG %d detected!",
0154         pag->pag_agno);
0155     xfs_warn(mp,
0156         "Start block 0x%x, block count 0x%x, references 0x%x",
0157         irec->rc_startblock, irec->rc_blockcount, irec->rc_refcount);
0158     return -EFSCORRUPTED;
0159 }
0160 
0161 /*
0162  * Update the record referred to by cur to the value given
0163  * by [bno, len, refcount].
0164  * This either works (return 0) or gets an EFSCORRUPTED error.
0165  */
0166 STATIC int
0167 xfs_refcount_update(
0168     struct xfs_btree_cur        *cur,
0169     struct xfs_refcount_irec    *irec)
0170 {
0171     union xfs_btree_rec rec;
0172     int         error;
0173 
0174     trace_xfs_refcount_update(cur->bc_mp, cur->bc_ag.pag->pag_agno, irec);
0175     rec.refc.rc_startblock = cpu_to_be32(irec->rc_startblock);
0176     rec.refc.rc_blockcount = cpu_to_be32(irec->rc_blockcount);
0177     rec.refc.rc_refcount = cpu_to_be32(irec->rc_refcount);
0178     error = xfs_btree_update(cur, &rec);
0179     if (error)
0180         trace_xfs_refcount_update_error(cur->bc_mp,
0181                 cur->bc_ag.pag->pag_agno, error, _RET_IP_);
0182     return error;
0183 }
0184 
0185 /*
0186  * Insert the record referred to by cur to the value given
0187  * by [bno, len, refcount].
0188  * This either works (return 0) or gets an EFSCORRUPTED error.
0189  */
0190 int
0191 xfs_refcount_insert(
0192     struct xfs_btree_cur        *cur,
0193     struct xfs_refcount_irec    *irec,
0194     int             *i)
0195 {
0196     int             error;
0197 
0198     trace_xfs_refcount_insert(cur->bc_mp, cur->bc_ag.pag->pag_agno, irec);
0199     cur->bc_rec.rc.rc_startblock = irec->rc_startblock;
0200     cur->bc_rec.rc.rc_blockcount = irec->rc_blockcount;
0201     cur->bc_rec.rc.rc_refcount = irec->rc_refcount;
0202     error = xfs_btree_insert(cur, i);
0203     if (error)
0204         goto out_error;
0205     if (XFS_IS_CORRUPT(cur->bc_mp, *i != 1)) {
0206         error = -EFSCORRUPTED;
0207         goto out_error;
0208     }
0209 
0210 out_error:
0211     if (error)
0212         trace_xfs_refcount_insert_error(cur->bc_mp,
0213                 cur->bc_ag.pag->pag_agno, error, _RET_IP_);
0214     return error;
0215 }
0216 
0217 /*
0218  * Remove the record referred to by cur, then set the pointer to the spot
0219  * where the record could be re-inserted, in case we want to increment or
0220  * decrement the cursor.
0221  * This either works (return 0) or gets an EFSCORRUPTED error.
0222  */
0223 STATIC int
0224 xfs_refcount_delete(
0225     struct xfs_btree_cur    *cur,
0226     int         *i)
0227 {
0228     struct xfs_refcount_irec    irec;
0229     int         found_rec;
0230     int         error;
0231 
0232     error = xfs_refcount_get_rec(cur, &irec, &found_rec);
0233     if (error)
0234         goto out_error;
0235     if (XFS_IS_CORRUPT(cur->bc_mp, found_rec != 1)) {
0236         error = -EFSCORRUPTED;
0237         goto out_error;
0238     }
0239     trace_xfs_refcount_delete(cur->bc_mp, cur->bc_ag.pag->pag_agno, &irec);
0240     error = xfs_btree_delete(cur, i);
0241     if (XFS_IS_CORRUPT(cur->bc_mp, *i != 1)) {
0242         error = -EFSCORRUPTED;
0243         goto out_error;
0244     }
0245     if (error)
0246         goto out_error;
0247     error = xfs_refcount_lookup_ge(cur, irec.rc_startblock, &found_rec);
0248 out_error:
0249     if (error)
0250         trace_xfs_refcount_delete_error(cur->bc_mp,
0251                 cur->bc_ag.pag->pag_agno, error, _RET_IP_);
0252     return error;
0253 }
0254 
0255 /*
0256  * Adjusting the Reference Count
0257  *
0258  * As stated elsewhere, the reference count btree (refcbt) stores
0259  * >1 reference counts for extents of physical blocks.  In this
0260  * operation, we're either raising or lowering the reference count of
0261  * some subrange stored in the tree:
0262  *
0263  *      <------ adjustment range ------>
0264  * ----+   +---+-----+ +--+--------+---------
0265  *  2  |   | 3 |  4  | |17|   55   |   10
0266  * ----+   +---+-----+ +--+--------+---------
0267  * X axis is physical blocks number;
0268  * reference counts are the numbers inside the rectangles
0269  *
0270  * The first thing we need to do is to ensure that there are no
0271  * refcount extents crossing either boundary of the range to be
0272  * adjusted.  For any extent that does cross a boundary, split it into
0273  * two extents so that we can increment the refcount of one of the
0274  * pieces later:
0275  *
0276  *      <------ adjustment range ------>
0277  * ----+   +---+-----+ +--+--------+----+----
0278  *  2  |   | 3 |  2  | |17|   55   | 10 | 10
0279  * ----+   +---+-----+ +--+--------+----+----
0280  *
0281  * For this next step, let's assume that all the physical blocks in
0282  * the adjustment range are mapped to a file and are therefore in use
0283  * at least once.  Therefore, we can infer that any gap in the
0284  * refcount tree within the adjustment range represents a physical
0285  * extent with refcount == 1:
0286  *
0287  *      <------ adjustment range ------>
0288  * ----+---+---+-----+-+--+--------+----+----
0289  *  2  |"1"| 3 |  2  |1|17|   55   | 10 | 10
0290  * ----+---+---+-----+-+--+--------+----+----
0291  *      ^
0292  *
0293  * For each extent that falls within the interval range, figure out
0294  * which extent is to the left or the right of that extent.  Now we
0295  * have a left, current, and right extent.  If the new reference count
0296  * of the center extent enables us to merge left, center, and right
0297  * into one record covering all three, do so.  If the center extent is
0298  * at the left end of the range, abuts the left extent, and its new
0299  * reference count matches the left extent's record, then merge them.
0300  * If the center extent is at the right end of the range, abuts the
0301  * right extent, and the reference counts match, merge those.  In the
0302  * example, we can left merge (assuming an increment operation):
0303  *
0304  *      <------ adjustment range ------>
0305  * --------+---+-----+-+--+--------+----+----
0306  *    2    | 3 |  2  |1|17|   55   | 10 | 10
0307  * --------+---+-----+-+--+--------+----+----
0308  *          ^
0309  *
0310  * For all other extents within the range, adjust the reference count
0311  * or delete it if the refcount falls below 2.  If we were
0312  * incrementing, the end result looks like this:
0313  *
0314  *      <------ adjustment range ------>
0315  * --------+---+-----+-+--+--------+----+----
0316  *    2    | 4 |  3  |2|18|   56   | 11 | 10
0317  * --------+---+-----+-+--+--------+----+----
0318  *
0319  * The result of a decrement operation looks as such:
0320  *
0321  *      <------ adjustment range ------>
0322  * ----+   +---+       +--+--------+----+----
0323  *  2  |   | 2 |       |16|   54   |  9 | 10
0324  * ----+   +---+       +--+--------+----+----
0325  *      DDDD    111111DD
0326  *
0327  * The blocks marked "D" are freed; the blocks marked "1" are only
0328  * referenced once and therefore the record is removed from the
0329  * refcount btree.
0330  */
0331 
0332 /* Next block after this extent. */
0333 static inline xfs_agblock_t
0334 xfs_refc_next(
0335     struct xfs_refcount_irec    *rc)
0336 {
0337     return rc->rc_startblock + rc->rc_blockcount;
0338 }
0339 
0340 /*
0341  * Split a refcount extent that crosses agbno.
0342  */
0343 STATIC int
0344 xfs_refcount_split_extent(
0345     struct xfs_btree_cur        *cur,
0346     xfs_agblock_t           agbno,
0347     bool                *shape_changed)
0348 {
0349     struct xfs_refcount_irec    rcext, tmp;
0350     int             found_rec;
0351     int             error;
0352 
0353     *shape_changed = false;
0354     error = xfs_refcount_lookup_le(cur, agbno, &found_rec);
0355     if (error)
0356         goto out_error;
0357     if (!found_rec)
0358         return 0;
0359 
0360     error = xfs_refcount_get_rec(cur, &rcext, &found_rec);
0361     if (error)
0362         goto out_error;
0363     if (XFS_IS_CORRUPT(cur->bc_mp, found_rec != 1)) {
0364         error = -EFSCORRUPTED;
0365         goto out_error;
0366     }
0367     if (rcext.rc_startblock == agbno || xfs_refc_next(&rcext) <= agbno)
0368         return 0;
0369 
0370     *shape_changed = true;
0371     trace_xfs_refcount_split_extent(cur->bc_mp, cur->bc_ag.pag->pag_agno,
0372             &rcext, agbno);
0373 
0374     /* Establish the right extent. */
0375     tmp = rcext;
0376     tmp.rc_startblock = agbno;
0377     tmp.rc_blockcount -= (agbno - rcext.rc_startblock);
0378     error = xfs_refcount_update(cur, &tmp);
0379     if (error)
0380         goto out_error;
0381 
0382     /* Insert the left extent. */
0383     tmp = rcext;
0384     tmp.rc_blockcount = agbno - rcext.rc_startblock;
0385     error = xfs_refcount_insert(cur, &tmp, &found_rec);
0386     if (error)
0387         goto out_error;
0388     if (XFS_IS_CORRUPT(cur->bc_mp, found_rec != 1)) {
0389         error = -EFSCORRUPTED;
0390         goto out_error;
0391     }
0392     return error;
0393 
0394 out_error:
0395     trace_xfs_refcount_split_extent_error(cur->bc_mp,
0396             cur->bc_ag.pag->pag_agno, error, _RET_IP_);
0397     return error;
0398 }
0399 
0400 /*
0401  * Merge the left, center, and right extents.
0402  */
0403 STATIC int
0404 xfs_refcount_merge_center_extents(
0405     struct xfs_btree_cur        *cur,
0406     struct xfs_refcount_irec    *left,
0407     struct xfs_refcount_irec    *center,
0408     struct xfs_refcount_irec    *right,
0409     unsigned long long      extlen,
0410     xfs_extlen_t            *aglen)
0411 {
0412     int             error;
0413     int             found_rec;
0414 
0415     trace_xfs_refcount_merge_center_extents(cur->bc_mp,
0416             cur->bc_ag.pag->pag_agno, left, center, right);
0417 
0418     /*
0419      * Make sure the center and right extents are not in the btree.
0420      * If the center extent was synthesized, the first delete call
0421      * removes the right extent and we skip the second deletion.
0422      * If center and right were in the btree, then the first delete
0423      * call removes the center and the second one removes the right
0424      * extent.
0425      */
0426     error = xfs_refcount_lookup_ge(cur, center->rc_startblock,
0427             &found_rec);
0428     if (error)
0429         goto out_error;
0430     if (XFS_IS_CORRUPT(cur->bc_mp, found_rec != 1)) {
0431         error = -EFSCORRUPTED;
0432         goto out_error;
0433     }
0434 
0435     error = xfs_refcount_delete(cur, &found_rec);
0436     if (error)
0437         goto out_error;
0438     if (XFS_IS_CORRUPT(cur->bc_mp, found_rec != 1)) {
0439         error = -EFSCORRUPTED;
0440         goto out_error;
0441     }
0442 
0443     if (center->rc_refcount > 1) {
0444         error = xfs_refcount_delete(cur, &found_rec);
0445         if (error)
0446             goto out_error;
0447         if (XFS_IS_CORRUPT(cur->bc_mp, found_rec != 1)) {
0448             error = -EFSCORRUPTED;
0449             goto out_error;
0450         }
0451     }
0452 
0453     /* Enlarge the left extent. */
0454     error = xfs_refcount_lookup_le(cur, left->rc_startblock,
0455             &found_rec);
0456     if (error)
0457         goto out_error;
0458     if (XFS_IS_CORRUPT(cur->bc_mp, found_rec != 1)) {
0459         error = -EFSCORRUPTED;
0460         goto out_error;
0461     }
0462 
0463     left->rc_blockcount = extlen;
0464     error = xfs_refcount_update(cur, left);
0465     if (error)
0466         goto out_error;
0467 
0468     *aglen = 0;
0469     return error;
0470 
0471 out_error:
0472     trace_xfs_refcount_merge_center_extents_error(cur->bc_mp,
0473             cur->bc_ag.pag->pag_agno, error, _RET_IP_);
0474     return error;
0475 }
0476 
0477 /*
0478  * Merge with the left extent.
0479  */
0480 STATIC int
0481 xfs_refcount_merge_left_extent(
0482     struct xfs_btree_cur        *cur,
0483     struct xfs_refcount_irec    *left,
0484     struct xfs_refcount_irec    *cleft,
0485     xfs_agblock_t           *agbno,
0486     xfs_extlen_t            *aglen)
0487 {
0488     int             error;
0489     int             found_rec;
0490 
0491     trace_xfs_refcount_merge_left_extent(cur->bc_mp,
0492             cur->bc_ag.pag->pag_agno, left, cleft);
0493 
0494     /* If the extent at agbno (cleft) wasn't synthesized, remove it. */
0495     if (cleft->rc_refcount > 1) {
0496         error = xfs_refcount_lookup_le(cur, cleft->rc_startblock,
0497                 &found_rec);
0498         if (error)
0499             goto out_error;
0500         if (XFS_IS_CORRUPT(cur->bc_mp, found_rec != 1)) {
0501             error = -EFSCORRUPTED;
0502             goto out_error;
0503         }
0504 
0505         error = xfs_refcount_delete(cur, &found_rec);
0506         if (error)
0507             goto out_error;
0508         if (XFS_IS_CORRUPT(cur->bc_mp, found_rec != 1)) {
0509             error = -EFSCORRUPTED;
0510             goto out_error;
0511         }
0512     }
0513 
0514     /* Enlarge the left extent. */
0515     error = xfs_refcount_lookup_le(cur, left->rc_startblock,
0516             &found_rec);
0517     if (error)
0518         goto out_error;
0519     if (XFS_IS_CORRUPT(cur->bc_mp, found_rec != 1)) {
0520         error = -EFSCORRUPTED;
0521         goto out_error;
0522     }
0523 
0524     left->rc_blockcount += cleft->rc_blockcount;
0525     error = xfs_refcount_update(cur, left);
0526     if (error)
0527         goto out_error;
0528 
0529     *agbno += cleft->rc_blockcount;
0530     *aglen -= cleft->rc_blockcount;
0531     return error;
0532 
0533 out_error:
0534     trace_xfs_refcount_merge_left_extent_error(cur->bc_mp,
0535             cur->bc_ag.pag->pag_agno, error, _RET_IP_);
0536     return error;
0537 }
0538 
0539 /*
0540  * Merge with the right extent.
0541  */
0542 STATIC int
0543 xfs_refcount_merge_right_extent(
0544     struct xfs_btree_cur        *cur,
0545     struct xfs_refcount_irec    *right,
0546     struct xfs_refcount_irec    *cright,
0547     xfs_extlen_t            *aglen)
0548 {
0549     int             error;
0550     int             found_rec;
0551 
0552     trace_xfs_refcount_merge_right_extent(cur->bc_mp,
0553             cur->bc_ag.pag->pag_agno, cright, right);
0554 
0555     /*
0556      * If the extent ending at agbno+aglen (cright) wasn't synthesized,
0557      * remove it.
0558      */
0559     if (cright->rc_refcount > 1) {
0560         error = xfs_refcount_lookup_le(cur, cright->rc_startblock,
0561             &found_rec);
0562         if (error)
0563             goto out_error;
0564         if (XFS_IS_CORRUPT(cur->bc_mp, found_rec != 1)) {
0565             error = -EFSCORRUPTED;
0566             goto out_error;
0567         }
0568 
0569         error = xfs_refcount_delete(cur, &found_rec);
0570         if (error)
0571             goto out_error;
0572         if (XFS_IS_CORRUPT(cur->bc_mp, found_rec != 1)) {
0573             error = -EFSCORRUPTED;
0574             goto out_error;
0575         }
0576     }
0577 
0578     /* Enlarge the right extent. */
0579     error = xfs_refcount_lookup_le(cur, right->rc_startblock,
0580             &found_rec);
0581     if (error)
0582         goto out_error;
0583     if (XFS_IS_CORRUPT(cur->bc_mp, found_rec != 1)) {
0584         error = -EFSCORRUPTED;
0585         goto out_error;
0586     }
0587 
0588     right->rc_startblock -= cright->rc_blockcount;
0589     right->rc_blockcount += cright->rc_blockcount;
0590     error = xfs_refcount_update(cur, right);
0591     if (error)
0592         goto out_error;
0593 
0594     *aglen -= cright->rc_blockcount;
0595     return error;
0596 
0597 out_error:
0598     trace_xfs_refcount_merge_right_extent_error(cur->bc_mp,
0599             cur->bc_ag.pag->pag_agno, error, _RET_IP_);
0600     return error;
0601 }
0602 
0603 #define XFS_FIND_RCEXT_SHARED   1
0604 #define XFS_FIND_RCEXT_COW  2
0605 /*
0606  * Find the left extent and the one after it (cleft).  This function assumes
0607  * that we've already split any extent crossing agbno.
0608  */
0609 STATIC int
0610 xfs_refcount_find_left_extents(
0611     struct xfs_btree_cur        *cur,
0612     struct xfs_refcount_irec    *left,
0613     struct xfs_refcount_irec    *cleft,
0614     xfs_agblock_t           agbno,
0615     xfs_extlen_t            aglen,
0616     int             flags)
0617 {
0618     struct xfs_refcount_irec    tmp;
0619     int             error;
0620     int             found_rec;
0621 
0622     left->rc_startblock = cleft->rc_startblock = NULLAGBLOCK;
0623     error = xfs_refcount_lookup_le(cur, agbno - 1, &found_rec);
0624     if (error)
0625         goto out_error;
0626     if (!found_rec)
0627         return 0;
0628 
0629     error = xfs_refcount_get_rec(cur, &tmp, &found_rec);
0630     if (error)
0631         goto out_error;
0632     if (XFS_IS_CORRUPT(cur->bc_mp, found_rec != 1)) {
0633         error = -EFSCORRUPTED;
0634         goto out_error;
0635     }
0636 
0637     if (xfs_refc_next(&tmp) != agbno)
0638         return 0;
0639     if ((flags & XFS_FIND_RCEXT_SHARED) && tmp.rc_refcount < 2)
0640         return 0;
0641     if ((flags & XFS_FIND_RCEXT_COW) && tmp.rc_refcount > 1)
0642         return 0;
0643     /* We have a left extent; retrieve (or invent) the next right one */
0644     *left = tmp;
0645 
0646     error = xfs_btree_increment(cur, 0, &found_rec);
0647     if (error)
0648         goto out_error;
0649     if (found_rec) {
0650         error = xfs_refcount_get_rec(cur, &tmp, &found_rec);
0651         if (error)
0652             goto out_error;
0653         if (XFS_IS_CORRUPT(cur->bc_mp, found_rec != 1)) {
0654             error = -EFSCORRUPTED;
0655             goto out_error;
0656         }
0657 
0658         /* if tmp starts at the end of our range, just use that */
0659         if (tmp.rc_startblock == agbno)
0660             *cleft = tmp;
0661         else {
0662             /*
0663              * There's a gap in the refcntbt at the start of the
0664              * range we're interested in (refcount == 1) so
0665              * synthesize the implied extent and pass it back.
0666              * We assume here that the agbno/aglen range was
0667              * passed in from a data fork extent mapping and
0668              * therefore is allocated to exactly one owner.
0669              */
0670             cleft->rc_startblock = agbno;
0671             cleft->rc_blockcount = min(aglen,
0672                     tmp.rc_startblock - agbno);
0673             cleft->rc_refcount = 1;
0674         }
0675     } else {
0676         /*
0677          * No extents, so pretend that there's one covering the whole
0678          * range.
0679          */
0680         cleft->rc_startblock = agbno;
0681         cleft->rc_blockcount = aglen;
0682         cleft->rc_refcount = 1;
0683     }
0684     trace_xfs_refcount_find_left_extent(cur->bc_mp, cur->bc_ag.pag->pag_agno,
0685             left, cleft, agbno);
0686     return error;
0687 
0688 out_error:
0689     trace_xfs_refcount_find_left_extent_error(cur->bc_mp,
0690             cur->bc_ag.pag->pag_agno, error, _RET_IP_);
0691     return error;
0692 }
0693 
0694 /*
0695  * Find the right extent and the one before it (cright).  This function
0696  * assumes that we've already split any extents crossing agbno + aglen.
0697  */
0698 STATIC int
0699 xfs_refcount_find_right_extents(
0700     struct xfs_btree_cur        *cur,
0701     struct xfs_refcount_irec    *right,
0702     struct xfs_refcount_irec    *cright,
0703     xfs_agblock_t           agbno,
0704     xfs_extlen_t            aglen,
0705     int             flags)
0706 {
0707     struct xfs_refcount_irec    tmp;
0708     int             error;
0709     int             found_rec;
0710 
0711     right->rc_startblock = cright->rc_startblock = NULLAGBLOCK;
0712     error = xfs_refcount_lookup_ge(cur, agbno + aglen, &found_rec);
0713     if (error)
0714         goto out_error;
0715     if (!found_rec)
0716         return 0;
0717 
0718     error = xfs_refcount_get_rec(cur, &tmp, &found_rec);
0719     if (error)
0720         goto out_error;
0721     if (XFS_IS_CORRUPT(cur->bc_mp, found_rec != 1)) {
0722         error = -EFSCORRUPTED;
0723         goto out_error;
0724     }
0725 
0726     if (tmp.rc_startblock != agbno + aglen)
0727         return 0;
0728     if ((flags & XFS_FIND_RCEXT_SHARED) && tmp.rc_refcount < 2)
0729         return 0;
0730     if ((flags & XFS_FIND_RCEXT_COW) && tmp.rc_refcount > 1)
0731         return 0;
0732     /* We have a right extent; retrieve (or invent) the next left one */
0733     *right = tmp;
0734 
0735     error = xfs_btree_decrement(cur, 0, &found_rec);
0736     if (error)
0737         goto out_error;
0738     if (found_rec) {
0739         error = xfs_refcount_get_rec(cur, &tmp, &found_rec);
0740         if (error)
0741             goto out_error;
0742         if (XFS_IS_CORRUPT(cur->bc_mp, found_rec != 1)) {
0743             error = -EFSCORRUPTED;
0744             goto out_error;
0745         }
0746 
0747         /* if tmp ends at the end of our range, just use that */
0748         if (xfs_refc_next(&tmp) == agbno + aglen)
0749             *cright = tmp;
0750         else {
0751             /*
0752              * There's a gap in the refcntbt at the end of the
0753              * range we're interested in (refcount == 1) so
0754              * create the implied extent and pass it back.
0755              * We assume here that the agbno/aglen range was
0756              * passed in from a data fork extent mapping and
0757              * therefore is allocated to exactly one owner.
0758              */
0759             cright->rc_startblock = max(agbno, xfs_refc_next(&tmp));
0760             cright->rc_blockcount = right->rc_startblock -
0761                     cright->rc_startblock;
0762             cright->rc_refcount = 1;
0763         }
0764     } else {
0765         /*
0766          * No extents, so pretend that there's one covering the whole
0767          * range.
0768          */
0769         cright->rc_startblock = agbno;
0770         cright->rc_blockcount = aglen;
0771         cright->rc_refcount = 1;
0772     }
0773     trace_xfs_refcount_find_right_extent(cur->bc_mp, cur->bc_ag.pag->pag_agno,
0774             cright, right, agbno + aglen);
0775     return error;
0776 
0777 out_error:
0778     trace_xfs_refcount_find_right_extent_error(cur->bc_mp,
0779             cur->bc_ag.pag->pag_agno, error, _RET_IP_);
0780     return error;
0781 }
0782 
0783 /* Is this extent valid? */
0784 static inline bool
0785 xfs_refc_valid(
0786     struct xfs_refcount_irec    *rc)
0787 {
0788     return rc->rc_startblock != NULLAGBLOCK;
0789 }
0790 
0791 /*
0792  * Try to merge with any extents on the boundaries of the adjustment range.
0793  */
0794 STATIC int
0795 xfs_refcount_merge_extents(
0796     struct xfs_btree_cur    *cur,
0797     xfs_agblock_t       *agbno,
0798     xfs_extlen_t        *aglen,
0799     enum xfs_refc_adjust_op adjust,
0800     int         flags,
0801     bool            *shape_changed)
0802 {
0803     struct xfs_refcount_irec    left = {0}, cleft = {0};
0804     struct xfs_refcount_irec    cright = {0}, right = {0};
0805     int             error;
0806     unsigned long long      ulen;
0807     bool                cequal;
0808 
0809     *shape_changed = false;
0810     /*
0811      * Find the extent just below agbno [left], just above agbno [cleft],
0812      * just below (agbno + aglen) [cright], and just above (agbno + aglen)
0813      * [right].
0814      */
0815     error = xfs_refcount_find_left_extents(cur, &left, &cleft, *agbno,
0816             *aglen, flags);
0817     if (error)
0818         return error;
0819     error = xfs_refcount_find_right_extents(cur, &right, &cright, *agbno,
0820             *aglen, flags);
0821     if (error)
0822         return error;
0823 
0824     /* No left or right extent to merge; exit. */
0825     if (!xfs_refc_valid(&left) && !xfs_refc_valid(&right))
0826         return 0;
0827 
0828     cequal = (cleft.rc_startblock == cright.rc_startblock) &&
0829          (cleft.rc_blockcount == cright.rc_blockcount);
0830 
0831     /* Try to merge left, cleft, and right.  cleft must == cright. */
0832     ulen = (unsigned long long)left.rc_blockcount + cleft.rc_blockcount +
0833             right.rc_blockcount;
0834     if (xfs_refc_valid(&left) && xfs_refc_valid(&right) &&
0835         xfs_refc_valid(&cleft) && xfs_refc_valid(&cright) && cequal &&
0836         left.rc_refcount == cleft.rc_refcount + adjust &&
0837         right.rc_refcount == cleft.rc_refcount + adjust &&
0838         ulen < MAXREFCEXTLEN) {
0839         *shape_changed = true;
0840         return xfs_refcount_merge_center_extents(cur, &left, &cleft,
0841                 &right, ulen, aglen);
0842     }
0843 
0844     /* Try to merge left and cleft. */
0845     ulen = (unsigned long long)left.rc_blockcount + cleft.rc_blockcount;
0846     if (xfs_refc_valid(&left) && xfs_refc_valid(&cleft) &&
0847         left.rc_refcount == cleft.rc_refcount + adjust &&
0848         ulen < MAXREFCEXTLEN) {
0849         *shape_changed = true;
0850         error = xfs_refcount_merge_left_extent(cur, &left, &cleft,
0851                 agbno, aglen);
0852         if (error)
0853             return error;
0854 
0855         /*
0856          * If we just merged left + cleft and cleft == cright,
0857          * we no longer have a cright to merge with right.  We're done.
0858          */
0859         if (cequal)
0860             return 0;
0861     }
0862 
0863     /* Try to merge cright and right. */
0864     ulen = (unsigned long long)right.rc_blockcount + cright.rc_blockcount;
0865     if (xfs_refc_valid(&right) && xfs_refc_valid(&cright) &&
0866         right.rc_refcount == cright.rc_refcount + adjust &&
0867         ulen < MAXREFCEXTLEN) {
0868         *shape_changed = true;
0869         return xfs_refcount_merge_right_extent(cur, &right, &cright,
0870                 aglen);
0871     }
0872 
0873     return error;
0874 }
0875 
0876 /*
0877  * XXX: This is a pretty hand-wavy estimate.  The penalty for guessing
0878  * true incorrectly is a shutdown FS; the penalty for guessing false
0879  * incorrectly is more transaction rolls than might be necessary.
0880  * Be conservative here.
0881  */
0882 static bool
0883 xfs_refcount_still_have_space(
0884     struct xfs_btree_cur        *cur)
0885 {
0886     unsigned long           overhead;
0887 
0888     /*
0889      * Worst case estimate: full splits of the free space and rmap btrees
0890      * to handle each of the shape changes to the refcount btree.
0891      */
0892     overhead = xfs_allocfree_block_count(cur->bc_mp,
0893                 cur->bc_ag.refc.shape_changes);
0894     overhead += cur->bc_mp->m_refc_maxlevels;
0895     overhead *= cur->bc_mp->m_sb.sb_blocksize;
0896 
0897     /*
0898      * Only allow 2 refcount extent updates per transaction if the
0899      * refcount continue update "error" has been injected.
0900      */
0901     if (cur->bc_ag.refc.nr_ops > 2 &&
0902         XFS_TEST_ERROR(false, cur->bc_mp,
0903             XFS_ERRTAG_REFCOUNT_CONTINUE_UPDATE))
0904         return false;
0905 
0906     if (cur->bc_ag.refc.nr_ops == 0)
0907         return true;
0908     else if (overhead > cur->bc_tp->t_log_res)
0909         return false;
0910     return  cur->bc_tp->t_log_res - overhead >
0911         cur->bc_ag.refc.nr_ops * XFS_REFCOUNT_ITEM_OVERHEAD;
0912 }
0913 
0914 /*
0915  * Adjust the refcounts of middle extents.  At this point we should have
0916  * split extents that crossed the adjustment range; merged with adjacent
0917  * extents; and updated agbno/aglen to reflect the merges.  Therefore,
0918  * all we have to do is update the extents inside [agbno, agbno + aglen].
0919  */
0920 STATIC int
0921 xfs_refcount_adjust_extents(
0922     struct xfs_btree_cur    *cur,
0923     xfs_agblock_t       *agbno,
0924     xfs_extlen_t        *aglen,
0925     enum xfs_refc_adjust_op adj)
0926 {
0927     struct xfs_refcount_irec    ext, tmp;
0928     int             error;
0929     int             found_rec, found_tmp;
0930     xfs_fsblock_t           fsbno;
0931 
0932     /* Merging did all the work already. */
0933     if (*aglen == 0)
0934         return 0;
0935 
0936     error = xfs_refcount_lookup_ge(cur, *agbno, &found_rec);
0937     if (error)
0938         goto out_error;
0939 
0940     while (*aglen > 0 && xfs_refcount_still_have_space(cur)) {
0941         error = xfs_refcount_get_rec(cur, &ext, &found_rec);
0942         if (error)
0943             goto out_error;
0944         if (!found_rec) {
0945             ext.rc_startblock = cur->bc_mp->m_sb.sb_agblocks;
0946             ext.rc_blockcount = 0;
0947             ext.rc_refcount = 0;
0948         }
0949 
0950         /*
0951          * Deal with a hole in the refcount tree; if a file maps to
0952          * these blocks and there's no refcountbt record, pretend that
0953          * there is one with refcount == 1.
0954          */
0955         if (ext.rc_startblock != *agbno) {
0956             tmp.rc_startblock = *agbno;
0957             tmp.rc_blockcount = min(*aglen,
0958                     ext.rc_startblock - *agbno);
0959             tmp.rc_refcount = 1 + adj;
0960             trace_xfs_refcount_modify_extent(cur->bc_mp,
0961                     cur->bc_ag.pag->pag_agno, &tmp);
0962 
0963             /*
0964              * Either cover the hole (increment) or
0965              * delete the range (decrement).
0966              */
0967             cur->bc_ag.refc.nr_ops++;
0968             if (tmp.rc_refcount) {
0969                 error = xfs_refcount_insert(cur, &tmp,
0970                         &found_tmp);
0971                 if (error)
0972                     goto out_error;
0973                 if (XFS_IS_CORRUPT(cur->bc_mp,
0974                            found_tmp != 1)) {
0975                     error = -EFSCORRUPTED;
0976                     goto out_error;
0977                 }
0978             } else {
0979                 fsbno = XFS_AGB_TO_FSB(cur->bc_mp,
0980                         cur->bc_ag.pag->pag_agno,
0981                         tmp.rc_startblock);
0982                 xfs_free_extent_later(cur->bc_tp, fsbno,
0983                           tmp.rc_blockcount, NULL);
0984             }
0985 
0986             (*agbno) += tmp.rc_blockcount;
0987             (*aglen) -= tmp.rc_blockcount;
0988 
0989             error = xfs_refcount_lookup_ge(cur, *agbno,
0990                     &found_rec);
0991             if (error)
0992                 goto out_error;
0993         }
0994 
0995         /* Stop if there's nothing left to modify */
0996         if (*aglen == 0 || !xfs_refcount_still_have_space(cur))
0997             break;
0998 
0999         /*
1000          * Adjust the reference count and either update the tree
1001          * (incr) or free the blocks (decr).
1002          */
1003         if (ext.rc_refcount == MAXREFCOUNT)
1004             goto skip;
1005         ext.rc_refcount += adj;
1006         trace_xfs_refcount_modify_extent(cur->bc_mp,
1007                 cur->bc_ag.pag->pag_agno, &ext);
1008         cur->bc_ag.refc.nr_ops++;
1009         if (ext.rc_refcount > 1) {
1010             error = xfs_refcount_update(cur, &ext);
1011             if (error)
1012                 goto out_error;
1013         } else if (ext.rc_refcount == 1) {
1014             error = xfs_refcount_delete(cur, &found_rec);
1015             if (error)
1016                 goto out_error;
1017             if (XFS_IS_CORRUPT(cur->bc_mp, found_rec != 1)) {
1018                 error = -EFSCORRUPTED;
1019                 goto out_error;
1020             }
1021             goto advloop;
1022         } else {
1023             fsbno = XFS_AGB_TO_FSB(cur->bc_mp,
1024                     cur->bc_ag.pag->pag_agno,
1025                     ext.rc_startblock);
1026             xfs_free_extent_later(cur->bc_tp, fsbno,
1027                     ext.rc_blockcount, NULL);
1028         }
1029 
1030 skip:
1031         error = xfs_btree_increment(cur, 0, &found_rec);
1032         if (error)
1033             goto out_error;
1034 
1035 advloop:
1036         (*agbno) += ext.rc_blockcount;
1037         (*aglen) -= ext.rc_blockcount;
1038     }
1039 
1040     return error;
1041 out_error:
1042     trace_xfs_refcount_modify_extent_error(cur->bc_mp,
1043             cur->bc_ag.pag->pag_agno, error, _RET_IP_);
1044     return error;
1045 }
1046 
1047 /* Adjust the reference count of a range of AG blocks. */
1048 STATIC int
1049 xfs_refcount_adjust(
1050     struct xfs_btree_cur    *cur,
1051     xfs_agblock_t       agbno,
1052     xfs_extlen_t        aglen,
1053     xfs_agblock_t       *new_agbno,
1054     xfs_extlen_t        *new_aglen,
1055     enum xfs_refc_adjust_op adj)
1056 {
1057     bool            shape_changed;
1058     int         shape_changes = 0;
1059     int         error;
1060 
1061     *new_agbno = agbno;
1062     *new_aglen = aglen;
1063     if (adj == XFS_REFCOUNT_ADJUST_INCREASE)
1064         trace_xfs_refcount_increase(cur->bc_mp, cur->bc_ag.pag->pag_agno,
1065                 agbno, aglen);
1066     else
1067         trace_xfs_refcount_decrease(cur->bc_mp, cur->bc_ag.pag->pag_agno,
1068                 agbno, aglen);
1069 
1070     /*
1071      * Ensure that no rcextents cross the boundary of the adjustment range.
1072      */
1073     error = xfs_refcount_split_extent(cur, agbno, &shape_changed);
1074     if (error)
1075         goto out_error;
1076     if (shape_changed)
1077         shape_changes++;
1078 
1079     error = xfs_refcount_split_extent(cur, agbno + aglen, &shape_changed);
1080     if (error)
1081         goto out_error;
1082     if (shape_changed)
1083         shape_changes++;
1084 
1085     /*
1086      * Try to merge with the left or right extents of the range.
1087      */
1088     error = xfs_refcount_merge_extents(cur, new_agbno, new_aglen, adj,
1089             XFS_FIND_RCEXT_SHARED, &shape_changed);
1090     if (error)
1091         goto out_error;
1092     if (shape_changed)
1093         shape_changes++;
1094     if (shape_changes)
1095         cur->bc_ag.refc.shape_changes++;
1096 
1097     /* Now that we've taken care of the ends, adjust the middle extents */
1098     error = xfs_refcount_adjust_extents(cur, new_agbno, new_aglen, adj);
1099     if (error)
1100         goto out_error;
1101 
1102     return 0;
1103 
1104 out_error:
1105     trace_xfs_refcount_adjust_error(cur->bc_mp, cur->bc_ag.pag->pag_agno,
1106             error, _RET_IP_);
1107     return error;
1108 }
1109 
1110 /* Clean up after calling xfs_refcount_finish_one. */
1111 void
1112 xfs_refcount_finish_one_cleanup(
1113     struct xfs_trans    *tp,
1114     struct xfs_btree_cur    *rcur,
1115     int         error)
1116 {
1117     struct xfs_buf      *agbp;
1118 
1119     if (rcur == NULL)
1120         return;
1121     agbp = rcur->bc_ag.agbp;
1122     xfs_btree_del_cursor(rcur, error);
1123     if (error)
1124         xfs_trans_brelse(tp, agbp);
1125 }
1126 
1127 /*
1128  * Process one of the deferred refcount operations.  We pass back the
1129  * btree cursor to maintain our lock on the btree between calls.
1130  * This saves time and eliminates a buffer deadlock between the
1131  * superblock and the AGF because we'll always grab them in the same
1132  * order.
1133  */
1134 int
1135 xfs_refcount_finish_one(
1136     struct xfs_trans        *tp,
1137     enum xfs_refcount_intent_type   type,
1138     xfs_fsblock_t           startblock,
1139     xfs_extlen_t            blockcount,
1140     xfs_fsblock_t           *new_fsb,
1141     xfs_extlen_t            *new_len,
1142     struct xfs_btree_cur        **pcur)
1143 {
1144     struct xfs_mount        *mp = tp->t_mountp;
1145     struct xfs_btree_cur        *rcur;
1146     struct xfs_buf          *agbp = NULL;
1147     int             error = 0;
1148     xfs_agblock_t           bno;
1149     xfs_agblock_t           new_agbno;
1150     unsigned long           nr_ops = 0;
1151     int             shape_changes = 0;
1152     struct xfs_perag        *pag;
1153 
1154     pag = xfs_perag_get(mp, XFS_FSB_TO_AGNO(mp, startblock));
1155     bno = XFS_FSB_TO_AGBNO(mp, startblock);
1156 
1157     trace_xfs_refcount_deferred(mp, XFS_FSB_TO_AGNO(mp, startblock),
1158             type, XFS_FSB_TO_AGBNO(mp, startblock),
1159             blockcount);
1160 
1161     if (XFS_TEST_ERROR(false, mp, XFS_ERRTAG_REFCOUNT_FINISH_ONE)) {
1162         error = -EIO;
1163         goto out_drop;
1164     }
1165 
1166     /*
1167      * If we haven't gotten a cursor or the cursor AG doesn't match
1168      * the startblock, get one now.
1169      */
1170     rcur = *pcur;
1171     if (rcur != NULL && rcur->bc_ag.pag != pag) {
1172         nr_ops = rcur->bc_ag.refc.nr_ops;
1173         shape_changes = rcur->bc_ag.refc.shape_changes;
1174         xfs_refcount_finish_one_cleanup(tp, rcur, 0);
1175         rcur = NULL;
1176         *pcur = NULL;
1177     }
1178     if (rcur == NULL) {
1179         error = xfs_alloc_read_agf(pag, tp, XFS_ALLOC_FLAG_FREEING,
1180                 &agbp);
1181         if (error)
1182             goto out_drop;
1183 
1184         rcur = xfs_refcountbt_init_cursor(mp, tp, agbp, pag);
1185         rcur->bc_ag.refc.nr_ops = nr_ops;
1186         rcur->bc_ag.refc.shape_changes = shape_changes;
1187     }
1188     *pcur = rcur;
1189 
1190     switch (type) {
1191     case XFS_REFCOUNT_INCREASE:
1192         error = xfs_refcount_adjust(rcur, bno, blockcount, &new_agbno,
1193                 new_len, XFS_REFCOUNT_ADJUST_INCREASE);
1194         *new_fsb = XFS_AGB_TO_FSB(mp, pag->pag_agno, new_agbno);
1195         break;
1196     case XFS_REFCOUNT_DECREASE:
1197         error = xfs_refcount_adjust(rcur, bno, blockcount, &new_agbno,
1198                 new_len, XFS_REFCOUNT_ADJUST_DECREASE);
1199         *new_fsb = XFS_AGB_TO_FSB(mp, pag->pag_agno, new_agbno);
1200         break;
1201     case XFS_REFCOUNT_ALLOC_COW:
1202         *new_fsb = startblock + blockcount;
1203         *new_len = 0;
1204         error = __xfs_refcount_cow_alloc(rcur, bno, blockcount);
1205         break;
1206     case XFS_REFCOUNT_FREE_COW:
1207         *new_fsb = startblock + blockcount;
1208         *new_len = 0;
1209         error = __xfs_refcount_cow_free(rcur, bno, blockcount);
1210         break;
1211     default:
1212         ASSERT(0);
1213         error = -EFSCORRUPTED;
1214     }
1215     if (!error && *new_len > 0)
1216         trace_xfs_refcount_finish_one_leftover(mp, pag->pag_agno, type,
1217                 bno, blockcount, new_agbno, *new_len);
1218 out_drop:
1219     xfs_perag_put(pag);
1220     return error;
1221 }
1222 
1223 /*
1224  * Record a refcount intent for later processing.
1225  */
1226 static void
1227 __xfs_refcount_add(
1228     struct xfs_trans        *tp,
1229     enum xfs_refcount_intent_type   type,
1230     xfs_fsblock_t           startblock,
1231     xfs_extlen_t            blockcount)
1232 {
1233     struct xfs_refcount_intent  *ri;
1234 
1235     trace_xfs_refcount_defer(tp->t_mountp,
1236             XFS_FSB_TO_AGNO(tp->t_mountp, startblock),
1237             type, XFS_FSB_TO_AGBNO(tp->t_mountp, startblock),
1238             blockcount);
1239 
1240     ri = kmem_cache_alloc(xfs_refcount_intent_cache,
1241             GFP_NOFS | __GFP_NOFAIL);
1242     INIT_LIST_HEAD(&ri->ri_list);
1243     ri->ri_type = type;
1244     ri->ri_startblock = startblock;
1245     ri->ri_blockcount = blockcount;
1246 
1247     xfs_defer_add(tp, XFS_DEFER_OPS_TYPE_REFCOUNT, &ri->ri_list);
1248 }
1249 
1250 /*
1251  * Increase the reference count of the blocks backing a file's extent.
1252  */
1253 void
1254 xfs_refcount_increase_extent(
1255     struct xfs_trans        *tp,
1256     struct xfs_bmbt_irec        *PREV)
1257 {
1258     if (!xfs_has_reflink(tp->t_mountp))
1259         return;
1260 
1261     __xfs_refcount_add(tp, XFS_REFCOUNT_INCREASE, PREV->br_startblock,
1262             PREV->br_blockcount);
1263 }
1264 
1265 /*
1266  * Decrease the reference count of the blocks backing a file's extent.
1267  */
1268 void
1269 xfs_refcount_decrease_extent(
1270     struct xfs_trans        *tp,
1271     struct xfs_bmbt_irec        *PREV)
1272 {
1273     if (!xfs_has_reflink(tp->t_mountp))
1274         return;
1275 
1276     __xfs_refcount_add(tp, XFS_REFCOUNT_DECREASE, PREV->br_startblock,
1277             PREV->br_blockcount);
1278 }
1279 
1280 /*
1281  * Given an AG extent, find the lowest-numbered run of shared blocks
1282  * within that range and return the range in fbno/flen.  If
1283  * find_end_of_shared is set, return the longest contiguous extent of
1284  * shared blocks; if not, just return the first extent we find.  If no
1285  * shared blocks are found, fbno and flen will be set to NULLAGBLOCK
1286  * and 0, respectively.
1287  */
1288 int
1289 xfs_refcount_find_shared(
1290     struct xfs_btree_cur        *cur,
1291     xfs_agblock_t           agbno,
1292     xfs_extlen_t            aglen,
1293     xfs_agblock_t           *fbno,
1294     xfs_extlen_t            *flen,
1295     bool                find_end_of_shared)
1296 {
1297     struct xfs_refcount_irec    tmp;
1298     int             i;
1299     int             have;
1300     int             error;
1301 
1302     trace_xfs_refcount_find_shared(cur->bc_mp, cur->bc_ag.pag->pag_agno,
1303             agbno, aglen);
1304 
1305     /* By default, skip the whole range */
1306     *fbno = NULLAGBLOCK;
1307     *flen = 0;
1308 
1309     /* Try to find a refcount extent that crosses the start */
1310     error = xfs_refcount_lookup_le(cur, agbno, &have);
1311     if (error)
1312         goto out_error;
1313     if (!have) {
1314         /* No left extent, look at the next one */
1315         error = xfs_btree_increment(cur, 0, &have);
1316         if (error)
1317             goto out_error;
1318         if (!have)
1319             goto done;
1320     }
1321     error = xfs_refcount_get_rec(cur, &tmp, &i);
1322     if (error)
1323         goto out_error;
1324     if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
1325         error = -EFSCORRUPTED;
1326         goto out_error;
1327     }
1328 
1329     /* If the extent ends before the start, look at the next one */
1330     if (tmp.rc_startblock + tmp.rc_blockcount <= agbno) {
1331         error = xfs_btree_increment(cur, 0, &have);
1332         if (error)
1333             goto out_error;
1334         if (!have)
1335             goto done;
1336         error = xfs_refcount_get_rec(cur, &tmp, &i);
1337         if (error)
1338             goto out_error;
1339         if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
1340             error = -EFSCORRUPTED;
1341             goto out_error;
1342         }
1343     }
1344 
1345     /* If the extent starts after the range we want, bail out */
1346     if (tmp.rc_startblock >= agbno + aglen)
1347         goto done;
1348 
1349     /* We found the start of a shared extent! */
1350     if (tmp.rc_startblock < agbno) {
1351         tmp.rc_blockcount -= (agbno - tmp.rc_startblock);
1352         tmp.rc_startblock = agbno;
1353     }
1354 
1355     *fbno = tmp.rc_startblock;
1356     *flen = min(tmp.rc_blockcount, agbno + aglen - *fbno);
1357     if (!find_end_of_shared)
1358         goto done;
1359 
1360     /* Otherwise, find the end of this shared extent */
1361     while (*fbno + *flen < agbno + aglen) {
1362         error = xfs_btree_increment(cur, 0, &have);
1363         if (error)
1364             goto out_error;
1365         if (!have)
1366             break;
1367         error = xfs_refcount_get_rec(cur, &tmp, &i);
1368         if (error)
1369             goto out_error;
1370         if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
1371             error = -EFSCORRUPTED;
1372             goto out_error;
1373         }
1374         if (tmp.rc_startblock >= agbno + aglen ||
1375             tmp.rc_startblock != *fbno + *flen)
1376             break;
1377         *flen = min(*flen + tmp.rc_blockcount, agbno + aglen - *fbno);
1378     }
1379 
1380 done:
1381     trace_xfs_refcount_find_shared_result(cur->bc_mp,
1382             cur->bc_ag.pag->pag_agno, *fbno, *flen);
1383 
1384 out_error:
1385     if (error)
1386         trace_xfs_refcount_find_shared_error(cur->bc_mp,
1387                 cur->bc_ag.pag->pag_agno, error, _RET_IP_);
1388     return error;
1389 }
1390 
1391 /*
1392  * Recovering CoW Blocks After a Crash
1393  *
1394  * Due to the way that the copy on write mechanism works, there's a window of
1395  * opportunity in which we can lose track of allocated blocks during a crash.
1396  * Because CoW uses delayed allocation in the in-core CoW fork, writeback
1397  * causes blocks to be allocated and stored in the CoW fork.  The blocks are
1398  * no longer in the free space btree but are not otherwise recorded anywhere
1399  * until the write completes and the blocks are mapped into the file.  A crash
1400  * in between allocation and remapping results in the replacement blocks being
1401  * lost.  This situation is exacerbated by the CoW extent size hint because
1402  * allocations can hang around for long time.
1403  *
1404  * However, there is a place where we can record these allocations before they
1405  * become mappings -- the reference count btree.  The btree does not record
1406  * extents with refcount == 1, so we can record allocations with a refcount of
1407  * 1.  Blocks being used for CoW writeout cannot be shared, so there should be
1408  * no conflict with shared block records.  These mappings should be created
1409  * when we allocate blocks to the CoW fork and deleted when they're removed
1410  * from the CoW fork.
1411  *
1412  * Minor nit: records for in-progress CoW allocations and records for shared
1413  * extents must never be merged, to preserve the property that (except for CoW
1414  * allocations) there are no refcount btree entries with refcount == 1.  The
1415  * only time this could potentially happen is when unsharing a block that's
1416  * adjacent to CoW allocations, so we must be careful to avoid this.
1417  *
1418  * At mount time we recover lost CoW allocations by searching the refcount
1419  * btree for these refcount == 1 mappings.  These represent CoW allocations
1420  * that were in progress at the time the filesystem went down, so we can free
1421  * them to get the space back.
1422  *
1423  * This mechanism is superior to creating EFIs for unmapped CoW extents for
1424  * several reasons -- first, EFIs pin the tail of the log and would have to be
1425  * periodically relogged to avoid filling up the log.  Second, CoW completions
1426  * will have to file an EFD and create new EFIs for whatever remains in the
1427  * CoW fork; this partially takes care of (1) but extent-size reservations
1428  * will have to periodically relog even if there's no writeout in progress.
1429  * This can happen if the CoW extent size hint is set, which you really want.
1430  * Third, EFIs cannot currently be automatically relogged into newer
1431  * transactions to advance the log tail.  Fourth, stuffing the log full of
1432  * EFIs places an upper bound on the number of CoW allocations that can be
1433  * held filesystem-wide at any given time.  Recording them in the refcount
1434  * btree doesn't require us to maintain any state in memory and doesn't pin
1435  * the log.
1436  */
1437 /*
1438  * Adjust the refcounts of CoW allocations.  These allocations are "magic"
1439  * in that they're not referenced anywhere else in the filesystem, so we
1440  * stash them in the refcount btree with a refcount of 1 until either file
1441  * remapping (or CoW cancellation) happens.
1442  */
1443 STATIC int
1444 xfs_refcount_adjust_cow_extents(
1445     struct xfs_btree_cur    *cur,
1446     xfs_agblock_t       agbno,
1447     xfs_extlen_t        aglen,
1448     enum xfs_refc_adjust_op adj)
1449 {
1450     struct xfs_refcount_irec    ext, tmp;
1451     int             error;
1452     int             found_rec, found_tmp;
1453 
1454     if (aglen == 0)
1455         return 0;
1456 
1457     /* Find any overlapping refcount records */
1458     error = xfs_refcount_lookup_ge(cur, agbno, &found_rec);
1459     if (error)
1460         goto out_error;
1461     error = xfs_refcount_get_rec(cur, &ext, &found_rec);
1462     if (error)
1463         goto out_error;
1464     if (!found_rec) {
1465         ext.rc_startblock = cur->bc_mp->m_sb.sb_agblocks +
1466                 XFS_REFC_COW_START;
1467         ext.rc_blockcount = 0;
1468         ext.rc_refcount = 0;
1469     }
1470 
1471     switch (adj) {
1472     case XFS_REFCOUNT_ADJUST_COW_ALLOC:
1473         /* Adding a CoW reservation, there should be nothing here. */
1474         if (XFS_IS_CORRUPT(cur->bc_mp,
1475                    agbno + aglen > ext.rc_startblock)) {
1476             error = -EFSCORRUPTED;
1477             goto out_error;
1478         }
1479 
1480         tmp.rc_startblock = agbno;
1481         tmp.rc_blockcount = aglen;
1482         tmp.rc_refcount = 1;
1483         trace_xfs_refcount_modify_extent(cur->bc_mp,
1484                 cur->bc_ag.pag->pag_agno, &tmp);
1485 
1486         error = xfs_refcount_insert(cur, &tmp,
1487                 &found_tmp);
1488         if (error)
1489             goto out_error;
1490         if (XFS_IS_CORRUPT(cur->bc_mp, found_tmp != 1)) {
1491             error = -EFSCORRUPTED;
1492             goto out_error;
1493         }
1494         break;
1495     case XFS_REFCOUNT_ADJUST_COW_FREE:
1496         /* Removing a CoW reservation, there should be one extent. */
1497         if (XFS_IS_CORRUPT(cur->bc_mp, ext.rc_startblock != agbno)) {
1498             error = -EFSCORRUPTED;
1499             goto out_error;
1500         }
1501         if (XFS_IS_CORRUPT(cur->bc_mp, ext.rc_blockcount != aglen)) {
1502             error = -EFSCORRUPTED;
1503             goto out_error;
1504         }
1505         if (XFS_IS_CORRUPT(cur->bc_mp, ext.rc_refcount != 1)) {
1506             error = -EFSCORRUPTED;
1507             goto out_error;
1508         }
1509 
1510         ext.rc_refcount = 0;
1511         trace_xfs_refcount_modify_extent(cur->bc_mp,
1512                 cur->bc_ag.pag->pag_agno, &ext);
1513         error = xfs_refcount_delete(cur, &found_rec);
1514         if (error)
1515             goto out_error;
1516         if (XFS_IS_CORRUPT(cur->bc_mp, found_rec != 1)) {
1517             error = -EFSCORRUPTED;
1518             goto out_error;
1519         }
1520         break;
1521     default:
1522         ASSERT(0);
1523     }
1524 
1525     return error;
1526 out_error:
1527     trace_xfs_refcount_modify_extent_error(cur->bc_mp,
1528             cur->bc_ag.pag->pag_agno, error, _RET_IP_);
1529     return error;
1530 }
1531 
1532 /*
1533  * Add or remove refcount btree entries for CoW reservations.
1534  */
1535 STATIC int
1536 xfs_refcount_adjust_cow(
1537     struct xfs_btree_cur    *cur,
1538     xfs_agblock_t       agbno,
1539     xfs_extlen_t        aglen,
1540     enum xfs_refc_adjust_op adj)
1541 {
1542     bool            shape_changed;
1543     int         error;
1544 
1545     agbno += XFS_REFC_COW_START;
1546 
1547     /*
1548      * Ensure that no rcextents cross the boundary of the adjustment range.
1549      */
1550     error = xfs_refcount_split_extent(cur, agbno, &shape_changed);
1551     if (error)
1552         goto out_error;
1553 
1554     error = xfs_refcount_split_extent(cur, agbno + aglen, &shape_changed);
1555     if (error)
1556         goto out_error;
1557 
1558     /*
1559      * Try to merge with the left or right extents of the range.
1560      */
1561     error = xfs_refcount_merge_extents(cur, &agbno, &aglen, adj,
1562             XFS_FIND_RCEXT_COW, &shape_changed);
1563     if (error)
1564         goto out_error;
1565 
1566     /* Now that we've taken care of the ends, adjust the middle extents */
1567     error = xfs_refcount_adjust_cow_extents(cur, agbno, aglen, adj);
1568     if (error)
1569         goto out_error;
1570 
1571     return 0;
1572 
1573 out_error:
1574     trace_xfs_refcount_adjust_cow_error(cur->bc_mp, cur->bc_ag.pag->pag_agno,
1575             error, _RET_IP_);
1576     return error;
1577 }
1578 
1579 /*
1580  * Record a CoW allocation in the refcount btree.
1581  */
1582 STATIC int
1583 __xfs_refcount_cow_alloc(
1584     struct xfs_btree_cur    *rcur,
1585     xfs_agblock_t       agbno,
1586     xfs_extlen_t        aglen)
1587 {
1588     trace_xfs_refcount_cow_increase(rcur->bc_mp, rcur->bc_ag.pag->pag_agno,
1589             agbno, aglen);
1590 
1591     /* Add refcount btree reservation */
1592     return xfs_refcount_adjust_cow(rcur, agbno, aglen,
1593             XFS_REFCOUNT_ADJUST_COW_ALLOC);
1594 }
1595 
1596 /*
1597  * Remove a CoW allocation from the refcount btree.
1598  */
1599 STATIC int
1600 __xfs_refcount_cow_free(
1601     struct xfs_btree_cur    *rcur,
1602     xfs_agblock_t       agbno,
1603     xfs_extlen_t        aglen)
1604 {
1605     trace_xfs_refcount_cow_decrease(rcur->bc_mp, rcur->bc_ag.pag->pag_agno,
1606             agbno, aglen);
1607 
1608     /* Remove refcount btree reservation */
1609     return xfs_refcount_adjust_cow(rcur, agbno, aglen,
1610             XFS_REFCOUNT_ADJUST_COW_FREE);
1611 }
1612 
1613 /* Record a CoW staging extent in the refcount btree. */
1614 void
1615 xfs_refcount_alloc_cow_extent(
1616     struct xfs_trans        *tp,
1617     xfs_fsblock_t           fsb,
1618     xfs_extlen_t            len)
1619 {
1620     struct xfs_mount        *mp = tp->t_mountp;
1621 
1622     if (!xfs_has_reflink(mp))
1623         return;
1624 
1625     __xfs_refcount_add(tp, XFS_REFCOUNT_ALLOC_COW, fsb, len);
1626 
1627     /* Add rmap entry */
1628     xfs_rmap_alloc_extent(tp, XFS_FSB_TO_AGNO(mp, fsb),
1629             XFS_FSB_TO_AGBNO(mp, fsb), len, XFS_RMAP_OWN_COW);
1630 }
1631 
1632 /* Forget a CoW staging event in the refcount btree. */
1633 void
1634 xfs_refcount_free_cow_extent(
1635     struct xfs_trans        *tp,
1636     xfs_fsblock_t           fsb,
1637     xfs_extlen_t            len)
1638 {
1639     struct xfs_mount        *mp = tp->t_mountp;
1640 
1641     if (!xfs_has_reflink(mp))
1642         return;
1643 
1644     /* Remove rmap entry */
1645     xfs_rmap_free_extent(tp, XFS_FSB_TO_AGNO(mp, fsb),
1646             XFS_FSB_TO_AGBNO(mp, fsb), len, XFS_RMAP_OWN_COW);
1647     __xfs_refcount_add(tp, XFS_REFCOUNT_FREE_COW, fsb, len);
1648 }
1649 
1650 struct xfs_refcount_recovery {
1651     struct list_head        rr_list;
1652     struct xfs_refcount_irec    rr_rrec;
1653 };
1654 
1655 /* Stuff an extent on the recovery list. */
1656 STATIC int
1657 xfs_refcount_recover_extent(
1658     struct xfs_btree_cur        *cur,
1659     const union xfs_btree_rec   *rec,
1660     void                *priv)
1661 {
1662     struct list_head        *debris = priv;
1663     struct xfs_refcount_recovery    *rr;
1664 
1665     if (XFS_IS_CORRUPT(cur->bc_mp,
1666                be32_to_cpu(rec->refc.rc_refcount) != 1))
1667         return -EFSCORRUPTED;
1668 
1669     rr = kmem_alloc(sizeof(struct xfs_refcount_recovery), 0);
1670     xfs_refcount_btrec_to_irec(rec, &rr->rr_rrec);
1671     list_add_tail(&rr->rr_list, debris);
1672 
1673     return 0;
1674 }
1675 
1676 /* Find and remove leftover CoW reservations. */
1677 int
1678 xfs_refcount_recover_cow_leftovers(
1679     struct xfs_mount        *mp,
1680     struct xfs_perag        *pag)
1681 {
1682     struct xfs_trans        *tp;
1683     struct xfs_btree_cur        *cur;
1684     struct xfs_buf          *agbp;
1685     struct xfs_refcount_recovery    *rr, *n;
1686     struct list_head        debris;
1687     union xfs_btree_irec        low;
1688     union xfs_btree_irec        high;
1689     xfs_fsblock_t           fsb;
1690     xfs_agblock_t           agbno;
1691     int             error;
1692 
1693     if (mp->m_sb.sb_agblocks >= XFS_REFC_COW_START)
1694         return -EOPNOTSUPP;
1695 
1696     INIT_LIST_HEAD(&debris);
1697 
1698     /*
1699      * In this first part, we use an empty transaction to gather up
1700      * all the leftover CoW extents so that we can subsequently
1701      * delete them.  The empty transaction is used to avoid
1702      * a buffer lock deadlock if there happens to be a loop in the
1703      * refcountbt because we're allowed to re-grab a buffer that is
1704      * already attached to our transaction.  When we're done
1705      * recording the CoW debris we cancel the (empty) transaction
1706      * and everything goes away cleanly.
1707      */
1708     error = xfs_trans_alloc_empty(mp, &tp);
1709     if (error)
1710         return error;
1711 
1712     error = xfs_alloc_read_agf(pag, tp, 0, &agbp);
1713     if (error)
1714         goto out_trans;
1715     cur = xfs_refcountbt_init_cursor(mp, tp, agbp, pag);
1716 
1717     /* Find all the leftover CoW staging extents. */
1718     memset(&low, 0, sizeof(low));
1719     memset(&high, 0, sizeof(high));
1720     low.rc.rc_startblock = XFS_REFC_COW_START;
1721     high.rc.rc_startblock = -1U;
1722     error = xfs_btree_query_range(cur, &low, &high,
1723             xfs_refcount_recover_extent, &debris);
1724     xfs_btree_del_cursor(cur, error);
1725     xfs_trans_brelse(tp, agbp);
1726     xfs_trans_cancel(tp);
1727     if (error)
1728         goto out_free;
1729 
1730     /* Now iterate the list to free the leftovers */
1731     list_for_each_entry_safe(rr, n, &debris, rr_list) {
1732         /* Set up transaction. */
1733         error = xfs_trans_alloc(mp, &M_RES(mp)->tr_write, 0, 0, 0, &tp);
1734         if (error)
1735             goto out_free;
1736 
1737         trace_xfs_refcount_recover_extent(mp, pag->pag_agno,
1738                 &rr->rr_rrec);
1739 
1740         /* Free the orphan record */
1741         agbno = rr->rr_rrec.rc_startblock - XFS_REFC_COW_START;
1742         fsb = XFS_AGB_TO_FSB(mp, pag->pag_agno, agbno);
1743         xfs_refcount_free_cow_extent(tp, fsb,
1744                 rr->rr_rrec.rc_blockcount);
1745 
1746         /* Free the block. */
1747         xfs_free_extent_later(tp, fsb, rr->rr_rrec.rc_blockcount, NULL);
1748 
1749         error = xfs_trans_commit(tp);
1750         if (error)
1751             goto out_free;
1752 
1753         list_del(&rr->rr_list);
1754         kmem_free(rr);
1755     }
1756 
1757     return error;
1758 out_trans:
1759     xfs_trans_cancel(tp);
1760 out_free:
1761     /* Free the leftover list */
1762     list_for_each_entry_safe(rr, n, &debris, rr_list) {
1763         list_del(&rr->rr_list);
1764         kmem_free(rr);
1765     }
1766     return error;
1767 }
1768 
1769 /* Is there a record covering a given extent? */
1770 int
1771 xfs_refcount_has_record(
1772     struct xfs_btree_cur    *cur,
1773     xfs_agblock_t       bno,
1774     xfs_extlen_t        len,
1775     bool            *exists)
1776 {
1777     union xfs_btree_irec    low;
1778     union xfs_btree_irec    high;
1779 
1780     memset(&low, 0, sizeof(low));
1781     low.rc.rc_startblock = bno;
1782     memset(&high, 0xFF, sizeof(high));
1783     high.rc.rc_startblock = bno + len - 1;
1784 
1785     return xfs_btree_has_record(cur, &low, &high, exists);
1786 }
1787 
1788 int __init
1789 xfs_refcount_intent_init_cache(void)
1790 {
1791     xfs_refcount_intent_cache = kmem_cache_create("xfs_refc_intent",
1792             sizeof(struct xfs_refcount_intent),
1793             0, 0, NULL);
1794 
1795     return xfs_refcount_intent_cache != NULL ? 0 : -ENOMEM;
1796 }
1797 
1798 void
1799 xfs_refcount_intent_destroy_cache(void)
1800 {
1801     kmem_cache_destroy(xfs_refcount_intent_cache);
1802     xfs_refcount_intent_cache = NULL;
1803 }
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!