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