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