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 /*
  28  * Lookup the first record less than or equal to [bno, len, owner, offset]
  29  * in the btree given by cur.
  30  */
  31 int
  32 xfs_rmap_lookup_le(
  33         struct xfs_btree_cur    *cur,
  34         xfs_agblock_t           bno,
  35         xfs_extlen_t            len,
  36         uint64_t                owner,
  37         uint64_t                offset,
  38         unsigned int            flags,
  39         int                     *stat)
  40 {
  41         cur->bc_rec.r.rm_startblock = bno;
  42         cur->bc_rec.r.rm_blockcount = len;
  43         cur->bc_rec.r.rm_owner = owner;
  44         cur->bc_rec.r.rm_offset = offset;
  45         cur->bc_rec.r.rm_flags = flags;
  46         return xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat);
  47 }
  48
  49 /*
  50  * Lookup the record exactly matching [bno, len, owner, offset]
  51  * in the btree given by cur.
  52  */
  53 int
  54 xfs_rmap_lookup_eq(
  55         struct xfs_btree_cur    *cur,
  56         xfs_agblock_t           bno,
  57         xfs_extlen_t            len,
  58         uint64_t                owner,
  59         uint64_t                offset,
  60         unsigned int            flags,
  61         int                     *stat)
  62 {
  63         cur->bc_rec.r.rm_startblock = bno;
  64         cur->bc_rec.r.rm_blockcount = len;
  65         cur->bc_rec.r.rm_owner = owner;
  66         cur->bc_rec.r.rm_offset = offset;
  67         cur->bc_rec.r.rm_flags = flags;
  68         return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat);
  69 }
  70
  71 /*
  72  * Update the record referred to by cur to the value given
  73  * by [bno, len, owner, offset].
  74  * This either works (return 0) or gets an EFSCORRUPTED error.
  75  */
  76 STATIC int
  77 xfs_rmap_update(
  78         struct xfs_btree_cur    *cur,
  79         struct xfs_rmap_irec    *irec)
  80 {
  81         union xfs_btree_rec     rec;
  82         int                     error;
  83
  84         trace_xfs_rmap_update(cur->bc_mp, cur->bc_ag.pag->pag_agno,
  85                         irec->rm_startblock, irec->rm_blockcount,
  86                         irec->rm_owner, irec->rm_offset, irec->rm_flags);
  87
  88         rec.rmap.rm_startblock = cpu_to_be32(irec->rm_startblock);
  89         rec.rmap.rm_blockcount = cpu_to_be32(irec->rm_blockcount);
  90         rec.rmap.rm_owner = cpu_to_be64(irec->rm_owner);
  91         rec.rmap.rm_offset = cpu_to_be64(
  92                         xfs_rmap_irec_offset_pack(irec));
  93         error = xfs_btree_update(cur, &rec);
  94         if (error)
  95                 trace_xfs_rmap_update_error(cur->bc_mp,
  96                                 cur->bc_ag.pag->pag_agno, error, _RET_IP_);
  97         return error;
  98 }
  99
 100 int
 101 xfs_rmap_insert(
 102         struct xfs_btree_cur    *rcur,
 103         xfs_agblock_t           agbno,
 104         xfs_extlen_t            len,
 105         uint64_t                owner,
 106         uint64_t                offset,
 107         unsigned int            flags)
 108 {
 109         int                     i;
 110         int                     error;
 111
 112         trace_xfs_rmap_insert(rcur->bc_mp, rcur->bc_ag.pag->pag_agno, agbno,
 113                         len, owner, offset, flags);
 114
 115         error = xfs_rmap_lookup_eq(rcur, agbno, len, owner, offset, flags, &i);
 116         if (error)
 117                 goto done;
 118         if (XFS_IS_CORRUPT(rcur->bc_mp, i != 0)) {
 119                 error = -EFSCORRUPTED;
 120                 goto done;
 121         }
 122
 123         rcur->bc_rec.r.rm_startblock = agbno;
 124         rcur->bc_rec.r.rm_blockcount = len;
 125         rcur->bc_rec.r.rm_owner = owner;
 126         rcur->bc_rec.r.rm_offset = offset;
 127         rcur->bc_rec.r.rm_flags = flags;
 128         error = xfs_btree_insert(rcur, &i);
 129         if (error)
 130                 goto done;
 131         if (XFS_IS_CORRUPT(rcur->bc_mp, i != 1)) {
 132                 error = -EFSCORRUPTED;
 133                 goto done;
 134         }
 135 done:
 136         if (error)
 137                 trace_xfs_rmap_insert_error(rcur->bc_mp,
 138                                 rcur->bc_ag.pag->pag_agno, error, _RET_IP_);
 139         return error;
 140 }
 141
 142 STATIC int
 143 xfs_rmap_delete(
 144         struct xfs_btree_cur    *rcur,
 145         xfs_agblock_t           agbno,
 146         xfs_extlen_t            len,
 147         uint64_t                owner,
 148         uint64_t                offset,
 149         unsigned int            flags)
 150 {
 151         int                     i;
 152         int                     error;
 153
 154         trace_xfs_rmap_delete(rcur->bc_mp, rcur->bc_ag.pag->pag_agno, agbno,
 155                         len, owner, offset, flags);
 156
 157         error = xfs_rmap_lookup_eq(rcur, agbno, len, owner, offset, flags, &i);
 158         if (error)
 159                 goto done;
 160         if (XFS_IS_CORRUPT(rcur->bc_mp, i != 1)) {
 161                 error = -EFSCORRUPTED;
 162                 goto done;
 163         }
 164
 165         error = xfs_btree_delete(rcur, &i);
 166         if (error)
 167                 goto done;
 168         if (XFS_IS_CORRUPT(rcur->bc_mp, i != 1)) {
 169                 error = -EFSCORRUPTED;
 170                 goto done;
 171         }
 172 done:
 173         if (error)
 174                 trace_xfs_rmap_delete_error(rcur->bc_mp,
 175                                 rcur->bc_ag.pag->pag_agno, error, _RET_IP_);
 176         return error;
 177 }
 178
 179 /* Convert an internal btree record to an rmap record. */
 180 int
 181 xfs_rmap_btrec_to_irec(
 182         const union xfs_btree_rec       *rec,
 183         struct xfs_rmap_irec            *irec)
 184 {
 185         irec->rm_startblock = be32_to_cpu(rec->rmap.rm_startblock);
 186         irec->rm_blockcount = be32_to_cpu(rec->rmap.rm_blockcount);
 187         irec->rm_owner = be64_to_cpu(rec->rmap.rm_owner);
 188         return xfs_rmap_irec_offset_unpack(be64_to_cpu(rec->rmap.rm_offset),
 189                         irec);
 190 }
 191
 192 /*
 193  * Get the data from the pointed-to record.
 194  */
 195 int
 196 xfs_rmap_get_rec(
 197         struct xfs_btree_cur    *cur,
 198         struct xfs_rmap_irec    *irec,
 199         int                     *stat)
 200 {
 201         struct xfs_mount        *mp = cur->bc_mp;
 202         xfs_agnumber_t          agno = cur->bc_ag.pag->pag_agno;
 203         union xfs_btree_rec     *rec;
 204         int                     error;
 205
 206         error = xfs_btree_get_rec(cur, &rec, stat);
 207         if (error || !*stat)
 208                 return error;
 209
 210         if (xfs_rmap_btrec_to_irec(rec, irec))
 211                 goto out_bad_rec;
 212
 213         if (irec->rm_blockcount == 0)
 214                 goto out_bad_rec;
 215         if (irec->rm_startblock <= XFS_AGFL_BLOCK(mp)) {
 216                 if (irec->rm_owner != XFS_RMAP_OWN_FS)
 217                         goto out_bad_rec;
 218                 if (irec->rm_blockcount != XFS_AGFL_BLOCK(mp) + 1)
 219                         goto out_bad_rec;
 220         } else {
 221                 /* check for valid extent range, including overflow */
 222                 if (!xfs_verify_agbno(mp, agno, irec->rm_startblock))
 223                         goto out_bad_rec;
 224                 if (irec->rm_startblock >
 225                                 irec->rm_startblock + irec->rm_blockcount)
 226                         goto out_bad_rec;
 227                 if (!xfs_verify_agbno(mp, agno,
 228                                 irec->rm_startblock + irec->rm_blockcount - 1))
 229                         goto out_bad_rec;
 230         }
 231
 232         if (!(xfs_verify_ino(mp, irec->rm_owner) ||
 233               (irec->rm_owner <= XFS_RMAP_OWN_FS &&
 234                irec->rm_owner >= XFS_RMAP_OWN_MIN)))
 235                 goto out_bad_rec;
 236
 237         return 0;
 238 out_bad_rec:
 239         xfs_warn(mp,
 240                 "Reverse Mapping BTree record corruption in AG %d detected!",
 241                 agno);
 242         xfs_warn(mp,
 243                 "Owner 0x%llx, flags 0x%x, start block 0x%x block count 0x%x",
 244                 irec->rm_owner, irec->rm_flags, irec->rm_startblock,
 245                 irec->rm_blockcount);
 246         return -EFSCORRUPTED;
 247 }
 248
 249 struct xfs_find_left_neighbor_info {
 250         struct xfs_rmap_irec    high;
 251         struct xfs_rmap_irec    *irec;
 252         int                     *stat;
 253 };
 254
 255 /* For each rmap given, figure out if it matches the key we want. */
 256 STATIC int
 257 xfs_rmap_find_left_neighbor_helper(
 258         struct xfs_btree_cur            *cur,
 259         const struct xfs_rmap_irec      *rec,
 260         void                            *priv)
 261 {
 262         struct xfs_find_left_neighbor_info      *info = priv;
 263
 264         trace_xfs_rmap_find_left_neighbor_candidate(cur->bc_mp,
 265                         cur->bc_ag.pag->pag_agno, rec->rm_startblock,
 266                         rec->rm_blockcount, rec->rm_owner, rec->rm_offset,
 267                         rec->rm_flags);
 268
 269         if (rec->rm_owner != info->high.rm_owner)
 270                 return 0;
 271         if (!XFS_RMAP_NON_INODE_OWNER(rec->rm_owner) &&
 272             !(rec->rm_flags & XFS_RMAP_BMBT_BLOCK) &&
 273             rec->rm_offset + rec->rm_blockcount - 1 != info->high.rm_offset)
 274                 return 0;
 275
 276         *info->irec = *rec;
 277         *info->stat = 1;
 278         return -ECANCELED;
 279 }
 280
 281 /*
 282  * Find the record to the left of the given extent, being careful only to
 283  * return a match with the same owner and adjacent physical and logical
 284  * block ranges.
 285  */
 286 int
 287 xfs_rmap_find_left_neighbor(
 288         struct xfs_btree_cur    *cur,
 289         xfs_agblock_t           bno,
 290         uint64_t                owner,
 291         uint64_t                offset,
 292         unsigned int            flags,
 293         struct xfs_rmap_irec    *irec,
 294         int                     *stat)
 295 {
 296         struct xfs_find_left_neighbor_info      info;
 297         int                     error;
 298
 299         *stat = 0;
 300         if (bno == 0)
 301                 return 0;
 302         info.high.rm_startblock = bno - 1;
 303         info.high.rm_owner = owner;
 304         if (!XFS_RMAP_NON_INODE_OWNER(owner) &&
 305             !(flags & XFS_RMAP_BMBT_BLOCK)) {
 306                 if (offset == 0)
 307                         return 0;
 308                 info.high.rm_offset = offset - 1;
 309         } else
 310                 info.high.rm_offset = 0;
 311         info.high.rm_flags = flags;
 312         info.high.rm_blockcount = 0;
 313         info.irec = irec;
 314         info.stat = stat;
 315
 316         trace_xfs_rmap_find_left_neighbor_query(cur->bc_mp,
 317                         cur->bc_ag.pag->pag_agno, bno, 0, owner, offset, flags);
 318
 319         error = xfs_rmap_query_range(cur, &info.high, &info.high,
 320                         xfs_rmap_find_left_neighbor_helper, &info);
 321         if (error == -ECANCELED)
 322                 error = 0;
 323         if (*stat)
 324                 trace_xfs_rmap_find_left_neighbor_result(cur->bc_mp,
 325                                 cur->bc_ag.pag->pag_agno, irec->rm_startblock,
 326                                 irec->rm_blockcount, irec->rm_owner,
 327                                 irec->rm_offset, irec->rm_flags);
 328         return error;
 329 }
 330
 331 /* For each rmap given, figure out if it matches the key we want. */
 332 STATIC int
 333 xfs_rmap_lookup_le_range_helper(
 334         struct xfs_btree_cur            *cur,
 335         const struct xfs_rmap_irec      *rec,
 336         void                            *priv)
 337 {
 338         struct xfs_find_left_neighbor_info      *info = priv;
 339
 340         trace_xfs_rmap_lookup_le_range_candidate(cur->bc_mp,
 341                         cur->bc_ag.pag->pag_agno, rec->rm_startblock,
 342                         rec->rm_blockcount, rec->rm_owner, rec->rm_offset,
 343                         rec->rm_flags);
 344
 345         if (rec->rm_owner != info->high.rm_owner)
 346                 return 0;
 347         if (!XFS_RMAP_NON_INODE_OWNER(rec->rm_owner) &&
 348             !(rec->rm_flags & XFS_RMAP_BMBT_BLOCK) &&
 349             (rec->rm_offset > info->high.rm_offset ||
 350              rec->rm_offset + rec->rm_blockcount <= info->high.rm_offset))
 351                 return 0;
 352
 353         *info->irec = *rec;
 354         *info->stat = 1;
 355         return -ECANCELED;
 356 }
 357
 358 /*
 359  * Find the record to the left of the given extent, being careful only to
 360  * return a match with the same owner and overlapping physical and logical
 361  * block ranges.  This is the overlapping-interval version of
 362  * xfs_rmap_lookup_le.
 363  */
 364 int
 365 xfs_rmap_lookup_le_range(
 366         struct xfs_btree_cur    *cur,
 367         xfs_agblock_t           bno,
 368         uint64_t                owner,
 369         uint64_t                offset,
 370         unsigned int            flags,
 371         struct xfs_rmap_irec    *irec,
 372         int                     *stat)
 373 {
 374         struct xfs_find_left_neighbor_info      info;
 375         int                     error;
 376
 377         info.high.rm_startblock = bno;
 378         info.high.rm_owner = owner;
 379         if (!XFS_RMAP_NON_INODE_OWNER(owner) && !(flags & XFS_RMAP_BMBT_BLOCK))
 380                 info.high.rm_offset = offset;
 381         else
 382                 info.high.rm_offset = 0;
 383         info.high.rm_flags = flags;
 384         info.high.rm_blockcount = 0;
 385         *stat = 0;
 386         info.irec = irec;
 387         info.stat = stat;
 388
 389         trace_xfs_rmap_lookup_le_range(cur->bc_mp,
 390                         cur->bc_ag.pag->pag_agno, bno, 0, owner, offset, flags);
 391         error = xfs_rmap_query_range(cur, &info.high, &info.high,
 392                         xfs_rmap_lookup_le_range_helper, &info);
 393         if (error == -ECANCELED)
 394                 error = 0;
 395         if (*stat)
 396                 trace_xfs_rmap_lookup_le_range_result(cur->bc_mp,
 397                                 cur->bc_ag.pag->pag_agno, irec->rm_startblock,
 398                                 irec->rm_blockcount, irec->rm_owner,
 399                                 irec->rm_offset, irec->rm_flags);
 400         return error;
 401 }
 402
 403 /*
 404  * Perform all the relevant owner checks for a removal op.  If we're doing an
 405  * unknown-owner removal then we have no owner information to check.
 406  */
 407 static int
 408 xfs_rmap_free_check_owner(
 409         struct xfs_mount        *mp,
 410         uint64_t                ltoff,
 411         struct xfs_rmap_irec    *rec,
 412         xfs_filblks_t           len,
 413         uint64_t                owner,
 414         uint64_t                offset,
 415         unsigned int            flags)
 416 {
 417         int                     error = 0;
 418
 419         if (owner == XFS_RMAP_OWN_UNKNOWN)
 420                 return 0;
 421
 422         /* Make sure the unwritten flag matches. */
 423         if (XFS_IS_CORRUPT(mp,
 424                            (flags & XFS_RMAP_UNWRITTEN) !=
 425                            (rec->rm_flags & XFS_RMAP_UNWRITTEN))) {
 426                 error = -EFSCORRUPTED;
 427                 goto out;
 428         }
 429
 430         /* Make sure the owner matches what we expect to find in the tree. */
 431         if (XFS_IS_CORRUPT(mp, owner != rec->rm_owner)) {
 432                 error = -EFSCORRUPTED;
 433                 goto out;
 434         }
 435
 436         /* Check the offset, if necessary. */
 437         if (XFS_RMAP_NON_INODE_OWNER(owner))
 438                 goto out;
 439
 440         if (flags & XFS_RMAP_BMBT_BLOCK) {
 441                 if (XFS_IS_CORRUPT(mp,
 442                                    !(rec->rm_flags & XFS_RMAP_BMBT_BLOCK))) {
 443                         error = -EFSCORRUPTED;
 444                         goto out;
 445                 }
 446         } else {
 447                 if (XFS_IS_CORRUPT(mp, rec->rm_offset > offset)) {
 448                         error = -EFSCORRUPTED;
 449                         goto out;
 450                 }
 451                 if (XFS_IS_CORRUPT(mp,
 452                                    offset + len > ltoff + rec->rm_blockcount)) {
 453                         error = -EFSCORRUPTED;
 454                         goto out;
 455                 }
 456         }
 457
 458 out:
 459         return error;
 460 }
 461
 462 /*
 463  * Find the extent in the rmap btree and remove it.
 464  *
 465  * The record we find should always be an exact match for the extent that we're
 466  * looking for, since we insert them into the btree without modification.
 467  *
 468  * Special Case #1: when growing the filesystem, we "free" an extent when
 469  * growing the last AG. This extent is new space and so it is not tracked as
 470  * used space in the btree. The growfs code will pass in an owner of
 471  * XFS_RMAP_OWN_NULL to indicate that it expected that there is no owner of this
 472  * extent. We verify that - the extent lookup result in a record that does not
 473  * overlap.
 474  *
 475  * Special Case #2: EFIs do not record the owner of the extent, so when
 476  * recovering EFIs from the log we pass in XFS_RMAP_OWN_UNKNOWN to tell the rmap
 477  * btree to ignore the owner (i.e. wildcard match) so we don't trigger
 478  * corruption checks during log recovery.
 479  */
 480 STATIC int
 481 xfs_rmap_unmap(
 482         struct xfs_btree_cur            *cur,
 483         xfs_agblock_t                   bno,
 484         xfs_extlen_t                    len,
 485         bool                            unwritten,
 486         const struct xfs_owner_info     *oinfo)
 487 {
 488         struct xfs_mount                *mp = cur->bc_mp;
 489         struct xfs_rmap_irec            ltrec;
 490         uint64_t                        ltoff;
 491         int                             error = 0;
 492         int                             i;
 493         uint64_t                        owner;
 494         uint64_t                        offset;
 495         unsigned int                    flags;
 496         bool                            ignore_off;
 497
 498         xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
 499         ignore_off = XFS_RMAP_NON_INODE_OWNER(owner) ||
 500                         (flags & XFS_RMAP_BMBT_BLOCK);
 501         if (unwritten)
 502                 flags |= XFS_RMAP_UNWRITTEN;
 503         trace_xfs_rmap_unmap(mp, cur->bc_ag.pag->pag_agno, bno, len,
 504                         unwritten, oinfo);
 505
 506         /*
 507          * We should always have a left record because there's a static record
 508          * for the AG headers at rm_startblock == 0 created by mkfs/growfs that
 509          * will not ever be removed from the tree.
 510          */
 511         error = xfs_rmap_lookup_le(cur, bno, len, owner, offset, flags, &i);
 512         if (error)
 513                 goto out_error;
 514         if (XFS_IS_CORRUPT(mp, i != 1)) {
 515                 error = -EFSCORRUPTED;
 516                 goto out_error;
 517         }
 518
 519         error = xfs_rmap_get_rec(cur, &ltrec, &i);
 520         if (error)
 521                 goto out_error;
 522         if (XFS_IS_CORRUPT(mp, i != 1)) {
 523                 error = -EFSCORRUPTED;
 524                 goto out_error;
 525         }
 526         trace_xfs_rmap_lookup_le_range_result(cur->bc_mp,
 527                         cur->bc_ag.pag->pag_agno, ltrec.rm_startblock,
 528                         ltrec.rm_blockcount, ltrec.rm_owner,
 529                         ltrec.rm_offset, ltrec.rm_flags);
 530         ltoff = ltrec.rm_offset;
 531
 532         /*
 533          * For growfs, the incoming extent must be beyond the left record we
 534          * just found as it is new space and won't be used by anyone. This is
 535          * just a corruption check as we don't actually do anything with this
 536          * extent.  Note that we need to use >= instead of > because it might
 537          * be the case that the "left" extent goes all the way to EOFS.
 538          */
 539         if (owner == XFS_RMAP_OWN_NULL) {
 540                 if (XFS_IS_CORRUPT(mp,
 541                                    bno <
 542                                    ltrec.rm_startblock + ltrec.rm_blockcount)) {
 543                         error = -EFSCORRUPTED;
 544                         goto out_error;
 545                 }
 546                 goto out_done;
 547         }
 548
 549         /*
 550          * If we're doing an unknown-owner removal for EFI recovery, we expect
 551          * to find the full range in the rmapbt or nothing at all.  If we
 552          * don't find any rmaps overlapping either end of the range, we're
 553          * done.  Hopefully this means that the EFI creator already queued
 554          * (and finished) a RUI to remove the rmap.
 555          */
 556         if (owner == XFS_RMAP_OWN_UNKNOWN &&
 557             ltrec.rm_startblock + ltrec.rm_blockcount <= bno) {
 558                 struct xfs_rmap_irec    rtrec;
 559
 560                 error = xfs_btree_increment(cur, 0, &i);
 561                 if (error)
 562                         goto out_error;
 563                 if (i == 0)
 564                         goto out_done;
 565                 error = xfs_rmap_get_rec(cur, &rtrec, &i);
 566                 if (error)
 567                         goto out_error;
 568                 if (XFS_IS_CORRUPT(mp, i != 1)) {
 569                         error = -EFSCORRUPTED;
 570                         goto out_error;
 571                 }
 572                 if (rtrec.rm_startblock >= bno + len)
 573                         goto out_done;
 574         }
 575
 576         /* Make sure the extent we found covers the entire freeing range. */
 577         if (XFS_IS_CORRUPT(mp,
 578                            ltrec.rm_startblock > bno ||
 579                            ltrec.rm_startblock + ltrec.rm_blockcount <
 580                            bno + len)) {
 581                 error = -EFSCORRUPTED;
 582                 goto out_error;
 583         }
 584
 585         /* Check owner information. */
 586         error = xfs_rmap_free_check_owner(mp, ltoff, &ltrec, len, owner,
 587                         offset, flags);
 588         if (error)
 589                 goto out_error;
 590
 591         if (ltrec.rm_startblock == bno && ltrec.rm_blockcount == len) {
 592                 /* exact match, simply remove the record from rmap tree */
 593                 trace_xfs_rmap_delete(mp, cur->bc_ag.pag->pag_agno,
 594                                 ltrec.rm_startblock, ltrec.rm_blockcount,
 595                                 ltrec.rm_owner, ltrec.rm_offset,
 596                                 ltrec.rm_flags);
 597                 error = xfs_btree_delete(cur, &i);
 598                 if (error)
 599                         goto out_error;
 600                 if (XFS_IS_CORRUPT(mp, i != 1)) {
 601                         error = -EFSCORRUPTED;
 602                         goto out_error;
 603                 }
 604         } else if (ltrec.rm_startblock == bno) {
 605                 /*
 606                  * overlap left hand side of extent: move the start, trim the
 607                  * length and update the current record.
 608                  *
 609                  *       ltbno                ltlen
 610                  * Orig:    |oooooooooooooooooooo|
 611                  * Freeing: |fffffffff|
 612                  * Result:            |rrrrrrrrrr|
 613                  *         bno       len
 614                  */
 615                 ltrec.rm_startblock += len;
 616                 ltrec.rm_blockcount -= len;
 617                 if (!ignore_off)
 618                         ltrec.rm_offset += len;
 619                 error = xfs_rmap_update(cur, &ltrec);
 620                 if (error)
 621                         goto out_error;
 622         } else if (ltrec.rm_startblock + ltrec.rm_blockcount == bno + len) {
 623                 /*
 624                  * overlap right hand side of extent: trim the length and update
 625                  * the current record.
 626                  *
 627                  *       ltbno                ltlen
 628                  * Orig:    |oooooooooooooooooooo|
 629                  * Freeing:            |fffffffff|
 630                  * Result:  |rrrrrrrrrr|
 631                  *                    bno       len
 632                  */
 633                 ltrec.rm_blockcount -= len;
 634                 error = xfs_rmap_update(cur, &ltrec);
 635                 if (error)
 636                         goto out_error;
 637         } else {
 638
 639                 /*
 640                  * overlap middle of extent: trim the length of the existing
 641                  * record to the length of the new left-extent size, increment
 642                  * the insertion position so we can insert a new record
 643                  * containing the remaining right-extent space.
 644                  *
 645                  *       ltbno                ltlen
 646                  * Orig:    |oooooooooooooooooooo|
 647                  * Freeing:       |fffffffff|
 648                  * Result:  |rrrrr|         |rrrr|
 649                  *               bno       len
 650                  */
 651                 xfs_extlen_t    orig_len = ltrec.rm_blockcount;
 652
 653                 ltrec.rm_blockcount = bno - ltrec.rm_startblock;
 654                 error = xfs_rmap_update(cur, &ltrec);
 655                 if (error)
 656                         goto out_error;
 657
 658                 error = xfs_btree_increment(cur, 0, &i);
 659                 if (error)
 660                         goto out_error;
 661
 662                 cur->bc_rec.r.rm_startblock = bno + len;
 663                 cur->bc_rec.r.rm_blockcount = orig_len - len -
 664                                                      ltrec.rm_blockcount;
 665                 cur->bc_rec.r.rm_owner = ltrec.rm_owner;
 666                 if (ignore_off)
 667                         cur->bc_rec.r.rm_offset = 0;
 668                 else
 669                         cur->bc_rec.r.rm_offset = offset + len;
 670                 cur->bc_rec.r.rm_flags = flags;
 671                 trace_xfs_rmap_insert(mp, cur->bc_ag.pag->pag_agno,
 672                                 cur->bc_rec.r.rm_startblock,
 673                                 cur->bc_rec.r.rm_blockcount,
 674                                 cur->bc_rec.r.rm_owner,
 675                                 cur->bc_rec.r.rm_offset,
 676                                 cur->bc_rec.r.rm_flags);
 677                 error = xfs_btree_insert(cur, &i);
 678                 if (error)
 679                         goto out_error;
 680         }
 681
 682 out_done:
 683         trace_xfs_rmap_unmap_done(mp, cur->bc_ag.pag->pag_agno, bno, len,
 684                         unwritten, oinfo);
 685 out_error:
 686         if (error)
 687                 trace_xfs_rmap_unmap_error(mp, cur->bc_ag.pag->pag_agno,
 688                                 error, _RET_IP_);
 689         return error;
 690 }
 691
 692 /*
 693  * Remove a reference to an extent in the rmap btree.
 694  */
 695 int
 696 xfs_rmap_free(
 697         struct xfs_trans                *tp,
 698         struct xfs_buf                  *agbp,
 699         struct xfs_perag                *pag,
 700         xfs_agblock_t                   bno,
 701         xfs_extlen_t                    len,
 702         const struct xfs_owner_info     *oinfo)
 703 {
 704         struct xfs_mount                *mp = tp->t_mountp;
 705         struct xfs_btree_cur            *cur;
 706         int                             error;
 707
 708         if (!xfs_has_rmapbt(mp))
 709                 return 0;
 710
 711         cur = xfs_rmapbt_init_cursor(mp, tp, agbp, pag);
 712
 713         error = xfs_rmap_unmap(cur, bno, len, false, oinfo);
 714
 715         xfs_btree_del_cursor(cur, error);
 716         return error;
 717 }
 718
 719 /*
 720  * A mergeable rmap must have the same owner and the same values for
 721  * the unwritten, attr_fork, and bmbt flags.  The startblock and
 722  * offset are checked separately.
 723  */
 724 static bool
 725 xfs_rmap_is_mergeable(
 726         struct xfs_rmap_irec    *irec,
 727         uint64_t                owner,
 728         unsigned int            flags)
 729 {
 730         if (irec->rm_owner == XFS_RMAP_OWN_NULL)
 731                 return false;
 732         if (irec->rm_owner != owner)
 733                 return false;
 734         if ((flags & XFS_RMAP_UNWRITTEN) ^
 735             (irec->rm_flags & XFS_RMAP_UNWRITTEN))
 736                 return false;
 737         if ((flags & XFS_RMAP_ATTR_FORK) ^
 738             (irec->rm_flags & XFS_RMAP_ATTR_FORK))
 739                 return false;
 740         if ((flags & XFS_RMAP_BMBT_BLOCK) ^
 741             (irec->rm_flags & XFS_RMAP_BMBT_BLOCK))
 742                 return false;
 743         return true;
 744 }
 745
 746 /*
 747  * When we allocate a new block, the first thing we do is add a reference to
 748  * the extent in the rmap btree. This takes the form of a [agbno, length,
 749  * owner, offset] record.  Flags are encoded in the high bits of the offset
 750  * field.
 751  */
 752 STATIC int
 753 xfs_rmap_map(
 754         struct xfs_btree_cur            *cur,
 755         xfs_agblock_t                   bno,
 756         xfs_extlen_t                    len,
 757         bool                            unwritten,
 758         const struct xfs_owner_info     *oinfo)
 759 {
 760         struct xfs_mount                *mp = cur->bc_mp;
 761         struct xfs_rmap_irec            ltrec;
 762         struct xfs_rmap_irec            gtrec;
 763         int                             have_gt;
 764         int                             have_lt;
 765         int                             error = 0;
 766         int                             i;
 767         uint64_t                        owner;
 768         uint64_t                        offset;
 769         unsigned int                    flags = 0;
 770         bool                            ignore_off;
 771
 772         xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
 773         ASSERT(owner != 0);
 774         ignore_off = XFS_RMAP_NON_INODE_OWNER(owner) ||
 775                         (flags & XFS_RMAP_BMBT_BLOCK);
 776         if (unwritten)
 777                 flags |= XFS_RMAP_UNWRITTEN;
 778         trace_xfs_rmap_map(mp, cur->bc_ag.pag->pag_agno, bno, len,
 779                         unwritten, oinfo);
 780         ASSERT(!xfs_rmap_should_skip_owner_update(oinfo));
 781
 782         /*
 783          * For the initial lookup, look for an exact match or the left-adjacent
 784          * record for our insertion point. This will also give us the record for
 785          * start block contiguity tests.
 786          */
 787         error = xfs_rmap_lookup_le(cur, bno, len, owner, offset, flags,
 788                         &have_lt);
 789         if (error)
 790                 goto out_error;
 791         if (have_lt) {
 792                 error = xfs_rmap_get_rec(cur, &ltrec, &have_lt);
 793                 if (error)
 794                         goto out_error;
 795                 if (XFS_IS_CORRUPT(mp, have_lt != 1)) {
 796                         error = -EFSCORRUPTED;
 797                         goto out_error;
 798                 }
 799                 trace_xfs_rmap_lookup_le_range_result(cur->bc_mp,
 800                                 cur->bc_ag.pag->pag_agno, ltrec.rm_startblock,
 801                                 ltrec.rm_blockcount, ltrec.rm_owner,
 802                                 ltrec.rm_offset, ltrec.rm_flags);
 803
 804                 if (!xfs_rmap_is_mergeable(&ltrec, owner, flags))
 805                         have_lt = 0;
 806         }
 807
 808         if (XFS_IS_CORRUPT(mp,
 809                            have_lt != 0 &&
 810                            ltrec.rm_startblock + ltrec.rm_blockcount > bno)) {
 811                 error = -EFSCORRUPTED;
 812                 goto out_error;
 813         }
 814
 815         /*
 816          * Increment the cursor to see if we have a right-adjacent record to our
 817          * insertion point. This will give us the record for end block
 818          * contiguity tests.
 819          */
 820         error = xfs_btree_increment(cur, 0, &have_gt);
 821         if (error)
 822                 goto out_error;
 823         if (have_gt) {
 824                 error = xfs_rmap_get_rec(cur, &gtrec, &have_gt);
 825                 if (error)
 826                         goto out_error;
 827                 if (XFS_IS_CORRUPT(mp, have_gt != 1)) {
 828                         error = -EFSCORRUPTED;
 829                         goto out_error;
 830                 }
 831                 if (XFS_IS_CORRUPT(mp, bno + len > gtrec.rm_startblock)) {
 832                         error = -EFSCORRUPTED;
 833                         goto out_error;
 834                 }
 835                 trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp,
 836                         cur->bc_ag.pag->pag_agno, gtrec.rm_startblock,
 837                         gtrec.rm_blockcount, gtrec.rm_owner,
 838                         gtrec.rm_offset, gtrec.rm_flags);
 839                 if (!xfs_rmap_is_mergeable(&gtrec, owner, flags))
 840                         have_gt = 0;
 841         }
 842
 843         /*
 844          * Note: cursor currently points one record to the right of ltrec, even
 845          * if there is no record in the tree to the right.
 846          */
 847         if (have_lt &&
 848             ltrec.rm_startblock + ltrec.rm_blockcount == bno &&
 849             (ignore_off || ltrec.rm_offset + ltrec.rm_blockcount == offset)) {
 850                 /*
 851                  * left edge contiguous, merge into left record.
 852                  *
 853                  *       ltbno     ltlen
 854                  * orig:   |ooooooooo|
 855                  * adding:           |aaaaaaaaa|
 856                  * result: |rrrrrrrrrrrrrrrrrrr|
 857                  *                  bno       len
 858                  */
 859                 ltrec.rm_blockcount += len;
 860                 if (have_gt &&
 861                     bno + len == gtrec.rm_startblock &&
 862                     (ignore_off || offset + len == gtrec.rm_offset) &&
 863                     (unsigned long)ltrec.rm_blockcount + len +
 864                                 gtrec.rm_blockcount <= XFS_RMAP_LEN_MAX) {
 865                         /*
 866                          * right edge also contiguous, delete right record
 867                          * and merge into left record.
 868                          *
 869                          *       ltbno     ltlen    gtbno     gtlen
 870                          * orig:   |ooooooooo|         |ooooooooo|
 871                          * adding:           |aaaaaaaaa|
 872                          * result: |rrrrrrrrrrrrrrrrrrrrrrrrrrrrr|
 873                          */
 874                         ltrec.rm_blockcount += gtrec.rm_blockcount;
 875                         trace_xfs_rmap_delete(mp, cur->bc_ag.pag->pag_agno,
 876                                         gtrec.rm_startblock,
 877                                         gtrec.rm_blockcount,
 878                                         gtrec.rm_owner,
 879                                         gtrec.rm_offset,
 880                                         gtrec.rm_flags);
 881                         error = xfs_btree_delete(cur, &i);
 882                         if (error)
 883                                 goto out_error;
 884                         if (XFS_IS_CORRUPT(mp, i != 1)) {
 885                                 error = -EFSCORRUPTED;
 886                                 goto out_error;
 887                         }
 888                 }
 889
 890                 /* point the cursor back to the left record and update */
 891                 error = xfs_btree_decrement(cur, 0, &have_gt);
 892                 if (error)
 893                         goto out_error;
 894                 error = xfs_rmap_update(cur, &ltrec);
 895                 if (error)
 896                         goto out_error;
 897         } else if (have_gt &&
 898                    bno + len == gtrec.rm_startblock &&
 899                    (ignore_off || offset + len == gtrec.rm_offset)) {
 900                 /*
 901                  * right edge contiguous, merge into right record.
 902                  *
 903                  *                 gtbno     gtlen
 904                  * Orig:             |ooooooooo|
 905                  * adding: |aaaaaaaaa|
 906                  * Result: |rrrrrrrrrrrrrrrrrrr|
 907                  *        bno       len
 908                  */
 909                 gtrec.rm_startblock = bno;
 910                 gtrec.rm_blockcount += len;
 911                 if (!ignore_off)
 912                         gtrec.rm_offset = offset;
 913                 error = xfs_rmap_update(cur, &gtrec);
 914                 if (error)
 915                         goto out_error;
 916         } else {
 917                 /*
 918                  * no contiguous edge with identical owner, insert
 919                  * new record at current cursor position.
 920                  */
 921                 cur->bc_rec.r.rm_startblock = bno;
 922                 cur->bc_rec.r.rm_blockcount = len;
 923                 cur->bc_rec.r.rm_owner = owner;
 924                 cur->bc_rec.r.rm_offset = offset;
 925                 cur->bc_rec.r.rm_flags = flags;
 926                 trace_xfs_rmap_insert(mp, cur->bc_ag.pag->pag_agno, bno, len,
 927                         owner, offset, flags);
 928                 error = xfs_btree_insert(cur, &i);
 929                 if (error)
 930                         goto out_error;
 931                 if (XFS_IS_CORRUPT(mp, i != 1)) {
 932                         error = -EFSCORRUPTED;
 933                         goto out_error;
 934                 }
 935         }
 936
 937         trace_xfs_rmap_map_done(mp, cur->bc_ag.pag->pag_agno, bno, len,
 938                         unwritten, oinfo);
 939 out_error:
 940         if (error)
 941                 trace_xfs_rmap_map_error(mp, cur->bc_ag.pag->pag_agno,
 942                                 error, _RET_IP_);
 943         return error;
 944 }
 945
 946 /*
 947  * Add a reference to an extent in the rmap btree.
 948  */
 949 int
 950 xfs_rmap_alloc(
 951         struct xfs_trans                *tp,
 952         struct xfs_buf                  *agbp,
 953         struct xfs_perag                *pag,
 954         xfs_agblock_t                   bno,
 955         xfs_extlen_t                    len,
 956         const struct xfs_owner_info     *oinfo)
 957 {
 958         struct xfs_mount                *mp = tp->t_mountp;
 959         struct xfs_btree_cur            *cur;
 960         int                             error;
 961
 962         if (!xfs_has_rmapbt(mp))
 963                 return 0;
 964
 965         cur = xfs_rmapbt_init_cursor(mp, tp, agbp, pag);
 966         error = xfs_rmap_map(cur, bno, len, false, oinfo);
 967
 968         xfs_btree_del_cursor(cur, error);
 969         return error;
 970 }
 971
 972 #define RMAP_LEFT_CONTIG        (1 << 0)
 973 #define RMAP_RIGHT_CONTIG       (1 << 1)
 974 #define RMAP_LEFT_FILLING       (1 << 2)
 975 #define RMAP_RIGHT_FILLING      (1 << 3)
 976 #define RMAP_LEFT_VALID         (1 << 6)
 977 #define RMAP_RIGHT_VALID        (1 << 7)
 978
 979 #define LEFT            r[0]
 980 #define RIGHT           r[1]
 981 #define PREV            r[2]
 982 #define NEW             r[3]
 983
 984 /*
 985  * Convert an unwritten extent to a real extent or vice versa.
 986  * Does not handle overlapping extents.
 987  */
 988 STATIC int
 989 xfs_rmap_convert(
 990         struct xfs_btree_cur            *cur,
 991         xfs_agblock_t                   bno,
 992         xfs_extlen_t                    len,
 993         bool                            unwritten,
 994         const struct xfs_owner_info     *oinfo)
 995 {
 996         struct xfs_mount                *mp = cur->bc_mp;
 997         struct xfs_rmap_irec            r[4];   /* neighbor extent entries */
 998                                                 /* left is 0, right is 1, */
 999                                                 /* prev is 2, new is 3 */
1000         uint64_t                owner;
1001         uint64_t                offset;
1002         uint64_t                new_endoff;
1003         unsigned int            oldext;
1004         unsigned int            newext;
1005         unsigned int            flags = 0;
1006         int                     i;
1007         int                     state = 0;
1008         int                     error;
1009
1010         xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
1011         ASSERT(!(XFS_RMAP_NON_INODE_OWNER(owner) ||
1012                         (flags & (XFS_RMAP_ATTR_FORK | XFS_RMAP_BMBT_BLOCK))));
1013         oldext = unwritten ? XFS_RMAP_UNWRITTEN : 0;
1014         new_endoff = offset + len;
1015         trace_xfs_rmap_convert(mp, cur->bc_ag.pag->pag_agno, bno, len,
1016                         unwritten, oinfo);
1017
1018         /*
1019          * For the initial lookup, look for an exact match or the left-adjacent
1020          * record for our insertion point. This will also give us the record for
1021          * start block contiguity tests.
1022          */
1023         error = xfs_rmap_lookup_le(cur, bno, len, owner, offset, oldext, &i);
1024         if (error)
1025                 goto done;
1026         if (XFS_IS_CORRUPT(mp, i != 1)) {
1027                 error = -EFSCORRUPTED;
1028                 goto done;
1029         }
1030
1031         error = xfs_rmap_get_rec(cur, &PREV, &i);
1032         if (error)
1033                 goto done;
1034         if (XFS_IS_CORRUPT(mp, i != 1)) {
1035                 error = -EFSCORRUPTED;
1036                 goto done;
1037         }
1038         trace_xfs_rmap_lookup_le_range_result(cur->bc_mp,
1039                         cur->bc_ag.pag->pag_agno, PREV.rm_startblock,
1040                         PREV.rm_blockcount, PREV.rm_owner,
1041                         PREV.rm_offset, PREV.rm_flags);
1042
1043         ASSERT(PREV.rm_offset <= offset);
1044         ASSERT(PREV.rm_offset + PREV.rm_blockcount >= new_endoff);
1045         ASSERT((PREV.rm_flags & XFS_RMAP_UNWRITTEN) == oldext);
1046         newext = ~oldext & XFS_RMAP_UNWRITTEN;
1047
1048         /*
1049          * Set flags determining what part of the previous oldext allocation
1050          * extent is being replaced by a newext allocation.
1051          */
1052         if (PREV.rm_offset == offset)
1053                 state |= RMAP_LEFT_FILLING;
1054         if (PREV.rm_offset + PREV.rm_blockcount == new_endoff)
1055                 state |= RMAP_RIGHT_FILLING;
1056
1057         /*
1058          * Decrement the cursor to see if we have a left-adjacent record to our
1059          * insertion point. This will give us the record for end block
1060          * contiguity tests.
1061          */
1062         error = xfs_btree_decrement(cur, 0, &i);
1063         if (error)
1064                 goto done;
1065         if (i) {
1066                 state |= RMAP_LEFT_VALID;
1067                 error = xfs_rmap_get_rec(cur, &LEFT, &i);
1068                 if (error)
1069                         goto done;
1070                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1071                         error = -EFSCORRUPTED;
1072                         goto done;
1073                 }
1074                 if (XFS_IS_CORRUPT(mp,
1075                                    LEFT.rm_startblock + LEFT.rm_blockcount >
1076                                    bno)) {
1077                         error = -EFSCORRUPTED;
1078                         goto done;
1079                 }
1080                 trace_xfs_rmap_find_left_neighbor_result(cur->bc_mp,
1081                                 cur->bc_ag.pag->pag_agno, LEFT.rm_startblock,
1082                                 LEFT.rm_blockcount, LEFT.rm_owner,
1083                                 LEFT.rm_offset, LEFT.rm_flags);
1084                 if (LEFT.rm_startblock + LEFT.rm_blockcount == bno &&
1085                     LEFT.rm_offset + LEFT.rm_blockcount == offset &&
1086                     xfs_rmap_is_mergeable(&LEFT, owner, newext))
1087                         state |= RMAP_LEFT_CONTIG;
1088         }
1089
1090         /*
1091          * Increment the cursor to see if we have a right-adjacent record to our
1092          * insertion point. This will give us the record for end block
1093          * contiguity tests.
1094          */
1095         error = xfs_btree_increment(cur, 0, &i);
1096         if (error)
1097                 goto done;
1098         if (XFS_IS_CORRUPT(mp, i != 1)) {
1099                 error = -EFSCORRUPTED;
1100                 goto done;
1101         }
1102         error = xfs_btree_increment(cur, 0, &i);
1103         if (error)
1104                 goto done;
1105         if (i) {
1106                 state |= RMAP_RIGHT_VALID;
1107                 error = xfs_rmap_get_rec(cur, &RIGHT, &i);
1108                 if (error)
1109                         goto done;
1110                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1111                         error = -EFSCORRUPTED;
1112                         goto done;
1113                 }
1114                 if (XFS_IS_CORRUPT(mp, bno + len > RIGHT.rm_startblock)) {
1115                         error = -EFSCORRUPTED;
1116                         goto done;
1117                 }
1118                 trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp,
1119                                 cur->bc_ag.pag->pag_agno, RIGHT.rm_startblock,
1120                                 RIGHT.rm_blockcount, RIGHT.rm_owner,
1121                                 RIGHT.rm_offset, RIGHT.rm_flags);
1122                 if (bno + len == RIGHT.rm_startblock &&
1123                     offset + len == RIGHT.rm_offset &&
1124                     xfs_rmap_is_mergeable(&RIGHT, owner, newext))
1125                         state |= RMAP_RIGHT_CONTIG;
1126         }
1127
1128         /* check that left + prev + right is not too long */
1129         if ((state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1130                          RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) ==
1131             (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1132              RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG) &&
1133             (unsigned long)LEFT.rm_blockcount + len +
1134              RIGHT.rm_blockcount > XFS_RMAP_LEN_MAX)
1135                 state &= ~RMAP_RIGHT_CONTIG;
1136
1137         trace_xfs_rmap_convert_state(mp, cur->bc_ag.pag->pag_agno, state,
1138                         _RET_IP_);
1139
1140         /* reset the cursor back to PREV */
1141         error = xfs_rmap_lookup_le(cur, bno, len, owner, offset, oldext, &i);
1142         if (error)
1143                 goto done;
1144         if (XFS_IS_CORRUPT(mp, i != 1)) {
1145                 error = -EFSCORRUPTED;
1146                 goto done;
1147         }
1148
1149         /*
1150          * Switch out based on the FILLING and CONTIG state bits.
1151          */
1152         switch (state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1153                          RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) {
1154         case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1155              RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1156                 /*
1157                  * Setting all of a previous oldext extent to newext.
1158                  * The left and right neighbors are both contiguous with new.
1159                  */
1160                 error = xfs_btree_increment(cur, 0, &i);
1161                 if (error)
1162                         goto done;
1163                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1164                         error = -EFSCORRUPTED;
1165                         goto done;
1166                 }
1167                 trace_xfs_rmap_delete(mp, cur->bc_ag.pag->pag_agno,
1168                                 RIGHT.rm_startblock, RIGHT.rm_blockcount,
1169                                 RIGHT.rm_owner, RIGHT.rm_offset,
1170                                 RIGHT.rm_flags);
1171                 error = xfs_btree_delete(cur, &i);
1172                 if (error)
1173                         goto done;
1174                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1175                         error = -EFSCORRUPTED;
1176                         goto done;
1177                 }
1178                 error = xfs_btree_decrement(cur, 0, &i);
1179                 if (error)
1180                         goto done;
1181                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1182                         error = -EFSCORRUPTED;
1183                         goto done;
1184                 }
1185                 trace_xfs_rmap_delete(mp, cur->bc_ag.pag->pag_agno,
1186                                 PREV.rm_startblock, PREV.rm_blockcount,
1187                                 PREV.rm_owner, PREV.rm_offset,
1188                                 PREV.rm_flags);
1189                 error = xfs_btree_delete(cur, &i);
1190                 if (error)
1191                         goto done;
1192                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1193                         error = -EFSCORRUPTED;
1194                         goto done;
1195                 }
1196                 error = xfs_btree_decrement(cur, 0, &i);
1197                 if (error)
1198                         goto done;
1199                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1200                         error = -EFSCORRUPTED;
1201                         goto done;
1202                 }
1203                 NEW = LEFT;
1204                 NEW.rm_blockcount += PREV.rm_blockcount + RIGHT.rm_blockcount;
1205                 error = xfs_rmap_update(cur, &NEW);
1206                 if (error)
1207                         goto done;
1208                 break;
1209
1210         case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG:
1211                 /*
1212                  * Setting all of a previous oldext extent to newext.
1213                  * The left neighbor is contiguous, the right is not.
1214                  */
1215                 trace_xfs_rmap_delete(mp, cur->bc_ag.pag->pag_agno,
1216                                 PREV.rm_startblock, PREV.rm_blockcount,
1217                                 PREV.rm_owner, PREV.rm_offset,
1218                                 PREV.rm_flags);
1219                 error = xfs_btree_delete(cur, &i);
1220                 if (error)
1221                         goto done;
1222                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1223                         error = -EFSCORRUPTED;
1224                         goto done;
1225                 }
1226                 error = xfs_btree_decrement(cur, 0, &i);
1227                 if (error)
1228                         goto done;
1229                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1230                         error = -EFSCORRUPTED;
1231                         goto done;
1232                 }
1233                 NEW = LEFT;
1234                 NEW.rm_blockcount += PREV.rm_blockcount;
1235                 error = xfs_rmap_update(cur, &NEW);
1236                 if (error)
1237                         goto done;
1238                 break;
1239
1240         case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1241                 /*
1242                  * Setting all of a previous oldext extent to newext.
1243                  * The right neighbor is contiguous, the left is not.
1244                  */
1245                 error = xfs_btree_increment(cur, 0, &i);
1246                 if (error)
1247                         goto done;
1248                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1249                         error = -EFSCORRUPTED;
1250                         goto done;
1251                 }
1252                 trace_xfs_rmap_delete(mp, cur->bc_ag.pag->pag_agno,
1253                                 RIGHT.rm_startblock, RIGHT.rm_blockcount,
1254                                 RIGHT.rm_owner, RIGHT.rm_offset,
1255                                 RIGHT.rm_flags);
1256                 error = xfs_btree_delete(cur, &i);
1257                 if (error)
1258                         goto done;
1259                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1260                         error = -EFSCORRUPTED;
1261                         goto done;
1262                 }
1263                 error = xfs_btree_decrement(cur, 0, &i);
1264                 if (error)
1265                         goto done;
1266                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1267                         error = -EFSCORRUPTED;
1268                         goto done;
1269                 }
1270                 NEW = PREV;
1271                 NEW.rm_blockcount = len + RIGHT.rm_blockcount;
1272                 NEW.rm_flags = newext;
1273                 error = xfs_rmap_update(cur, &NEW);
1274                 if (error)
1275                         goto done;
1276                 break;
1277
1278         case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING:
1279                 /*
1280                  * Setting all of a previous oldext extent to newext.
1281                  * Neither the left nor right neighbors are contiguous with
1282                  * the new one.
1283                  */
1284                 NEW = PREV;
1285                 NEW.rm_flags = newext;
1286                 error = xfs_rmap_update(cur, &NEW);
1287                 if (error)
1288                         goto done;
1289                 break;
1290
1291         case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG:
1292                 /*
1293                  * Setting the first part of a previous oldext extent to newext.
1294                  * The left neighbor is contiguous.
1295                  */
1296                 NEW = PREV;
1297                 NEW.rm_offset += len;
1298                 NEW.rm_startblock += len;
1299                 NEW.rm_blockcount -= len;
1300                 error = xfs_rmap_update(cur, &NEW);
1301                 if (error)
1302                         goto done;
1303                 error = xfs_btree_decrement(cur, 0, &i);
1304                 if (error)
1305                         goto done;
1306                 NEW = LEFT;
1307                 NEW.rm_blockcount += len;
1308                 error = xfs_rmap_update(cur, &NEW);
1309                 if (error)
1310                         goto done;
1311                 break;
1312
1313         case RMAP_LEFT_FILLING:
1314                 /*
1315                  * Setting the first part of a previous oldext extent to newext.
1316                  * The left neighbor is not contiguous.
1317                  */
1318                 NEW = PREV;
1319                 NEW.rm_startblock += len;
1320                 NEW.rm_offset += len;
1321                 NEW.rm_blockcount -= len;
1322                 error = xfs_rmap_update(cur, &NEW);
1323                 if (error)
1324                         goto done;
1325                 NEW.rm_startblock = bno;
1326                 NEW.rm_owner = owner;
1327                 NEW.rm_offset = offset;
1328                 NEW.rm_blockcount = len;
1329                 NEW.rm_flags = newext;
1330                 cur->bc_rec.r = NEW;
1331                 trace_xfs_rmap_insert(mp, cur->bc_ag.pag->pag_agno, bno,
1332                                 len, owner, offset, newext);
1333                 error = xfs_btree_insert(cur, &i);
1334                 if (error)
1335                         goto done;
1336                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1337                         error = -EFSCORRUPTED;
1338                         goto done;
1339                 }
1340                 break;
1341
1342         case RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1343                 /*
1344                  * Setting the last part of a previous oldext extent to newext.
1345                  * The right neighbor is contiguous with the new allocation.
1346                  */
1347                 NEW = PREV;
1348                 NEW.rm_blockcount -= len;
1349                 error = xfs_rmap_update(cur, &NEW);
1350                 if (error)
1351                         goto done;
1352                 error = xfs_btree_increment(cur, 0, &i);
1353                 if (error)
1354                         goto done;
1355                 NEW = RIGHT;
1356                 NEW.rm_offset = offset;
1357                 NEW.rm_startblock = bno;
1358                 NEW.rm_blockcount += len;
1359                 error = xfs_rmap_update(cur, &NEW);
1360                 if (error)
1361                         goto done;
1362                 break;
1363
1364         case RMAP_RIGHT_FILLING:
1365                 /*
1366                  * Setting the last part of a previous oldext extent to newext.
1367                  * The right neighbor is not contiguous.
1368                  */
1369                 NEW = PREV;
1370                 NEW.rm_blockcount -= len;
1371                 error = xfs_rmap_update(cur, &NEW);
1372                 if (error)
1373                         goto done;
1374                 error = xfs_rmap_lookup_eq(cur, bno, len, owner, offset,
1375                                 oldext, &i);
1376                 if (error)
1377                         goto done;
1378                 if (XFS_IS_CORRUPT(mp, i != 0)) {
1379                         error = -EFSCORRUPTED;
1380                         goto done;
1381                 }
1382                 NEW.rm_startblock = bno;
1383                 NEW.rm_owner = owner;
1384                 NEW.rm_offset = offset;
1385                 NEW.rm_blockcount = len;
1386                 NEW.rm_flags = newext;
1387                 cur->bc_rec.r = NEW;
1388                 trace_xfs_rmap_insert(mp, cur->bc_ag.pag->pag_agno, bno,
1389                                 len, owner, offset, newext);
1390                 error = xfs_btree_insert(cur, &i);
1391                 if (error)
1392                         goto done;
1393                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1394                         error = -EFSCORRUPTED;
1395                         goto done;
1396                 }
1397                 break;
1398
1399         case 0:
1400                 /*
1401                  * Setting the middle part of a previous oldext extent to
1402                  * newext.  Contiguity is impossible here.
1403                  * One extent becomes three extents.
1404                  */
1405                 /* new right extent - oldext */
1406                 NEW.rm_startblock = bno + len;
1407                 NEW.rm_owner = owner;
1408                 NEW.rm_offset = new_endoff;
1409                 NEW.rm_blockcount = PREV.rm_offset + PREV.rm_blockcount -
1410                                 new_endoff;
1411                 NEW.rm_flags = PREV.rm_flags;
1412                 error = xfs_rmap_update(cur, &NEW);
1413                 if (error)
1414                         goto done;
1415                 /* new left extent - oldext */
1416                 NEW = PREV;
1417                 NEW.rm_blockcount = offset - PREV.rm_offset;
1418                 cur->bc_rec.r = NEW;
1419                 trace_xfs_rmap_insert(mp, cur->bc_ag.pag->pag_agno,
1420                                 NEW.rm_startblock, NEW.rm_blockcount,
1421                                 NEW.rm_owner, NEW.rm_offset,
1422                                 NEW.rm_flags);
1423                 error = xfs_btree_insert(cur, &i);
1424                 if (error)
1425                         goto done;
1426                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1427                         error = -EFSCORRUPTED;
1428                         goto done;
1429                 }
1430                 /*
1431                  * Reset the cursor to the position of the new extent
1432                  * we are about to insert as we can't trust it after
1433                  * the previous insert.
1434                  */
1435                 error = xfs_rmap_lookup_eq(cur, bno, len, owner, offset,
1436                                 oldext, &i);
1437                 if (error)
1438                         goto done;
1439                 if (XFS_IS_CORRUPT(mp, i != 0)) {
1440                         error = -EFSCORRUPTED;
1441                         goto done;
1442                 }
1443                 /* new middle extent - newext */
1444                 cur->bc_rec.r.rm_flags &= ~XFS_RMAP_UNWRITTEN;
1445                 cur->bc_rec.r.rm_flags |= newext;
1446                 trace_xfs_rmap_insert(mp, cur->bc_ag.pag->pag_agno, bno, len,
1447                                 owner, offset, newext);
1448                 error = xfs_btree_insert(cur, &i);
1449                 if (error)
1450                         goto done;
1451                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1452                         error = -EFSCORRUPTED;
1453                         goto done;
1454                 }
1455                 break;
1456
1457         case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1458         case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1459         case RMAP_LEFT_FILLING | RMAP_RIGHT_CONTIG:
1460         case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG:
1461         case RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1462         case RMAP_LEFT_CONTIG:
1463         case RMAP_RIGHT_CONTIG:
1464                 /*
1465                  * These cases are all impossible.
1466                  */
1467                 ASSERT(0);
1468         }
1469
1470         trace_xfs_rmap_convert_done(mp, cur->bc_ag.pag->pag_agno, bno, len,
1471                         unwritten, oinfo);
1472 done:
1473         if (error)
1474                 trace_xfs_rmap_convert_error(cur->bc_mp,
1475                                 cur->bc_ag.pag->pag_agno, error, _RET_IP_);
1476         return error;
1477 }
1478
1479 /*
1480  * Convert an unwritten extent to a real extent or vice versa.  If there is no
1481  * possibility of overlapping extents, delegate to the simpler convert
1482  * function.
1483  */
1484 STATIC int
1485 xfs_rmap_convert_shared(
1486         struct xfs_btree_cur            *cur,
1487         xfs_agblock_t                   bno,
1488         xfs_extlen_t                    len,
1489         bool                            unwritten,
1490         const struct xfs_owner_info     *oinfo)
1491 {
1492         struct xfs_mount                *mp = cur->bc_mp;
1493         struct xfs_rmap_irec            r[4];   /* neighbor extent entries */
1494                                                 /* left is 0, right is 1, */
1495                                                 /* prev is 2, new is 3 */
1496         uint64_t                owner;
1497         uint64_t                offset;
1498         uint64_t                new_endoff;
1499         unsigned int            oldext;
1500         unsigned int            newext;
1501         unsigned int            flags = 0;
1502         int                     i;
1503         int                     state = 0;
1504         int                     error;
1505
1506         xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
1507         ASSERT(!(XFS_RMAP_NON_INODE_OWNER(owner) ||
1508                         (flags & (XFS_RMAP_ATTR_FORK | XFS_RMAP_BMBT_BLOCK))));
1509         oldext = unwritten ? XFS_RMAP_UNWRITTEN : 0;
1510         new_endoff = offset + len;
1511         trace_xfs_rmap_convert(mp, cur->bc_ag.pag->pag_agno, bno, len,
1512                         unwritten, oinfo);
1513
1514         /*
1515          * For the initial lookup, look for and exact match or the left-adjacent
1516          * record for our insertion point. This will also give us the record for
1517          * start block contiguity tests.
1518          */
1519         error = xfs_rmap_lookup_le_range(cur, bno, owner, offset, oldext,
1520                         &PREV, &i);
1521         if (error)
1522                 goto done;
1523         if (XFS_IS_CORRUPT(mp, i != 1)) {
1524                 error = -EFSCORRUPTED;
1525                 goto done;
1526         }
1527
1528         ASSERT(PREV.rm_offset <= offset);
1529         ASSERT(PREV.rm_offset + PREV.rm_blockcount >= new_endoff);
1530         ASSERT((PREV.rm_flags & XFS_RMAP_UNWRITTEN) == oldext);
1531         newext = ~oldext & XFS_RMAP_UNWRITTEN;
1532
1533         /*
1534          * Set flags determining what part of the previous oldext allocation
1535          * extent is being replaced by a newext allocation.
1536          */
1537         if (PREV.rm_offset == offset)
1538                 state |= RMAP_LEFT_FILLING;
1539         if (PREV.rm_offset + PREV.rm_blockcount == new_endoff)
1540                 state |= RMAP_RIGHT_FILLING;
1541
1542         /* Is there a left record that abuts our range? */
1543         error = xfs_rmap_find_left_neighbor(cur, bno, owner, offset, newext,
1544                         &LEFT, &i);
1545         if (error)
1546                 goto done;
1547         if (i) {
1548                 state |= RMAP_LEFT_VALID;
1549                 if (XFS_IS_CORRUPT(mp,
1550                                    LEFT.rm_startblock + LEFT.rm_blockcount >
1551                                    bno)) {
1552                         error = -EFSCORRUPTED;
1553                         goto done;
1554                 }
1555                 if (xfs_rmap_is_mergeable(&LEFT, owner, newext))
1556                         state |= RMAP_LEFT_CONTIG;
1557         }
1558
1559         /* Is there a right record that abuts our range? */
1560         error = xfs_rmap_lookup_eq(cur, bno + len, len, owner, offset + len,
1561                         newext, &i);
1562         if (error)
1563                 goto done;
1564         if (i) {
1565                 state |= RMAP_RIGHT_VALID;
1566                 error = xfs_rmap_get_rec(cur, &RIGHT, &i);
1567                 if (error)
1568                         goto done;
1569                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1570                         error = -EFSCORRUPTED;
1571                         goto done;
1572                 }
1573                 if (XFS_IS_CORRUPT(mp, bno + len > RIGHT.rm_startblock)) {
1574                         error = -EFSCORRUPTED;
1575                         goto done;
1576                 }
1577                 trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp,
1578                                 cur->bc_ag.pag->pag_agno, RIGHT.rm_startblock,
1579                                 RIGHT.rm_blockcount, RIGHT.rm_owner,
1580                                 RIGHT.rm_offset, RIGHT.rm_flags);
1581                 if (xfs_rmap_is_mergeable(&RIGHT, owner, newext))
1582                         state |= RMAP_RIGHT_CONTIG;
1583         }
1584
1585         /* check that left + prev + right is not too long */
1586         if ((state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1587                          RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) ==
1588             (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1589              RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG) &&
1590             (unsigned long)LEFT.rm_blockcount + len +
1591              RIGHT.rm_blockcount > XFS_RMAP_LEN_MAX)
1592                 state &= ~RMAP_RIGHT_CONTIG;
1593
1594         trace_xfs_rmap_convert_state(mp, cur->bc_ag.pag->pag_agno, state,
1595                         _RET_IP_);
1596         /*
1597          * Switch out based on the FILLING and CONTIG state bits.
1598          */
1599         switch (state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1600                          RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) {
1601         case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1602              RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1603                 /*
1604                  * Setting all of a previous oldext extent to newext.
1605                  * The left and right neighbors are both contiguous with new.
1606                  */
1607                 error = xfs_rmap_delete(cur, RIGHT.rm_startblock,
1608                                 RIGHT.rm_blockcount, RIGHT.rm_owner,
1609                                 RIGHT.rm_offset, RIGHT.rm_flags);
1610                 if (error)
1611                         goto done;
1612                 error = xfs_rmap_delete(cur, PREV.rm_startblock,
1613                                 PREV.rm_blockcount, PREV.rm_owner,
1614                                 PREV.rm_offset, PREV.rm_flags);
1615                 if (error)
1616                         goto done;
1617                 NEW = LEFT;
1618                 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1619                                 NEW.rm_blockcount, NEW.rm_owner,
1620                                 NEW.rm_offset, NEW.rm_flags, &i);
1621                 if (error)
1622                         goto done;
1623                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1624                         error = -EFSCORRUPTED;
1625                         goto done;
1626                 }
1627                 NEW.rm_blockcount += PREV.rm_blockcount + RIGHT.rm_blockcount;
1628                 error = xfs_rmap_update(cur, &NEW);
1629                 if (error)
1630                         goto done;
1631                 break;
1632
1633         case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG:
1634                 /*
1635                  * Setting all of a previous oldext extent to newext.
1636                  * The left neighbor is contiguous, the right is not.
1637                  */
1638                 error = xfs_rmap_delete(cur, PREV.rm_startblock,
1639                                 PREV.rm_blockcount, PREV.rm_owner,
1640                                 PREV.rm_offset, PREV.rm_flags);
1641                 if (error)
1642                         goto done;
1643                 NEW = LEFT;
1644                 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1645                                 NEW.rm_blockcount, NEW.rm_owner,
1646                                 NEW.rm_offset, NEW.rm_flags, &i);
1647                 if (error)
1648                         goto done;
1649                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1650                         error = -EFSCORRUPTED;
1651                         goto done;
1652                 }
1653                 NEW.rm_blockcount += PREV.rm_blockcount;
1654                 error = xfs_rmap_update(cur, &NEW);
1655                 if (error)
1656                         goto done;
1657                 break;
1658
1659         case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1660                 /*
1661                  * Setting all of a previous oldext extent to newext.
1662                  * The right neighbor is contiguous, the left is not.
1663                  */
1664                 error = xfs_rmap_delete(cur, RIGHT.rm_startblock,
1665                                 RIGHT.rm_blockcount, RIGHT.rm_owner,
1666                                 RIGHT.rm_offset, RIGHT.rm_flags);
1667                 if (error)
1668                         goto done;
1669                 NEW = PREV;
1670                 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1671                                 NEW.rm_blockcount, NEW.rm_owner,
1672                                 NEW.rm_offset, NEW.rm_flags, &i);
1673                 if (error)
1674                         goto done;
1675                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1676                         error = -EFSCORRUPTED;
1677                         goto done;
1678                 }
1679                 NEW.rm_blockcount += RIGHT.rm_blockcount;
1680                 NEW.rm_flags = RIGHT.rm_flags;
1681                 error = xfs_rmap_update(cur, &NEW);
1682                 if (error)
1683                         goto done;
1684                 break;
1685
1686         case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING:
1687                 /*
1688                  * Setting all of a previous oldext extent to newext.
1689                  * Neither the left nor right neighbors are contiguous with
1690                  * the new one.
1691                  */
1692                 NEW = PREV;
1693                 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1694                                 NEW.rm_blockcount, NEW.rm_owner,
1695                                 NEW.rm_offset, NEW.rm_flags, &i);
1696                 if (error)
1697                         goto done;
1698                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1699                         error = -EFSCORRUPTED;
1700                         goto done;
1701                 }
1702                 NEW.rm_flags = newext;
1703                 error = xfs_rmap_update(cur, &NEW);
1704                 if (error)
1705                         goto done;
1706                 break;
1707
1708         case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG:
1709                 /*
1710                  * Setting the first part of a previous oldext extent to newext.
1711                  * The left neighbor is contiguous.
1712                  */
1713                 NEW = PREV;
1714                 error = xfs_rmap_delete(cur, NEW.rm_startblock,
1715                                 NEW.rm_blockcount, NEW.rm_owner,
1716                                 NEW.rm_offset, NEW.rm_flags);
1717                 if (error)
1718                         goto done;
1719                 NEW.rm_offset += len;
1720                 NEW.rm_startblock += len;
1721                 NEW.rm_blockcount -= len;
1722                 error = xfs_rmap_insert(cur, NEW.rm_startblock,
1723                                 NEW.rm_blockcount, NEW.rm_owner,
1724                                 NEW.rm_offset, NEW.rm_flags);
1725                 if (error)
1726                         goto done;
1727                 NEW = LEFT;
1728                 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1729                                 NEW.rm_blockcount, NEW.rm_owner,
1730                                 NEW.rm_offset, NEW.rm_flags, &i);
1731                 if (error)
1732                         goto done;
1733                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1734                         error = -EFSCORRUPTED;
1735                         goto done;
1736                 }
1737                 NEW.rm_blockcount += len;
1738                 error = xfs_rmap_update(cur, &NEW);
1739                 if (error)
1740                         goto done;
1741                 break;
1742
1743         case RMAP_LEFT_FILLING:
1744                 /*
1745                  * Setting the first part of a previous oldext extent to newext.
1746                  * The left neighbor is not contiguous.
1747                  */
1748                 NEW = PREV;
1749                 error = xfs_rmap_delete(cur, NEW.rm_startblock,
1750                                 NEW.rm_blockcount, NEW.rm_owner,
1751                                 NEW.rm_offset, NEW.rm_flags);
1752                 if (error)
1753                         goto done;
1754                 NEW.rm_offset += len;
1755                 NEW.rm_startblock += len;
1756                 NEW.rm_blockcount -= len;
1757                 error = xfs_rmap_insert(cur, NEW.rm_startblock,
1758                                 NEW.rm_blockcount, NEW.rm_owner,
1759                                 NEW.rm_offset, NEW.rm_flags);
1760                 if (error)
1761                         goto done;
1762                 error = xfs_rmap_insert(cur, bno, len, owner, offset, newext);
1763                 if (error)
1764                         goto done;
1765                 break;
1766
1767         case RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1768                 /*
1769                  * Setting the last part of a previous oldext extent to newext.
1770                  * The right neighbor is contiguous with the new allocation.
1771                  */
1772                 NEW = PREV;
1773                 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1774                                 NEW.rm_blockcount, NEW.rm_owner,
1775                                 NEW.rm_offset, NEW.rm_flags, &i);
1776                 if (error)
1777                         goto done;
1778                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1779                         error = -EFSCORRUPTED;
1780                         goto done;
1781                 }
1782                 NEW.rm_blockcount = offset - NEW.rm_offset;
1783                 error = xfs_rmap_update(cur, &NEW);
1784                 if (error)
1785                         goto done;
1786                 NEW = RIGHT;
1787                 error = xfs_rmap_delete(cur, NEW.rm_startblock,
1788                                 NEW.rm_blockcount, NEW.rm_owner,
1789                                 NEW.rm_offset, NEW.rm_flags);
1790                 if (error)
1791                         goto done;
1792                 NEW.rm_offset = offset;
1793                 NEW.rm_startblock = bno;
1794                 NEW.rm_blockcount += len;
1795                 error = xfs_rmap_insert(cur, NEW.rm_startblock,
1796                                 NEW.rm_blockcount, NEW.rm_owner,
1797                                 NEW.rm_offset, NEW.rm_flags);
1798                 if (error)
1799                         goto done;
1800                 break;
1801
1802         case RMAP_RIGHT_FILLING:
1803                 /*
1804                  * Setting the last part of a previous oldext extent to newext.
1805                  * The right neighbor is not contiguous.
1806                  */
1807                 NEW = PREV;
1808                 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1809                                 NEW.rm_blockcount, NEW.rm_owner,
1810                                 NEW.rm_offset, NEW.rm_flags, &i);
1811                 if (error)
1812                         goto done;
1813                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1814                         error = -EFSCORRUPTED;
1815                         goto done;
1816                 }
1817                 NEW.rm_blockcount -= len;
1818                 error = xfs_rmap_update(cur, &NEW);
1819                 if (error)
1820                         goto done;
1821                 error = xfs_rmap_insert(cur, bno, len, owner, offset, newext);
1822                 if (error)
1823                         goto done;
1824                 break;
1825
1826         case 0:
1827                 /*
1828                  * Setting the middle part of a previous oldext extent to
1829                  * newext.  Contiguity is impossible here.
1830                  * One extent becomes three extents.
1831                  */
1832                 /* new right extent - oldext */
1833                 NEW.rm_startblock = bno + len;
1834                 NEW.rm_owner = owner;
1835                 NEW.rm_offset = new_endoff;
1836                 NEW.rm_blockcount = PREV.rm_offset + PREV.rm_blockcount -
1837                                 new_endoff;
1838                 NEW.rm_flags = PREV.rm_flags;
1839                 error = xfs_rmap_insert(cur, NEW.rm_startblock,
1840                                 NEW.rm_blockcount, NEW.rm_owner, NEW.rm_offset,
1841                                 NEW.rm_flags);
1842                 if (error)
1843                         goto done;
1844                 /* new left extent - oldext */
1845                 NEW = PREV;
1846                 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1847                                 NEW.rm_blockcount, NEW.rm_owner,
1848                                 NEW.rm_offset, NEW.rm_flags, &i);
1849                 if (error)
1850                         goto done;
1851                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1852                         error = -EFSCORRUPTED;
1853                         goto done;
1854                 }
1855                 NEW.rm_blockcount = offset - NEW.rm_offset;
1856                 error = xfs_rmap_update(cur, &NEW);
1857                 if (error)
1858                         goto done;
1859                 /* new middle extent - newext */
1860                 NEW.rm_startblock = bno;
1861                 NEW.rm_blockcount = len;
1862                 NEW.rm_owner = owner;
1863                 NEW.rm_offset = offset;
1864                 NEW.rm_flags = newext;
1865                 error = xfs_rmap_insert(cur, NEW.rm_startblock,
1866                                 NEW.rm_blockcount, NEW.rm_owner, NEW.rm_offset,
1867                                 NEW.rm_flags);
1868                 if (error)
1869                         goto done;
1870                 break;
1871
1872         case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1873         case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1874         case RMAP_LEFT_FILLING | RMAP_RIGHT_CONTIG:
1875         case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG:
1876         case RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1877         case RMAP_LEFT_CONTIG:
1878         case RMAP_RIGHT_CONTIG:
1879                 /*
1880                  * These cases are all impossible.
1881                  */
1882                 ASSERT(0);
1883         }
1884
1885         trace_xfs_rmap_convert_done(mp, cur->bc_ag.pag->pag_agno, bno, len,
1886                         unwritten, oinfo);
1887 done:
1888         if (error)
1889                 trace_xfs_rmap_convert_error(cur->bc_mp,
1890                                 cur->bc_ag.pag->pag_agno, error, _RET_IP_);
1891         return error;
1892 }
1893
1894 #undef  NEW
1895 #undef  LEFT
1896 #undef  RIGHT
1897 #undef  PREV
1898
1899 /*
1900  * Find an extent in the rmap btree and unmap it.  For rmap extent types that
1901  * can overlap (data fork rmaps on reflink filesystems) we must be careful
1902  * that the prev/next records in the btree might belong to another owner.
1903  * Therefore we must use delete+insert to alter any of the key fields.
1904  *
1905  * For every other situation there can only be one owner for a given extent,
1906  * so we can call the regular _free function.
1907  */
1908 STATIC int
1909 xfs_rmap_unmap_shared(
1910         struct xfs_btree_cur            *cur,
1911         xfs_agblock_t                   bno,
1912         xfs_extlen_t                    len,
1913         bool                            unwritten,
1914         const struct xfs_owner_info     *oinfo)
1915 {
1916         struct xfs_mount                *mp = cur->bc_mp;
1917         struct xfs_rmap_irec            ltrec;
1918         uint64_t                        ltoff;
1919         int                             error = 0;
1920         int                             i;
1921         uint64_t                        owner;
1922         uint64_t                        offset;
1923         unsigned int                    flags;
1924
1925         xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
1926         if (unwritten)
1927                 flags |= XFS_RMAP_UNWRITTEN;
1928         trace_xfs_rmap_unmap(mp, cur->bc_ag.pag->pag_agno, bno, len,
1929                         unwritten, oinfo);
1930
1931         /*
1932          * We should always have a left record because there's a static record
1933          * for the AG headers at rm_startblock == 0 created by mkfs/growfs that
1934          * will not ever be removed from the tree.
1935          */
1936         error = xfs_rmap_lookup_le_range(cur, bno, owner, offset, flags,
1937                         &ltrec, &i);
1938         if (error)
1939                 goto out_error;
1940         if (XFS_IS_CORRUPT(mp, i != 1)) {
1941                 error = -EFSCORRUPTED;
1942                 goto out_error;
1943         }
1944         ltoff = ltrec.rm_offset;
1945
1946         /* Make sure the extent we found covers the entire freeing range. */
1947         if (XFS_IS_CORRUPT(mp,
1948                            ltrec.rm_startblock > bno ||
1949                            ltrec.rm_startblock + ltrec.rm_blockcount <
1950                            bno + len)) {
1951                 error = -EFSCORRUPTED;
1952                 goto out_error;
1953         }
1954
1955         /* Make sure the owner matches what we expect to find in the tree. */
1956         if (XFS_IS_CORRUPT(mp, owner != ltrec.rm_owner)) {
1957                 error = -EFSCORRUPTED;
1958                 goto out_error;
1959         }
1960
1961         /* Make sure the unwritten flag matches. */
1962         if (XFS_IS_CORRUPT(mp,
1963                            (flags & XFS_RMAP_UNWRITTEN) !=
1964                            (ltrec.rm_flags & XFS_RMAP_UNWRITTEN))) {
1965                 error = -EFSCORRUPTED;
1966                 goto out_error;
1967         }
1968
1969         /* Check the offset. */
1970         if (XFS_IS_CORRUPT(mp, ltrec.rm_offset > offset)) {
1971                 error = -EFSCORRUPTED;
1972                 goto out_error;
1973         }
1974         if (XFS_IS_CORRUPT(mp, offset > ltoff + ltrec.rm_blockcount)) {
1975                 error = -EFSCORRUPTED;
1976                 goto out_error;
1977         }
1978
1979         if (ltrec.rm_startblock == bno && ltrec.rm_blockcount == len) {
1980                 /* Exact match, simply remove the record from rmap tree. */
1981                 error = xfs_rmap_delete(cur, ltrec.rm_startblock,
1982                                 ltrec.rm_blockcount, ltrec.rm_owner,
1983                                 ltrec.rm_offset, ltrec.rm_flags);
1984                 if (error)
1985                         goto out_error;
1986         } else if (ltrec.rm_startblock == bno) {
1987                 /*
1988                  * Overlap left hand side of extent: move the start, trim the
1989                  * length and update the current record.
1990                  *
1991                  *       ltbno                ltlen
1992                  * Orig:    |oooooooooooooooooooo|
1993                  * Freeing: |fffffffff|
1994                  * Result:            |rrrrrrrrrr|
1995                  *         bno       len
1996                  */
1997
1998                 /* Delete prev rmap. */
1999                 error = xfs_rmap_delete(cur, ltrec.rm_startblock,
2000                                 ltrec.rm_blockcount, ltrec.rm_owner,
2001                                 ltrec.rm_offset, ltrec.rm_flags);
2002                 if (error)
2003                         goto out_error;
2004
2005                 /* Add an rmap at the new offset. */
2006                 ltrec.rm_startblock += len;
2007                 ltrec.rm_blockcount -= len;
2008                 ltrec.rm_offset += len;
2009                 error = xfs_rmap_insert(cur, ltrec.rm_startblock,
2010                                 ltrec.rm_blockcount, ltrec.rm_owner,
2011                                 ltrec.rm_offset, ltrec.rm_flags);
2012                 if (error)
2013                         goto out_error;
2014         } else if (ltrec.rm_startblock + ltrec.rm_blockcount == bno + len) {
2015                 /*
2016                  * Overlap right hand side of extent: trim the length and
2017                  * update the current record.
2018                  *
2019                  *       ltbno                ltlen
2020                  * Orig:    |oooooooooooooooooooo|
2021                  * Freeing:            |fffffffff|
2022                  * Result:  |rrrrrrrrrr|
2023                  *                    bno       len
2024                  */
2025                 error = xfs_rmap_lookup_eq(cur, ltrec.rm_startblock,
2026                                 ltrec.rm_blockcount, ltrec.rm_owner,
2027                                 ltrec.rm_offset, ltrec.rm_flags, &i);
2028                 if (error)
2029                         goto out_error;
2030                 if (XFS_IS_CORRUPT(mp, i != 1)) {
2031                         error = -EFSCORRUPTED;
2032                         goto out_error;
2033                 }
2034                 ltrec.rm_blockcount -= len;
2035                 error = xfs_rmap_update(cur, &ltrec);
2036                 if (error)
2037                         goto out_error;
2038         } else {
2039                 /*
2040                  * Overlap middle of extent: trim the length of the existing
2041                  * record to the length of the new left-extent size, increment
2042                  * the insertion position so we can insert a new record
2043                  * containing the remaining right-extent space.
2044                  *
2045                  *       ltbno                ltlen
2046                  * Orig:    |oooooooooooooooooooo|
2047                  * Freeing:       |fffffffff|
2048                  * Result:  |rrrrr|         |rrrr|
2049                  *               bno       len
2050                  */
2051                 xfs_extlen_t    orig_len = ltrec.rm_blockcount;
2052
2053                 /* Shrink the left side of the rmap */
2054                 error = xfs_rmap_lookup_eq(cur, ltrec.rm_startblock,
2055                                 ltrec.rm_blockcount, ltrec.rm_owner,
2056                                 ltrec.rm_offset, ltrec.rm_flags, &i);
2057                 if (error)
2058                         goto out_error;
2059                 if (XFS_IS_CORRUPT(mp, i != 1)) {
2060                         error = -EFSCORRUPTED;
2061                         goto out_error;
2062                 }
2063                 ltrec.rm_blockcount = bno - ltrec.rm_startblock;
2064                 error = xfs_rmap_update(cur, &ltrec);
2065                 if (error)
2066                         goto out_error;
2067
2068                 /* Add an rmap at the new offset */
2069                 error = xfs_rmap_insert(cur, bno + len,
2070                                 orig_len - len - ltrec.rm_blockcount,
2071                                 ltrec.rm_owner, offset + len,
2072                                 ltrec.rm_flags);
2073                 if (error)
2074                         goto out_error;
2075         }
2076
2077         trace_xfs_rmap_unmap_done(mp, cur->bc_ag.pag->pag_agno, bno, len,
2078                         unwritten, oinfo);
2079 out_error:
2080         if (error)
2081                 trace_xfs_rmap_unmap_error(cur->bc_mp,
2082                                 cur->bc_ag.pag->pag_agno, error, _RET_IP_);
2083         return error;
2084 }
2085
2086 /*
2087  * Find an extent in the rmap btree and map it.  For rmap extent types that
2088  * can overlap (data fork rmaps on reflink filesystems) we must be careful
2089  * that the prev/next records in the btree might belong to another owner.
2090  * Therefore we must use delete+insert to alter any of the key fields.
2091  *
2092  * For every other situation there can only be one owner for a given extent,
2093  * so we can call the regular _alloc function.
2094  */
2095 STATIC int
2096 xfs_rmap_map_shared(
2097         struct xfs_btree_cur            *cur,
2098         xfs_agblock_t                   bno,
2099         xfs_extlen_t                    len,
2100         bool                            unwritten,
2101         const struct xfs_owner_info     *oinfo)
2102 {
2103         struct xfs_mount                *mp = cur->bc_mp;
2104         struct xfs_rmap_irec            ltrec;
2105         struct xfs_rmap_irec            gtrec;
2106         int                             have_gt;
2107         int                             have_lt;
2108         int                             error = 0;
2109         int                             i;
2110         uint64_t                        owner;
2111         uint64_t                        offset;
2112         unsigned int                    flags = 0;
2113
2114         xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
2115         if (unwritten)
2116                 flags |= XFS_RMAP_UNWRITTEN;
2117         trace_xfs_rmap_map(mp, cur->bc_ag.pag->pag_agno, bno, len,
2118                         unwritten, oinfo);
2119
2120         /* Is there a left record that abuts our range? */
2121         error = xfs_rmap_find_left_neighbor(cur, bno, owner, offset, flags,
2122                         &ltrec, &have_lt);
2123         if (error)
2124                 goto out_error;
2125         if (have_lt &&
2126             !xfs_rmap_is_mergeable(&ltrec, owner, flags))
2127                 have_lt = 0;
2128
2129         /* Is there a right record that abuts our range? */
2130         error = xfs_rmap_lookup_eq(cur, bno + len, len, owner, offset + len,
2131                         flags, &have_gt);
2132         if (error)
2133                 goto out_error;
2134         if (have_gt) {
2135                 error = xfs_rmap_get_rec(cur, &gtrec, &have_gt);
2136                 if (error)
2137                         goto out_error;
2138                 if (XFS_IS_CORRUPT(mp, have_gt != 1)) {
2139                         error = -EFSCORRUPTED;
2140                         goto out_error;
2141                 }
2142                 trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp,
2143                         cur->bc_ag.pag->pag_agno, gtrec.rm_startblock,
2144                         gtrec.rm_blockcount, gtrec.rm_owner,
2145                         gtrec.rm_offset, gtrec.rm_flags);
2146
2147                 if (!xfs_rmap_is_mergeable(&gtrec, owner, flags))
2148                         have_gt = 0;
2149         }
2150
2151         if (have_lt &&
2152             ltrec.rm_startblock + ltrec.rm_blockcount == bno &&
2153             ltrec.rm_offset + ltrec.rm_blockcount == offset) {
2154                 /*
2155                  * Left edge contiguous, merge into left record.
2156                  *
2157                  *       ltbno     ltlen
2158                  * orig:   |ooooooooo|
2159                  * adding:           |aaaaaaaaa|
2160                  * result: |rrrrrrrrrrrrrrrrrrr|
2161                  *                  bno       len
2162                  */
2163                 ltrec.rm_blockcount += len;
2164                 if (have_gt &&
2165                     bno + len == gtrec.rm_startblock &&
2166                     offset + len == gtrec.rm_offset) {
2167                         /*
2168                          * Right edge also contiguous, delete right record
2169                          * and merge into left record.
2170                          *
2171                          *       ltbno     ltlen    gtbno     gtlen
2172                          * orig:   |ooooooooo|         |ooooooooo|
2173                          * adding:           |aaaaaaaaa|
2174                          * result: |rrrrrrrrrrrrrrrrrrrrrrrrrrrrr|
2175                          */
2176                         ltrec.rm_blockcount += gtrec.rm_blockcount;
2177                         error = xfs_rmap_delete(cur, gtrec.rm_startblock,
2178                                         gtrec.rm_blockcount, gtrec.rm_owner,
2179                                         gtrec.rm_offset, gtrec.rm_flags);
2180                         if (error)
2181                                 goto out_error;
2182                 }
2183
2184                 /* Point the cursor back to the left record and update. */
2185                 error = xfs_rmap_lookup_eq(cur, ltrec.rm_startblock,
2186                                 ltrec.rm_blockcount, ltrec.rm_owner,
2187                                 ltrec.rm_offset, ltrec.rm_flags, &i);
2188                 if (error)
2189                         goto out_error;
2190                 if (XFS_IS_CORRUPT(mp, i != 1)) {
2191                         error = -EFSCORRUPTED;
2192                         goto out_error;
2193                 }
2194
2195                 error = xfs_rmap_update(cur, &ltrec);
2196                 if (error)
2197                         goto out_error;
2198         } else if (have_gt &&
2199                    bno + len == gtrec.rm_startblock &&
2200                    offset + len == gtrec.rm_offset) {
2201                 /*
2202                  * Right edge contiguous, merge into right record.
2203                  *
2204                  *                 gtbno     gtlen
2205                  * Orig:             |ooooooooo|
2206                  * adding: |aaaaaaaaa|
2207                  * Result: |rrrrrrrrrrrrrrrrrrr|
2208                  *        bno       len
2209                  */
2210                 /* Delete the old record. */
2211                 error = xfs_rmap_delete(cur, gtrec.rm_startblock,
2212                                 gtrec.rm_blockcount, gtrec.rm_owner,
2213                                 gtrec.rm_offset, gtrec.rm_flags);
2214                 if (error)
2215                         goto out_error;
2216
2217                 /* Move the start and re-add it. */
2218                 gtrec.rm_startblock = bno;
2219                 gtrec.rm_blockcount += len;
2220                 gtrec.rm_offset = offset;
2221                 error = xfs_rmap_insert(cur, gtrec.rm_startblock,
2222                                 gtrec.rm_blockcount, gtrec.rm_owner,
2223                                 gtrec.rm_offset, gtrec.rm_flags);
2224                 if (error)
2225                         goto out_error;
2226         } else {
2227                 /*
2228                  * No contiguous edge with identical owner, insert
2229                  * new record at current cursor position.
2230                  */
2231                 error = xfs_rmap_insert(cur, bno, len, owner, offset, flags);
2232                 if (error)
2233                         goto out_error;
2234         }
2235
2236         trace_xfs_rmap_map_done(mp, cur->bc_ag.pag->pag_agno, bno, len,
2237                         unwritten, oinfo);
2238 out_error:
2239         if (error)
2240                 trace_xfs_rmap_map_error(cur->bc_mp,
2241                                 cur->bc_ag.pag->pag_agno, error, _RET_IP_);
2242         return error;
2243 }
2244
2245 /* Insert a raw rmap into the rmapbt. */
2246 int
2247 xfs_rmap_map_raw(
2248         struct xfs_btree_cur    *cur,
2249         struct xfs_rmap_irec    *rmap)
2250 {
2251         struct xfs_owner_info   oinfo;
2252
2253         oinfo.oi_owner = rmap->rm_owner;
2254         oinfo.oi_offset = rmap->rm_offset;
2255         oinfo.oi_flags = 0;
2256         if (rmap->rm_flags & XFS_RMAP_ATTR_FORK)
2257                 oinfo.oi_flags |= XFS_OWNER_INFO_ATTR_FORK;
2258         if (rmap->rm_flags & XFS_RMAP_BMBT_BLOCK)
2259                 oinfo.oi_flags |= XFS_OWNER_INFO_BMBT_BLOCK;
2260
2261         if (rmap->rm_flags || XFS_RMAP_NON_INODE_OWNER(rmap->rm_owner))
2262                 return xfs_rmap_map(cur, rmap->rm_startblock,
2263                                 rmap->rm_blockcount,
2264                                 rmap->rm_flags & XFS_RMAP_UNWRITTEN,
2265                                 &oinfo);
2266
2267         return xfs_rmap_map_shared(cur, rmap->rm_startblock,
2268                         rmap->rm_blockcount,
2269                         rmap->rm_flags & XFS_RMAP_UNWRITTEN,
2270                         &oinfo);
2271 }
2272
2273 struct xfs_rmap_query_range_info {
2274         xfs_rmap_query_range_fn fn;
2275         void                            *priv;
2276 };
2277
2278 /* Format btree record and pass to our callback. */
2279 STATIC int
2280 xfs_rmap_query_range_helper(
2281         struct xfs_btree_cur            *cur,
2282         const union xfs_btree_rec       *rec,
2283         void                            *priv)
2284 {
2285         struct xfs_rmap_query_range_info        *query = priv;
2286         struct xfs_rmap_irec                    irec;
2287         int                                     error;
2288
2289         error = xfs_rmap_btrec_to_irec(rec, &irec);
2290         if (error)
2291                 return error;
2292         return query->fn(cur, &irec, query->priv);
2293 }
2294
2295 /* Find all rmaps between two keys. */
2296 int
2297 xfs_rmap_query_range(
2298         struct xfs_btree_cur                    *cur,
2299         const struct xfs_rmap_irec              *low_rec,
2300         const struct xfs_rmap_irec              *high_rec,
2301         xfs_rmap_query_range_fn                 fn,
2302         void                                    *priv)
2303 {
2304         union xfs_btree_irec                    low_brec;
2305         union xfs_btree_irec                    high_brec;
2306         struct xfs_rmap_query_range_info        query;
2307
2308         low_brec.r = *low_rec;
2309         high_brec.r = *high_rec;
2310         query.priv = priv;
2311         query.fn = fn;
2312         return xfs_btree_query_range(cur, &low_brec, &high_brec,
2313                         xfs_rmap_query_range_helper, &query);
2314 }
2315
2316 /* Find all rmaps. */
2317 int
2318 xfs_rmap_query_all(
2319         struct xfs_btree_cur                    *cur,
2320         xfs_rmap_query_range_fn                 fn,
2321         void                                    *priv)
2322 {
2323         struct xfs_rmap_query_range_info        query;
2324
2325         query.priv = priv;
2326         query.fn = fn;
2327         return xfs_btree_query_all(cur, xfs_rmap_query_range_helper, &query);
2328 }
2329
2330 /* Clean up after calling xfs_rmap_finish_one. */
2331 void
2332 xfs_rmap_finish_one_cleanup(
2333         struct xfs_trans        *tp,
2334         struct xfs_btree_cur    *rcur,
2335         int                     error)
2336 {
2337         struct xfs_buf          *agbp;
2338
2339         if (rcur == NULL)
2340                 return;
2341         agbp = rcur->bc_ag.agbp;
2342         xfs_btree_del_cursor(rcur, error);
2343         if (error)
2344                 xfs_trans_brelse(tp, agbp);
2345 }
2346
2347 /*
2348  * Process one of the deferred rmap operations.  We pass back the
2349  * btree cursor to maintain our lock on the rmapbt between calls.
2350  * This saves time and eliminates a buffer deadlock between the
2351  * superblock and the AGF because we'll always grab them in the same
2352  * order.
2353  */
2354 int
2355 xfs_rmap_finish_one(
2356         struct xfs_trans                *tp,
2357         enum xfs_rmap_intent_type       type,
2358         uint64_t                        owner,
2359         int                             whichfork,
2360         xfs_fileoff_t                   startoff,
2361         xfs_fsblock_t                   startblock,
2362         xfs_filblks_t                   blockcount,
2363         xfs_exntst_t                    state,
2364         struct xfs_btree_cur            **pcur)
2365 {
2366         struct xfs_mount                *mp = tp->t_mountp;
2367         struct xfs_perag                *pag;
2368         struct xfs_btree_cur            *rcur;
2369         struct xfs_buf                  *agbp = NULL;
2370         int                             error = 0;
2371         struct xfs_owner_info           oinfo;
2372         xfs_agblock_t                   bno;
2373         bool                            unwritten;
2374
2375         pag = xfs_perag_get(mp, XFS_FSB_TO_AGNO(mp, startblock));
2376         bno = XFS_FSB_TO_AGBNO(mp, startblock);
2377
2378         trace_xfs_rmap_deferred(mp, pag->pag_agno, type, bno, owner, whichfork,
2379                         startoff, blockcount, state);
2380
2381         if (XFS_TEST_ERROR(false, mp, XFS_ERRTAG_RMAP_FINISH_ONE)) {
2382                 error = -EIO;
2383                 goto out_drop;
2384         }
2385
2386
2387         /*
2388          * If we haven't gotten a cursor or the cursor AG doesn't match
2389          * the startblock, get one now.
2390          */
2391         rcur = *pcur;
2392         if (rcur != NULL && rcur->bc_ag.pag != pag) {
2393                 xfs_rmap_finish_one_cleanup(tp, rcur, 0);
2394                 rcur = NULL;
2395                 *pcur = NULL;
2396         }
2397         if (rcur == NULL) {
2398                 /*
2399                  * Refresh the freelist before we start changing the
2400                  * rmapbt, because a shape change could cause us to
2401                  * allocate blocks.
2402                  */
2403                 error = xfs_free_extent_fix_freelist(tp, pag, &agbp);
2404                 if (error)
2405                         goto out_drop;
2406                 if (XFS_IS_CORRUPT(tp->t_mountp, !agbp)) {
2407                         error = -EFSCORRUPTED;
2408                         goto out_drop;
2409                 }
2410
2411                 rcur = xfs_rmapbt_init_cursor(mp, tp, agbp, pag);
2412         }
2413         *pcur = rcur;
2414
2415         xfs_rmap_ino_owner(&oinfo, owner, whichfork, startoff);
2416         unwritten = state == XFS_EXT_UNWRITTEN;
2417         bno = XFS_FSB_TO_AGBNO(rcur->bc_mp, startblock);
2418
2419         switch (type) {
2420         case XFS_RMAP_ALLOC:
2421         case XFS_RMAP_MAP:
2422                 error = xfs_rmap_map(rcur, bno, blockcount, unwritten, &oinfo);
2423                 break;
2424         case XFS_RMAP_MAP_SHARED:
2425                 error = xfs_rmap_map_shared(rcur, bno, blockcount, unwritten,
2426                                 &oinfo);
2427                 break;
2428         case XFS_RMAP_FREE:
2429         case XFS_RMAP_UNMAP:
2430                 error = xfs_rmap_unmap(rcur, bno, blockcount, unwritten,
2431                                 &oinfo);
2432                 break;
2433         case XFS_RMAP_UNMAP_SHARED:
2434                 error = xfs_rmap_unmap_shared(rcur, bno, blockcount, unwritten,
2435                                 &oinfo);
2436                 break;
2437         case XFS_RMAP_CONVERT:
2438                 error = xfs_rmap_convert(rcur, bno, blockcount, !unwritten,
2439                                 &oinfo);
2440                 break;
2441         case XFS_RMAP_CONVERT_SHARED:
2442                 error = xfs_rmap_convert_shared(rcur, bno, blockcount,
2443                                 !unwritten, &oinfo);
2444                 break;
2445         default:
2446                 ASSERT(0);
2447                 error = -EFSCORRUPTED;
2448         }
2449 out_drop:
2450         xfs_perag_put(pag);
2451         return error;
2452 }
2453
2454 /*
2455  * Don't defer an rmap if we aren't an rmap filesystem.
2456  */
2457 static bool
2458 xfs_rmap_update_is_needed(
2459         struct xfs_mount        *mp,
2460         int                     whichfork)
2461 {
2462         return xfs_has_rmapbt(mp) && whichfork != XFS_COW_FORK;
2463 }
2464
2465 /*
2466  * Record a rmap intent; the list is kept sorted first by AG and then by
2467  * increasing age.
2468  */
2469 static void
2470 __xfs_rmap_add(
2471         struct xfs_trans                *tp,
2472         enum xfs_rmap_intent_type       type,
2473         uint64_t                        owner,
2474         int                             whichfork,
2475         struct xfs_bmbt_irec            *bmap)
2476 {
2477         struct xfs_rmap_intent          *ri;
2478
2479         trace_xfs_rmap_defer(tp->t_mountp,
2480                         XFS_FSB_TO_AGNO(tp->t_mountp, bmap->br_startblock),
2481                         type,
2482                         XFS_FSB_TO_AGBNO(tp->t_mountp, bmap->br_startblock),
2483                         owner, whichfork,
2484                         bmap->br_startoff,
2485                         bmap->br_blockcount,
2486                         bmap->br_state);
2487
2488         ri = kmem_alloc(sizeof(struct xfs_rmap_intent), KM_NOFS);
2489         INIT_LIST_HEAD(&ri->ri_list);
2490         ri->ri_type = type;
2491         ri->ri_owner = owner;
2492         ri->ri_whichfork = whichfork;
2493         ri->ri_bmap = *bmap;
2494
2495         xfs_defer_add(tp, XFS_DEFER_OPS_TYPE_RMAP, &ri->ri_list);
2496 }
2497
2498 /* Map an extent into a file. */
2499 void
2500 xfs_rmap_map_extent(
2501         struct xfs_trans        *tp,
2502         struct xfs_inode        *ip,
2503         int                     whichfork,
2504         struct xfs_bmbt_irec    *PREV)
2505 {
2506         enum xfs_rmap_intent_type type = XFS_RMAP_MAP;
2507
2508         if (!xfs_rmap_update_is_needed(tp->t_mountp, whichfork))
2509                 return;
2510
2511         if (whichfork != XFS_ATTR_FORK && xfs_is_reflink_inode(ip))
2512                 type = XFS_RMAP_MAP_SHARED;
2513
2514         __xfs_rmap_add(tp, type, ip->i_ino, whichfork, PREV);
2515 }
2516
2517 /* Unmap an extent out of a file. */
2518 void
2519 xfs_rmap_unmap_extent(
2520         struct xfs_trans        *tp,
2521         struct xfs_inode        *ip,
2522         int                     whichfork,
2523         struct xfs_bmbt_irec    *PREV)
2524 {
2525         enum xfs_rmap_intent_type type = XFS_RMAP_UNMAP;
2526
2527         if (!xfs_rmap_update_is_needed(tp->t_mountp, whichfork))
2528                 return;
2529
2530         if (whichfork != XFS_ATTR_FORK && xfs_is_reflink_inode(ip))
2531                 type = XFS_RMAP_UNMAP_SHARED;
2532
2533         __xfs_rmap_add(tp, type, ip->i_ino, whichfork, PREV);
2534 }
2535
2536 /*
2537  * Convert a data fork extent from unwritten to real or vice versa.
2538  *
2539  * Note that tp can be NULL here as no transaction is used for COW fork
2540  * unwritten conversion.
2541  */
2542 void
2543 xfs_rmap_convert_extent(
2544         struct xfs_mount        *mp,
2545         struct xfs_trans        *tp,
2546         struct xfs_inode        *ip,
2547         int                     whichfork,
2548         struct xfs_bmbt_irec    *PREV)
2549 {
2550         enum xfs_rmap_intent_type type = XFS_RMAP_CONVERT;
2551
2552         if (!xfs_rmap_update_is_needed(mp, whichfork))
2553                 return;
2554
2555         if (whichfork != XFS_ATTR_FORK && xfs_is_reflink_inode(ip))
2556                 type = XFS_RMAP_CONVERT_SHARED;
2557
2558         __xfs_rmap_add(tp, type, ip->i_ino, whichfork, PREV);
2559 }
2560
2561 /* Schedule the creation of an rmap for non-file data. */
2562 void
2563 xfs_rmap_alloc_extent(
2564         struct xfs_trans        *tp,
2565         xfs_agnumber_t          agno,
2566         xfs_agblock_t           bno,
2567         xfs_extlen_t            len,
2568         uint64_t                owner)
2569 {
2570         struct xfs_bmbt_irec    bmap;
2571
2572         if (!xfs_rmap_update_is_needed(tp->t_mountp, XFS_DATA_FORK))
2573                 return;
2574
2575         bmap.br_startblock = XFS_AGB_TO_FSB(tp->t_mountp, agno, bno);
2576         bmap.br_blockcount = len;
2577         bmap.br_startoff = 0;
2578         bmap.br_state = XFS_EXT_NORM;
2579
2580         __xfs_rmap_add(tp, XFS_RMAP_ALLOC, owner, XFS_DATA_FORK, &bmap);
2581 }
2582
2583 /* Schedule the deletion of an rmap for non-file data. */
2584 void
2585 xfs_rmap_free_extent(
2586         struct xfs_trans        *tp,
2587         xfs_agnumber_t          agno,
2588         xfs_agblock_t           bno,
2589         xfs_extlen_t            len,
2590         uint64_t                owner)
2591 {
2592         struct xfs_bmbt_irec    bmap;
2593
2594         if (!xfs_rmap_update_is_needed(tp->t_mountp, XFS_DATA_FORK))
2595                 return;
2596
2597         bmap.br_startblock = XFS_AGB_TO_FSB(tp->t_mountp, agno, bno);
2598         bmap.br_blockcount = len;
2599         bmap.br_startoff = 0;
2600         bmap.br_state = XFS_EXT_NORM;
2601
2602         __xfs_rmap_add(tp, XFS_RMAP_FREE, owner, XFS_DATA_FORK, &bmap);
2603 }
2604
2605 /* Compare rmap records.  Returns -1 if a < b, 1 if a > b, and 0 if equal. */
2606 int
2607 xfs_rmap_compare(
2608         const struct xfs_rmap_irec      *a,
2609         const struct xfs_rmap_irec      *b)
2610 {
2611         __u64                           oa;
2612         __u64                           ob;
2613
2614         oa = xfs_rmap_irec_offset_pack(a);
2615         ob = xfs_rmap_irec_offset_pack(b);
2616
2617         if (a->rm_startblock < b->rm_startblock)
2618                 return -1;
2619         else if (a->rm_startblock > b->rm_startblock)
2620                 return 1;
2621         else if (a->rm_owner < b->rm_owner)
2622                 return -1;
2623         else if (a->rm_owner > b->rm_owner)
2624                 return 1;
2625         else if (oa < ob)
2626                 return -1;
2627         else if (oa > ob)
2628                 return 1;
2629         else
2630                 return 0;
2631 }
2632
2633 /* Is there a record covering a given extent? */
2634 int
2635 xfs_rmap_has_record(
2636         struct xfs_btree_cur    *cur,
2637         xfs_agblock_t           bno,
2638         xfs_extlen_t            len,
2639         bool                    *exists)
2640 {
2641         union xfs_btree_irec    low;
2642         union xfs_btree_irec    high;
2643
2644         memset(&low, 0, sizeof(low));
2645         low.r.rm_startblock = bno;
2646         memset(&high, 0xFF, sizeof(high));
2647         high.r.rm_startblock = bno + len - 1;
2648
2649         return xfs_btree_has_record(cur, &low, &high, exists);
2650 }
2651
2652 /*
2653  * Is there a record for this owner completely covering a given physical
2654  * extent?  If so, *has_rmap will be set to true.  If there is no record
2655  * or the record only covers part of the range, we set *has_rmap to false.
2656  * This function doesn't perform range lookups or offset checks, so it is
2657  * not suitable for checking data fork blocks.
2658  */
2659 int
2660 xfs_rmap_record_exists(
2661         struct xfs_btree_cur            *cur,
2662         xfs_agblock_t                   bno,
2663         xfs_extlen_t                    len,
2664         const struct xfs_owner_info     *oinfo,
2665         bool                            *has_rmap)
2666 {
2667         uint64_t                        owner;
2668         uint64_t                        offset;
2669         unsigned int                    flags;
2670         int                             has_record;
2671         struct xfs_rmap_irec            irec;
2672         int                             error;
2673
2674         xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
2675         ASSERT(XFS_RMAP_NON_INODE_OWNER(owner) ||
2676                (flags & XFS_RMAP_BMBT_BLOCK));
2677
2678         error = xfs_rmap_lookup_le(cur, bno, len, owner, offset, flags,
2679                         &has_record);
2680         if (error)
2681                 return error;
2682         if (!has_record) {
2683                 *has_rmap = false;
2684                 return 0;
2685         }
2686
2687         error = xfs_rmap_get_rec(cur, &irec, &has_record);
2688         if (error)
2689                 return error;
2690         if (!has_record) {
2691                 *has_rmap = false;
2692                 return 0;
2693         }
2694
2695         *has_rmap = (irec.rm_owner == owner && irec.rm_startblock <= bno &&
2696                      irec.rm_startblock + irec.rm_blockcount >= bno + len);
2697         return 0;
2698 }
2699
2700 struct xfs_rmap_key_state {
2701         uint64_t                        owner;
2702         uint64_t                        offset;
2703         unsigned int                    flags;
2704 };
2705
2706 /* For each rmap given, figure out if it doesn't match the key we want. */
2707 STATIC int
2708 xfs_rmap_has_other_keys_helper(
2709         struct xfs_btree_cur            *cur,
2710         const struct xfs_rmap_irec      *rec,
2711         void                            *priv)
2712 {
2713         struct xfs_rmap_key_state       *rks = priv;
2714
2715         if (rks->owner == rec->rm_owner && rks->offset == rec->rm_offset &&
2716             ((rks->flags & rec->rm_flags) & XFS_RMAP_KEY_FLAGS) == rks->flags)
2717                 return 0;
2718         return -ECANCELED;
2719 }
2720
2721 /*
2722  * Given an extent and some owner info, can we find records overlapping
2723  * the extent whose owner info does not match the given owner?
2724  */
2725 int
2726 xfs_rmap_has_other_keys(
2727         struct xfs_btree_cur            *cur,
2728         xfs_agblock_t                   bno,
2729         xfs_extlen_t                    len,
2730         const struct xfs_owner_info     *oinfo,
2731         bool                            *has_rmap)
2732 {
2733         struct xfs_rmap_irec            low = {0};
2734         struct xfs_rmap_irec            high;
2735         struct xfs_rmap_key_state       rks;
2736         int                             error;
2737
2738         xfs_owner_info_unpack(oinfo, &rks.owner, &rks.offset, &rks.flags);
2739         *has_rmap = false;
2740
2741         low.rm_startblock = bno;
2742         memset(&high, 0xFF, sizeof(high));
2743         high.rm_startblock = bno + len - 1;
2744
2745         error = xfs_rmap_query_range(cur, &low, &high,
2746                         xfs_rmap_has_other_keys_helper, &rks);
2747         if (error == -ECANCELED) {
2748                 *has_rmap = true;
2749                 return 0;
2750         }
2751
2752         return error;
2753 }
2754
2755 const struct xfs_owner_info XFS_RMAP_OINFO_SKIP_UPDATE = {
2756         .oi_owner = XFS_RMAP_OWN_NULL,
2757 };
2758 const struct xfs_owner_info XFS_RMAP_OINFO_ANY_OWNER = {
2759         .oi_owner = XFS_RMAP_OWN_UNKNOWN,
2760 };
2761 const struct xfs_owner_info XFS_RMAP_OINFO_FS = {
2762         .oi_owner = XFS_RMAP_OWN_FS,
2763 };
2764 const struct xfs_owner_info XFS_RMAP_OINFO_LOG = {
2765         .oi_owner = XFS_RMAP_OWN_LOG,
2766 };
2767 const struct xfs_owner_info XFS_RMAP_OINFO_AG = {
2768         .oi_owner = XFS_RMAP_OWN_AG,
2769 };
2770 const struct xfs_owner_info XFS_RMAP_OINFO_INOBT = {
2771         .oi_owner = XFS_RMAP_OWN_INOBT,
2772 };
2773 const struct xfs_owner_info XFS_RMAP_OINFO_INODES = {
2774         .oi_owner = XFS_RMAP_OWN_INODES,
2775 };
2776 const struct xfs_owner_info XFS_RMAP_OINFO_REFC = {
2777         .oi_owner = XFS_RMAP_OWN_REFC,
2778 };
2779 const struct xfs_owner_info XFS_RMAP_OINFO_COW = {
2780         .oi_owner = XFS_RMAP_OWN_COW,
2781 };