fs/xfs/libxfs/xfs_rmap.c

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