fs/xfs/libxfs/xfs_rmap.c

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