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