fs/xfs/libxfs/xfs_rmap.c

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