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         const 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         const 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
 674         xfs_btree_del_cursor(cur, error);
 675         return error;
 676 }
 677
 678 /*
 679  * A mergeable rmap must have the same owner and the same values for
 680  * the unwritten, attr_fork, and bmbt flags.  The startblock and
 681  * offset are checked separately.
 682  */
 683 static bool
 684 xfs_rmap_is_mergeable(
 685         struct xfs_rmap_irec    *irec,
 686         uint64_t                owner,
 687         unsigned int            flags)
 688 {
 689         if (irec->rm_owner == XFS_RMAP_OWN_NULL)
 690                 return false;
 691         if (irec->rm_owner != owner)
 692                 return false;
 693         if ((flags & XFS_RMAP_UNWRITTEN) ^
 694             (irec->rm_flags & XFS_RMAP_UNWRITTEN))
 695                 return false;
 696         if ((flags & XFS_RMAP_ATTR_FORK) ^
 697             (irec->rm_flags & XFS_RMAP_ATTR_FORK))
 698                 return false;
 699         if ((flags & XFS_RMAP_BMBT_BLOCK) ^
 700             (irec->rm_flags & XFS_RMAP_BMBT_BLOCK))
 701                 return false;
 702         return true;
 703 }
 704
 705 /*
 706  * When we allocate a new block, the first thing we do is add a reference to
 707  * the extent in the rmap btree. This takes the form of a [agbno, length,
 708  * owner, offset] record.  Flags are encoded in the high bits of the offset
 709  * field.
 710  */
 711 STATIC int
 712 xfs_rmap_map(
 713         struct xfs_btree_cur            *cur,
 714         xfs_agblock_t                   bno,
 715         xfs_extlen_t                    len,
 716         bool                            unwritten,
 717         const struct xfs_owner_info     *oinfo)
 718 {
 719         struct xfs_mount                *mp = cur->bc_mp;
 720         struct xfs_rmap_irec            ltrec;
 721         struct xfs_rmap_irec            gtrec;
 722         int                             have_gt;
 723         int                             have_lt;
 724         int                             error = 0;
 725         int                             i;
 726         uint64_t                        owner;
 727         uint64_t                        offset;
 728         unsigned int                    flags = 0;
 729         bool                            ignore_off;
 730
 731         xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
 732         ASSERT(owner != 0);
 733         ignore_off = XFS_RMAP_NON_INODE_OWNER(owner) ||
 734                         (flags & XFS_RMAP_BMBT_BLOCK);
 735         if (unwritten)
 736                 flags |= XFS_RMAP_UNWRITTEN;
 737         trace_xfs_rmap_map(mp, cur->bc_private.a.agno, bno, len,
 738                         unwritten, oinfo);
 739         ASSERT(!xfs_rmap_should_skip_owner_update(oinfo));
 740
 741         /*
 742          * For the initial lookup, look for an exact match or the left-adjacent
 743          * record for our insertion point. This will also give us the record for
 744          * start block contiguity tests.
 745          */
 746         error = xfs_rmap_lookup_le(cur, bno, len, owner, offset, flags,
 747                         &have_lt);
 748         if (error)
 749                 goto out_error;
 750         if (have_lt) {
 751                 error = xfs_rmap_get_rec(cur, &ltrec, &have_lt);
 752                 if (error)
 753                         goto out_error;
 754                 XFS_WANT_CORRUPTED_GOTO(mp, have_lt == 1, out_error);
 755                 trace_xfs_rmap_lookup_le_range_result(cur->bc_mp,
 756                                 cur->bc_private.a.agno, ltrec.rm_startblock,
 757                                 ltrec.rm_blockcount, ltrec.rm_owner,
 758                                 ltrec.rm_offset, ltrec.rm_flags);
 759
 760                 if (!xfs_rmap_is_mergeable(&ltrec, owner, flags))
 761                         have_lt = 0;
 762         }
 763
 764         XFS_WANT_CORRUPTED_GOTO(mp,
 765                 have_lt == 0 ||
 766                 ltrec.rm_startblock + ltrec.rm_blockcount <= bno, out_error);
 767
 768         /*
 769          * Increment the cursor to see if we have a right-adjacent record to our
 770          * insertion point. This will give us the record for end block
 771          * contiguity tests.
 772          */
 773         error = xfs_btree_increment(cur, 0, &have_gt);
 774         if (error)
 775                 goto out_error;
 776         if (have_gt) {
 777                 error = xfs_rmap_get_rec(cur, &gtrec, &have_gt);
 778                 if (error)
 779                         goto out_error;
 780                 XFS_WANT_CORRUPTED_GOTO(mp, have_gt == 1, out_error);
 781                 XFS_WANT_CORRUPTED_GOTO(mp, bno + len <= gtrec.rm_startblock,
 782                                         out_error);
 783                 trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp,
 784                         cur->bc_private.a.agno, gtrec.rm_startblock,
 785                         gtrec.rm_blockcount, gtrec.rm_owner,
 786                         gtrec.rm_offset, gtrec.rm_flags);
 787                 if (!xfs_rmap_is_mergeable(&gtrec, owner, flags))
 788                         have_gt = 0;
 789         }
 790
 791         /*
 792          * Note: cursor currently points one record to the right of ltrec, even
 793          * if there is no record in the tree to the right.
 794          */
 795         if (have_lt &&
 796             ltrec.rm_startblock + ltrec.rm_blockcount == bno &&
 797             (ignore_off || ltrec.rm_offset + ltrec.rm_blockcount == offset)) {
 798                 /*
 799                  * left edge contiguous, merge into left record.
 800                  *
 801                  *       ltbno     ltlen
 802                  * orig:   |ooooooooo|
 803                  * adding:           |aaaaaaaaa|
 804                  * result: |rrrrrrrrrrrrrrrrrrr|
 805                  *                  bno       len
 806                  */
 807                 ltrec.rm_blockcount += len;
 808                 if (have_gt &&
 809                     bno + len == gtrec.rm_startblock &&
 810                     (ignore_off || offset + len == gtrec.rm_offset) &&
 811                     (unsigned long)ltrec.rm_blockcount + len +
 812                                 gtrec.rm_blockcount <= XFS_RMAP_LEN_MAX) {
 813                         /*
 814                          * right edge also contiguous, delete right record
 815                          * and merge into left record.
 816                          *
 817                          *       ltbno     ltlen    gtbno     gtlen
 818                          * orig:   |ooooooooo|         |ooooooooo|
 819                          * adding:           |aaaaaaaaa|
 820                          * result: |rrrrrrrrrrrrrrrrrrrrrrrrrrrrr|
 821                          */
 822                         ltrec.rm_blockcount += gtrec.rm_blockcount;
 823                         trace_xfs_rmap_delete(mp, cur->bc_private.a.agno,
 824                                         gtrec.rm_startblock,
 825                                         gtrec.rm_blockcount,
 826                                         gtrec.rm_owner,
 827                                         gtrec.rm_offset,
 828                                         gtrec.rm_flags);
 829                         error = xfs_btree_delete(cur, &i);
 830                         if (error)
 831                                 goto out_error;
 832                         XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error);
 833                 }
 834
 835                 /* point the cursor back to the left record and update */
 836                 error = xfs_btree_decrement(cur, 0, &have_gt);
 837                 if (error)
 838                         goto out_error;
 839                 error = xfs_rmap_update(cur, &ltrec);
 840                 if (error)
 841                         goto out_error;
 842         } else if (have_gt &&
 843                    bno + len == gtrec.rm_startblock &&
 844                    (ignore_off || offset + len == gtrec.rm_offset)) {
 845                 /*
 846                  * right edge contiguous, merge into right record.
 847                  *
 848                  *                 gtbno     gtlen
 849                  * Orig:             |ooooooooo|
 850                  * adding: |aaaaaaaaa|
 851                  * Result: |rrrrrrrrrrrrrrrrrrr|
 852                  *        bno       len
 853                  */
 854                 gtrec.rm_startblock = bno;
 855                 gtrec.rm_blockcount += len;
 856                 if (!ignore_off)
 857                         gtrec.rm_offset = offset;
 858                 error = xfs_rmap_update(cur, &gtrec);
 859                 if (error)
 860                         goto out_error;
 861         } else {
 862                 /*
 863                  * no contiguous edge with identical owner, insert
 864                  * new record at current cursor position.
 865                  */
 866                 cur->bc_rec.r.rm_startblock = bno;
 867                 cur->bc_rec.r.rm_blockcount = len;
 868                 cur->bc_rec.r.rm_owner = owner;
 869                 cur->bc_rec.r.rm_offset = offset;
 870                 cur->bc_rec.r.rm_flags = flags;
 871                 trace_xfs_rmap_insert(mp, cur->bc_private.a.agno, bno, len,
 872                         owner, offset, flags);
 873                 error = xfs_btree_insert(cur, &i);
 874                 if (error)
 875                         goto out_error;
 876                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error);
 877         }
 878
 879         trace_xfs_rmap_map_done(mp, cur->bc_private.a.agno, bno, len,
 880                         unwritten, oinfo);
 881 out_error:
 882         if (error)
 883                 trace_xfs_rmap_map_error(mp, cur->bc_private.a.agno,
 884                                 error, _RET_IP_);
 885         return error;
 886 }
 887
 888 /*
 889  * Add a reference to an extent in the rmap btree.
 890  */
 891 int
 892 xfs_rmap_alloc(
 893         struct xfs_trans                *tp,
 894         struct xfs_buf                  *agbp,
 895         xfs_agnumber_t                  agno,
 896         xfs_agblock_t                   bno,
 897         xfs_extlen_t                    len,
 898         const struct xfs_owner_info     *oinfo)
 899 {
 900         struct xfs_mount                *mp = tp->t_mountp;
 901         struct xfs_btree_cur            *cur;
 902         int                             error;
 903
 904         if (!xfs_sb_version_hasrmapbt(&mp->m_sb))
 905                 return 0;
 906
 907         cur = xfs_rmapbt_init_cursor(mp, tp, agbp, agno);
 908         error = xfs_rmap_map(cur, bno, len, false, oinfo);
 909
 910         xfs_btree_del_cursor(cur, error);
 911         return error;
 912 }
 913
 914 #define RMAP_LEFT_CONTIG        (1 << 0)
 915 #define RMAP_RIGHT_CONTIG       (1 << 1)
 916 #define RMAP_LEFT_FILLING       (1 << 2)
 917 #define RMAP_RIGHT_FILLING      (1 << 3)
 918 #define RMAP_LEFT_VALID         (1 << 6)
 919 #define RMAP_RIGHT_VALID        (1 << 7)
 920
 921 #define LEFT            r[0]
 922 #define RIGHT           r[1]
 923 #define PREV            r[2]
 924 #define NEW             r[3]
 925
 926 /*
 927  * Convert an unwritten extent to a real extent or vice versa.
 928  * Does not handle overlapping extents.
 929  */
 930 STATIC int
 931 xfs_rmap_convert(
 932         struct xfs_btree_cur            *cur,
 933         xfs_agblock_t                   bno,
 934         xfs_extlen_t                    len,
 935         bool                            unwritten,
 936         const struct xfs_owner_info     *oinfo)
 937 {
 938         struct xfs_mount                *mp = cur->bc_mp;
 939         struct xfs_rmap_irec            r[4];   /* neighbor extent entries */
 940                                                 /* left is 0, right is 1, */
 941                                                 /* prev is 2, new is 3 */
 942         uint64_t                owner;
 943         uint64_t                offset;
 944         uint64_t                new_endoff;
 945         unsigned int            oldext;
 946         unsigned int            newext;
 947         unsigned int            flags = 0;
 948         int                     i;
 949         int                     state = 0;
 950         int                     error;
 951
 952         xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
 953         ASSERT(!(XFS_RMAP_NON_INODE_OWNER(owner) ||
 954                         (flags & (XFS_RMAP_ATTR_FORK | XFS_RMAP_BMBT_BLOCK))));
 955         oldext = unwritten ? XFS_RMAP_UNWRITTEN : 0;
 956         new_endoff = offset + len;
 957         trace_xfs_rmap_convert(mp, cur->bc_private.a.agno, bno, len,
 958                         unwritten, oinfo);
 959
 960         /*
 961          * For the initial lookup, look for an exact match or the left-adjacent
 962          * record for our insertion point. This will also give us the record for
 963          * start block contiguity tests.
 964          */
 965         error = xfs_rmap_lookup_le(cur, bno, len, owner, offset, oldext, &i);
 966         if (error)
 967                 goto done;
 968         XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
 969
 970         error = xfs_rmap_get_rec(cur, &PREV, &i);
 971         if (error)
 972                 goto done;
 973         XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
 974         trace_xfs_rmap_lookup_le_range_result(cur->bc_mp,
 975                         cur->bc_private.a.agno, PREV.rm_startblock,
 976                         PREV.rm_blockcount, PREV.rm_owner,
 977                         PREV.rm_offset, PREV.rm_flags);
 978
 979         ASSERT(PREV.rm_offset <= offset);
 980         ASSERT(PREV.rm_offset + PREV.rm_blockcount >= new_endoff);
 981         ASSERT((PREV.rm_flags & XFS_RMAP_UNWRITTEN) == oldext);
 982         newext = ~oldext & XFS_RMAP_UNWRITTEN;
 983
 984         /*
 985          * Set flags determining what part of the previous oldext allocation
 986          * extent is being replaced by a newext allocation.
 987          */
 988         if (PREV.rm_offset == offset)
 989                 state |= RMAP_LEFT_FILLING;
 990         if (PREV.rm_offset + PREV.rm_blockcount == new_endoff)
 991                 state |= RMAP_RIGHT_FILLING;
 992
 993         /*
 994          * Decrement the cursor to see if we have a left-adjacent record to our
 995          * insertion point. This will give us the record for end block
 996          * contiguity tests.
 997          */
 998         error = xfs_btree_decrement(cur, 0, &i);
 999         if (error)
1000                 goto done;
1001         if (i) {
1002                 state |= RMAP_LEFT_VALID;
1003                 error = xfs_rmap_get_rec(cur, &LEFT, &i);
1004                 if (error)
1005                         goto done;
1006                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1007                 XFS_WANT_CORRUPTED_GOTO(mp,
1008                                 LEFT.rm_startblock + LEFT.rm_blockcount <= bno,
1009                                 done);
1010                 trace_xfs_rmap_find_left_neighbor_result(cur->bc_mp,
1011                                 cur->bc_private.a.agno, LEFT.rm_startblock,
1012                                 LEFT.rm_blockcount, LEFT.rm_owner,
1013                                 LEFT.rm_offset, LEFT.rm_flags);
1014                 if (LEFT.rm_startblock + LEFT.rm_blockcount == bno &&
1015                     LEFT.rm_offset + LEFT.rm_blockcount == offset &&
1016                     xfs_rmap_is_mergeable(&LEFT, owner, newext))
1017                         state |= RMAP_LEFT_CONTIG;
1018         }
1019
1020         /*
1021          * Increment the cursor to see if we have a right-adjacent record to our
1022          * insertion point. This will give us the record for end block
1023          * contiguity tests.
1024          */
1025         error = xfs_btree_increment(cur, 0, &i);
1026         if (error)
1027                 goto done;
1028         XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1029         error = xfs_btree_increment(cur, 0, &i);
1030         if (error)
1031                 goto done;
1032         if (i) {
1033                 state |= RMAP_RIGHT_VALID;
1034                 error = xfs_rmap_get_rec(cur, &RIGHT, &i);
1035                 if (error)
1036                         goto done;
1037                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1038                 XFS_WANT_CORRUPTED_GOTO(mp, bno + len <= RIGHT.rm_startblock,
1039                                         done);
1040                 trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp,
1041                                 cur->bc_private.a.agno, RIGHT.rm_startblock,
1042                                 RIGHT.rm_blockcount, RIGHT.rm_owner,
1043                                 RIGHT.rm_offset, RIGHT.rm_flags);
1044                 if (bno + len == RIGHT.rm_startblock &&
1045                     offset + len == RIGHT.rm_offset &&
1046                     xfs_rmap_is_mergeable(&RIGHT, owner, newext))
1047                         state |= RMAP_RIGHT_CONTIG;
1048         }
1049
1050         /* check that left + prev + right is not too long */
1051         if ((state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1052                          RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) ==
1053             (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1054              RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG) &&
1055             (unsigned long)LEFT.rm_blockcount + len +
1056              RIGHT.rm_blockcount > XFS_RMAP_LEN_MAX)
1057                 state &= ~RMAP_RIGHT_CONTIG;
1058
1059         trace_xfs_rmap_convert_state(mp, cur->bc_private.a.agno, state,
1060                         _RET_IP_);
1061
1062         /* reset the cursor back to PREV */
1063         error = xfs_rmap_lookup_le(cur, bno, len, owner, offset, oldext, &i);
1064         if (error)
1065                 goto done;
1066         XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1067
1068         /*
1069          * Switch out based on the FILLING and CONTIG state bits.
1070          */
1071         switch (state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1072                          RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) {
1073         case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1074              RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1075                 /*
1076                  * Setting all of a previous oldext extent to newext.
1077                  * The left and right neighbors are both contiguous with new.
1078                  */
1079                 error = xfs_btree_increment(cur, 0, &i);
1080                 if (error)
1081                         goto done;
1082                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1083                 trace_xfs_rmap_delete(mp, cur->bc_private.a.agno,
1084                                 RIGHT.rm_startblock, RIGHT.rm_blockcount,
1085                                 RIGHT.rm_owner, RIGHT.rm_offset,
1086                                 RIGHT.rm_flags);
1087                 error = xfs_btree_delete(cur, &i);
1088                 if (error)
1089                         goto done;
1090                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1091                 error = xfs_btree_decrement(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                                 PREV.rm_startblock, PREV.rm_blockcount,
1097                                 PREV.rm_owner, PREV.rm_offset,
1098                                 PREV.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                 NEW = LEFT;
1108                 NEW.rm_blockcount += PREV.rm_blockcount + RIGHT.rm_blockcount;
1109                 error = xfs_rmap_update(cur, &NEW);
1110                 if (error)
1111                         goto done;
1112                 break;
1113
1114         case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG:
1115                 /*
1116                  * Setting all of a previous oldext extent to newext.
1117                  * The left neighbor is contiguous, the right is not.
1118                  */
1119                 trace_xfs_rmap_delete(mp, cur->bc_private.a.agno,
1120                                 PREV.rm_startblock, PREV.rm_blockcount,
1121                                 PREV.rm_owner, PREV.rm_offset,
1122                                 PREV.rm_flags);
1123                 error = xfs_btree_delete(cur, &i);
1124                 if (error)
1125                         goto done;
1126                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1127                 error = xfs_btree_decrement(cur, 0, &i);
1128                 if (error)
1129                         goto done;
1130                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1131                 NEW = LEFT;
1132                 NEW.rm_blockcount += PREV.rm_blockcount;
1133                 error = xfs_rmap_update(cur, &NEW);
1134                 if (error)
1135                         goto done;
1136                 break;
1137
1138         case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1139                 /*
1140                  * Setting all of a previous oldext extent to newext.
1141                  * The right neighbor is contiguous, the left is not.
1142                  */
1143                 error = xfs_btree_increment(cur, 0, &i);
1144                 if (error)
1145                         goto done;
1146                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1147                 trace_xfs_rmap_delete(mp, cur->bc_private.a.agno,
1148                                 RIGHT.rm_startblock, RIGHT.rm_blockcount,
1149                                 RIGHT.rm_owner, RIGHT.rm_offset,
1150                                 RIGHT.rm_flags);
1151                 error = xfs_btree_delete(cur, &i);
1152                 if (error)
1153                         goto done;
1154                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1155                 error = xfs_btree_decrement(cur, 0, &i);
1156                 if (error)
1157                         goto done;
1158                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1159                 NEW = PREV;
1160                 NEW.rm_blockcount = len + RIGHT.rm_blockcount;
1161                 NEW.rm_flags = newext;
1162                 error = xfs_rmap_update(cur, &NEW);
1163                 if (error)
1164                         goto done;
1165                 break;
1166
1167         case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING:
1168                 /*
1169                  * Setting all of a previous oldext extent to newext.
1170                  * Neither the left nor right neighbors are contiguous with
1171                  * the new one.
1172                  */
1173                 NEW = PREV;
1174                 NEW.rm_flags = newext;
1175                 error = xfs_rmap_update(cur, &NEW);
1176                 if (error)
1177                         goto done;
1178                 break;
1179
1180         case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG:
1181                 /*
1182                  * Setting the first part of a previous oldext extent to newext.
1183                  * The left neighbor is contiguous.
1184                  */
1185                 NEW = PREV;
1186                 NEW.rm_offset += len;
1187                 NEW.rm_startblock += len;
1188                 NEW.rm_blockcount -= len;
1189                 error = xfs_rmap_update(cur, &NEW);
1190                 if (error)
1191                         goto done;
1192                 error = xfs_btree_decrement(cur, 0, &i);
1193                 if (error)
1194                         goto done;
1195                 NEW = LEFT;
1196                 NEW.rm_blockcount += len;
1197                 error = xfs_rmap_update(cur, &NEW);
1198                 if (error)
1199                         goto done;
1200                 break;
1201
1202         case RMAP_LEFT_FILLING:
1203                 /*
1204                  * Setting the first part of a previous oldext extent to newext.
1205                  * The left neighbor is not contiguous.
1206                  */
1207                 NEW = PREV;
1208                 NEW.rm_startblock += len;
1209                 NEW.rm_offset += len;
1210                 NEW.rm_blockcount -= len;
1211                 error = xfs_rmap_update(cur, &NEW);
1212                 if (error)
1213                         goto done;
1214                 NEW.rm_startblock = bno;
1215                 NEW.rm_owner = owner;
1216                 NEW.rm_offset = offset;
1217                 NEW.rm_blockcount = len;
1218                 NEW.rm_flags = newext;
1219                 cur->bc_rec.r = NEW;
1220                 trace_xfs_rmap_insert(mp, cur->bc_private.a.agno, bno,
1221                                 len, owner, offset, newext);
1222                 error = xfs_btree_insert(cur, &i);
1223                 if (error)
1224                         goto done;
1225                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1226                 break;
1227
1228         case RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1229                 /*
1230                  * Setting the last part of a previous oldext extent to newext.
1231                  * The right neighbor is contiguous with the new allocation.
1232                  */
1233                 NEW = PREV;
1234                 NEW.rm_blockcount -= len;
1235                 error = xfs_rmap_update(cur, &NEW);
1236                 if (error)
1237                         goto done;
1238                 error = xfs_btree_increment(cur, 0, &i);
1239                 if (error)
1240                         goto done;
1241                 NEW = RIGHT;
1242                 NEW.rm_offset = offset;
1243                 NEW.rm_startblock = bno;
1244                 NEW.rm_blockcount += len;
1245                 error = xfs_rmap_update(cur, &NEW);
1246                 if (error)
1247                         goto done;
1248                 break;
1249
1250         case RMAP_RIGHT_FILLING:
1251                 /*
1252                  * Setting the last part of a previous oldext extent to newext.
1253                  * The right neighbor is not contiguous.
1254                  */
1255                 NEW = PREV;
1256                 NEW.rm_blockcount -= len;
1257                 error = xfs_rmap_update(cur, &NEW);
1258                 if (error)
1259                         goto done;
1260                 error = xfs_rmap_lookup_eq(cur, bno, len, owner, offset,
1261                                 oldext, &i);
1262                 if (error)
1263                         goto done;
1264                 XFS_WANT_CORRUPTED_GOTO(mp, i == 0, done);
1265                 NEW.rm_startblock = bno;
1266                 NEW.rm_owner = owner;
1267                 NEW.rm_offset = offset;
1268                 NEW.rm_blockcount = len;
1269                 NEW.rm_flags = newext;
1270                 cur->bc_rec.r = NEW;
1271                 trace_xfs_rmap_insert(mp, cur->bc_private.a.agno, bno,
1272                                 len, owner, offset, newext);
1273                 error = xfs_btree_insert(cur, &i);
1274                 if (error)
1275                         goto done;
1276                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1277                 break;
1278
1279         case 0:
1280                 /*
1281                  * Setting the middle part of a previous oldext extent to
1282                  * newext.  Contiguity is impossible here.
1283                  * One extent becomes three extents.
1284                  */
1285                 /* new right extent - oldext */
1286                 NEW.rm_startblock = bno + len;
1287                 NEW.rm_owner = owner;
1288                 NEW.rm_offset = new_endoff;
1289                 NEW.rm_blockcount = PREV.rm_offset + PREV.rm_blockcount -
1290                                 new_endoff;
1291                 NEW.rm_flags = PREV.rm_flags;
1292                 error = xfs_rmap_update(cur, &NEW);
1293                 if (error)
1294                         goto done;
1295                 /* new left extent - oldext */
1296                 NEW = PREV;
1297                 NEW.rm_blockcount = offset - PREV.rm_offset;
1298                 cur->bc_rec.r = NEW;
1299                 trace_xfs_rmap_insert(mp, cur->bc_private.a.agno,
1300                                 NEW.rm_startblock, NEW.rm_blockcount,
1301                                 NEW.rm_owner, NEW.rm_offset,
1302                                 NEW.rm_flags);
1303                 error = xfs_btree_insert(cur, &i);
1304                 if (error)
1305                         goto done;
1306                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1307                 /*
1308                  * Reset the cursor to the position of the new extent
1309                  * we are about to insert as we can't trust it after
1310                  * the previous insert.
1311                  */
1312                 error = xfs_rmap_lookup_eq(cur, bno, len, owner, offset,
1313                                 oldext, &i);
1314                 if (error)
1315                         goto done;
1316                 XFS_WANT_CORRUPTED_GOTO(mp, i == 0, done);
1317                 /* new middle extent - newext */
1318                 cur->bc_rec.r.rm_flags &= ~XFS_RMAP_UNWRITTEN;
1319                 cur->bc_rec.r.rm_flags |= newext;
1320                 trace_xfs_rmap_insert(mp, cur->bc_private.a.agno, bno, len,
1321                                 owner, offset, newext);
1322                 error = xfs_btree_insert(cur, &i);
1323                 if (error)
1324                         goto done;
1325                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1326                 break;
1327
1328         case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1329         case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1330         case RMAP_LEFT_FILLING | RMAP_RIGHT_CONTIG:
1331         case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG:
1332         case RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1333         case RMAP_LEFT_CONTIG:
1334         case RMAP_RIGHT_CONTIG:
1335                 /*
1336                  * These cases are all impossible.
1337                  */
1338                 ASSERT(0);
1339         }
1340
1341         trace_xfs_rmap_convert_done(mp, cur->bc_private.a.agno, bno, len,
1342                         unwritten, oinfo);
1343 done:
1344         if (error)
1345                 trace_xfs_rmap_convert_error(cur->bc_mp,
1346                                 cur->bc_private.a.agno, error, _RET_IP_);
1347         return error;
1348 }
1349
1350 /*
1351  * Convert an unwritten extent to a real extent or vice versa.  If there is no
1352  * possibility of overlapping extents, delegate to the simpler convert
1353  * function.
1354  */
1355 STATIC int
1356 xfs_rmap_convert_shared(
1357         struct xfs_btree_cur            *cur,
1358         xfs_agblock_t                   bno,
1359         xfs_extlen_t                    len,
1360         bool                            unwritten,
1361         const struct xfs_owner_info     *oinfo)
1362 {
1363         struct xfs_mount                *mp = cur->bc_mp;
1364         struct xfs_rmap_irec            r[4];   /* neighbor extent entries */
1365                                                 /* left is 0, right is 1, */
1366                                                 /* prev is 2, new is 3 */
1367         uint64_t                owner;
1368         uint64_t                offset;
1369         uint64_t                new_endoff;
1370         unsigned int            oldext;
1371         unsigned int            newext;
1372         unsigned int            flags = 0;
1373         int                     i;
1374         int                     state = 0;
1375         int                     error;
1376
1377         xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
1378         ASSERT(!(XFS_RMAP_NON_INODE_OWNER(owner) ||
1379                         (flags & (XFS_RMAP_ATTR_FORK | XFS_RMAP_BMBT_BLOCK))));
1380         oldext = unwritten ? XFS_RMAP_UNWRITTEN : 0;
1381         new_endoff = offset + len;
1382         trace_xfs_rmap_convert(mp, cur->bc_private.a.agno, bno, len,
1383                         unwritten, oinfo);
1384
1385         /*
1386          * For the initial lookup, look for and exact match or the left-adjacent
1387          * record for our insertion point. This will also give us the record for
1388          * start block contiguity tests.
1389          */
1390         error = xfs_rmap_lookup_le_range(cur, bno, owner, offset, flags,
1391                         &PREV, &i);
1392         if (error)
1393                 goto done;
1394         XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1395
1396         ASSERT(PREV.rm_offset <= offset);
1397         ASSERT(PREV.rm_offset + PREV.rm_blockcount >= new_endoff);
1398         ASSERT((PREV.rm_flags & XFS_RMAP_UNWRITTEN) == oldext);
1399         newext = ~oldext & XFS_RMAP_UNWRITTEN;
1400
1401         /*
1402          * Set flags determining what part of the previous oldext allocation
1403          * extent is being replaced by a newext allocation.
1404          */
1405         if (PREV.rm_offset == offset)
1406                 state |= RMAP_LEFT_FILLING;
1407         if (PREV.rm_offset + PREV.rm_blockcount == new_endoff)
1408                 state |= RMAP_RIGHT_FILLING;
1409
1410         /* Is there a left record that abuts our range? */
1411         error = xfs_rmap_find_left_neighbor(cur, bno, owner, offset, newext,
1412                         &LEFT, &i);
1413         if (error)
1414                 goto done;
1415         if (i) {
1416                 state |= RMAP_LEFT_VALID;
1417                 XFS_WANT_CORRUPTED_GOTO(mp,
1418                                 LEFT.rm_startblock + LEFT.rm_blockcount <= bno,
1419                                 done);
1420                 if (xfs_rmap_is_mergeable(&LEFT, owner, newext))
1421                         state |= RMAP_LEFT_CONTIG;
1422         }
1423
1424         /* Is there a right record that abuts our range? */
1425         error = xfs_rmap_lookup_eq(cur, bno + len, len, owner, offset + len,
1426                         newext, &i);
1427         if (error)
1428                 goto done;
1429         if (i) {
1430                 state |= RMAP_RIGHT_VALID;
1431                 error = xfs_rmap_get_rec(cur, &RIGHT, &i);
1432                 if (error)
1433                         goto done;
1434                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1435                 XFS_WANT_CORRUPTED_GOTO(mp, bno + len <= RIGHT.rm_startblock,
1436                                 done);
1437                 trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp,
1438                                 cur->bc_private.a.agno, RIGHT.rm_startblock,
1439                                 RIGHT.rm_blockcount, RIGHT.rm_owner,
1440                                 RIGHT.rm_offset, RIGHT.rm_flags);
1441                 if (xfs_rmap_is_mergeable(&RIGHT, owner, newext))
1442                         state |= RMAP_RIGHT_CONTIG;
1443         }
1444
1445         /* check that left + prev + right is not too long */
1446         if ((state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1447                          RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) ==
1448             (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1449              RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG) &&
1450             (unsigned long)LEFT.rm_blockcount + len +
1451              RIGHT.rm_blockcount > XFS_RMAP_LEN_MAX)
1452                 state &= ~RMAP_RIGHT_CONTIG;
1453
1454         trace_xfs_rmap_convert_state(mp, cur->bc_private.a.agno, state,
1455                         _RET_IP_);
1456         /*
1457          * Switch out based on the FILLING and CONTIG state bits.
1458          */
1459         switch (state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1460                          RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) {
1461         case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG |
1462              RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1463                 /*
1464                  * Setting all of a previous oldext extent to newext.
1465                  * The left and right neighbors are both contiguous with new.
1466                  */
1467                 error = xfs_rmap_delete(cur, RIGHT.rm_startblock,
1468                                 RIGHT.rm_blockcount, RIGHT.rm_owner,
1469                                 RIGHT.rm_offset, RIGHT.rm_flags);
1470                 if (error)
1471                         goto done;
1472                 error = xfs_rmap_delete(cur, PREV.rm_startblock,
1473                                 PREV.rm_blockcount, PREV.rm_owner,
1474                                 PREV.rm_offset, PREV.rm_flags);
1475                 if (error)
1476                         goto done;
1477                 NEW = LEFT;
1478                 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1479                                 NEW.rm_blockcount, NEW.rm_owner,
1480                                 NEW.rm_offset, NEW.rm_flags, &i);
1481                 if (error)
1482                         goto done;
1483                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1484                 NEW.rm_blockcount += PREV.rm_blockcount + RIGHT.rm_blockcount;
1485                 error = xfs_rmap_update(cur, &NEW);
1486                 if (error)
1487                         goto done;
1488                 break;
1489
1490         case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG:
1491                 /*
1492                  * Setting all of a previous oldext extent to newext.
1493                  * The left neighbor is contiguous, the right is not.
1494                  */
1495                 error = xfs_rmap_delete(cur, PREV.rm_startblock,
1496                                 PREV.rm_blockcount, PREV.rm_owner,
1497                                 PREV.rm_offset, PREV.rm_flags);
1498                 if (error)
1499                         goto done;
1500                 NEW = LEFT;
1501                 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1502                                 NEW.rm_blockcount, NEW.rm_owner,
1503                                 NEW.rm_offset, NEW.rm_flags, &i);
1504                 if (error)
1505                         goto done;
1506                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1507                 NEW.rm_blockcount += PREV.rm_blockcount;
1508                 error = xfs_rmap_update(cur, &NEW);
1509                 if (error)
1510                         goto done;
1511                 break;
1512
1513         case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1514                 /*
1515                  * Setting all of a previous oldext extent to newext.
1516                  * The right neighbor is contiguous, the left is not.
1517                  */
1518                 error = xfs_rmap_delete(cur, RIGHT.rm_startblock,
1519                                 RIGHT.rm_blockcount, RIGHT.rm_owner,
1520                                 RIGHT.rm_offset, RIGHT.rm_flags);
1521                 if (error)
1522                         goto done;
1523                 NEW = PREV;
1524                 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1525                                 NEW.rm_blockcount, NEW.rm_owner,
1526                                 NEW.rm_offset, NEW.rm_flags, &i);
1527                 if (error)
1528                         goto done;
1529                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1530                 NEW.rm_blockcount += RIGHT.rm_blockcount;
1531                 NEW.rm_flags = RIGHT.rm_flags;
1532                 error = xfs_rmap_update(cur, &NEW);
1533                 if (error)
1534                         goto done;
1535                 break;
1536
1537         case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING:
1538                 /*
1539                  * Setting all of a previous oldext extent to newext.
1540                  * Neither the left nor right neighbors are contiguous with
1541                  * the new one.
1542                  */
1543                 NEW = PREV;
1544                 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1545                                 NEW.rm_blockcount, NEW.rm_owner,
1546                                 NEW.rm_offset, NEW.rm_flags, &i);
1547                 if (error)
1548                         goto done;
1549                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1550                 NEW.rm_flags = newext;
1551                 error = xfs_rmap_update(cur, &NEW);
1552                 if (error)
1553                         goto done;
1554                 break;
1555
1556         case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG:
1557                 /*
1558                  * Setting the first part of a previous oldext extent to newext.
1559                  * The left neighbor is contiguous.
1560                  */
1561                 NEW = PREV;
1562                 error = xfs_rmap_delete(cur, NEW.rm_startblock,
1563                                 NEW.rm_blockcount, NEW.rm_owner,
1564                                 NEW.rm_offset, NEW.rm_flags);
1565                 if (error)
1566                         goto done;
1567                 NEW.rm_offset += len;
1568                 NEW.rm_startblock += len;
1569                 NEW.rm_blockcount -= len;
1570                 error = xfs_rmap_insert(cur, NEW.rm_startblock,
1571                                 NEW.rm_blockcount, NEW.rm_owner,
1572                                 NEW.rm_offset, NEW.rm_flags);
1573                 if (error)
1574                         goto done;
1575                 NEW = LEFT;
1576                 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1577                                 NEW.rm_blockcount, NEW.rm_owner,
1578                                 NEW.rm_offset, NEW.rm_flags, &i);
1579                 if (error)
1580                         goto done;
1581                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1582                 NEW.rm_blockcount += len;
1583                 error = xfs_rmap_update(cur, &NEW);
1584                 if (error)
1585                         goto done;
1586                 break;
1587
1588         case RMAP_LEFT_FILLING:
1589                 /*
1590                  * Setting the first part of a previous oldext extent to newext.
1591                  * The left neighbor is not contiguous.
1592                  */
1593                 NEW = PREV;
1594                 error = xfs_rmap_delete(cur, NEW.rm_startblock,
1595                                 NEW.rm_blockcount, NEW.rm_owner,
1596                                 NEW.rm_offset, NEW.rm_flags);
1597                 if (error)
1598                         goto done;
1599                 NEW.rm_offset += len;
1600                 NEW.rm_startblock += len;
1601                 NEW.rm_blockcount -= len;
1602                 error = xfs_rmap_insert(cur, NEW.rm_startblock,
1603                                 NEW.rm_blockcount, NEW.rm_owner,
1604                                 NEW.rm_offset, NEW.rm_flags);
1605                 if (error)
1606                         goto done;
1607                 error = xfs_rmap_insert(cur, bno, len, owner, offset, newext);
1608                 if (error)
1609                         goto done;
1610                 break;
1611
1612         case RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG:
1613                 /*
1614                  * Setting the last part of a previous oldext extent to newext.
1615                  * The right neighbor is contiguous with the new allocation.
1616                  */
1617                 NEW = PREV;
1618                 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1619                                 NEW.rm_blockcount, NEW.rm_owner,
1620                                 NEW.rm_offset, NEW.rm_flags, &i);
1621                 if (error)
1622                         goto done;
1623                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1624                 NEW.rm_blockcount = offset - NEW.rm_offset;
1625                 error = xfs_rmap_update(cur, &NEW);
1626                 if (error)
1627                         goto done;
1628                 NEW = RIGHT;
1629                 error = xfs_rmap_delete(cur, NEW.rm_startblock,
1630                                 NEW.rm_blockcount, NEW.rm_owner,
1631                                 NEW.rm_offset, NEW.rm_flags);
1632                 if (error)
1633                         goto done;
1634                 NEW.rm_offset = offset;
1635                 NEW.rm_startblock = bno;
1636                 NEW.rm_blockcount += len;
1637                 error = xfs_rmap_insert(cur, NEW.rm_startblock,
1638                                 NEW.rm_blockcount, NEW.rm_owner,
1639                                 NEW.rm_offset, NEW.rm_flags);
1640                 if (error)
1641                         goto done;
1642                 break;
1643
1644         case RMAP_RIGHT_FILLING:
1645                 /*
1646                  * Setting the last part of a previous oldext extent to newext.
1647                  * The right neighbor is not contiguous.
1648                  */
1649                 NEW = PREV;
1650                 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1651                                 NEW.rm_blockcount, NEW.rm_owner,
1652                                 NEW.rm_offset, NEW.rm_flags, &i);
1653                 if (error)
1654                         goto done;
1655                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1656                 NEW.rm_blockcount -= len;
1657                 error = xfs_rmap_update(cur, &NEW);
1658                 if (error)
1659                         goto done;
1660                 error = xfs_rmap_insert(cur, bno, len, owner, offset, newext);
1661                 if (error)
1662                         goto done;
1663                 break;
1664
1665         case 0:
1666                 /*
1667                  * Setting the middle part of a previous oldext extent to
1668                  * newext.  Contiguity is impossible here.
1669                  * One extent becomes three extents.
1670                  */
1671                 /* new right extent - oldext */
1672                 NEW.rm_startblock = bno + len;
1673                 NEW.rm_owner = owner;
1674                 NEW.rm_offset = new_endoff;
1675                 NEW.rm_blockcount = PREV.rm_offset + PREV.rm_blockcount -
1676                                 new_endoff;
1677                 NEW.rm_flags = PREV.rm_flags;
1678                 error = xfs_rmap_insert(cur, NEW.rm_startblock,
1679                                 NEW.rm_blockcount, NEW.rm_owner, NEW.rm_offset,
1680                                 NEW.rm_flags);
1681                 if (error)
1682                         goto done;
1683                 /* new left extent - oldext */
1684                 NEW = PREV;
1685                 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock,
1686                                 NEW.rm_blockcount, NEW.rm_owner,
1687                                 NEW.rm_offset, NEW.rm_flags, &i);
1688                 if (error)
1689                         goto done;
1690                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done);
1691                 NEW.rm_blockcount = offset - NEW.rm_offset;
1692                 error = xfs_rmap_update(cur, &NEW);
1693                 if (error)
1694                         goto done;
1695                 /* new middle extent - newext */
1696                 NEW.rm_startblock = bno;
1697                 NEW.rm_blockcount = len;
1698                 NEW.rm_owner = owner;
1699                 NEW.rm_offset = offset;
1700                 NEW.rm_flags = newext;
1701                 error = xfs_rmap_insert(cur, NEW.rm_startblock,
1702                                 NEW.rm_blockcount, NEW.rm_owner, NEW.rm_offset,
1703                                 NEW.rm_flags);
1704                 if (error)
1705                         goto done;
1706                 break;
1707
1708         case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1709         case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1710         case RMAP_LEFT_FILLING | RMAP_RIGHT_CONTIG:
1711         case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG:
1712         case RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG:
1713         case RMAP_LEFT_CONTIG:
1714         case RMAP_RIGHT_CONTIG:
1715                 /*
1716                  * These cases are all impossible.
1717                  */
1718                 ASSERT(0);
1719         }
1720
1721         trace_xfs_rmap_convert_done(mp, cur->bc_private.a.agno, bno, len,
1722                         unwritten, oinfo);
1723 done:
1724         if (error)
1725                 trace_xfs_rmap_convert_error(cur->bc_mp,
1726                                 cur->bc_private.a.agno, error, _RET_IP_);
1727         return error;
1728 }
1729
1730 #undef  NEW
1731 #undef  LEFT
1732 #undef  RIGHT
1733 #undef  PREV
1734
1735 /*
1736  * Find an extent in the rmap btree and unmap it.  For rmap extent types that
1737  * can overlap (data fork rmaps on reflink filesystems) we must be careful
1738  * that the prev/next records in the btree might belong to another owner.
1739  * Therefore we must use delete+insert to alter any of the key fields.
1740  *
1741  * For every other situation there can only be one owner for a given extent,
1742  * so we can call the regular _free function.
1743  */
1744 STATIC int
1745 xfs_rmap_unmap_shared(
1746         struct xfs_btree_cur            *cur,
1747         xfs_agblock_t                   bno,
1748         xfs_extlen_t                    len,
1749         bool                            unwritten,
1750         const struct xfs_owner_info     *oinfo)
1751 {
1752         struct xfs_mount                *mp = cur->bc_mp;
1753         struct xfs_rmap_irec            ltrec;
1754         uint64_t                        ltoff;
1755         int                             error = 0;
1756         int                             i;
1757         uint64_t                        owner;
1758         uint64_t                        offset;
1759         unsigned int                    flags;
1760
1761         xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
1762         if (unwritten)
1763                 flags |= XFS_RMAP_UNWRITTEN;
1764         trace_xfs_rmap_unmap(mp, cur->bc_private.a.agno, bno, len,
1765                         unwritten, oinfo);
1766
1767         /*
1768          * We should always have a left record because there's a static record
1769          * for the AG headers at rm_startblock == 0 created by mkfs/growfs that
1770          * will not ever be removed from the tree.
1771          */
1772         error = xfs_rmap_lookup_le_range(cur, bno, owner, offset, flags,
1773                         &ltrec, &i);
1774         if (error)
1775                 goto out_error;
1776         XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error);
1777         ltoff = ltrec.rm_offset;
1778
1779         /* Make sure the extent we found covers the entire freeing range. */
1780         XFS_WANT_CORRUPTED_GOTO(mp, ltrec.rm_startblock <= bno &&
1781                 ltrec.rm_startblock + ltrec.rm_blockcount >=
1782                 bno + len, out_error);
1783
1784         /* Make sure the owner matches what we expect to find in the tree. */
1785         XFS_WANT_CORRUPTED_GOTO(mp, owner == ltrec.rm_owner, out_error);
1786
1787         /* Make sure the unwritten flag matches. */
1788         XFS_WANT_CORRUPTED_GOTO(mp, (flags & XFS_RMAP_UNWRITTEN) ==
1789                         (ltrec.rm_flags & XFS_RMAP_UNWRITTEN), out_error);
1790
1791         /* Check the offset. */
1792         XFS_WANT_CORRUPTED_GOTO(mp, ltrec.rm_offset <= offset, out_error);
1793         XFS_WANT_CORRUPTED_GOTO(mp, offset <= ltoff + ltrec.rm_blockcount,
1794                         out_error);
1795
1796         if (ltrec.rm_startblock == bno && ltrec.rm_blockcount == len) {
1797                 /* Exact match, simply remove the record from rmap tree. */
1798                 error = xfs_rmap_delete(cur, ltrec.rm_startblock,
1799                                 ltrec.rm_blockcount, ltrec.rm_owner,
1800                                 ltrec.rm_offset, ltrec.rm_flags);
1801                 if (error)
1802                         goto out_error;
1803         } else if (ltrec.rm_startblock == bno) {
1804                 /*
1805                  * Overlap left hand side of extent: move the start, trim the
1806                  * length and update the current record.
1807                  *
1808                  *       ltbno                ltlen
1809                  * Orig:    |oooooooooooooooooooo|
1810                  * Freeing: |fffffffff|
1811                  * Result:            |rrrrrrrrrr|
1812                  *         bno       len
1813                  */
1814
1815                 /* Delete prev rmap. */
1816                 error = xfs_rmap_delete(cur, ltrec.rm_startblock,
1817                                 ltrec.rm_blockcount, ltrec.rm_owner,
1818                                 ltrec.rm_offset, ltrec.rm_flags);
1819                 if (error)
1820                         goto out_error;
1821
1822                 /* Add an rmap at the new offset. */
1823                 ltrec.rm_startblock += len;
1824                 ltrec.rm_blockcount -= len;
1825                 ltrec.rm_offset += len;
1826                 error = xfs_rmap_insert(cur, ltrec.rm_startblock,
1827                                 ltrec.rm_blockcount, ltrec.rm_owner,
1828                                 ltrec.rm_offset, ltrec.rm_flags);
1829                 if (error)
1830                         goto out_error;
1831         } else if (ltrec.rm_startblock + ltrec.rm_blockcount == bno + len) {
1832                 /*
1833                  * Overlap right hand side of extent: trim the length and
1834                  * update the current record.
1835                  *
1836                  *       ltbno                ltlen
1837                  * Orig:    |oooooooooooooooooooo|
1838                  * Freeing:            |fffffffff|
1839                  * Result:  |rrrrrrrrrr|
1840                  *                    bno       len
1841                  */
1842                 error = xfs_rmap_lookup_eq(cur, ltrec.rm_startblock,
1843                                 ltrec.rm_blockcount, ltrec.rm_owner,
1844                                 ltrec.rm_offset, ltrec.rm_flags, &i);
1845                 if (error)
1846                         goto out_error;
1847                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error);
1848                 ltrec.rm_blockcount -= len;
1849                 error = xfs_rmap_update(cur, &ltrec);
1850                 if (error)
1851                         goto out_error;
1852         } else {
1853                 /*
1854                  * Overlap middle of extent: trim the length of the existing
1855                  * record to the length of the new left-extent size, increment
1856                  * the insertion position so we can insert a new record
1857                  * containing the remaining right-extent space.
1858                  *
1859                  *       ltbno                ltlen
1860                  * Orig:    |oooooooooooooooooooo|
1861                  * Freeing:       |fffffffff|
1862                  * Result:  |rrrrr|         |rrrr|
1863                  *               bno       len
1864                  */
1865                 xfs_extlen_t    orig_len = ltrec.rm_blockcount;
1866
1867                 /* Shrink the left side of the rmap */
1868                 error = xfs_rmap_lookup_eq(cur, ltrec.rm_startblock,
1869                                 ltrec.rm_blockcount, ltrec.rm_owner,
1870                                 ltrec.rm_offset, ltrec.rm_flags, &i);
1871                 if (error)
1872                         goto out_error;
1873                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error);
1874                 ltrec.rm_blockcount = bno - ltrec.rm_startblock;
1875                 error = xfs_rmap_update(cur, &ltrec);
1876                 if (error)
1877                         goto out_error;
1878
1879                 /* Add an rmap at the new offset */
1880                 error = xfs_rmap_insert(cur, bno + len,
1881                                 orig_len - len - ltrec.rm_blockcount,
1882                                 ltrec.rm_owner, offset + len,
1883                                 ltrec.rm_flags);
1884                 if (error)
1885                         goto out_error;
1886         }
1887
1888         trace_xfs_rmap_unmap_done(mp, cur->bc_private.a.agno, bno, len,
1889                         unwritten, oinfo);
1890 out_error:
1891         if (error)
1892                 trace_xfs_rmap_unmap_error(cur->bc_mp,
1893                                 cur->bc_private.a.agno, error, _RET_IP_);
1894         return error;
1895 }
1896
1897 /*
1898  * Find an extent in the rmap btree and map it.  For rmap extent types that
1899  * can overlap (data fork rmaps on reflink filesystems) we must be careful
1900  * that the prev/next records in the btree might belong to another owner.
1901  * Therefore we must use delete+insert to alter any of the key fields.
1902  *
1903  * For every other situation there can only be one owner for a given extent,
1904  * so we can call the regular _alloc function.
1905  */
1906 STATIC int
1907 xfs_rmap_map_shared(
1908         struct xfs_btree_cur            *cur,
1909         xfs_agblock_t                   bno,
1910         xfs_extlen_t                    len,
1911         bool                            unwritten,
1912         const struct xfs_owner_info     *oinfo)
1913 {
1914         struct xfs_mount                *mp = cur->bc_mp;
1915         struct xfs_rmap_irec            ltrec;
1916         struct xfs_rmap_irec            gtrec;
1917         int                             have_gt;
1918         int                             have_lt;
1919         int                             error = 0;
1920         int                             i;
1921         uint64_t                        owner;
1922         uint64_t                        offset;
1923         unsigned int                    flags = 0;
1924
1925         xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
1926         if (unwritten)
1927                 flags |= XFS_RMAP_UNWRITTEN;
1928         trace_xfs_rmap_map(mp, cur->bc_private.a.agno, bno, len,
1929                         unwritten, oinfo);
1930
1931         /* Is there a left record that abuts our range? */
1932         error = xfs_rmap_find_left_neighbor(cur, bno, owner, offset, flags,
1933                         &ltrec, &have_lt);
1934         if (error)
1935                 goto out_error;
1936         if (have_lt &&
1937             !xfs_rmap_is_mergeable(&ltrec, owner, flags))
1938                 have_lt = 0;
1939
1940         /* Is there a right record that abuts our range? */
1941         error = xfs_rmap_lookup_eq(cur, bno + len, len, owner, offset + len,
1942                         flags, &have_gt);
1943         if (error)
1944                 goto out_error;
1945         if (have_gt) {
1946                 error = xfs_rmap_get_rec(cur, &gtrec, &have_gt);
1947                 if (error)
1948                         goto out_error;
1949                 XFS_WANT_CORRUPTED_GOTO(mp, have_gt == 1, out_error);
1950                 trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp,
1951                         cur->bc_private.a.agno, gtrec.rm_startblock,
1952                         gtrec.rm_blockcount, gtrec.rm_owner,
1953                         gtrec.rm_offset, gtrec.rm_flags);
1954
1955                 if (!xfs_rmap_is_mergeable(&gtrec, owner, flags))
1956                         have_gt = 0;
1957         }
1958
1959         if (have_lt &&
1960             ltrec.rm_startblock + ltrec.rm_blockcount == bno &&
1961             ltrec.rm_offset + ltrec.rm_blockcount == offset) {
1962                 /*
1963                  * Left edge contiguous, merge into left record.
1964                  *
1965                  *       ltbno     ltlen
1966                  * orig:   |ooooooooo|
1967                  * adding:           |aaaaaaaaa|
1968                  * result: |rrrrrrrrrrrrrrrrrrr|
1969                  *                  bno       len
1970                  */
1971                 ltrec.rm_blockcount += len;
1972                 if (have_gt &&
1973                     bno + len == gtrec.rm_startblock &&
1974                     offset + len == gtrec.rm_offset) {
1975                         /*
1976                          * Right edge also contiguous, delete right record
1977                          * and merge into left record.
1978                          *
1979                          *       ltbno     ltlen    gtbno     gtlen
1980                          * orig:   |ooooooooo|         |ooooooooo|
1981                          * adding:           |aaaaaaaaa|
1982                          * result: |rrrrrrrrrrrrrrrrrrrrrrrrrrrrr|
1983                          */
1984                         ltrec.rm_blockcount += gtrec.rm_blockcount;
1985                         error = xfs_rmap_delete(cur, gtrec.rm_startblock,
1986                                         gtrec.rm_blockcount, gtrec.rm_owner,
1987                                         gtrec.rm_offset, gtrec.rm_flags);
1988                         if (error)
1989                                 goto out_error;
1990                 }
1991
1992                 /* Point the cursor back to the left record and update. */
1993                 error = xfs_rmap_lookup_eq(cur, ltrec.rm_startblock,
1994                                 ltrec.rm_blockcount, ltrec.rm_owner,
1995                                 ltrec.rm_offset, ltrec.rm_flags, &i);
1996                 if (error)
1997                         goto out_error;
1998                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error);
1999
2000                 error = xfs_rmap_update(cur, &ltrec);
2001                 if (error)
2002                         goto out_error;
2003         } else if (have_gt &&
2004                    bno + len == gtrec.rm_startblock &&
2005                    offset + len == gtrec.rm_offset) {
2006                 /*
2007                  * Right edge contiguous, merge into right record.
2008                  *
2009                  *                 gtbno     gtlen
2010                  * Orig:             |ooooooooo|
2011                  * adding: |aaaaaaaaa|
2012                  * Result: |rrrrrrrrrrrrrrrrrrr|
2013                  *        bno       len
2014                  */
2015                 /* Delete the old record. */
2016                 error = xfs_rmap_delete(cur, gtrec.rm_startblock,
2017                                 gtrec.rm_blockcount, gtrec.rm_owner,
2018                                 gtrec.rm_offset, gtrec.rm_flags);
2019                 if (error)
2020                         goto out_error;
2021
2022                 /* Move the start and re-add it. */
2023                 gtrec.rm_startblock = bno;
2024                 gtrec.rm_blockcount += len;
2025                 gtrec.rm_offset = offset;
2026                 error = xfs_rmap_insert(cur, gtrec.rm_startblock,
2027                                 gtrec.rm_blockcount, gtrec.rm_owner,
2028                                 gtrec.rm_offset, gtrec.rm_flags);
2029                 if (error)
2030                         goto out_error;
2031         } else {
2032                 /*
2033                  * No contiguous edge with identical owner, insert
2034                  * new record at current cursor position.
2035                  */
2036                 error = xfs_rmap_insert(cur, bno, len, owner, offset, flags);
2037                 if (error)
2038                         goto out_error;
2039         }
2040
2041         trace_xfs_rmap_map_done(mp, cur->bc_private.a.agno, bno, len,
2042                         unwritten, oinfo);
2043 out_error:
2044         if (error)
2045                 trace_xfs_rmap_map_error(cur->bc_mp,
2046                                 cur->bc_private.a.agno, error, _RET_IP_);
2047         return error;
2048 }
2049
2050 /* Insert a raw rmap into the rmapbt. */
2051 int
2052 xfs_rmap_map_raw(
2053         struct xfs_btree_cur    *cur,
2054         struct xfs_rmap_irec    *rmap)
2055 {
2056         struct xfs_owner_info   oinfo;
2057
2058         oinfo.oi_owner = rmap->rm_owner;
2059         oinfo.oi_offset = rmap->rm_offset;
2060         oinfo.oi_flags = 0;
2061         if (rmap->rm_flags & XFS_RMAP_ATTR_FORK)
2062                 oinfo.oi_flags |= XFS_OWNER_INFO_ATTR_FORK;
2063         if (rmap->rm_flags & XFS_RMAP_BMBT_BLOCK)
2064                 oinfo.oi_flags |= XFS_OWNER_INFO_BMBT_BLOCK;
2065
2066         if (rmap->rm_flags || XFS_RMAP_NON_INODE_OWNER(rmap->rm_owner))
2067                 return xfs_rmap_map(cur, rmap->rm_startblock,
2068                                 rmap->rm_blockcount,
2069                                 rmap->rm_flags & XFS_RMAP_UNWRITTEN,
2070                                 &oinfo);
2071
2072         return xfs_rmap_map_shared(cur, rmap->rm_startblock,
2073                         rmap->rm_blockcount,
2074                         rmap->rm_flags & XFS_RMAP_UNWRITTEN,
2075                         &oinfo);
2076 }
2077
2078 struct xfs_rmap_query_range_info {
2079         xfs_rmap_query_range_fn fn;
2080         void                            *priv;
2081 };
2082
2083 /* Format btree record and pass to our callback. */
2084 STATIC int
2085 xfs_rmap_query_range_helper(
2086         struct xfs_btree_cur    *cur,
2087         union xfs_btree_rec     *rec,
2088         void                    *priv)
2089 {
2090         struct xfs_rmap_query_range_info        *query = priv;
2091         struct xfs_rmap_irec                    irec;
2092         int                                     error;
2093
2094         error = xfs_rmap_btrec_to_irec(rec, &irec);
2095         if (error)
2096                 return error;
2097         return query->fn(cur, &irec, query->priv);
2098 }
2099
2100 /* Find all rmaps between two keys. */
2101 int
2102 xfs_rmap_query_range(
2103         struct xfs_btree_cur                    *cur,
2104         struct xfs_rmap_irec                    *low_rec,
2105         struct xfs_rmap_irec                    *high_rec,
2106         xfs_rmap_query_range_fn                 fn,
2107         void                                    *priv)
2108 {
2109         union xfs_btree_irec                    low_brec;
2110         union xfs_btree_irec                    high_brec;
2111         struct xfs_rmap_query_range_info        query;
2112
2113         low_brec.r = *low_rec;
2114         high_brec.r = *high_rec;
2115         query.priv = priv;
2116         query.fn = fn;
2117         return xfs_btree_query_range(cur, &low_brec, &high_brec,
2118                         xfs_rmap_query_range_helper, &query);
2119 }
2120
2121 /* Find all rmaps. */
2122 int
2123 xfs_rmap_query_all(
2124         struct xfs_btree_cur                    *cur,
2125         xfs_rmap_query_range_fn                 fn,
2126         void                                    *priv)
2127 {
2128         struct xfs_rmap_query_range_info        query;
2129
2130         query.priv = priv;
2131         query.fn = fn;
2132         return xfs_btree_query_all(cur, xfs_rmap_query_range_helper, &query);
2133 }
2134
2135 /* Clean up after calling xfs_rmap_finish_one. */
2136 void
2137 xfs_rmap_finish_one_cleanup(
2138         struct xfs_trans        *tp,
2139         struct xfs_btree_cur    *rcur,
2140         int                     error)
2141 {
2142         struct xfs_buf          *agbp;
2143
2144         if (rcur == NULL)
2145                 return;
2146         agbp = rcur->bc_private.a.agbp;
2147         xfs_btree_del_cursor(rcur, error);
2148         if (error)
2149                 xfs_trans_brelse(tp, agbp);
2150 }
2151
2152 /*
2153  * Process one of the deferred rmap operations.  We pass back the
2154  * btree cursor to maintain our lock on the rmapbt between calls.
2155  * This saves time and eliminates a buffer deadlock between the
2156  * superblock and the AGF because we'll always grab them in the same
2157  * order.
2158  */
2159 int
2160 xfs_rmap_finish_one(
2161         struct xfs_trans                *tp,
2162         enum xfs_rmap_intent_type       type,
2163         uint64_t                        owner,
2164         int                             whichfork,
2165         xfs_fileoff_t                   startoff,
2166         xfs_fsblock_t                   startblock,
2167         xfs_filblks_t                   blockcount,
2168         xfs_exntst_t                    state,
2169         struct xfs_btree_cur            **pcur)
2170 {
2171         struct xfs_mount                *mp = tp->t_mountp;
2172         struct xfs_btree_cur            *rcur;
2173         struct xfs_buf                  *agbp = NULL;
2174         int                             error = 0;
2175         xfs_agnumber_t                  agno;
2176         struct xfs_owner_info           oinfo;
2177         xfs_agblock_t                   bno;
2178         bool                            unwritten;
2179
2180         agno = XFS_FSB_TO_AGNO(mp, startblock);
2181         ASSERT(agno != NULLAGNUMBER);
2182         bno = XFS_FSB_TO_AGBNO(mp, startblock);
2183
2184         trace_xfs_rmap_deferred(mp, agno, type, bno, owner, whichfork,
2185                         startoff, blockcount, state);
2186
2187         if (XFS_TEST_ERROR(false, mp,
2188                         XFS_ERRTAG_RMAP_FINISH_ONE))
2189                 return -EIO;
2190
2191         /*
2192          * If we haven't gotten a cursor or the cursor AG doesn't match
2193          * the startblock, get one now.
2194          */
2195         rcur = *pcur;
2196         if (rcur != NULL && rcur->bc_private.a.agno != agno) {
2197                 xfs_rmap_finish_one_cleanup(tp, rcur, 0);
2198                 rcur = NULL;
2199                 *pcur = NULL;
2200         }
2201         if (rcur == NULL) {
2202                 /*
2203                  * Refresh the freelist before we start changing the
2204                  * rmapbt, because a shape change could cause us to
2205                  * allocate blocks.
2206                  */
2207                 error = xfs_free_extent_fix_freelist(tp, agno, &agbp);
2208                 if (error)
2209                         return error;
2210                 if (!agbp)
2211                         return -EFSCORRUPTED;
2212
2213                 rcur = xfs_rmapbt_init_cursor(mp, tp, agbp, agno);
2214                 if (!rcur) {
2215                         error = -ENOMEM;
2216                         goto out_cur;
2217                 }
2218         }
2219         *pcur = rcur;
2220
2221         xfs_rmap_ino_owner(&oinfo, owner, whichfork, startoff);
2222         unwritten = state == XFS_EXT_UNWRITTEN;
2223         bno = XFS_FSB_TO_AGBNO(rcur->bc_mp, startblock);
2224
2225         switch (type) {
2226         case XFS_RMAP_ALLOC:
2227         case XFS_RMAP_MAP:
2228                 error = xfs_rmap_map(rcur, bno, blockcount, unwritten, &oinfo);
2229                 break;
2230         case XFS_RMAP_MAP_SHARED:
2231                 error = xfs_rmap_map_shared(rcur, bno, blockcount, unwritten,
2232                                 &oinfo);
2233                 break;
2234         case XFS_RMAP_FREE:
2235         case XFS_RMAP_UNMAP:
2236                 error = xfs_rmap_unmap(rcur, bno, blockcount, unwritten,
2237                                 &oinfo);
2238                 break;
2239         case XFS_RMAP_UNMAP_SHARED:
2240                 error = xfs_rmap_unmap_shared(rcur, bno, blockcount, unwritten,
2241                                 &oinfo);
2242                 break;
2243         case XFS_RMAP_CONVERT:
2244                 error = xfs_rmap_convert(rcur, bno, blockcount, !unwritten,
2245                                 &oinfo);
2246                 break;
2247         case XFS_RMAP_CONVERT_SHARED:
2248                 error = xfs_rmap_convert_shared(rcur, bno, blockcount,
2249                                 !unwritten, &oinfo);
2250                 break;
2251         default:
2252                 ASSERT(0);
2253                 error = -EFSCORRUPTED;
2254         }
2255         return error;
2256
2257 out_cur:
2258         xfs_trans_brelse(tp, agbp);
2259
2260         return error;
2261 }
2262
2263 /*
2264  * Don't defer an rmap if we aren't an rmap filesystem.
2265  */
2266 static bool
2267 xfs_rmap_update_is_needed(
2268         struct xfs_mount        *mp,
2269         int                     whichfork)
2270 {
2271         return xfs_sb_version_hasrmapbt(&mp->m_sb) && whichfork != XFS_COW_FORK;
2272 }
2273
2274 /*
2275  * Record a rmap intent; the list is kept sorted first by AG and then by
2276  * increasing age.
2277  */
2278 static int
2279 __xfs_rmap_add(
2280         struct xfs_trans                *tp,
2281         enum xfs_rmap_intent_type       type,
2282         uint64_t                        owner,
2283         int                             whichfork,
2284         struct xfs_bmbt_irec            *bmap)
2285 {
2286         struct xfs_rmap_intent          *ri;
2287
2288         trace_xfs_rmap_defer(tp->t_mountp,
2289                         XFS_FSB_TO_AGNO(tp->t_mountp, bmap->br_startblock),
2290                         type,
2291                         XFS_FSB_TO_AGBNO(tp->t_mountp, bmap->br_startblock),
2292                         owner, whichfork,
2293                         bmap->br_startoff,
2294                         bmap->br_blockcount,
2295                         bmap->br_state);
2296
2297         ri = kmem_alloc(sizeof(struct xfs_rmap_intent), KM_SLEEP | KM_NOFS);
2298         INIT_LIST_HEAD(&ri->ri_list);
2299         ri->ri_type = type;
2300         ri->ri_owner = owner;
2301         ri->ri_whichfork = whichfork;
2302         ri->ri_bmap = *bmap;
2303
2304         xfs_defer_add(tp, XFS_DEFER_OPS_TYPE_RMAP, &ri->ri_list);
2305         return 0;
2306 }
2307
2308 /* Map an extent into a file. */
2309 int
2310 xfs_rmap_map_extent(
2311         struct xfs_trans        *tp,
2312         struct xfs_inode        *ip,
2313         int                     whichfork,
2314         struct xfs_bmbt_irec    *PREV)
2315 {
2316         if (!xfs_rmap_update_is_needed(tp->t_mountp, whichfork))
2317                 return 0;
2318
2319         return __xfs_rmap_add(tp, xfs_is_reflink_inode(ip) ?
2320                         XFS_RMAP_MAP_SHARED : XFS_RMAP_MAP, ip->i_ino,
2321                         whichfork, PREV);
2322 }
2323
2324 /* Unmap an extent out of a file. */
2325 int
2326 xfs_rmap_unmap_extent(
2327         struct xfs_trans        *tp,
2328         struct xfs_inode        *ip,
2329         int                     whichfork,
2330         struct xfs_bmbt_irec    *PREV)
2331 {
2332         if (!xfs_rmap_update_is_needed(tp->t_mountp, whichfork))
2333                 return 0;
2334
2335         return __xfs_rmap_add(tp, xfs_is_reflink_inode(ip) ?
2336                         XFS_RMAP_UNMAP_SHARED : XFS_RMAP_UNMAP, ip->i_ino,
2337                         whichfork, PREV);
2338 }
2339
2340 /*
2341  * Convert a data fork extent from unwritten to real or vice versa.
2342  *
2343  * Note that tp can be NULL here as no transaction is used for COW fork
2344  * unwritten conversion.
2345  */
2346 int
2347 xfs_rmap_convert_extent(
2348         struct xfs_mount        *mp,
2349         struct xfs_trans        *tp,
2350         struct xfs_inode        *ip,
2351         int                     whichfork,
2352         struct xfs_bmbt_irec    *PREV)
2353 {
2354         if (!xfs_rmap_update_is_needed(mp, whichfork))
2355                 return 0;
2356
2357         return __xfs_rmap_add(tp, xfs_is_reflink_inode(ip) ?
2358                         XFS_RMAP_CONVERT_SHARED : XFS_RMAP_CONVERT, ip->i_ino,
2359                         whichfork, PREV);
2360 }
2361
2362 /* Schedule the creation of an rmap for non-file data. */
2363 int
2364 xfs_rmap_alloc_extent(
2365         struct xfs_trans        *tp,
2366         xfs_agnumber_t          agno,
2367         xfs_agblock_t           bno,
2368         xfs_extlen_t            len,
2369         uint64_t                owner)
2370 {
2371         struct xfs_bmbt_irec    bmap;
2372
2373         if (!xfs_rmap_update_is_needed(tp->t_mountp, XFS_DATA_FORK))
2374                 return 0;
2375
2376         bmap.br_startblock = XFS_AGB_TO_FSB(tp->t_mountp, agno, bno);
2377         bmap.br_blockcount = len;
2378         bmap.br_startoff = 0;
2379         bmap.br_state = XFS_EXT_NORM;
2380
2381         return __xfs_rmap_add(tp, XFS_RMAP_ALLOC, owner, XFS_DATA_FORK, &bmap);
2382 }
2383
2384 /* Schedule the deletion of an rmap for non-file data. */
2385 int
2386 xfs_rmap_free_extent(
2387         struct xfs_trans        *tp,
2388         xfs_agnumber_t          agno,
2389         xfs_agblock_t           bno,
2390         xfs_extlen_t            len,
2391         uint64_t                owner)
2392 {
2393         struct xfs_bmbt_irec    bmap;
2394
2395         if (!xfs_rmap_update_is_needed(tp->t_mountp, XFS_DATA_FORK))
2396                 return 0;
2397
2398         bmap.br_startblock = XFS_AGB_TO_FSB(tp->t_mountp, agno, bno);
2399         bmap.br_blockcount = len;
2400         bmap.br_startoff = 0;
2401         bmap.br_state = XFS_EXT_NORM;
2402
2403         return __xfs_rmap_add(tp, XFS_RMAP_FREE, owner, XFS_DATA_FORK, &bmap);
2404 }
2405
2406 /* Compare rmap records.  Returns -1 if a < b, 1 if a > b, and 0 if equal. */
2407 int
2408 xfs_rmap_compare(
2409         const struct xfs_rmap_irec      *a,
2410         const struct xfs_rmap_irec      *b)
2411 {
2412         __u64                           oa;
2413         __u64                           ob;
2414
2415         oa = xfs_rmap_irec_offset_pack(a);
2416         ob = xfs_rmap_irec_offset_pack(b);
2417
2418         if (a->rm_startblock < b->rm_startblock)
2419                 return -1;
2420         else if (a->rm_startblock > b->rm_startblock)
2421                 return 1;
2422         else if (a->rm_owner < b->rm_owner)
2423                 return -1;
2424         else if (a->rm_owner > b->rm_owner)
2425                 return 1;
2426         else if (oa < ob)
2427                 return -1;
2428         else if (oa > ob)
2429                 return 1;
2430         else
2431                 return 0;
2432 }
2433
2434 /* Is there a record covering a given extent? */
2435 int
2436 xfs_rmap_has_record(
2437         struct xfs_btree_cur    *cur,
2438         xfs_agblock_t           bno,
2439         xfs_extlen_t            len,
2440         bool                    *exists)
2441 {
2442         union xfs_btree_irec    low;
2443         union xfs_btree_irec    high;
2444
2445         memset(&low, 0, sizeof(low));
2446         low.r.rm_startblock = bno;
2447         memset(&high, 0xFF, sizeof(high));
2448         high.r.rm_startblock = bno + len - 1;
2449
2450         return xfs_btree_has_record(cur, &low, &high, exists);
2451 }
2452
2453 /*
2454  * Is there a record for this owner completely covering a given physical
2455  * extent?  If so, *has_rmap will be set to true.  If there is no record
2456  * or the record only covers part of the range, we set *has_rmap to false.
2457  * This function doesn't perform range lookups or offset checks, so it is
2458  * not suitable for checking data fork blocks.
2459  */
2460 int
2461 xfs_rmap_record_exists(
2462         struct xfs_btree_cur            *cur,
2463         xfs_agblock_t                   bno,
2464         xfs_extlen_t                    len,
2465         const struct xfs_owner_info     *oinfo,
2466         bool                            *has_rmap)
2467 {
2468         uint64_t                        owner;
2469         uint64_t                        offset;
2470         unsigned int                    flags;
2471         int                             has_record;
2472         struct xfs_rmap_irec            irec;
2473         int                             error;
2474
2475         xfs_owner_info_unpack(oinfo, &owner, &offset, &flags);
2476         ASSERT(XFS_RMAP_NON_INODE_OWNER(owner) ||
2477                (flags & XFS_RMAP_BMBT_BLOCK));
2478
2479         error = xfs_rmap_lookup_le(cur, bno, len, owner, offset, flags,
2480                         &has_record);
2481         if (error)
2482                 return error;
2483         if (!has_record) {
2484                 *has_rmap = false;
2485                 return 0;
2486         }
2487
2488         error = xfs_rmap_get_rec(cur, &irec, &has_record);
2489         if (error)
2490                 return error;
2491         if (!has_record) {
2492                 *has_rmap = false;
2493                 return 0;
2494         }
2495
2496         *has_rmap = (irec.rm_owner == owner && irec.rm_startblock <= bno &&
2497                      irec.rm_startblock + irec.rm_blockcount >= bno + len);
2498         return 0;
2499 }
2500
2501 struct xfs_rmap_key_state {
2502         uint64_t                        owner;
2503         uint64_t                        offset;
2504         unsigned int                    flags;
2505         bool                            has_rmap;
2506 };
2507
2508 /* For each rmap given, figure out if it doesn't match the key we want. */
2509 STATIC int
2510 xfs_rmap_has_other_keys_helper(
2511         struct xfs_btree_cur            *cur,
2512         struct xfs_rmap_irec            *rec,
2513         void                            *priv)
2514 {
2515         struct xfs_rmap_key_state       *rks = priv;
2516
2517         if (rks->owner == rec->rm_owner && rks->offset == rec->rm_offset &&
2518             ((rks->flags & rec->rm_flags) & XFS_RMAP_KEY_FLAGS) == rks->flags)
2519                 return 0;
2520         rks->has_rmap = true;
2521         return XFS_BTREE_QUERY_RANGE_ABORT;
2522 }
2523
2524 /*
2525  * Given an extent and some owner info, can we find records overlapping
2526  * the extent whose owner info does not match the given owner?
2527  */
2528 int
2529 xfs_rmap_has_other_keys(
2530         struct xfs_btree_cur            *cur,
2531         xfs_agblock_t                   bno,
2532         xfs_extlen_t                    len,
2533         const struct xfs_owner_info     *oinfo,
2534         bool                            *has_rmap)
2535 {
2536         struct xfs_rmap_irec            low = {0};
2537         struct xfs_rmap_irec            high;
2538         struct xfs_rmap_key_state       rks;
2539         int                             error;
2540
2541         xfs_owner_info_unpack(oinfo, &rks.owner, &rks.offset, &rks.flags);
2542         rks.has_rmap = false;
2543
2544         low.rm_startblock = bno;
2545         memset(&high, 0xFF, sizeof(high));
2546         high.rm_startblock = bno + len - 1;
2547
2548         error = xfs_rmap_query_range(cur, &low, &high,
2549                         xfs_rmap_has_other_keys_helper, &rks);
2550         *has_rmap = rks.has_rmap;
2551         return error;
2552 }