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