fs/xfs/libxfs/xfs_rmap.c

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