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