fs/xfs/libxfs/xfs_rmap.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Copyright (c) 2014 Red Hat, Inc.
   4  * All Rights Reserved.
   5  */
   6 #include "xfs.h"
   7 #include "xfs_fs.h"
   8 #include "xfs_shared.h"
   9 #include "xfs_format.h"
  10 #include "xfs_log_format.h"
  11 #include "xfs_trans_resv.h"
  12 #include "xfs_bit.h"
  13 #include "xfs_mount.h"
  14 #include "xfs_sb.h"
  15 #include "xfs_defer.h"
  16 #include "xfs_btree.h"
  17 #include "xfs_trans.h"
  18 #include "xfs_alloc.h"
  19 #include "xfs_rmap.h"
  20 #include "xfs_rmap_btree.h"
  21 #include "xfs_trace.h"
  22 #include "xfs_errortag.h"
  23 #include "xfs_error.h"
  24 #include "xfs_inode.h"
  25 #include "xfs_ag.h"
  26
  27 struct kmem_cache       *xfs_rmap_intent_cache;
  28
  29 /*
  30  * Lookup the first record less than or equal to [bno, len, owner, offset]
  31  * in the btree given by cur.
  32  */
  33 int
  34 xfs_rmap_lookup_le(
  35         struct xfs_btree_cur    *cur,
  36         xfs_agblock_t           bno,
  37         uint64_t                owner,
  38         uint64_t                offset,
  39         unsigned int            flags,
  40         struct xfs_rmap_irec    *irec,
  41         int                     *stat)
  42 {
  43         int                     get_stat = 0;
  44         int                     error;
  45
  46         cur->bc_rec.r.rm_startblock = bno;
  47         cur->bc_rec.r.rm_blockcount = 0;
  48         cur->bc_rec.r.rm_owner = owner;
  49         cur->bc_rec.r.rm_offset = offset;
  50         cur->bc_rec.r.rm_flags = flags;
  51
  52         error = xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat);
  53         if (error || !(*stat) || !irec)
  54                 return error;
  55
  56         error = xfs_rmap_get_rec(cur, irec, &get_stat);
  57         if (error)
  58                 return error;
  59         if (!get_stat)
  60                 return -EFSCORRUPTED;
  61
  62         return 0;
  63 }
  64
  65 /*
  66  * Lookup the record exactly matching [bno, len, owner, offset]
  67  * in the btree given by cur.
  68  */
  69 int
  70 xfs_rmap_lookup_eq(
  71         struct xfs_btree_cur    *cur,
  72         xfs_agblock_t           bno,
  73         xfs_extlen_t            len,
  74         uint64_t                owner,
  75         uint64_t                offset,
  76         unsigned int            flags,
  77         int                     *stat)
  78 {
  79         cur->bc_rec.r.rm_startblock = bno;
  80         cur->bc_rec.r.rm_blockcount = len;
  81         cur->bc_rec.r.rm_owner = owner;
  82         cur->bc_rec.r.rm_offset = offset;
  83         cur->bc_rec.r.rm_flags = flags;
  84         return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat);
  85 }
  86
  87 /*
  88  * Update the record referred to by cur to the value given
  89  * by [bno, len, owner, offset].
  90  * This either works (return 0) or gets an EFSCORRUPTED error.
  91  */
  92 STATIC int
  93 xfs_rmap_update(
  94         struct xfs_btree_cur    *cur,
  95         struct xfs_rmap_irec    *irec)
  96 {
  97         union xfs_btree_rec     rec;
  98         int                     error;
  99
 100         trace_xfs_rmap_update(cur->bc_mp, cur->bc_ag.pag->pag_agno,
 101                         irec->rm_startblock, irec->rm_blockcount,
 102                         irec->rm_owner, irec->rm_offset, irec->rm_flags);
 103
 104         rec.rmap.rm_startblock = cpu_to_be32(irec->rm_startblock);
 105         rec.rmap.rm_blockcount = cpu_to_be32(irec->rm_blockcount);
 106         rec.rmap.rm_owner = cpu_to_be64(irec->rm_owner);
 107         rec.rmap.rm_offset = cpu_to_be64(
 108                         xfs_rmap_irec_offset_pack(irec));
 109         error = xfs_btree_update(cur, &rec);
 110         if (error)
 111                 trace_xfs_rmap_update_error(cur->bc_mp,
 112                                 cur->bc_ag.pag->pag_agno, error, _RET_IP_);
 113         return error;
 114 }
 115
 116 int
 117 xfs_rmap_insert(
 118         struct xfs_btree_cur    *rcur,
 119         xfs_agblock_t           agbno,
 120         xfs_extlen_t            len,
 121         uint64_t                owner,
 122         uint64_t                offset,
 123         unsigned int            flags)
 124 {
 125         int                     i;
 126         int                     error;
 127
 128         trace_xfs_rmap_insert(rcur->bc_mp, rcur->bc_ag.pag->pag_agno, agbno,
 129                         len, owner, offset, flags);
 130
 131         error = xfs_rmap_lookup_eq(rcur, agbno, len, owner, offset, flags, &i);
 132         if (error)
 133                 goto done;
 134         if (XFS_IS_CORRUPT(rcur->bc_mp, i != 0)) {
 135                 error = -EFSCORRUPTED;
 136                 goto done;
 137         }
 138
 139         rcur->bc_rec.r.rm_startblock = agbno;
 140         rcur->bc_rec.r.rm_blockcount = len;
 141         rcur->bc_rec.r.rm_owner = owner;
 142         rcur->bc_rec.r.rm_offset = offset;
 143         rcur->bc_rec.r.rm_flags = flags;
 144         error = xfs_btree_insert(rcur, &i);
 145         if (error)
 146                 goto done;
 147         if (XFS_IS_CORRUPT(rcur->bc_mp, i != 1)) {
 148                 error = -EFSCORRUPTED;
 149                 goto done;
 150         }
 151 done:
 152         if (error)
 153                 trace_xfs_rmap_insert_error(rcur->bc_mp,
 154                                 rcur->bc_ag.pag->pag_agno, error, _RET_IP_);
 155         return error;
 156 }
 157
 158 STATIC int
 159 xfs_rmap_delete(
 160         struct xfs_btree_cur    *rcur,
 161         xfs_agblock_t           agbno,
 162         xfs_extlen_t            len,
 163         uint64_t                owner,
 164         uint64_t                offset,
 165         unsigned int            flags)
 166 {
 167         int                     i;
 168         int                     error;
 169
 170         trace_xfs_rmap_delete(rcur->bc_mp, rcur->bc_ag.pag->pag_agno, agbno,
 171                         len, owner, offset, flags);
 172
 173         error = xfs_rmap_lookup_eq(rcur, agbno, len, owner, offset, flags, &i);
 174         if (error)
 175                 goto done;
 176         if (XFS_IS_CORRUPT(rcur->bc_mp, i != 1)) {
 177                 error = -EFSCORRUPTED;
 178                 goto done;
 179         }
 180
 181         error = xfs_btree_delete(rcur, &i);
 182         if (error)
 183                 goto done;
 184         if (XFS_IS_CORRUPT(rcur->bc_mp, i != 1)) {
 185                 error = -EFSCORRUPTED;
 186                 goto done;
 187         }
 188 done:
 189         if (error)
 190                 trace_xfs_rmap_delete_error(rcur->bc_mp,
 191                                 rcur->bc_ag.pag->pag_agno, error, _RET_IP_);
 192         return error;
 193 }
 194
 195 /* Convert an internal btree record to an rmap record. */
 196 int
 197 xfs_rmap_btrec_to_irec(
 198         const union xfs_btree_rec       *rec,
 199         struct xfs_rmap_irec            *irec)
 200 {
 201         irec->rm_startblock = be32_to_cpu(rec->rmap.rm_startblock);
 202         irec->rm_blockcount = be32_to_cpu(rec->rmap.rm_blockcount);
 203         irec->rm_owner = be64_to_cpu(rec->rmap.rm_owner);
 204         return xfs_rmap_irec_offset_unpack(be64_to_cpu(rec->rmap.rm_offset),
 205                         irec);
 206 }
 207
 208 /*
 209  * Get the data from the pointed-to record.
 210  */
 211 int
 212 xfs_rmap_get_rec(
 213         struct xfs_btree_cur    *cur,
 214         struct xfs_rmap_irec    *irec,
 215         int                     *stat)
 216 {
 217         struct xfs_mount        *mp = cur->bc_mp;
 218         xfs_agnumber_t          agno = cur->bc_ag.pag->pag_agno;
 219         union xfs_btree_rec     *rec;
 220         int                     error;
 221
 222         error = xfs_btree_get_rec(cur, &rec, stat);
 223         if (error || !*stat)
 224                 return error;
 225
 226         if (xfs_rmap_btrec_to_irec(rec, irec))
 227                 goto out_bad_rec;
 228
 229         if (irec->rm_blockcount == 0)
 230                 goto out_bad_rec;
 231         if (irec->rm_startblock <= XFS_AGFL_BLOCK(mp)) {
 232                 if (irec->rm_owner != XFS_RMAP_OWN_FS)
 233                         goto out_bad_rec;
 234                 if (irec->rm_blockcount != XFS_AGFL_BLOCK(mp) + 1)
 235                         goto out_bad_rec;
 236         } else {
 237                 /* check for valid extent range, including overflow */
 238                 if (!xfs_verify_agbno(mp, agno, irec->rm_startblock))
 239                         goto out_bad_rec;
 240                 if (irec->rm_startblock >
 241                                 irec->rm_startblock + irec->rm_blockcount)
 242                         goto out_bad_rec;
 243                 if (!xfs_verify_agbno(mp, agno,
 244                                 irec->rm_startblock + irec->rm_blockcount - 1))
 245                         goto out_bad_rec;
 246         }
 247
 248         if (!(xfs_verify_ino(mp, irec->rm_owner) ||
 249               (irec->rm_owner <= XFS_RMAP_OWN_FS &&
 250                irec->rm_owner >= XFS_RMAP_OWN_MIN)))
 251                 goto out_bad_rec;
 252
 253         return 0;
 254 out_bad_rec:
 255         xfs_warn(mp,
 256                 "Reverse Mapping BTree record corruption in AG %d detected!",
 257                 agno);
 258         xfs_warn(mp,
 259                 "Owner 0x%llx, flags 0x%x, start block 0x%x block count 0x%x",
 260                 irec->rm_owner, irec->rm_flags, irec->rm_startblock,
 261                 irec->rm_blockcount);
 262         return -EFSCORRUPTED;
 263 }
 264
 265 struct xfs_find_left_neighbor_info {
 266         struct xfs_rmap_irec    high;
 267         struct xfs_rmap_irec    *irec;
 268 };
 269
 270 /* For each rmap given, figure out if it matches the key we want. */
 271 STATIC int
 272 xfs_rmap_find_left_neighbor_helper(
 273         struct xfs_btree_cur            *cur,
 274         const struct xfs_rmap_irec      *rec,
 275         void                            *priv)
 276 {
 277         struct xfs_find_left_neighbor_info      *info = priv;
 278
 279         trace_xfs_rmap_find_left_neighbor_candidate(cur->bc_mp,
 280                         cur->bc_ag.pag->pag_agno, rec->rm_startblock,
 281                         rec->rm_blockcount, rec->rm_owner, rec->rm_offset,
 282                         rec->rm_flags);
 283
 284         if (rec->rm_owner != info->high.rm_owner)
 285                 return 0;
 286         if (!XFS_RMAP_NON_INODE_OWNER(rec->rm_owner) &&
 287             !(rec->rm_flags & XFS_RMAP_BMBT_BLOCK) &&
 288             rec->rm_offset + rec->rm_blockcount - 1 != info->high.rm_offset)
 289                 return 0;
 290
 291         *info->irec = *rec;
 292         return -ECANCELED;
 293 }
 294
 295 /*
 296  * Find the record to the left of the given extent, being careful only to
 297  * return a match with the same owner and adjacent physical and logical
 298  * block ranges.
 299  */
 300 STATIC int
 301 xfs_rmap_find_left_neighbor(
 302         struct xfs_btree_cur    *cur,
 303         xfs_agblock_t           bno,
 304         uint64_t                owner,
 305         uint64_t                offset,
 306         unsigned int            flags,
 307         struct xfs_rmap_irec    *irec,
 308         int                     *stat)
 309 {
 310         struct xfs_find_left_neighbor_info      info;
 311         int                     found = 0;
 312         int                     error;
 313
 314         *stat = 0;
 315         if (bno == 0)
 316                 return 0;
 317         info.high.rm_startblock = bno - 1;
 318         info.high.rm_owner = owner;
 319         if (!XFS_RMAP_NON_INODE_OWNER(owner) &&
 320             !(flags & XFS_RMAP_BMBT_BLOCK)) {
 321                 if (offset == 0)
 322                         return 0;
 323                 info.high.rm_offset = offset - 1;
 324         } else
 325                 info.high.rm_offset = 0;
 326         info.high.rm_flags = flags;
 327         info.high.rm_blockcount = 0;
 328         info.irec = irec;
 329
 330         trace_xfs_rmap_find_left_neighbor_query(cur->bc_mp,
 331                         cur->bc_ag.pag->pag_agno, bno, 0, owner, offset, flags);
 332
 333         /*
 334          * Historically, we always used the range query to walk every reverse
 335          * mapping that could possibly overlap the key that the caller asked
 336          * for, and filter out the ones that don't.  That is very slow when
 337          * there are a lot of records.
 338          *
 339          * However, there are two scenarios where the classic btree search can
 340          * produce correct results -- if the index contains a record that is an
 341          * exact match for the lookup key; and if there are no other records
 342          * between the record we want and the key we supplied.
 343          *
 344          * As an optimization, try a non-overlapped lookup first.  This makes
 345          * extent conversion and remap operations run a bit faster if the
 346          * physical extents aren't being shared.  If we don't find what we
 347          * want, we fall back to the overlapped query.
 348          */
 349         error = xfs_rmap_lookup_le(cur, bno, owner, offset, flags, irec,
 350                         &found);
 351         if (error)
 352                 return error;
 353         if (found)
 354                 error = xfs_rmap_find_left_neighbor_helper(cur, irec, &info);
 355         if (!error)
 356                 error = xfs_rmap_query_range(cur, &info.high, &info.high,
 357                                 xfs_rmap_find_left_neighbor_helper, &info);
 358         if (error != -ECANCELED)
 359                 return error;
 360
 361         *stat = 1;
 362         trace_xfs_rmap_find_left_neighbor_result(cur->bc_mp,
 363                         cur->bc_ag.pag->pag_agno, irec->rm_startblock,
 364                         irec->rm_blockcount, irec->rm_owner, irec->rm_offset,
 365                         irec->rm_flags);
 366         return 0;
 367 }
 368
 369 /* For each rmap given, figure out if it matches the key we want. */
 370 STATIC int
 371 xfs_rmap_lookup_le_range_helper(
 372         struct xfs_btree_cur            *cur,
 373         const struct xfs_rmap_irec      *rec,
 374         void                            *priv)
 375 {
 376         struct xfs_find_left_neighbor_info      *info = priv;
 377
 378         trace_xfs_rmap_lookup_le_range_candidate(cur->bc_mp,
 379                         cur->bc_ag.pag->pag_agno, rec->rm_startblock,
 380                         rec->rm_blockcount, rec->rm_owner, rec->rm_offset,
 381                         rec->rm_flags);
 382
 383         if (rec->rm_owner != info->high.rm_owner)
 384                 return 0;
 385         if (!XFS_RMAP_NON_INODE_OWNER(rec->rm_owner) &&
 386             !(rec->rm_flags & XFS_RMAP_BMBT_BLOCK) &&
 387             (rec->rm_offset > info->high.rm_offset ||
 388              rec->rm_offset + rec->rm_blockcount <= info->high.rm_offset))
 389                 return 0;
 390
 391         *info->irec = *rec;
 392         return -ECANCELED;
 393 }
 394
 395 /*
 396  * Find the record to the left of the given extent, being careful only to
 397  * return a match with the same owner and overlapping physical and logical
 398  * block ranges.  This is the overlapping-interval version of
 399  * xfs_rmap_lookup_le.
 400  */
 401 int
 402 xfs_rmap_lookup_le_range(
 403         struct xfs_btree_cur    *cur,
 404         xfs_agblock_t           bno,
 405         uint64_t                owner,
 406         uint64_t                offset,
 407         unsigned int            flags,
 408         struct xfs_rmap_irec    *irec,
 409         int                     *stat)
 410 {
 411         struct xfs_find_left_neighbor_info      info;
 412         int                     found = 0;
 413         int                     error;
 414
 415         info.high.rm_startblock = bno;
 416         info.high.rm_owner = owner;
 417         if (!XFS_RMAP_NON_INODE_OWNER(owner) && !(flags & XFS_RMAP_BMBT_BLOCK))
 418                 info.high.rm_offset = offset;
 419         else
 420                 info.high.rm_offset = 0;
 421         info.high.rm_flags = flags;
 422         info.high.rm_blockcount = 0;
 423         *stat = 0;
 424         info.irec = irec;
 425
 426         trace_xfs_rmap_lookup_le_range(cur->bc_mp, cur->bc_ag.pag->pag_agno,
 427                         bno, 0, owner, offset, flags);
 428
 429         /*
 430          * Historically, we always used the range query to walk every reverse
 431          * mapping that could possibly overlap the key that the caller asked
 432          * for, and filter out the ones that don't.  That is very slow when
 433          * there are a lot of records.
 434          *
 435          * However, there are two scenarios where the classic btree search can
 436          * produce correct results -- if the index contains a record that is an
 437          * exact match for the lookup key; and if there are no other records
 438          * between the record we want and the key we supplied.
 439          *
 440          * As an optimization, try a non-overlapped lookup first.  This makes
 441          * scrub run much faster on most filesystems because bmbt records are
 442          * usually an exact match for rmap records.  If we don't find what we
 443          * want, we fall back to the overlapped query.
 444          */
 445         error = xfs_rmap_lookup_le(cur, bno, owner, offset, flags, irec,
 446                         &found);
 447         if (error)
 448                 return error;
 449         if (found)
 450                 error = xfs_rmap_lookup_le_range_helper(cur, irec, &info);
 451         if (!error)
 452                 error = xfs_rmap_query_range(cur, &info.high, &info.high,
 453                                 xfs_rmap_lookup_le_range_helper, &info);
 454         if (error != -ECANCELED)
 455                 return error;
 456
 457         *stat = 1;
 458         trace_xfs_rmap_lookup_le_range_result(cur->bc_mp,
 459                         cur->bc_ag.pag->pag_agno, irec->rm_startblock,
 460                         irec->rm_blockcount, irec->rm_owner, irec->rm_offset,
 461                         irec->rm_flags);
 462         return 0;
 463 }
 464
 465 /*
 466  * Perform all the relevant owner checks for a removal op.  If we're doing an
 467  * unknown-owner removal then we have no owner information to check.
 468  */
 469 static int
 470 xfs_rmap_free_check_owner(
 471         struct xfs_mount        *mp,
 472         uint64_t                ltoff,
 473         struct xfs_rmap_irec    *rec,
 474         xfs_filblks_t           len,
 475         uint64_t                owner,
 476         uint64_t                offset,
 477         unsigned int            flags)
 478 {
 479         int                     error = 0;
 480
 481         if (owner == XFS_RMAP_OWN_UNKNOWN)
 482                 return 0;
 483
 484         /* Make sure the unwritten flag matches. */
 485         if (XFS_IS_CORRUPT(mp,
 486                            (flags & XFS_RMAP_UNWRITTEN) !=
 487                            (rec->rm_flags & XFS_RMAP_UNWRITTEN))) {
 488                 error = -EFSCORRUPTED;
 489                 goto out;
 490         }
 491
 492         /* Make sure the owner matches what we expect to find in the tree. */
 493         if (XFS_IS_CORRUPT(mp, owner != rec->rm_owner)) {
 494                 error = -EFSCORRUPTED;
 495                 goto out;
 496         }
 497
 498         /* Check the offset, if necessary. */
 499         if (XFS_RMAP_NON_INODE_OWNER(owner))
 500                 goto out;
 501
 502         if (flags & XFS_RMAP_BMBT_BLOCK) {
 503                 if (XFS_IS_CORRUPT(mp,
 504                                    !(rec->rm_flags & XFS_RMAP_BMBT_BLOCK))) {
 505                         error = -EFSCORRUPTED;
 506                         goto out;
 507                 }
 508         } else {
 509                 if (XFS_IS_CORRUPT(mp, rec->rm_offset > offset)) {
 510                         error = -EFSCORRUPTED;
 511                         goto out;
 512                 }
 513                 if (XFS_IS_CORRUPT(mp,
 514                                    offset + len > ltoff + rec->rm_blockcount)) {
 515                         error = -EFSCORRUPTED;
 516                         goto out;
 517                 }
 518         }
 519
 520 out:
 521         return error;
 522 }
 523
 524 /*
 525  * Find the extent in the rmap btree and remove it.
 526  *
 527  * The record we find should always be an exact match for the extent that we're
 528  * looking for, since we insert them into the btree without modification.
 529  *
 530  * Special Case #1: when growing the filesystem, we "free" an extent when
 531  * growing the last AG. This extent is new space and so it is not tracked as
 532  * used space in the btree. The growfs code will pass in an owner of
 533  * XFS_RMAP_OWN_NULL to indicate that it expected that there is no owner of this
 534  * extent. We verify that - the extent lookup result in a record that does not
 535  * overlap.
 536  *
 537  * Special Case #2: EFIs do not record the owner of the extent, so when
 538  * recovering EFIs from the log we pass in XFS_RMAP_OWN_UNKNOWN to tell the rmap
 539  * btree to ignore the owner (i.e. wildcard match) so we don't trigger
 540  * corruption checks during log recovery.
 541  */
 542 STATIC int
 543 xfs_rmap_unmap(
 544         struct xfs_btree_cur            *cur,
 545         xfs_agblock_t                   bno,
 546         xfs_extlen_t                    len,
 547         bool                            unwritten,
 548         const struct xfs_owner_info     *oinfo)
 549 {
 550         struct xfs_mount                *mp = cur->bc_mp;
 551         struct xfs_rmap_irec            ltrec;
 552         uint64_t                        ltoff;
 553         int                             error = 0;
 554         int                             i;
 555         uint64_t                        owner;
 556         uint64_t                        offset;
 557         unsigned int                    flags;
 558         bool                            ignore_off;
 559
 560         xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
 561         ignore_off = XFS_RMAP_NON_INODE_OWNER(owner) ||
 562                         (flags & XFS_RMAP_BMBT_BLOCK);
 563         if (unwritten)
 564                 flags |= XFS_RMAP_UNWRITTEN;
 565         trace_xfs_rmap_unmap(mp, cur->bc_ag.pag->pag_agno, bno, len,
 566                         unwritten, oinfo);
 567
 568         /*
 569          * We should always have a left record because there's a static record
 570          * for the AG headers at rm_startblock == 0 created by mkfs/growfs that
 571          * will not ever be removed from the tree.
 572          */
 573         error = xfs_rmap_lookup_le(cur, bno, owner, offset, flags, &ltrec, &i);
 574         if (error)
 575                 goto out_error;
 576         if (XFS_IS_CORRUPT(mp, i != 1)) {
 577                 error = -EFSCORRUPTED;
 578                 goto out_error;
 579         }
 580
 581         trace_xfs_rmap_lookup_le_range_result(cur->bc_mp,
 582                         cur->bc_ag.pag->pag_agno, ltrec.rm_startblock,
 583                         ltrec.rm_blockcount, ltrec.rm_owner,
 584                         ltrec.rm_offset, ltrec.rm_flags);
 585         ltoff = ltrec.rm_offset;
 586
 587         /*
 588          * For growfs, the incoming extent must be beyond the left record we
 589          * just found as it is new space and won't be used by anyone. This is
 590          * just a corruption check as we don't actually do anything with this
 591          * extent.  Note that we need to use >= instead of > because it might
 592          * be the case that the "left" extent goes all the way to EOFS.
 593          */
 594         if (owner == XFS_RMAP_OWN_NULL) {
 595                 if (XFS_IS_CORRUPT(mp,
 596                                    bno <
 597                                    ltrec.rm_startblock + ltrec.rm_blockcount)) {
 598                         error = -EFSCORRUPTED;
 599                         goto out_error;
 600                 }
 601                 goto out_done;
 602         }
 603
 604         /*
 605          * If we're doing an unknown-owner removal for EFI recovery, we expect
 606          * to find the full range in the rmapbt or nothing at all.  If we
 607          * don't find any rmaps overlapping either end of the range, we're
 608          * done.  Hopefully this means that the EFI creator already queued
 609          * (and finished) a RUI to remove the rmap.
 610          */
 611         if (owner == XFS_RMAP_OWN_UNKNOWN &&
 612             ltrec.rm_startblock + ltrec.rm_blockcount <= bno) {
 613                 struct xfs_rmap_irec    rtrec;
 614
 615                 error = xfs_btree_increment(cur, 0, &i);
 616                 if (error)
 617                         goto out_error;
 618                 if (i == 0)
 619                         goto out_done;
 620                 error = xfs_rmap_get_rec(cur, &rtrec, &i);
 621                 if (error)
 622                         goto out_error;
 623                 if (XFS_IS_CORRUPT(mp, i != 1)) {
 624                         error = -EFSCORRUPTED;
 625                         goto out_error;
 626                 }
 627                 if (rtrec.rm_startblock >= bno + len)
 628                         goto out_done;
 629         }
 630
 631         /* Make sure the extent we found covers the entire freeing range. */
 632         if (XFS_IS_CORRUPT(mp,
 633                            ltrec.rm_startblock > bno ||
 634                            ltrec.rm_startblock + ltrec.rm_blockcount <
 635                            bno + len)) {
 636                 error = -EFSCORRUPTED;
 637                 goto out_error;
 638         }
 639
 640         /* Check owner information. */
 641         error = xfs_rmap_free_check_owner(mp, ltoff, &ltrec, len, owner,
 642                         offset, flags);
 643         if (error)
 644                 goto out_error;
 645
 646         if (ltrec.rm_startblock == bno && ltrec.rm_blockcount == len) {
 647                 /* exact match, simply remove the record from rmap tree */
 648                 trace_xfs_rmap_delete(mp, cur->bc_ag.pag->pag_agno,
 649                                 ltrec.rm_startblock, ltrec.rm_blockcount,
 650                                 ltrec.rm_owner, ltrec.rm_offset,
 651                                 ltrec.rm_flags);
 652                 error = xfs_btree_delete(cur, &i);
 653                 if (error)
 654                         goto out_error;
 655                 if (XFS_IS_CORRUPT(mp, i != 1)) {
 656                         error = -EFSCORRUPTED;
 657                         goto out_error;
 658                 }
 659         } else if (ltrec.rm_startblock == bno) {
 660                 /*
 661                  * overlap left hand side of extent: move the start, trim the
 662                  * length and update the current record.
 663                  *
 664                  *       ltbno                ltlen
 665                  * Orig:    |oooooooooooooooooooo|
 666                  * Freeing: |fffffffff|
 667                  * Result:            |rrrrrrrrrr|
 668                  *         bno       len
 669                  */
 670                 ltrec.rm_startblock += len;
 671                 ltrec.rm_blockcount -= len;
 672                 if (!ignore_off)
 673                         ltrec.rm_offset += len;
 674                 error = xfs_rmap_update(cur, &ltrec);
 675                 if (error)
 676                         goto out_error;
 677         } else if (ltrec.rm_startblock + ltrec.rm_blockcount == bno + len) {
 678                 /*
 679                  * overlap right hand side of extent: trim the length and update
 680                  * the current record.
 681                  *
 682                  *       ltbno                ltlen
 683                  * Orig:    |oooooooooooooooooooo|
 684                  * Freeing:            |fffffffff|
 685                  * Result:  |rrrrrrrrrr|
 686                  *                    bno       len
 687                  */
 688                 ltrec.rm_blockcount -= len;
 689                 error = xfs_rmap_update(cur, &ltrec);
 690                 if (error)
 691                         goto out_error;
 692         } else {
 693
 694                 /*
 695                  * overlap middle of extent: trim the length of the existing
 696                  * record to the length of the new left-extent size, increment
 697                  * the insertion position so we can insert a new record
 698                  * containing the remaining right-extent space.
 699                  *
 700                  *       ltbno                ltlen
 701                  * Orig:    |oooooooooooooooooooo|
 702                  * Freeing:       |fffffffff|
 703                  * Result:  |rrrrr|         |rrrr|
 704                  *               bno       len
 705                  */
 706                 xfs_extlen_t    orig_len = ltrec.rm_blockcount;
 707
 708                 ltrec.rm_blockcount = bno - ltrec.rm_startblock;
 709                 error = xfs_rmap_update(cur, &ltrec);
 710                 if (error)
 711                         goto out_error;
 712
 713                 error = xfs_btree_increment(cur, 0, &i);
 714                 if (error)
 715                         goto out_error;
 716
 717                 cur->bc_rec.r.rm_startblock = bno + len;
 718                 cur->bc_rec.r.rm_blockcount = orig_len - len -
 719                                                      ltrec.rm_blockcount;
 720                 cur->bc_rec.r.rm_owner = ltrec.rm_owner;
 721                 if (ignore_off)
 722                         cur->bc_rec.r.rm_offset = 0;
 723                 else
 724                         cur->bc_rec.r.rm_offset = offset + len;
 725                 cur->bc_rec.r.rm_flags = flags;
 726                 trace_xfs_rmap_insert(mp, cur->bc_ag.pag->pag_agno,
 727                                 cur->bc_rec.r.rm_startblock,
 728                                 cur->bc_rec.r.rm_blockcount,
 729                                 cur->bc_rec.r.rm_owner,
 730                                 cur->bc_rec.r.rm_offset,
 731                                 cur->bc_rec.r.rm_flags);
 732                 error = xfs_btree_insert(cur, &i);
 733                 if (error)
 734                         goto out_error;
 735         }
 736
 737 out_done:
 738         trace_xfs_rmap_unmap_done(mp, cur->bc_ag.pag->pag_agno, bno, len,
 739                         unwritten, oinfo);
 740 out_error:
 741         if (error)
 742                 trace_xfs_rmap_unmap_error(mp, cur->bc_ag.pag->pag_agno,
 743                                 error, _RET_IP_);
 744         return error;
 745 }
 746
 747 /*
 748  * Remove a reference to an extent in the rmap btree.
 749  */
 750 int
 751 xfs_rmap_free(
 752         struct xfs_trans                *tp,
 753         struct xfs_buf                  *agbp,
 754         struct xfs_perag                *pag,
 755         xfs_agblock_t                   bno,
 756         xfs_extlen_t                    len,
 757         const struct xfs_owner_info     *oinfo)
 758 {
 759         struct xfs_mount                *mp = tp->t_mountp;
 760         struct xfs_btree_cur            *cur;
 761         int                             error;
 762
 763         if (!xfs_has_rmapbt(mp))
 764                 return 0;
 765
 766         cur = xfs_rmapbt_init_cursor(mp, tp, agbp, pag);
 767
 768         error = xfs_rmap_unmap(cur, bno, len, false, oinfo);
 769
 770         xfs_btree_del_cursor(cur, error);
 771         return error;
 772 }
 773
 774 /*
 775  * A mergeable rmap must have the same owner and the same values for
 776  * the unwritten, attr_fork, and bmbt flags.  The startblock and
 777  * offset are checked separately.
 778  */
 779 static bool
 780 xfs_rmap_is_mergeable(
 781         struct xfs_rmap_irec    *irec,
 782         uint64_t                owner,
 783         unsigned int            flags)
 784 {
 785         if (irec->rm_owner == XFS_RMAP_OWN_NULL)
 786                 return false;
 787         if (irec->rm_owner != owner)
 788                 return false;
 789         if ((flags & XFS_RMAP_UNWRITTEN) ^
 790             (irec->rm_flags & XFS_RMAP_UNWRITTEN))
 791                 return false;
 792         if ((flags & XFS_RMAP_ATTR_FORK) ^
 793             (irec->rm_flags & XFS_RMAP_ATTR_FORK))
 794                 return false;
 795         if ((flags & XFS_RMAP_BMBT_BLOCK) ^
 796             (irec->rm_flags & XFS_RMAP_BMBT_BLOCK))
 797                 return false;
 798         return true;
 799 }
 800
 801 /*
 802  * When we allocate a new block, the first thing we do is add a reference to
 803  * the extent in the rmap btree. This takes the form of a [agbno, length,
 804  * owner, offset] record.  Flags are encoded in the high bits of the offset
 805  * field.
 806  */
 807 STATIC int
 808 xfs_rmap_map(
 809         struct xfs_btree_cur            *cur,
 810         xfs_agblock_t                   bno,
 811         xfs_extlen_t                    len,
 812         bool                            unwritten,
 813         const struct xfs_owner_info     *oinfo)
 814 {
 815         struct xfs_mount                *mp = cur->bc_mp;
 816         struct xfs_rmap_irec            ltrec;
 817         struct xfs_rmap_irec            gtrec;
 818         int                             have_gt;
 819         int                             have_lt;
 820         int                             error = 0;
 821         int                             i;
 822         uint64_t                        owner;
 823         uint64_t                        offset;
 824         unsigned int                    flags = 0;
 825         bool                            ignore_off;
 826
 827         xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
 828         ASSERT(owner != 0);
 829         ignore_off = XFS_RMAP_NON_INODE_OWNER(owner) ||
 830                         (flags & XFS_RMAP_BMBT_BLOCK);
 831         if (unwritten)
 832                 flags |= XFS_RMAP_UNWRITTEN;
 833         trace_xfs_rmap_map(mp, cur->bc_ag.pag->pag_agno, bno, len,
 834                         unwritten, oinfo);
 835         ASSERT(!xfs_rmap_should_skip_owner_update(oinfo));
 836
 837         /*
 838          * For the initial lookup, look for an exact match or the left-adjacent
 839          * record for our insertion point. This will also give us the record for
 840          * start block contiguity tests.
 841          */
 842         error = xfs_rmap_lookup_le(cur, bno, owner, offset, flags, &ltrec,
 843                         &have_lt);
 844         if (error)
 845                 goto out_error;
 846         if (have_lt) {
 847                 trace_xfs_rmap_lookup_le_range_result(cur->bc_mp,
 848                                 cur->bc_ag.pag->pag_agno, ltrec.rm_startblock,
 849                                 ltrec.rm_blockcount, ltrec.rm_owner,
 850                                 ltrec.rm_offset, ltrec.rm_flags);
 851
 852                 if (!xfs_rmap_is_mergeable(&ltrec, owner, flags))
 853                         have_lt = 0;
 854         }
 855
 856         if (XFS_IS_CORRUPT(mp,
 857                            have_lt != 0 &&
 858                            ltrec.rm_startblock + ltrec.rm_blockcount > bno)) {
 859                 error = -EFSCORRUPTED;
 860                 goto out_error;
 861         }
 862
 863         /*
 864          * Increment the cursor to see if we have a right-adjacent record to our
 865          * insertion point. This will give us the record for end block
 866          * contiguity tests.
 867          */
 868         error = xfs_btree_increment(cur, 0, &have_gt);
 869         if (error)
 870                 goto out_error;
 871         if (have_gt) {
 872                 error = xfs_rmap_get_rec(cur, &gtrec, &have_gt);
 873                 if (error)
 874                         goto out_error;
 875                 if (XFS_IS_CORRUPT(mp, have_gt != 1)) {
 876                         error = -EFSCORRUPTED;
 877                         goto out_error;
 878                 }
 879                 if (XFS_IS_CORRUPT(mp, bno + len > gtrec.rm_startblock)) {
 880                         error = -EFSCORRUPTED;
 881                         goto out_error;
 882                 }
 883                 trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp,
 884                         cur->bc_ag.pag->pag_agno, gtrec.rm_startblock,
 885                         gtrec.rm_blockcount, gtrec.rm_owner,
 886                         gtrec.rm_offset, gtrec.rm_flags);
 887                 if (!xfs_rmap_is_mergeable(&gtrec, owner, flags))
 888                         have_gt = 0;
 889         }
 890
 891         /*
 892          * Note: cursor currently points one record to the right of ltrec, even
 893          * if there is no record in the tree to the right.
 894          */
 895         if (have_lt &&
 896             ltrec.rm_startblock + ltrec.rm_blockcount == bno &&
 897             (ignore_off || ltrec.rm_offset + ltrec.rm_blockcount == offset)) {
 898                 /*
 899                  * left edge contiguous, merge into left record.
 900                  *
 901                  *       ltbno     ltlen
 902                  * orig:   |ooooooooo|
 903                  * adding:           |aaaaaaaaa|
 904                  * result: |rrrrrrrrrrrrrrrrrrr|
 905                  *                  bno       len
 906                  */
 907                 ltrec.rm_blockcount += len;
 908                 if (have_gt &&
 909                     bno + len == gtrec.rm_startblock &&
 910                     (ignore_off || offset + len == gtrec.rm_offset) &&
 911                     (unsigned long)ltrec.rm_blockcount + len +
 912                                 gtrec.rm_blockcount <= XFS_RMAP_LEN_MAX) {
 913                         /*
 914                          * right edge also contiguous, delete right record
 915                          * and merge into left record.
 916                          *
 917                          *       ltbno     ltlen    gtbno     gtlen
 918                          * orig:   |ooooooooo|         |ooooooooo|
 919                          * adding:           |aaaaaaaaa|
 920                          * result: |rrrrrrrrrrrrrrrrrrrrrrrrrrrrr|
 921                          */
 922                         ltrec.rm_blockcount += gtrec.rm_blockcount;
 923                         trace_xfs_rmap_delete(mp, cur->bc_ag.pag->pag_agno,
 924                                         gtrec.rm_startblock,
 925                                         gtrec.rm_blockcount,
 926                                         gtrec.rm_owner,
 927                                         gtrec.rm_offset,
 928                                         gtrec.rm_flags);
 929                         error = xfs_btree_delete(cur, &i);
 930                         if (error)
 931                                 goto out_error;
 932                         if (XFS_IS_CORRUPT(mp, i != 1)) {
 933                                 error = -EFSCORRUPTED;
 934                                 goto out_error;
 935                         }
 936                 }
 937
 938                 /* point the cursor back to the left record and update */
 939                 error = xfs_btree_decrement(cur, 0, &have_gt);
 940                 if (error)
 941                         goto out_error;
 942                 error = xfs_rmap_update(cur, &ltrec);
 943                 if (error)
 944                         goto out_error;
 945         } else if (have_gt &&
 946                    bno + len == gtrec.rm_startblock &&
 947                    (ignore_off || offset + len == gtrec.rm_offset)) {
 948                 /*
 949                  * right edge contiguous, merge into right record.
 950                  *
 951                  *                 gtbno     gtlen
 952                  * Orig:             |ooooooooo|
 953                  * adding: |aaaaaaaaa|
 954                  * Result: |rrrrrrrrrrrrrrrrrrr|
 955                  *        bno       len
 956                  */
 957                 gtrec.rm_startblock = bno;
 958                 gtrec.rm_blockcount += len;
 959                 if (!ignore_off)
 960                         gtrec.rm_offset = offset;
 961                 error = xfs_rmap_update(cur, &gtrec);
 962                 if (error)
 963                         goto out_error;
 964         } else {
 965                 /*
 966                  * no contiguous edge with identical owner, insert
 967                  * new record at current cursor position.
 968                  */
 969                 cur->bc_rec.r.rm_startblock = bno;
 970                 cur->bc_rec.r.rm_blockcount = len;
 971                 cur->bc_rec.r.rm_owner = owner;
 972                 cur->bc_rec.r.rm_offset = offset;
 973                 cur->bc_rec.r.rm_flags = flags;
 974                 trace_xfs_rmap_insert(mp, cur->bc_ag.pag->pag_agno, bno, len,
 975                         owner, offset, flags);
 976                 error = xfs_btree_insert(cur, &i);
 977                 if (error)
 978                         goto out_error;
 979                 if (XFS_IS_CORRUPT(mp, i != 1)) {
 980                         error = -EFSCORRUPTED;
 981                         goto out_error;
 982                 }
 983         }
 984
 985         trace_xfs_rmap_map_done(mp, cur->bc_ag.pag->pag_agno, bno, len,
 986                         unwritten, oinfo);
 987 out_error:
 988         if (error)
 989                 trace_xfs_rmap_map_error(mp, cur->bc_ag.pag->pag_agno,
 990                                 error, _RET_IP_);
 991         return error;
 992 }
 993
 994 /*
 995  * Add a reference to an extent in the rmap btree.
 996  */
 997 int
 998 xfs_rmap_alloc(
 999         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 }