1/*
   2 * Copyright (C) 2012 Alexander Block.  All rights reserved.
   3 *
   4 * This program is free software; you can redistribute it and/or
   5 * modify it under the terms of the GNU General Public
   6 * License v2 as published by the Free Software Foundation.
   7 *
   8 * This program is distributed in the hope that it will be useful,
   9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11 * General Public License for more details.
  12 *
  13 * You should have received a copy of the GNU General Public
  14 * License along with this program; if not, write to the
  15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16 * Boston, MA 021110-1307, USA.
  17 */
  18
  19#include <linux/bsearch.h>
  20#include <linux/fs.h>
  21#include <linux/file.h>
  22#include <linux/sort.h>
  23#include <linux/mount.h>
  24#include <linux/xattr.h>
  25#include <linux/posix_acl_xattr.h>
  26#include <linux/radix-tree.h>
  27#include <linux/vmalloc.h>
  28#include <linux/string.h>
  29
  30#include "send.h"
  31#include "backref.h"
  32#include "hash.h"
  33#include "locking.h"
  34#include "disk-io.h"
  35#include "btrfs_inode.h"
  36#include "transaction.h"
  37#include "compression.h"
  38
  39static int g_verbose = 0;
  40
  41#define verbose_printk(...) if (g_verbose) printk(__VA_ARGS__)
  42
  43/*
  44 * A fs_path is a helper to dynamically build path names with unknown size.
  45 * It reallocates the internal buffer on demand.
  46 * It allows fast adding of path elements on the right side (normal path) and
  47 * fast adding to the left side (reversed path). A reversed path can also be
  48 * unreversed if needed.
  49 */
  50struct fs_path {
  51	union {
  52		struct {
  53			char *start;
  54			char *end;
  55
  56			char *buf;
  57			unsigned short buf_len:15;
  58			unsigned short reversed:1;
  59			char inline_buf[];
  60		};
  61		/*
  62		 * Average path length does not exceed 200 bytes, we'll have
  63		 * better packing in the slab and higher chance to satisfy
  64		 * a allocation later during send.
  65		 */
  66		char pad[256];
  67	};
  68};
  69#define FS_PATH_INLINE_SIZE \
  70	(sizeof(struct fs_path) - offsetof(struct fs_path, inline_buf))
  71
  72
  73/* reused for each extent */
  74struct clone_root {
  75	struct btrfs_root *root;
  76	u64 ino;
  77	u64 offset;
  78
  79	u64 found_refs;
  80};
  81
  82#define SEND_CTX_MAX_NAME_CACHE_SIZE 128
  83#define SEND_CTX_NAME_CACHE_CLEAN_SIZE (SEND_CTX_MAX_NAME_CACHE_SIZE * 2)
  84
  85struct send_ctx {
  86	struct file *send_filp;
  87	loff_t send_off;
  88	char *send_buf;
  89	u32 send_size;
  90	u32 send_max_size;
  91	u64 total_send_size;
  92	u64 cmd_send_size[BTRFS_SEND_C_MAX + 1];
  93	u64 flags;	/* 'flags' member of btrfs_ioctl_send_args is u64 */
  94
  95	struct btrfs_root *send_root;
  96	struct btrfs_root *parent_root;
  97	struct clone_root *clone_roots;
  98	int clone_roots_cnt;
  99
 100	/* current state of the compare_tree call */
 101	struct btrfs_path *left_path;
 102	struct btrfs_path *right_path;
 103	struct btrfs_key *cmp_key;
 104
 105	/*
 106	 * infos of the currently processed inode. In case of deleted inodes,
 107	 * these are the values from the deleted inode.
 108	 */
 109	u64 cur_ino;
 110	u64 cur_inode_gen;
 111	int cur_inode_new;
 112	int cur_inode_new_gen;
 113	int cur_inode_deleted;
 114	u64 cur_inode_size;
 115	u64 cur_inode_mode;
 116	u64 cur_inode_rdev;
 117	u64 cur_inode_last_extent;
 118
 119	u64 send_progress;
 120
 121	struct list_head new_refs;
 122	struct list_head deleted_refs;
 123
 124	struct radix_tree_root name_cache;
 125	struct list_head name_cache_list;
 126	int name_cache_size;
 127
 128	struct file_ra_state ra;
 129
 130	char *read_buf;
 131
 132	/*
 133	 * We process inodes by their increasing order, so if before an
 134	 * incremental send we reverse the parent/child relationship of
 135	 * directories such that a directory with a lower inode number was
 136	 * the parent of a directory with a higher inode number, and the one
 137	 * becoming the new parent got renamed too, we can't rename/move the
 138	 * directory with lower inode number when we finish processing it - we
 139	 * must process the directory with higher inode number first, then
 140	 * rename/move it and then rename/move the directory with lower inode
 141	 * number. Example follows.
 142	 *
 143	 * Tree state when the first send was performed:
 144	 *
 145	 * .
 146	 * |-- a                   (ino 257)
 147	 *     |-- b               (ino 258)
 148	 *         |
 149	 *         |
 150	 *         |-- c           (ino 259)
 151	 *         |   |-- d       (ino 260)
 152	 *         |
 153	 *         |-- c2          (ino 261)
 154	 *
 155	 * Tree state when the second (incremental) send is performed:
 156	 *
 157	 * .
 158	 * |-- a                   (ino 257)
 159	 *     |-- b               (ino 258)
 160	 *         |-- c2          (ino 261)
 161	 *             |-- d2      (ino 260)
 162	 *                 |-- cc  (ino 259)
 163	 *
 164	 * The sequence of steps that lead to the second state was:
 165	 *
 166	 * mv /a/b/c/d /a/b/c2/d2
 167	 * mv /a/b/c /a/b/c2/d2/cc
 168	 *
 169	 * "c" has lower inode number, but we can't move it (2nd mv operation)
 170	 * before we move "d", which has higher inode number.
 171	 *
 172	 * So we just memorize which move/rename operations must be performed
 173	 * later when their respective parent is processed and moved/renamed.
 174	 */
 175
 176	/* Indexed by parent directory inode number. */
 177	struct rb_root pending_dir_moves;
 178
 179	/*
 180	 * Reverse index, indexed by the inode number of a directory that
 181	 * is waiting for the move/rename of its immediate parent before its
 182	 * own move/rename can be performed.
 183	 */
 184	struct rb_root waiting_dir_moves;
 185
 186	/*
 187	 * A directory that is going to be rm'ed might have a child directory
 188	 * which is in the pending directory moves index above. In this case,
 189	 * the directory can only be removed after the move/rename of its child
 190	 * is performed. Example:
 191	 *
 192	 * Parent snapshot:
 193	 *
 194	 * .                        (ino 256)
 195	 * |-- a/                   (ino 257)
 196	 *     |-- b/               (ino 258)
 197	 *         |-- c/           (ino 259)
 198	 *         |   |-- x/       (ino 260)
 199	 *         |
 200	 *         |-- y/           (ino 261)
 201	 *
 202	 * Send snapshot:
 203	 *
 204	 * .                        (ino 256)
 205	 * |-- a/                   (ino 257)
 206	 *     |-- b/               (ino 258)
 207	 *         |-- YY/          (ino 261)
 208	 *              |-- x/      (ino 260)
 209	 *
 210	 * Sequence of steps that lead to the send snapshot:
 211	 * rm -f /a/b/c/foo.txt
 212	 * mv /a/b/y /a/b/YY
 213	 * mv /a/b/c/x /a/b/YY
 214	 * rmdir /a/b/c
 215	 *
 216	 * When the child is processed, its move/rename is delayed until its
 217	 * parent is processed (as explained above), but all other operations
 218	 * like update utimes, chown, chgrp, etc, are performed and the paths
 219	 * that it uses for those operations must use the orphanized name of
 220	 * its parent (the directory we're going to rm later), so we need to
 221	 * memorize that name.
 222	 *
 223	 * Indexed by the inode number of the directory to be deleted.
 224	 */
 225	struct rb_root orphan_dirs;
 226};
 227
 228struct pending_dir_move {
 229	struct rb_node node;
 230	struct list_head list;
 231	u64 parent_ino;
 232	u64 ino;
 233	u64 gen;
 234	bool is_orphan;
 235	struct list_head update_refs;
 236};
 237
 238struct waiting_dir_move {
 239	struct rb_node node;
 240	u64 ino;
 241	/*
 242	 * There might be some directory that could not be removed because it
 243	 * was waiting for this directory inode to be moved first. Therefore
 244	 * after this directory is moved, we can try to rmdir the ino rmdir_ino.
 245	 */
 246	u64 rmdir_ino;
 247	bool orphanized;
 248};
 249
 250struct orphan_dir_info {
 251	struct rb_node node;
 252	u64 ino;
 253	u64 gen;
 254};
 255
 256struct name_cache_entry {
 257	struct list_head list;
 258	/*
 259	 * radix_tree has only 32bit entries but we need to handle 64bit inums.
 260	 * We use the lower 32bit of the 64bit inum to store it in the tree. If
 261	 * more then one inum would fall into the same entry, we use radix_list
 262	 * to store the additional entries. radix_list is also used to store
 263	 * entries where two entries have the same inum but different
 264	 * generations.
 265	 */
 266	struct list_head radix_list;
 267	u64 ino;
 268	u64 gen;
 269	u64 parent_ino;
 270	u64 parent_gen;
 271	int ret;
 272	int need_later_update;
 273	int name_len;
 274	char name[];
 275};
 276
 277static int is_waiting_for_move(struct send_ctx *sctx, u64 ino);
 278
 279static struct waiting_dir_move *
 280get_waiting_dir_move(struct send_ctx *sctx, u64 ino);
 281
 282static int is_waiting_for_rm(struct send_ctx *sctx, u64 dir_ino);
 283
 284static int need_send_hole(struct send_ctx *sctx)
 285{
 286	return (sctx->parent_root && !sctx->cur_inode_new &&
 287		!sctx->cur_inode_new_gen && !sctx->cur_inode_deleted &&
 288		S_ISREG(sctx->cur_inode_mode));
 289}
 290
 291static void fs_path_reset(struct fs_path *p)
 292{
 293	if (p->reversed) {
 294		p->start = p->buf + p->buf_len - 1;
 295		p->end = p->start;
 296		*p->start = 0;
 297	} else {
 298		p->start = p->buf;
 299		p->end = p->start;
 300		*p->start = 0;
 301	}
 302}
 303
 304static struct fs_path *fs_path_alloc(void)
 305{
 306	struct fs_path *p;
 307
 308	p = kmalloc(sizeof(*p), GFP_KERNEL);
 309	if (!p)
 310		return NULL;
 311	p->reversed = 0;
 312	p->buf = p->inline_buf;
 313	p->buf_len = FS_PATH_INLINE_SIZE;
 314	fs_path_reset(p);
 315	return p;
 316}
 317
 318static struct fs_path *fs_path_alloc_reversed(void)
 319{
 320	struct fs_path *p;
 321
 322	p = fs_path_alloc();
 323	if (!p)
 324		return NULL;
 325	p->reversed = 1;
 326	fs_path_reset(p);
 327	return p;
 328}
 329
 330static void fs_path_free(struct fs_path *p)
 331{
 332	if (!p)
 333		return;
 334	if (p->buf != p->inline_buf)
 335		kfree(p->buf);
 336	kfree(p);
 337}
 338
 339static int fs_path_len(struct fs_path *p)
 340{
 341	return p->end - p->start;
 342}
 343
 344static int fs_path_ensure_buf(struct fs_path *p, int len)
 345{
 346	char *tmp_buf;
 347	int path_len;
 348	int old_buf_len;
 349
 350	len++;
 351
 352	if (p->buf_len >= len)
 353		return 0;
 354
 355	if (len > PATH_MAX) {
 356		WARN_ON(1);
 357		return -ENOMEM;
 358	}
 359
 360	path_len = p->end - p->start;
 361	old_buf_len = p->buf_len;
 362
 363	/*
 364	 * First time the inline_buf does not suffice
 365	 */
 366	if (p->buf == p->inline_buf) {
 367		tmp_buf = kmalloc(len, GFP_KERNEL);
 368		if (tmp_buf)
 369			memcpy(tmp_buf, p->buf, old_buf_len);
 370	} else {
 371		tmp_buf = krealloc(p->buf, len, GFP_KERNEL);
 372	}
 373	if (!tmp_buf)
 374		return -ENOMEM;
 375	p->buf = tmp_buf;
 376	/*
 377	 * The real size of the buffer is bigger, this will let the fast path
 378	 * happen most of the time
 379	 */
 380	p->buf_len = ksize(p->buf);
 381
 382	if (p->reversed) {
 383		tmp_buf = p->buf + old_buf_len - path_len - 1;
 384		p->end = p->buf + p->buf_len - 1;
 385		p->start = p->end - path_len;
 386		memmove(p->start, tmp_buf, path_len + 1);
 387	} else {
 388		p->start = p->buf;
 389		p->end = p->start + path_len;
 390	}
 391	return 0;
 392}
 393
 394static int fs_path_prepare_for_add(struct fs_path *p, int name_len,
 395				   char **prepared)
 396{
 397	int ret;
 398	int new_len;
 399
 400	new_len = p->end - p->start + name_len;
 401	if (p->start != p->end)
 402		new_len++;
 403	ret = fs_path_ensure_buf(p, new_len);
 404	if (ret < 0)
 405		goto out;
 406
 407	if (p->reversed) {
 408		if (p->start != p->end)
 409			*--p->start = '/';
 410		p->start -= name_len;
 411		*prepared = p->start;
 412	} else {
 413		if (p->start != p->end)
 414			*p->end++ = '/';
 415		*prepared = p->end;
 416		p->end += name_len;
 417		*p->end = 0;
 418	}
 419
 420out:
 421	return ret;
 422}
 423
 424static int fs_path_add(struct fs_path *p, const char *name, int name_len)
 425{
 426	int ret;
 427	char *prepared;
 428
 429	ret = fs_path_prepare_for_add(p, name_len, &prepared);
 430	if (ret < 0)
 431		goto out;
 432	memcpy(prepared, name, name_len);
 433
 434out:
 435	return ret;
 436}
 437
 438static int fs_path_add_path(struct fs_path *p, struct fs_path *p2)
 439{
 440	int ret;
 441	char *prepared;
 442
 443	ret = fs_path_prepare_for_add(p, p2->end - p2->start, &prepared);
 444	if (ret < 0)
 445		goto out;
 446	memcpy(prepared, p2->start, p2->end - p2->start);
 447
 448out:
 449	return ret;
 450}
 451
 452static int fs_path_add_from_extent_buffer(struct fs_path *p,
 453					  struct extent_buffer *eb,
 454					  unsigned long off, int len)
 455{
 456	int ret;
 457	char *prepared;
 458
 459	ret = fs_path_prepare_for_add(p, len, &prepared);
 460	if (ret < 0)
 461		goto out;
 462
 463	read_extent_buffer(eb, prepared, off, len);
 464
 465out:
 466	return ret;
 467}
 468
 469static int fs_path_copy(struct fs_path *p, struct fs_path *from)
 470{
 471	int ret;
 472
 473	p->reversed = from->reversed;
 474	fs_path_reset(p);
 475
 476	ret = fs_path_add_path(p, from);
 477
 478	return ret;
 479}
 480
 481
 482static void fs_path_unreverse(struct fs_path *p)
 483{
 484	char *tmp;
 485	int len;
 486
 487	if (!p->reversed)
 488		return;
 489
 490	tmp = p->start;
 491	len = p->end - p->start;
 492	p->start = p->buf;
 493	p->end = p->start + len;
 494	memmove(p->start, tmp, len + 1);
 495	p->reversed = 0;
 496}
 497
 498static struct btrfs_path *alloc_path_for_send(void)
 499{
 500	struct btrfs_path *path;
 501
 502	path = btrfs_alloc_path();
 503	if (!path)
 504		return NULL;
 505	path->search_commit_root = 1;
 506	path->skip_locking = 1;
 507	path->need_commit_sem = 1;
 508	return path;
 509}
 510
 511static int write_buf(struct file *filp, const void *buf, u32 len, loff_t *off)
 512{
 513	int ret;
 514	mm_segment_t old_fs;
 515	u32 pos = 0;
 516
 517	old_fs = get_fs();
 518	set_fs(KERNEL_DS);
 519
 520	while (pos < len) {
 521		ret = vfs_write(filp, (__force const char __user *)buf + pos,
 522				len - pos, off);
 523		/* TODO handle that correctly */
 524		/*if (ret == -ERESTARTSYS) {
 525			continue;
 526		}*/
 527		if (ret < 0)
 528			goto out;
 529		if (ret == 0) {
 530			ret = -EIO;
 531			goto out;
 532		}
 533		pos += ret;
 534	}
 535
 536	ret = 0;
 537
 538out:
 539	set_fs(old_fs);
 540	return ret;
 541}
 542
 543static int tlv_put(struct send_ctx *sctx, u16 attr, const void *data, int len)
 544{
 545	struct btrfs_tlv_header *hdr;
 546	int total_len = sizeof(*hdr) + len;
 547	int left = sctx->send_max_size - sctx->send_size;
 548
 549	if (unlikely(left < total_len))
 550		return -EOVERFLOW;
 551
 552	hdr = (struct btrfs_tlv_header *) (sctx->send_buf + sctx->send_size);
 553	hdr->tlv_type = cpu_to_le16(attr);
 554	hdr->tlv_len = cpu_to_le16(len);
 555	memcpy(hdr + 1, data, len);
 556	sctx->send_size += total_len;
 557
 558	return 0;
 559}
 560
 561#define TLV_PUT_DEFINE_INT(bits) \
 562	static int tlv_put_u##bits(struct send_ctx *sctx,	 	\
 563			u##bits attr, u##bits value)			\
 564	{								\
 565		__le##bits __tmp = cpu_to_le##bits(value);		\
 566		return tlv_put(sctx, attr, &__tmp, sizeof(__tmp));	\
 567	}
 568
 569TLV_PUT_DEFINE_INT(64)
 570
 571static int tlv_put_string(struct send_ctx *sctx, u16 attr,
 572			  const char *str, int len)
 573{
 574	if (len == -1)
 575		len = strlen(str);
 576	return tlv_put(sctx, attr, str, len);
 577}
 578
 579static int tlv_put_uuid(struct send_ctx *sctx, u16 attr,
 580			const u8 *uuid)
 581{
 582	return tlv_put(sctx, attr, uuid, BTRFS_UUID_SIZE);
 583}
 584
 585static int tlv_put_btrfs_timespec(struct send_ctx *sctx, u16 attr,
 586				  struct extent_buffer *eb,
 587				  struct btrfs_timespec *ts)
 588{
 589	struct btrfs_timespec bts;
 590	read_extent_buffer(eb, &bts, (unsigned long)ts, sizeof(bts));
 591	return tlv_put(sctx, attr, &bts, sizeof(bts));
 592}
 593
 594
 595#define TLV_PUT(sctx, attrtype, attrlen, data) \
 596	do { \
 597		ret = tlv_put(sctx, attrtype, attrlen, data); \
 598		if (ret < 0) \
 599			goto tlv_put_failure; \
 600	} while (0)
 601
 602#define TLV_PUT_INT(sctx, attrtype, bits, value) \
 603	do { \
 604		ret = tlv_put_u##bits(sctx, attrtype, value); \
 605		if (ret < 0) \
 606			goto tlv_put_failure; \
 607	} while (0)
 608
 609#define TLV_PUT_U8(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 8, data)
 610#define TLV_PUT_U16(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 16, data)
 611#define TLV_PUT_U32(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 32, data)
 612#define TLV_PUT_U64(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 64, data)
 613#define TLV_PUT_STRING(sctx, attrtype, str, len) \
 614	do { \
 615		ret = tlv_put_string(sctx, attrtype, str, len); \
 616		if (ret < 0) \
 617			goto tlv_put_failure; \
 618	} while (0)
 619#define TLV_PUT_PATH(sctx, attrtype, p) \
 620	do { \
 621		ret = tlv_put_string(sctx, attrtype, p->start, \
 622			p->end - p->start); \
 623		if (ret < 0) \
 624			goto tlv_put_failure; \
 625	} while(0)
 626#define TLV_PUT_UUID(sctx, attrtype, uuid) \
 627	do { \
 628		ret = tlv_put_uuid(sctx, attrtype, uuid); \
 629		if (ret < 0) \
 630			goto tlv_put_failure; \
 631	} while (0)
 632#define TLV_PUT_BTRFS_TIMESPEC(sctx, attrtype, eb, ts) \
 633	do { \
 634		ret = tlv_put_btrfs_timespec(sctx, attrtype, eb, ts); \
 635		if (ret < 0) \
 636			goto tlv_put_failure; \
 637	} while (0)
 638
 639static int send_header(struct send_ctx *sctx)
 640{
 641	struct btrfs_stream_header hdr;
 642
 643	strcpy(hdr.magic, BTRFS_SEND_STREAM_MAGIC);
 644	hdr.version = cpu_to_le32(BTRFS_SEND_STREAM_VERSION);
 645
 646	return write_buf(sctx->send_filp, &hdr, sizeof(hdr),
 647					&sctx->send_off);
 648}
 649
 650/*
 651 * For each command/item we want to send to userspace, we call this function.
 652 */
 653static int begin_cmd(struct send_ctx *sctx, int cmd)
 654{
 655	struct btrfs_cmd_header *hdr;
 656
 657	if (WARN_ON(!sctx->send_buf))
 658		return -EINVAL;
 659
 660	BUG_ON(sctx->send_size);
 661
 662	sctx->send_size += sizeof(*hdr);
 663	hdr = (struct btrfs_cmd_header *)sctx->send_buf;
 664	hdr->cmd = cpu_to_le16(cmd);
 665
 666	return 0;
 667}
 668
 669static int send_cmd(struct send_ctx *sctx)
 670{
 671	int ret;
 672	struct btrfs_cmd_header *hdr;
 673	u32 crc;
 674
 675	hdr = (struct btrfs_cmd_header *)sctx->send_buf;
 676	hdr->len = cpu_to_le32(sctx->send_size - sizeof(*hdr));
 677	hdr->crc = 0;
 678
 679	crc = btrfs_crc32c(0, (unsigned char *)sctx->send_buf, sctx->send_size);
 680	hdr->crc = cpu_to_le32(crc);
 681
 682	ret = write_buf(sctx->send_filp, sctx->send_buf, sctx->send_size,
 683					&sctx->send_off);
 684
 685	sctx->total_send_size += sctx->send_size;
 686	sctx->cmd_send_size[le16_to_cpu(hdr->cmd)] += sctx->send_size;
 687	sctx->send_size = 0;
 688
 689	return ret;
 690}
 691
 692/*
 693 * Sends a move instruction to user space
 694 */
 695static int send_rename(struct send_ctx *sctx,
 696		     struct fs_path *from, struct fs_path *to)
 697{
 698	int ret;
 699
 700verbose_printk("btrfs: send_rename %s -> %s\n", from->start, to->start);
 701
 702	ret = begin_cmd(sctx, BTRFS_SEND_C_RENAME);
 703	if (ret < 0)
 704		goto out;
 705
 706	TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, from);
 707	TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH_TO, to);
 708
 709	ret = send_cmd(sctx);
 710
 711tlv_put_failure:
 712out:
 713	return ret;
 714}
 715
 716/*
 717 * Sends a link instruction to user space
 718 */
 719static int send_link(struct send_ctx *sctx,
 720		     struct fs_path *path, struct fs_path *lnk)
 721{
 722	int ret;
 723
 724verbose_printk("btrfs: send_link %s -> %s\n", path->start, lnk->start);
 725
 726	ret = begin_cmd(sctx, BTRFS_SEND_C_LINK);
 727	if (ret < 0)
 728		goto out;
 729
 730	TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);
 731	TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH_LINK, lnk);
 732
 733	ret = send_cmd(sctx);
 734
 735tlv_put_failure:
 736out:
 737	return ret;
 738}
 739
 740/*
 741 * Sends an unlink instruction to user space
 742 */
 743static int send_unlink(struct send_ctx *sctx, struct fs_path *path)
 744{
 745	int ret;
 746
 747verbose_printk("btrfs: send_unlink %s\n", path->start);
 748
 749	ret = begin_cmd(sctx, BTRFS_SEND_C_UNLINK);
 750	if (ret < 0)
 751		goto out;
 752
 753	TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);
 754
 755	ret = send_cmd(sctx);
 756
 757tlv_put_failure:
 758out:
 759	return ret;
 760}
 761
 762/*
 763 * Sends a rmdir instruction to user space
 764 */
 765static int send_rmdir(struct send_ctx *sctx, struct fs_path *path)
 766{
 767	int ret;
 768
 769verbose_printk("btrfs: send_rmdir %s\n", path->start);
 770
 771	ret = begin_cmd(sctx, BTRFS_SEND_C_RMDIR);
 772	if (ret < 0)
 773		goto out;
 774
 775	TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);
 776
 777	ret = send_cmd(sctx);
 778
 779tlv_put_failure:
 780out:
 781	return ret;
 782}
 783
 784/*
 785 * Helper function to retrieve some fields from an inode item.
 786 */
 787static int __get_inode_info(struct btrfs_root *root, struct btrfs_path *path,
 788			  u64 ino, u64 *size, u64 *gen, u64 *mode, u64 *uid,
 789			  u64 *gid, u64 *rdev)
 790{
 791	int ret;
 792	struct btrfs_inode_item *ii;
 793	struct btrfs_key key;
 794
 795	key.objectid = ino;
 796	key.type = BTRFS_INODE_ITEM_KEY;
 797	key.offset = 0;
 798	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 799	if (ret) {
 800		if (ret > 0)
 801			ret = -ENOENT;
 802		return ret;
 803	}
 804
 805	ii = btrfs_item_ptr(path->nodes[0], path->slots[0],
 806			struct btrfs_inode_item);
 807	if (size)
 808		*size = btrfs_inode_size(path->nodes[0], ii);
 809	if (gen)
 810		*gen = btrfs_inode_generation(path->nodes[0], ii);
 811	if (mode)
 812		*mode = btrfs_inode_mode(path->nodes[0], ii);
 813	if (uid)
 814		*uid = btrfs_inode_uid(path->nodes[0], ii);
 815	if (gid)
 816		*gid = btrfs_inode_gid(path->nodes[0], ii);
 817	if (rdev)
 818		*rdev = btrfs_inode_rdev(path->nodes[0], ii);
 819
 820	return ret;
 821}
 822
 823static int get_inode_info(struct btrfs_root *root,
 824			  u64 ino, u64 *size, u64 *gen,
 825			  u64 *mode, u64 *uid, u64 *gid,
 826			  u64 *rdev)
 827{
 828	struct btrfs_path *path;
 829	int ret;
 830
 831	path = alloc_path_for_send();
 832	if (!path)
 833		return -ENOMEM;
 834	ret = __get_inode_info(root, path, ino, size, gen, mode, uid, gid,
 835			       rdev);
 836	btrfs_free_path(path);
 837	return ret;
 838}
 839
 840typedef int (*iterate_inode_ref_t)(int num, u64 dir, int index,
 841				   struct fs_path *p,
 842				   void *ctx);
 843
 844/*
 845 * Helper function to iterate the entries in ONE btrfs_inode_ref or
 846 * btrfs_inode_extref.
 847 * The iterate callback may return a non zero value to stop iteration. This can
 848 * be a negative value for error codes or 1 to simply stop it.
 849 *
 850 * path must point to the INODE_REF or INODE_EXTREF when called.
 851 */
 852static int iterate_inode_ref(struct btrfs_root *root, struct btrfs_path *path,
 853			     struct btrfs_key *found_key, int resolve,
 854			     iterate_inode_ref_t iterate, void *ctx)
 855{
 856	struct extent_buffer *eb = path->nodes[0];
 857	struct btrfs_item *item;
 858	struct btrfs_inode_ref *iref;
 859	struct btrfs_inode_extref *extref;
 860	struct btrfs_path *tmp_path;
 861	struct fs_path *p;
 862	u32 cur = 0;
 863	u32 total;
 864	int slot = path->slots[0];
 865	u32 name_len;
 866	char *start;
 867	int ret = 0;
 868	int num = 0;
 869	int index;
 870	u64 dir;
 871	unsigned long name_off;
 872	unsigned long elem_size;
 873	unsigned long ptr;
 874
 875	p = fs_path_alloc_reversed();
 876	if (!p)
 877		return -ENOMEM;
 878
 879	tmp_path = alloc_path_for_send();
 880	if (!tmp_path) {
 881		fs_path_free(p);
 882		return -ENOMEM;
 883	}
 884
 885
 886	if (found_key->type == BTRFS_INODE_REF_KEY) {
 887		ptr = (unsigned long)btrfs_item_ptr(eb, slot,
 888						    struct btrfs_inode_ref);
 889		item = btrfs_item_nr(slot);
 890		total = btrfs_item_size(eb, item);
 891		elem_size = sizeof(*iref);
 892	} else {
 893		ptr = btrfs_item_ptr_offset(eb, slot);
 894		total = btrfs_item_size_nr(eb, slot);
 895		elem_size = sizeof(*extref);
 896	}
 897
 898	while (cur < total) {
 899		fs_path_reset(p);
 900
 901		if (found_key->type == BTRFS_INODE_REF_KEY) {
 902			iref = (struct btrfs_inode_ref *)(ptr + cur);
 903			name_len = btrfs_inode_ref_name_len(eb, iref);
 904			name_off = (unsigned long)(iref + 1);
 905			index = btrfs_inode_ref_index(eb, iref);
 906			dir = found_key->offset;
 907		} else {
 908			extref = (struct btrfs_inode_extref *)(ptr + cur);
 909			name_len = btrfs_inode_extref_name_len(eb, extref);
 910			name_off = (unsigned long)&extref->name;
 911			index = btrfs_inode_extref_index(eb, extref);
 912			dir = btrfs_inode_extref_parent(eb, extref);
 913		}
 914
 915		if (resolve) {
 916			start = btrfs_ref_to_path(root, tmp_path, name_len,
 917						  name_off, eb, dir,
 918						  p->buf, p->buf_len);
 919			if (IS_ERR(start)) {
 920				ret = PTR_ERR(start);
 921				goto out;
 922			}
 923			if (start < p->buf) {
 924				/* overflow , try again with larger buffer */
 925				ret = fs_path_ensure_buf(p,
 926						p->buf_len + p->buf - start);
 927				if (ret < 0)
 928					goto out;
 929				start = btrfs_ref_to_path(root, tmp_path,
 930							  name_len, name_off,
 931							  eb, dir,
 932							  p->buf, p->buf_len);
 933				if (IS_ERR(start)) {
 934					ret = PTR_ERR(start);
 935					goto out;
 936				}
 937				BUG_ON(start < p->buf);
 938			}
 939			p->start = start;
 940		} else {
 941			ret = fs_path_add_from_extent_buffer(p, eb, name_off,
 942							     name_len);
 943			if (ret < 0)
 944				goto out;
 945		}
 946
 947		cur += elem_size + name_len;
 948		ret = iterate(num, dir, index, p, ctx);
 949		if (ret)
 950			goto out;
 951		num++;
 952	}
 953
 954out:
 955	btrfs_free_path(tmp_path);
 956	fs_path_free(p);
 957	return ret;
 958}
 959
 960typedef int (*iterate_dir_item_t)(int num, struct btrfs_key *di_key,
 961				  const char *name, int name_len,
 962				  const char *data, int data_len,
 963				  u8 type, void *ctx);
 964
 965/*
 966 * Helper function to iterate the entries in ONE btrfs_dir_item.
 967 * The iterate callback may return a non zero value to stop iteration. This can
 968 * be a negative value for error codes or 1 to simply stop it.
 969 *
 970 * path must point to the dir item when called.
 971 */
 972static int iterate_dir_item(struct btrfs_root *root, struct btrfs_path *path,
 973			    struct btrfs_key *found_key,
 974			    iterate_dir_item_t iterate, void *ctx)
 975{
 976	int ret = 0;
 977	struct extent_buffer *eb;
 978	struct btrfs_item *item;
 979	struct btrfs_dir_item *di;
 980	struct btrfs_key di_key;
 981	char *buf = NULL;
 982	int buf_len;
 983	u32 name_len;
 984	u32 data_len;
 985	u32 cur;
 986	u32 len;
 987	u32 total;
 988	int slot;
 989	int num;
 990	u8 type;
 991
 992	/*
 993	 * Start with a small buffer (1 page). If later we end up needing more
 994	 * space, which can happen for xattrs on a fs with a leaf size greater
 995	 * then the page size, attempt to increase the buffer. Typically xattr
 996	 * values are small.
 997	 */
 998	buf_len = PATH_MAX;
 999	buf = kmalloc(buf_len, GFP_KERNEL);
1000	if (!buf) {
1001		ret = -ENOMEM;
1002		goto out;
1003	}
1004
1005	eb = path->nodes[0];
1006	slot = path->slots[0];
1007	item = btrfs_item_nr(slot);
1008	di = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);
1009	cur = 0;
1010	len = 0;
1011	total = btrfs_item_size(eb, item);
1012
1013	num = 0;
1014	while (cur < total) {
1015		name_len = btrfs_dir_name_len(eb, di);
1016		data_len = btrfs_dir_data_len(eb, di);
1017		type = btrfs_dir_type(eb, di);
1018		btrfs_dir_item_key_to_cpu(eb, di, &di_key);
1019
1020		if (type == BTRFS_FT_XATTR) {
1021			if (name_len > XATTR_NAME_MAX) {
1022				ret = -ENAMETOOLONG;
1023				goto out;
1024			}
1025			if (name_len + data_len > BTRFS_MAX_XATTR_SIZE(root)) {
1026				ret = -E2BIG;
1027				goto out;
1028			}
1029		} else {
1030			/*
1031			 * Path too long
1032			 */
1033			if (name_len + data_len > PATH_MAX) {
1034				ret = -ENAMETOOLONG;
1035				goto out;
1036			}
1037		}
1038
1039		if (name_len + data_len > buf_len) {
1040			buf_len = name_len + data_len;
1041			if (is_vmalloc_addr(buf)) {
1042				vfree(buf);
1043				buf = NULL;
1044			} else {
1045				char *tmp = krealloc(buf, buf_len,
1046						GFP_KERNEL | __GFP_NOWARN);
1047
1048				if (!tmp)
1049					kfree(buf);
1050				buf = tmp;
1051			}
1052			if (!buf) {
1053				buf = vmalloc(buf_len);
1054				if (!buf) {
1055					ret = -ENOMEM;
1056					goto out;
1057				}
1058			}
1059		}
1060
1061		read_extent_buffer(eb, buf, (unsigned long)(di + 1),
1062				name_len + data_len);
1063
1064		len = sizeof(*di) + name_len + data_len;
1065		di = (struct btrfs_dir_item *)((char *)di + len);
1066		cur += len;
1067
1068		ret = iterate(num, &di_key, buf, name_len, buf + name_len,
1069				data_len, type, ctx);
1070		if (ret < 0)
1071			goto out;
1072		if (ret) {
1073			ret = 0;
1074			goto out;
1075		}
1076
1077		num++;
1078	}
1079
1080out:
1081	kvfree(buf);
1082	return ret;
1083}
1084
1085static int __copy_first_ref(int num, u64 dir, int index,
1086			    struct fs_path *p, void *ctx)
1087{
1088	int ret;
1089	struct fs_path *pt = ctx;
1090
1091	ret = fs_path_copy(pt, p);
1092	if (ret < 0)
1093		return ret;
1094
1095	/* we want the first only */
1096	return 1;
1097}
1098
1099/*
1100 * Retrieve the first path of an inode. If an inode has more then one
1101 * ref/hardlink, this is ignored.
1102 */
1103static int get_inode_path(struct btrfs_root *root,
1104			  u64 ino, struct fs_path *path)
1105{
1106	int ret;
1107	struct btrfs_key key, found_key;
1108	struct btrfs_path *p;
1109
1110	p = alloc_path_for_send();
1111	if (!p)
1112		return -ENOMEM;
1113
1114	fs_path_reset(path);
1115
1116	key.objectid = ino;
1117	key.type = BTRFS_INODE_REF_KEY;
1118	key.offset = 0;
1119
1120	ret = btrfs_search_slot_for_read(root, &key, p, 1, 0);
1121	if (ret < 0)
1122		goto out;
1123	if (ret) {
1124		ret = 1;
1125		goto out;
1126	}
1127	btrfs_item_key_to_cpu(p->nodes[0], &found_key, p->slots[0]);
1128	if (found_key.objectid != ino ||
1129	    (found_key.type != BTRFS_INODE_REF_KEY &&
1130	     found_key.type != BTRFS_INODE_EXTREF_KEY)) {
1131		ret = -ENOENT;
1132		goto out;
1133	}
1134
1135	ret = iterate_inode_ref(root, p, &found_key, 1,
1136				__copy_first_ref, path);
1137	if (ret < 0)
1138		goto out;
1139	ret = 0;
1140
1141out:
1142	btrfs_free_path(p);
1143	return ret;
1144}
1145
1146struct backref_ctx {
1147	struct send_ctx *sctx;
1148
1149	struct btrfs_path *path;
1150	/* number of total found references */
1151	u64 found;
1152
1153	/*
1154	 * used for clones found in send_root. clones found behind cur_objectid
1155	 * and cur_offset are not considered as allowed clones.
1156	 */
1157	u64 cur_objectid;
1158	u64 cur_offset;
1159
1160	/* may be truncated in case it's the last extent in a file */
1161	u64 extent_len;
1162
1163	/* data offset in the file extent item */
1164	u64 data_offset;
1165
1166	/* Just to check for bugs in backref resolving */
1167	int found_itself;
1168};
1169
1170static int __clone_root_cmp_bsearch(const void *key, const void *elt)
1171{
1172	u64 root = (u64)(uintptr_t)key;
1173	struct clone_root *cr = (struct clone_root *)elt;
1174
1175	if (root < cr->root->objectid)
1176		return -1;
1177	if (root > cr->root->objectid)
1178		return 1;
1179	return 0;
1180}
1181
1182static int __clone_root_cmp_sort(const void *e1, const void *e2)
1183{
1184	struct clone_root *cr1 = (struct clone_root *)e1;
1185	struct clone_root *cr2 = (struct clone_root *)e2;
1186
1187	if (cr1->root->objectid < cr2->root->objectid)
1188		return -1;
1189	if (cr1->root->objectid > cr2->root->objectid)
1190		return 1;
1191	return 0;
1192}
1193
1194/*
1195 * Called for every backref that is found for the current extent.
1196 * Results are collected in sctx->clone_roots->ino/offset/found_refs
1197 */
1198static int __iterate_backrefs(u64 ino, u64 offset, u64 root, void *ctx_)
1199{
1200	struct backref_ctx *bctx = ctx_;
1201	struct clone_root *found;
1202	int ret;
1203	u64 i_size;
1204
1205	/* First check if the root is in the list of accepted clone sources */
1206	found = bsearch((void *)(uintptr_t)root, bctx->sctx->clone_roots,
1207			bctx->sctx->clone_roots_cnt,
1208			sizeof(struct clone_root),
1209			__clone_root_cmp_bsearch);
1210	if (!found)
1211		return 0;
1212
1213	if (found->root == bctx->sctx->send_root &&
1214	    ino == bctx->cur_objectid &&
1215	    offset == bctx->cur_offset) {
1216		bctx->found_itself = 1;
1217	}
1218
1219	/*
1220	 * There are inodes that have extents that lie behind its i_size. Don't
1221	 * accept clones from these extents.
1222	 */
1223	ret = __get_inode_info(found->root, bctx->path, ino, &i_size, NULL, NULL,
1224			       NULL, NULL, NULL);
1225	btrfs_release_path(bctx->path);
1226	if (ret < 0)
1227		return ret;
1228
1229	if (offset + bctx->data_offset + bctx->extent_len > i_size)
1230		return 0;
1231
1232	/*
1233	 * Make sure we don't consider clones from send_root that are
1234	 * behind the current inode/offset.
1235	 */
1236	if (found->root == bctx->sctx->send_root) {
1237		/*
1238		 * TODO for the moment we don't accept clones from the inode
1239		 * that is currently send. We may change this when
1240		 * BTRFS_IOC_CLONE_RANGE supports cloning from and to the same
1241		 * file.
1242		 */
1243		if (ino >= bctx->cur_objectid)
1244			return 0;
1245#if 0
1246		if (ino > bctx->cur_objectid)
1247			return 0;
1248		if (offset + bctx->extent_len > bctx->cur_offset)
1249			return 0;
1250#endif
1251	}
1252
1253	bctx->found++;
1254	found->found_refs++;
1255	if (ino < found->ino) {
1256		found->ino = ino;
1257		found->offset = offset;
1258	} else if (found->ino == ino) {
1259		/*
1260		 * same extent found more then once in the same file.
1261		 */
1262		if (found->offset > offset + bctx->extent_len)
1263			found->offset = offset;
1264	}
1265
1266	return 0;
1267}
1268
1269/*
1270 * Given an inode, offset and extent item, it finds a good clone for a clone
1271 * instruction. Returns -ENOENT when none could be found. The function makes
1272 * sure that the returned clone is usable at the point where sending is at the
1273 * moment. This means, that no clones are accepted which lie behind the current
1274 * inode+offset.
1275 *
1276 * path must point to the extent item when called.
1277 */
1278static int find_extent_clone(struct send_ctx *sctx,
1279			     struct btrfs_path *path,
1280			     u64 ino, u64 data_offset,
1281			     u64 ino_size,
1282			     struct clone_root **found)
1283{
1284	int ret;
1285	int extent_type;
1286	u64 logical;
1287	u64 disk_byte;
1288	u64 num_bytes;
1289	u64 extent_item_pos;
1290	u64 flags = 0;
1291	struct btrfs_file_extent_item *fi;
1292	struct extent_buffer *eb = path->nodes[0];
1293	struct backref_ctx *backref_ctx = NULL;
1294	struct clone_root *cur_clone_root;
1295	struct btrfs_key found_key;
1296	struct btrfs_path *tmp_path;
1297	int compressed;
1298	u32 i;
1299
1300	tmp_path = alloc_path_for_send();
1301	if (!tmp_path)
1302		return -ENOMEM;
1303
1304	/* We only use this path under the commit sem */
1305	tmp_path->need_commit_sem = 0;
1306
1307	backref_ctx = kmalloc(sizeof(*backref_ctx), GFP_KERNEL);
1308	if (!backref_ctx) {
1309		ret = -ENOMEM;
1310		goto out;
1311	}
1312
1313	backref_ctx->path = tmp_path;
1314
1315	if (data_offset >= ino_size) {
1316		/*
1317		 * There may be extents that lie behind the file's size.
1318		 * I at least had this in combination with snapshotting while
1319		 * writing large files.
1320		 */
1321		ret = 0;
1322		goto out;
1323	}
1324
1325	fi = btrfs_item_ptr(eb, path->slots[0],
1326			struct btrfs_file_extent_item);
1327	extent_type = btrfs_file_extent_type(eb, fi);
1328	if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
1329		ret = -ENOENT;
1330		goto out;
1331	}
1332	compressed = btrfs_file_extent_compression(eb, fi);
1333
1334	num_bytes = btrfs_file_extent_num_bytes(eb, fi);
1335	disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);
1336	if (disk_byte == 0) {
1337		ret = -ENOENT;
1338		goto out;
1339	}
1340	logical = disk_byte + btrfs_file_extent_offset(eb, fi);
1341
1342	down_read(&sctx->send_root->fs_info->commit_root_sem);
1343	ret = extent_from_logical(sctx->send_root->fs_info, disk_byte, tmp_path,
1344				  &found_key, &flags);
1345	up_read(&sctx->send_root->fs_info->commit_root_sem);
1346	btrfs_release_path(tmp_path);
1347
1348	if (ret < 0)
1349		goto out;
1350	if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
1351		ret = -EIO;
1352		goto out;
1353	}
1354
1355	/*
1356	 * Setup the clone roots.
1357	 */
1358	for (i = 0; i < sctx->clone_roots_cnt; i++) {
1359		cur_clone_root = sctx->clone_roots + i;
1360		cur_clone_root->ino = (u64)-1;
1361		cur_clone_root->offset = 0;
1362		cur_clone_root->found_refs = 0;
1363	}
1364
1365	backref_ctx->sctx = sctx;
1366	backref_ctx->found = 0;
1367	backref_ctx->cur_objectid = ino;
1368	backref_ctx->cur_offset = data_offset;
1369	backref_ctx->found_itself = 0;
1370	backref_ctx->extent_len = num_bytes;
1371	/*
1372	 * For non-compressed extents iterate_extent_inodes() gives us extent
1373	 * offsets that already take into account the data offset, but not for
1374	 * compressed extents, since the offset is logical and not relative to
1375	 * the physical extent locations. We must take this into account to
1376	 * avoid sending clone offsets that go beyond the source file's size,
1377	 * which would result in the clone ioctl failing with -EINVAL on the
1378	 * receiving end.
1379	 */
1380	if (compressed == BTRFS_COMPRESS_NONE)
1381		backref_ctx->data_offset = 0;
1382	else
1383		backref_ctx->data_offset = btrfs_file_extent_offset(eb, fi);
1384
1385	/*
1386	 * The last extent of a file may be too large due to page alignment.
1387	 * We need to adjust extent_len in this case so that the checks in
1388	 * __iterate_backrefs work.
1389	 */
1390	if (data_offset + num_bytes >= ino_size)
1391		backref_ctx->extent_len = ino_size - data_offset;
1392
1393	/*
1394	 * Now collect all backrefs.
1395	 */
1396	if (compressed == BTRFS_COMPRESS_NONE)
1397		extent_item_pos = logical - found_key.objectid;
1398	else
1399		extent_item_pos = 0;
1400	ret = iterate_extent_inodes(sctx->send_root->fs_info,
1401					found_key.objectid, extent_item_pos, 1,
1402					__iterate_backrefs, backref_ctx);
1403
1404	if (ret < 0)
1405		goto out;
1406
1407	if (!backref_ctx->found_itself) {
1408		/* found a bug in backref code? */
1409		ret = -EIO;
1410		btrfs_err(sctx->send_root->fs_info, "did not find backref in "
1411				"send_root. inode=%llu, offset=%llu, "
1412				"disk_byte=%llu found extent=%llu",
1413				ino, data_offset, disk_byte, found_key.objectid);
1414		goto out;
1415	}
1416
1417verbose_printk(KERN_DEBUG "btrfs: find_extent_clone: data_offset=%llu, "
1418		"ino=%llu, "
1419		"num_bytes=%llu, logical=%llu\n",
1420		data_offset, ino, num_bytes, logical);
1421
1422	if (!backref_ctx->found)
1423		verbose_printk("btrfs:    no clones found\n");
1424
1425	cur_clone_root = NULL;
1426	for (i = 0; i < sctx->clone_roots_cnt; i++) {
1427		if (sctx->clone_roots[i].found_refs) {
1428			if (!cur_clone_root)
1429				cur_clone_root = sctx->clone_roots + i;
1430			else if (sctx->clone_roots[i].root == sctx->send_root)
1431				/* prefer clones from send_root over others */
1432				cur_clone_root = sctx->clone_roots + i;
1433		}
1434
1435	}
1436
1437	if (cur_clone_root) {
1438		*found = cur_clone_root;
1439		ret = 0;
1440	} else {
1441		ret = -ENOENT;
1442	}
1443
1444out:
1445	btrfs_free_path(tmp_path);
1446	kfree(backref_ctx);
1447	return ret;
1448}
1449
1450static int read_symlink(struct btrfs_root *root,
1451			u64 ino,
1452			struct fs_path *dest)
1453{
1454	int ret;
1455	struct btrfs_path *path;
1456	struct btrfs_key key;
1457	struct btrfs_file_extent_item *ei;
1458	u8 type;
1459	u8 compression;
1460	unsigned long off;
1461	int len;
1462
1463	path = alloc_path_for_send();
1464	if (!path)
1465		return -ENOMEM;
1466
1467	key.objectid = ino;
1468	key.type = BTRFS_EXTENT_DATA_KEY;
1469	key.offset = 0;
1470	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1471	if (ret < 0)
1472		goto out;
1473	if (ret) {
1474		/*
1475		 * An empty symlink inode. Can happen in rare error paths when
1476		 * creating a symlink (transaction committed before the inode
1477		 * eviction handler removed the symlink inode items and a crash
1478		 * happened in between or the subvol was snapshoted in between).
1479		 * Print an informative message to dmesg/syslog so that the user
1480		 * can delete the symlink.
1481		 */
1482		btrfs_err(root->fs_info,
1483			  "Found empty symlink inode %llu at root %llu",
1484			  ino, root->root_key.objectid);
1485		ret = -EIO;
1486		goto out;
1487	}
1488
1489	ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
1490			struct btrfs_file_extent_item);
1491	type = btrfs_file_extent_type(path->nodes[0], ei);
1492	compression = btrfs_file_extent_compression(path->nodes[0], ei);
1493	BUG_ON(type != BTRFS_FILE_EXTENT_INLINE);
1494	BUG_ON(compression);
1495
1496	off = btrfs_file_extent_inline_start(ei);
1497	len = btrfs_file_extent_inline_len(path->nodes[0], path->slots[0], ei);
1498
1499	ret = fs_path_add_from_extent_buffer(dest, path->nodes[0], off, len);
1500
1501out:
1502	btrfs_free_path(path);
1503	return ret;
1504}
1505
1506/*
1507 * Helper function to generate a file name that is unique in the root of
1508 * send_root and parent_root. This is used to generate names for orphan inodes.
1509 */
1510static int gen_unique_name(struct send_ctx *sctx,
1511			   u64 ino, u64 gen,
1512			   struct fs_path *dest)
1513{
1514	int ret = 0;
1515	struct btrfs_path *path;
1516	struct btrfs_dir_item *di;
1517	char tmp[64];
1518	int len;
1519	u64 idx = 0;
1520
1521	path = alloc_path_for_send();
1522	if (!path)
1523		return -ENOMEM;
1524
1525	while (1) {
1526		len = snprintf(tmp, sizeof(tmp), "o%llu-%llu-%llu",
1527				ino, gen, idx);
1528		ASSERT(len < sizeof(tmp));
1529
1530		di = btrfs_lookup_dir_item(NULL, sctx->send_root,
1531				path, BTRFS_FIRST_FREE_OBJECTID,
1532				tmp, strlen(tmp), 0);
1533		btrfs_release_path(path);
1534		if (IS_ERR(di)) {
1535			ret = PTR_ERR(di);
1536			goto out;
1537		}
1538		if (di) {
1539			/* not unique, try again */
1540			idx++;
1541			continue;
1542		}
1543
1544		if (!sctx->parent_root) {
1545			/* unique */
1546			ret = 0;
1547			break;
1548		}
1549
1550		di = btrfs_lookup_dir_item(NULL, sctx->parent_root,
1551				path, BTRFS_FIRST_FREE_OBJECTID,
1552				tmp, strlen(tmp), 0);
1553		btrfs_release_path(path);
1554		if (IS_ERR(di)) {
1555			ret = PTR_ERR(di);
1556			goto out;
1557		}
1558		if (di) {
1559			/* not unique, try again */
1560			idx++;
1561			continue;
1562		}
1563		/* unique */
1564		break;
1565	}
1566
1567	ret = fs_path_add(dest, tmp, strlen(tmp));
1568
1569out:
1570	btrfs_free_path(path);
1571	return ret;
1572}
1573
1574enum inode_state {
1575	inode_state_no_change,
1576	inode_state_will_create,
1577	inode_state_did_create,
1578	inode_state_will_delete,
1579	inode_state_did_delete,
1580};
1581
1582static int get_cur_inode_state(struct send_ctx *sctx, u64 ino, u64 gen)
1583{
1584	int ret;
1585	int left_ret;
1586	int right_ret;
1587	u64 left_gen;
1588	u64 right_gen;
1589
1590	ret = get_inode_info(sctx->send_root, ino, NULL, &left_gen, NULL, NULL,
1591			NULL, NULL);
1592	if (ret < 0 && ret != -ENOENT)
1593		goto out;
1594	left_ret = ret;
1595
1596	if (!sctx->parent_root) {
1597		right_ret = -ENOENT;
1598	} else {
1599		ret = get_inode_info(sctx->parent_root, ino, NULL, &right_gen,
1600				NULL, NULL, NULL, NULL);
1601		if (ret < 0 && ret != -ENOENT)
1602			goto out;
1603		right_ret = ret;
1604	}
1605
1606	if (!left_ret && !right_ret) {
1607		if (left_gen == gen && right_gen == gen) {
1608			ret = inode_state_no_change;
1609		} else if (left_gen == gen) {
1610			if (ino < sctx->send_progress)
1611				ret = inode_state_did_create;
1612			else
1613				ret = inode_state_will_create;
1614		} else if (right_gen == gen) {
1615			if (ino < sctx->send_progress)
1616				ret = inode_state_did_delete;
1617			else
1618				ret = inode_state_will_delete;
1619		} else  {
1620			ret = -ENOENT;
1621		}
1622	} else if (!left_ret) {
1623		if (left_gen == gen) {
1624			if (ino < sctx->send_progress)
1625				ret = inode_state_did_create;
1626			else
1627				ret = inode_state_will_create;
1628		} else {
1629			ret = -ENOENT;
1630		}
1631	} else if (!right_ret) {
1632		if (right_gen == gen) {
1633			if (ino < sctx->send_progress)
1634				ret = inode_state_did_delete;
1635			else
1636				ret = inode_state_will_delete;
1637		} else {
1638			ret = -ENOENT;
1639		}
1640	} else {
1641		ret = -ENOENT;
1642	}
1643
1644out:
1645	return ret;
1646}
1647
1648static int is_inode_existent(struct send_ctx *sctx, u64 ino, u64 gen)
1649{
1650	int ret;
1651
1652	ret = get_cur_inode_state(sctx, ino, gen);
1653	if (ret < 0)
1654		goto out;
1655
1656	if (ret == inode_state_no_change ||
1657	    ret == inode_state_did_create ||
1658	    ret == inode_state_will_delete)
1659		ret = 1;
1660	else
1661		ret = 0;
1662
1663out:
1664	return ret;
1665}
1666
1667/*
1668 * Helper function to lookup a dir item in a dir.
1669 */
1670static int lookup_dir_item_inode(struct btrfs_root *root,
1671				 u64 dir, const char *name, int name_len,
1672				 u64 *found_inode,
1673				 u8 *found_type)
1674{
1675	int ret = 0;
1676	struct btrfs_dir_item *di;
1677	struct btrfs_key key;
1678	struct btrfs_path *path;
1679
1680	path = alloc_path_for_send();
1681	if (!path)
1682		return -ENOMEM;
1683
1684	di = btrfs_lookup_dir_item(NULL, root, path,
1685			dir, name, name_len, 0);
1686	if (!di) {
1687		ret = -ENOENT;
1688		goto out;
1689	}
1690	if (IS_ERR(di)) {
1691		ret = PTR_ERR(di);
1692		goto out;
1693	}
1694	btrfs_dir_item_key_to_cpu(path->nodes[0], di, &key);
1695	if (key.type == BTRFS_ROOT_ITEM_KEY) {
1696		ret = -ENOENT;
1697		goto out;
1698	}
1699	*found_inode = key.objectid;
1700	*found_type = btrfs_dir_type(path->nodes[0], di);
1701
1702out:
1703	btrfs_free_path(path);
1704	return ret;
1705}
1706
1707/*
1708 * Looks up the first btrfs_inode_ref of a given ino. It returns the parent dir,
1709 * generation of the parent dir and the name of the dir entry.
1710 */
1711static int get_first_ref(struct btrfs_root *root, u64 ino,
1712			 u64 *dir, u64 *dir_gen, struct fs_path *name)
1713{
1714	int ret;
1715	struct btrfs_key key;
1716	struct btrfs_key found_key;
1717	struct btrfs_path *path;
1718	int len;
1719	u64 parent_dir;
1720
1721	path = alloc_path_for_send();
1722	if (!path)
1723		return -ENOMEM;
1724
1725	key.objectid = ino;
1726	key.type = BTRFS_INODE_REF_KEY;
1727	key.offset = 0;
1728
1729	ret = btrfs_search_slot_for_read(root, &key, path, 1, 0);
1730	if (ret < 0)
1731		goto out;
1732	if (!ret)
1733		btrfs_item_key_to_cpu(path->nodes[0], &found_key,
1734				path->slots[0]);
1735	if (ret || found_key.objectid != ino ||
1736	    (found_key.type != BTRFS_INODE_REF_KEY &&
1737	     found_key.type != BTRFS_INODE_EXTREF_KEY)) {
1738		ret = -ENOENT;
1739		goto out;
1740	}
1741
1742	if (found_key.type == BTRFS_INODE_REF_KEY) {
1743		struct btrfs_inode_ref *iref;
1744		iref = btrfs_item_ptr(path->nodes[0], path->slots[0],
1745				      struct btrfs_inode_ref);
1746		len = btrfs_inode_ref_name_len(path->nodes[0], iref);
1747		ret = fs_path_add_from_extent_buffer(name, path->nodes[0],
1748						     (unsigned long)(iref + 1),
1749						     len);
1750		parent_dir = found_key.offset;
1751	} else {
1752		struct btrfs_inode_extref *extref;
1753		extref = btrfs_item_ptr(path->nodes[0], path->slots[0],
1754					struct btrfs_inode_extref);
1755		len = btrfs_inode_extref_name_len(path->nodes[0], extref);
1756		ret = fs_path_add_from_extent_buffer(name, path->nodes[0],
1757					(unsigned long)&extref->name, len);
1758		parent_dir = btrfs_inode_extref_parent(path->nodes[0], extref);
1759	}
1760	if (ret < 0)
1761		goto out;
1762	btrfs_release_path(path);
1763
1764	if (dir_gen) {
1765		ret = get_inode_info(root, parent_dir, NULL, dir_gen, NULL,
1766				     NULL, NULL, NULL);
1767		if (ret < 0)
1768			goto out;
1769	}
1770
1771	*dir = parent_dir;
1772
1773out:
1774	btrfs_free_path(path);
1775	return ret;
1776}
1777
1778static int is_first_ref(struct btrfs_root *root,
1779			u64 ino, u64 dir,
1780			const char *name, int name_len)
1781{
1782	int ret;
1783	struct fs_path *tmp_name;
1784	u64 tmp_dir;
1785
1786	tmp_name = fs_path_alloc();
1787	if (!tmp_name)
1788		return -ENOMEM;
1789
1790	ret = get_first_ref(root, ino, &tmp_dir, NULL, tmp_name);
1791	if (ret < 0)
1792		goto out;
1793
1794	if (dir != tmp_dir || name_len != fs_path_len(tmp_name)) {
1795		ret = 0;
1796		goto out;
1797	}
1798
1799	ret = !memcmp(tmp_name->start, name, name_len);
1800
1801out:
1802	fs_path_free(tmp_name);
1803	return ret;
1804}
1805
1806/*
1807 * Used by process_recorded_refs to determine if a new ref would overwrite an
1808 * already existing ref. In case it detects an overwrite, it returns the
1809 * inode/gen in who_ino/who_gen.
1810 * When an overwrite is detected, process_recorded_refs does proper orphanizing
1811 * to make sure later references to the overwritten inode are possible.
1812 * Orphanizing is however only required for the first ref of an inode.
1813 * process_recorded_refs does an additional is_first_ref check to see if
1814 * orphanizing is really required.
1815 */
1816static int will_overwrite_ref(struct send_ctx *sctx, u64 dir, u64 dir_gen,
1817			      const char *name, int name_len,
1818			      u64 *who_ino, u64 *who_gen)
1819{
1820	int ret = 0;
1821	u64 gen;
1822	u64 other_inode = 0;
1823	u8 other_type = 0;
1824
1825	if (!sctx->parent_root)
1826		goto out;
1827
1828	ret = is_inode_existent(sctx, dir, dir_gen);
1829	if (ret <= 0)
1830		goto out;
1831
1832	/*
1833	 * If we have a parent root we need to verify that the parent dir was
1834	 * not delted and then re-created, if it was then we have no overwrite
1835	 * and we can just unlink this entry.
1836	 */
1837	if (sctx->parent_root) {
1838		ret = get_inode_info(sctx->parent_root, dir, NULL, &gen, NULL,
1839				     NULL, NULL, NULL);
1840		if (ret < 0 && ret != -ENOENT)
1841			goto out;
1842		if (ret) {
1843			ret = 0;
1844			goto out;
1845		}
1846		if (gen != dir_gen)
1847			goto out;
1848	}
1849
1850	ret = lookup_dir_item_inode(sctx->parent_root, dir, name, name_len,
1851			&other_inode, &other_type);
1852	if (ret < 0 && ret != -ENOENT)
1853		goto out;
1854	if (ret) {
1855		ret = 0;
1856		goto out;
1857	}
1858
1859	/*
1860	 * Check if the overwritten ref was already processed. If yes, the ref
1861	 * was already unlinked/moved, so we can safely assume that we will not
1862	 * overwrite anything at this point in time.
1863	 */
1864	if (other_inode > sctx->send_progress) {
1865		ret = get_inode_info(sctx->parent_root, other_inode, NULL,
1866				who_gen, NULL, NULL, NULL, NULL);
1867		if (ret < 0)
1868			goto out;
1869
1870		ret = 1;
1871		*who_ino = other_inode;
1872	} else {
1873		ret = 0;
1874	}
1875
1876out:
1877	return ret;
1878}
1879
1880/*
1881 * Checks if the ref was overwritten by an already processed inode. This is
1882 * used by __get_cur_name_and_parent to find out if the ref was orphanized and
1883 * thus the orphan name needs be used.
1884 * process_recorded_refs also uses it to avoid unlinking of refs that were
1885 * overwritten.
1886 */
1887static int did_overwrite_ref(struct send_ctx *sctx,
1888			    u64 dir, u64 dir_gen,
1889			    u64 ino, u64 ino_gen,
1890			    const char *name, int name_len)
1891{
1892	int ret = 0;
1893	u64 gen;
1894	u64 ow_inode;
1895	u8 other_type;
1896
1897	if (!sctx->parent_root)
1898		goto out;
1899
1900	ret = is_inode_existent(sctx, dir, dir_gen);
1901	if (ret <= 0)
1902		goto out;
1903
1904	/* check if the ref was overwritten by another ref */
1905	ret = lookup_dir_item_inode(sctx->send_root, dir, name, name_len,
1906			&ow_inode, &other_type);
1907	if (ret < 0 && ret != -ENOENT)
1908		goto out;
1909	if (ret) {
1910		/* was never and will never be overwritten */
1911		ret = 0;
1912		goto out;
1913	}
1914
1915	ret = get_inode_info(sctx->send_root, ow_inode, NULL, &gen, NULL, NULL,
1916			NULL, NULL);
1917	if (ret < 0)
1918		goto out;
1919
1920	if (ow_inode == ino && gen == ino_gen) {
1921		ret = 0;
1922		goto out;
1923	}
1924
1925	/*
1926	 * We know that it is or will be overwritten. Check this now.
1927	 * The current inode being processed might have been the one that caused
1928	 * inode 'ino' to be orphanized, therefore check if ow_inode matches
1929	 * the current inode being processed.
1930	 */
1931	if ((ow_inode < sctx->send_progress) ||
1932	    (ino != sctx->cur_ino && ow_inode == sctx->cur_ino &&
1933	     gen == sctx->cur_inode_gen))
1934		ret = 1;
1935	else
1936		ret = 0;
1937
1938out:
1939	return ret;
1940}
1941
1942/*
1943 * Same as did_overwrite_ref, but also checks if it is the first ref of an inode
1944 * that got overwritten. This is used by process_recorded_refs to determine
1945 * if it has to use the path as returned by get_cur_path or the orphan name.
1946 */
1947static int did_overwrite_first_ref(struct send_ctx *sctx, u64 ino, u64 gen)
1948{
1949	int ret = 0;
1950	struct fs_path *name = NULL;
1951	u64 dir;
1952	u64 dir_gen;
1953
1954	if (!sctx->parent_root)
1955		goto out;
1956
1957	name = fs_path_alloc();
1958	if (!name)
1959		return -ENOMEM;
1960
1961	ret = get_first_ref(sctx->parent_root, ino, &dir, &dir_gen, name);
1962	if (ret < 0)
1963		goto out;
1964
1965	ret = did_overwrite_ref(sctx, dir, dir_gen, ino, gen,
1966			name->start, fs_path_len(name));
1967
1968out:
1969	fs_path_free(name);
1970	return ret;
1971}
1972
1973/*
1974 * Insert a name cache entry. On 32bit kernels the radix tree index is 32bit,
1975 * so we need to do some special handling in case we have clashes. This function
1976 * takes care of this with the help of name_cache_entry::radix_list.
1977 * In case of error, nce is kfreed.
1978 */
1979static int name_cache_insert(struct send_ctx *sctx,
1980			     struct name_cache_entry *nce)
1981{
1982	int ret = 0;
1983	struct list_head *nce_head;
1984
1985	nce_head = radix_tree_lookup(&sctx->name_cache,
1986			(unsigned long)nce->ino);
1987	if (!nce_head) {
1988		nce_head = kmalloc(sizeof(*nce_head), GFP_KERNEL);
1989		if (!nce_head) {
1990			kfree(nce);
1991			return -ENOMEM;
1992		}
1993		INIT_LIST_HEAD(nce_head);
1994
1995		ret = radix_tree_insert(&sctx->name_cache, nce->ino, nce_head);
1996		if (ret < 0) {
1997			kfree(nce_head);
1998			kfree(nce);
1999			return ret;
2000		}
2001	}
2002	list_add_tail(&nce->radix_list, nce_head);
2003	list_add_tail(&nce->list, &sctx->name_cache_list);
2004	sctx->name_cache_size++;
2005
2006	return ret;
2007}
2008
2009static void name_cache_delete(struct send_ctx *sctx,
2010			      struct name_cache_entry *nce)
2011{
2012	struct list_head *nce_head;
2013
2014	nce_head = radix_tree_lookup(&sctx->name_cache,
2015			(unsigned long)nce->ino);
2016	if (!nce_head) {
2017		btrfs_err(sctx->send_root->fs_info,
2018	      "name_cache_delete lookup failed ino %llu cache size %d, leaking memory",
2019			nce->ino, sctx->name_cache_size);
2020	}
2021
2022	list_del(&nce->radix_list);
2023	list_del(&nce->list);
2024	sctx->name_cache_size--;
2025
2026	/*
2027	 * We may not get to the final release of nce_head if the lookup fails
2028	 */
2029	if (nce_head && list_empty(nce_head)) {
2030		radix_tree_delete(&sctx->name_cache, (unsigned long)nce->ino);
2031		kfree(nce_head);
2032	}
2033}
2034
2035static struct name_cache_entry *name_cache_search(struct send_ctx *sctx,
2036						    u64 ino, u64 gen)
2037{
2038	struct list_head *nce_head;
2039	struct name_cache_entry *cur;
2040
2041	nce_head = radix_tree_lookup(&sctx->name_cache, (unsigned long)ino);
2042	if (!nce_head)
2043		return NULL;
2044
2045	list_for_each_entry(cur, nce_head, radix_list) {
2046		if (cur->ino == ino && cur->gen == gen)
2047			return cur;
2048	}
2049	return NULL;
2050}
2051
2052/*
2053 * Removes the entry from the list and adds it back to the end. This marks the
2054 * entry as recently used so that name_cache_clean_unused does not remove it.
2055 */
2056static void name_cache_used(struct send_ctx *sctx, struct name_cache_entry *nce)
2057{
2058	list_del(&nce->list);
2059	list_add_tail(&nce->list, &sctx->name_cache_list);
2060}
2061
2062/*
2063 * Remove some entries from the beginning of name_cache_list.
2064 */
2065static void name_cache_clean_unused(struct send_ctx *sctx)
2066{
2067	struct name_cache_entry *nce;
2068
2069	if (sctx->name_cache_size < SEND_CTX_NAME_CACHE_CLEAN_SIZE)
2070		return;
2071
2072	while (sctx->name_cache_size > SEND_CTX_MAX_NAME_CACHE_SIZE) {
2073		nce = list_entry(sctx->name_cache_list.next,
2074				struct name_cache_entry, list);
2075		name_cache_delete(sctx, nce);
2076		kfree(nce);
2077	}
2078}
2079
2080static void name_cache_free(struct send_ctx *sctx)
2081{
2082	struct name_cache_entry *nce;
2083
2084	while (!list_empty(&sctx->name_cache_list)) {
2085		nce = list_entry(sctx->name_cache_list.next,
2086				struct name_cache_entry, list);
2087		name_cache_delete(sctx, nce);
2088		kfree(nce);
2089	}
2090}
2091
2092/*
2093 * Used by get_cur_path for each ref up to the root.
2094 * Returns 0 if it succeeded.
2095 * Returns 1 if the inode is not existent or got overwritten. In that case, the
2096 * name is an orphan name. This instructs get_cur_path to stop iterating. If 1
2097 * is returned, parent_ino/parent_gen are not guaranteed to be valid.
2098 * Returns <0 in case of error.
2099 */
2100static int __get_cur_name_and_parent(struct send_ctx *sctx,
2101				     u64 ino, u64 gen,
2102				     u64 *parent_ino,
2103				     u64 *parent_gen,
2104				     struct fs_path *dest)
2105{
2106	int ret;
2107	int nce_ret;
2108	struct name_cache_entry *nce = NULL;
2109
2110	/*
2111	 * First check if we already did a call to this function with the same
2112	 * ino/gen. If yes, check if the cache entry is still up-to-date. If yes
2113	 * return the cached result.
2114	 */
2115	nce = name_cache_search(sctx, ino, gen);
2116	if (nce) {
2117		if (ino < sctx->send_progress && nce->need_later_update) {
2118			name_cache_delete(sctx, nce);
2119			kfree(nce);
2120			nce = NULL;
2121		} else {
2122			name_cache_used(sctx, nce);
2123			*parent_ino = nce->parent_ino;
2124			*parent_gen = nce->parent_gen;
2125			ret = fs_path_add(dest, nce->name, nce->name_len);
2126			if (ret < 0)
2127				goto out;
2128			ret = nce->ret;
2129			goto out;
2130		}
2131	}
2132
2133	/*
2134	 * If the inode is not existent yet, add the orphan name and return 1.
2135	 * This should only happen for the parent dir that we determine in
2136	 * __record_new_ref
2137	 */
2138	ret = is_inode_existent(sctx, ino, gen);
2139	if (ret < 0)
2140		goto out;
2141
2142	if (!ret) {
2143		ret = gen_unique_name(sctx, ino, gen, dest);
2144		if (ret < 0)
2145			goto out;
2146		ret = 1;
2147		goto out_cache;
2148	}
2149
2150	/*
2151	 * Depending on whether the inode was already processed or not, use
2152	 * send_root or parent_root for ref lookup.
2153	 */
2154	if (ino < sctx->send_progress)
2155		ret = get_first_ref(sctx->send_root, ino,
2156				    parent_ino, parent_gen, dest);
2157	else
2158		ret = get_first_ref(sctx->parent_root, ino,
2159				    parent_ino, parent_gen, dest);
2160	if (ret < 0)
2161		goto out;
2162
2163	/*
2164	 * Check if the ref was overwritten by an inode's ref that was processed
2165	 * earlier. If yes, treat as orphan and return 1.
2166	 */
2167	ret = did_overwrite_ref(sctx, *parent_ino, *parent_gen, ino, gen,
2168			dest->start, dest->end - dest->start);
2169	if (ret < 0)
2170		goto out;
2171	if (ret) {
2172		fs_path_reset(dest);
2173		ret = gen_unique_name(sctx, ino, gen, dest);
2174		if (ret < 0)
2175			goto out;
2176		ret = 1;
2177	}
2178
2179out_cache:
2180	/*
2181	 * Store the result of the lookup in the name cache.
2182	 */
2183	nce = kmalloc(sizeof(*nce) + fs_path_len(dest) + 1, GFP_KERNEL);
2184	if (!nce) {
2185		ret = -ENOMEM;
2186		goto out;
2187	}
2188
2189	nce->ino = ino;
2190	nce->gen = gen;
2191	nce->parent_ino = *parent_ino;
2192	nce->parent_gen = *parent_gen;
2193	nce->name_len = fs_path_len(dest);
2194	nce->ret = ret;
2195	strcpy(nce->name, dest->start);
2196
2197	if (ino < sctx->send_progress)
2198		nce->need_later_update = 0;
2199	else
2200		nce->need_later_update = 1;
2201
2202	nce_ret = name_cache_insert(sctx, nce);
2203	if (nce_ret < 0)
2204		ret = nce_ret;
2205	name_cache_clean_unused(sctx);
2206
2207out:
2208	return ret;
2209}
2210
2211/*
2212 * Magic happens here. This function returns the first ref to an inode as it
2213 * would look like while receiving the stream at this point in time.
2214 * We walk the path up to the root. For every inode in between, we check if it
2215 * was already processed/sent. If yes, we continue with the parent as found
2216 * in send_root. If not, we continue with the parent as found in parent_root.
2217 * If we encounter an inode that was deleted at this point in time, we use the
2218 * inodes "orphan" name instead of the real name and stop. Same with new inodes
2219 * that were not created yet and overwritten inodes/refs.
2220 *
2221 * When do we have have orphan inodes:
2222 * 1. When an inode is freshly created and thus no valid refs are available yet
2223 * 2. When a directory lost all it's refs (deleted) but still has dir items
2224 *    inside which were not processed yet (pending for move/delete). If anyone
2225 *    tried to get the path to the dir items, it would get a path inside that
2226 *    orphan directory.
2227 * 3. When an inode is moved around or gets new links, it may overwrite the ref
2228 *    of an unprocessed inode. If in that case the first ref would be
2229 *    overwritten, the overwritten inode gets "orphanized". Later when we
2230 *    process this overwritten inode, it is restored at a new place by moving
2231 *    the orphan inode.
2232 *
2233 * sctx->send_progress tells this function at which point in time receiving
2234 * would be.
2235 */
2236static int get_cur_path(struct send_ctx *sctx, u64 ino, u64 gen,
2237			struct fs_path *dest)
2238{
2239	int ret = 0;
2240	struct fs_path *name = NULL;
2241	u64 parent_inode = 0;
2242	u64 parent_gen = 0;
2243	int stop = 0;
2244
2245	name = fs_path_alloc();
2246	if (!name) {
2247		ret = -ENOMEM;
2248		goto out;
2249	}
2250
2251	dest->reversed = 1;
2252	fs_path_reset(dest);
2253
2254	while (!stop && ino != BTRFS_FIRST_FREE_OBJECTID) {
2255		struct waiting_dir_move *wdm;
2256
2257		fs_path_reset(name);
2258
2259		if (is_waiting_for_rm(sctx, ino)) {
2260			ret = gen_unique_name(sctx, ino, gen, name);
2261			if (ret < 0)
2262				goto out;
2263			ret = fs_path_add_path(dest, name);
2264			break;
2265		}
2266
2267		wdm = get_waiting_dir_move(sctx, ino);
2268		if (wdm && wdm->orphanized) {
2269			ret = gen_unique_name(sctx, ino, gen, name);
2270			stop = 1;
2271		} else if (wdm) {
2272			ret = get_first_ref(sctx->parent_root, ino,
2273					    &parent_inode, &parent_gen, name);
2274		} else {
2275			ret = __get_cur_name_and_parent(sctx, ino, gen,
2276							&parent_inode,
2277							&parent_gen, name);
2278			if (ret)
2279				stop = 1;
2280		}
2281
2282		if (ret < 0)
2283			goto out;
2284
2285		ret = fs_path_add_path(dest, name);
2286		if (ret < 0)
2287			goto out;
2288
2289		ino = parent_inode;
2290		gen = parent_gen;
2291	}
2292
2293out:
2294	fs_path_free(name);
2295	if (!ret)
2296		fs_path_unreverse(dest);
2297	return ret;
2298}
2299
2300/*
2301 * Sends a BTRFS_SEND_C_SUBVOL command/item to userspace
2302 */
2303static int send_subvol_begin(struct send_ctx *sctx)
2304{
2305	int ret;
2306	struct btrfs_root *send_root = sctx->send_root;
2307	struct btrfs_root *parent_root = sctx->parent_root;
2308	struct btrfs_path *path;
2309	struct btrfs_key key;
2310	struct btrfs_root_ref *ref;
2311	struct extent_buffer *leaf;
2312	char *name = NULL;
2313	int namelen;
2314
2315	path = btrfs_alloc_path();
2316	if (!path)
2317		return -ENOMEM;
2318
2319	name = kmalloc(BTRFS_PATH_NAME_MAX, GFP_KERNEL);
2320	if (!name) {
2321		btrfs_free_path(path);
2322		return -ENOMEM;
2323	}
2324
2325	key.objectid = send_root->objectid;
2326	key.type = BTRFS_ROOT_BACKREF_KEY;
2327	key.offset = 0;
2328
2329	ret = btrfs_search_slot_for_read(send_root->fs_info->tree_root,
2330				&key, path, 1, 0);
2331	if (ret < 0)
2332		goto out;
2333	if (ret) {
2334		ret = -ENOENT;
2335		goto out;
2336	}
2337
2338	leaf = path->nodes[0];
2339	btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
2340	if (key.type != BTRFS_ROOT_BACKREF_KEY ||
2341	    key.objectid != send_root->objectid) {
2342		ret = -ENOENT;
2343		goto out;
2344	}
2345	ref = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_root_ref);
2346	namelen = btrfs_root_ref_name_len(leaf, ref);
2347	read_extent_buffer(leaf, name, (unsigned long)(ref + 1), namelen);
2348	btrfs_release_path(path);
2349
2350	if (parent_root) {
2351		ret = begin_cmd(sctx, BTRFS_SEND_C_SNAPSHOT);
2352		if (ret < 0)
2353			goto out;
2354	} else {
2355		ret = begin_cmd(sctx, BTRFS_SEND_C_SUBVOL);
2356		if (ret < 0)
2357			goto out;
2358	}
2359
2360	TLV_PUT_STRING(sctx, BTRFS_SEND_A_PATH, name, namelen);
2361
2362	if (!btrfs_is_empty_uuid(sctx->send_root->root_item.received_uuid))
2363		TLV_PUT_UUID(sctx, BTRFS_SEND_A_UUID,
2364			    sctx->send_root->root_item.received_uuid);
2365	else
2366		TLV_PUT_UUID(sctx, BTRFS_SEND_A_UUID,
2367			    sctx->send_root->root_item.uuid);
2368
2369	TLV_PUT_U64(sctx, BTRFS_SEND_A_CTRANSID,
2370		    le64_to_cpu(sctx->send_root->root_item.ctransid));
2371	if (parent_root) {
2372		if (!btrfs_is_empty_uuid(parent_root->root_item.received_uuid))
2373			TLV_PUT_UUID(sctx, BTRFS_SEND_A_CLONE_UUID,
2374				     parent_root->root_item.received_uuid);
2375		else
2376			TLV_PUT_UUID(sctx, BTRFS_SEND_A_CLONE_UUID,
2377				     parent_root->root_item.uuid);
2378		TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_CTRANSID,
2379			    le64_to_cpu(sctx->parent_root->root_item.ctransid));
2380	}
2381
2382	ret = send_cmd(sctx);
2383
2384tlv_put_failure:
2385out:
2386	btrfs_free_path(path);
2387	kfree(name);
2388	return ret;
2389}
2390
2391static int send_truncate(struct send_ctx *sctx, u64 ino, u64 gen, u64 size)
2392{
2393	int ret = 0;
2394	struct fs_path *p;
2395
2396verbose_printk("btrfs: send_truncate %llu size=%llu\n", ino, size);
2397
2398	p = fs_path_alloc();
2399	if (!p)
2400		return -ENOMEM;
2401
2402	ret = begin_cmd(sctx, BTRFS_SEND_C_TRUNCATE);
2403	if (ret < 0)
2404		goto out;
2405
2406	ret = get_cur_path(sctx, ino, gen, p);
2407	if (ret < 0)
2408		goto out;
2409	TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
2410	TLV_PUT_U64(sctx, BTRFS_SEND_A_SIZE, size);
2411
2412	ret = send_cmd(sctx);
2413
2414tlv_put_failure:
2415out:
2416	fs_path_free(p);
2417	return ret;
2418}
2419
2420static int send_chmod(struct send_ctx *sctx, u64 ino, u64 gen, u64 mode)
2421{
2422	int ret = 0;
2423	struct fs_path *p;
2424
2425verbose_printk("btrfs: send_chmod %llu mode=%llu\n", ino, mode);
2426
2427	p = fs_path_alloc();
2428	if (!p)
2429		return -ENOMEM;
2430
2431	ret = begin_cmd(sctx, BTRFS_SEND_C_CHMOD);
2432	if (ret < 0)
2433		goto out;
2434
2435	ret = get_cur_path(sctx, ino, gen, p);
2436	if (ret < 0)
2437		goto out;
2438	TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
2439	TLV_PUT_U64(sctx, BTRFS_SEND_A_MODE, mode & 07777);
2440
2441	ret = send_cmd(sctx);
2442
2443tlv_put_failure:
2444out:
2445	fs_path_free(p);
2446	return ret;
2447}
2448
2449static int send_chown(struct send_ctx *sctx, u64 ino, u64 gen, u64 uid, u64 gid)
2450{
2451	int ret = 0;
2452	struct fs_path *p;
2453
2454verbose_printk("btrfs: send_chown %llu uid=%llu, gid=%llu\n", ino, uid, gid);
2455
2456	p = fs_path_alloc();
2457	if (!p)
2458		return -ENOMEM;
2459
2460	ret = begin_cmd(sctx, BTRFS_SEND_C_CHOWN);
2461	if (ret < 0)
2462		goto out;
2463
2464	ret = get_cur_path(sctx, ino, gen, p);
2465	if (ret < 0)
2466		goto out;
2467	TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
2468	TLV_PUT_U64(sctx, BTRFS_SEND_A_UID, uid);
2469	TLV_PUT_U64(sctx, BTRFS_SEND_A_GID, gid);
2470
2471	ret = send_cmd(sctx);
2472
2473tlv_put_failure:
2474out:
2475	fs_path_free(p);
2476	return ret;
2477}
2478
2479static int send_utimes(struct send_ctx *sctx, u64 ino, u64 gen)
2480{
2481	int ret = 0;
2482	struct fs_path *p = NULL;
2483	struct btrfs_inode_item *ii;
2484	struct btrfs_path *path = NULL;
2485	struct extent_buffer *eb;
2486	struct btrfs_key key;
2487	int slot;
2488
2489verbose_printk("btrfs: send_utimes %llu\n", ino);
2490
2491	p = fs_path_alloc();
2492	if (!p)
2493		return -ENOMEM;
2494
2495	path = alloc_path_for_send();
2496	if (!path) {
2497		ret = -ENOMEM;
2498		goto out;
2499	}
2500
2501	key.objectid = ino;
2502	key.type = BTRFS_INODE_ITEM_KEY;
2503	key.offset = 0;
2504	ret = btrfs_search_slot(NULL, sctx->send_root, &key, path, 0, 0);
2505	if (ret < 0)
2506		goto out;
2507
2508	eb = path->nodes[0];
2509	slot = path->slots[0];
2510	ii = btrfs_item_ptr(eb, slot, struct btrfs_inode_item);
2511
2512	ret = begin_cmd(sctx, BTRFS_SEND_C_UTIMES);
2513	if (ret < 0)
2514		goto out;
2515
2516	ret = get_cur_path(sctx, ino, gen, p);
2517	if (ret < 0)
2518		goto out;
2519	TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
2520	TLV_PUT_BTRFS_TIMESPEC(sctx, BTRFS_SEND_A_ATIME, eb, &ii->atime);
2521	TLV_PUT_BTRFS_TIMESPEC(sctx, BTRFS_SEND_A_MTIME, eb, &ii->mtime);
2522	TLV_PUT_BTRFS_TIMESPEC(sctx, BTRFS_SEND_A_CTIME, eb, &ii->ctime);
2523	/* TODO Add otime support when the otime patches get into upstream */
2524
2525	ret = send_cmd(sctx);
2526
2527tlv_put_failure:
2528out:
2529	fs_path_free(p);
2530	btrfs_free_path(path);
2531	return ret;
2532}
2533
2534/*
2535 * Sends a BTRFS_SEND_C_MKXXX or SYMLINK command to user space. We don't have
2536 * a valid path yet because we did not process the refs yet. So, the inode
2537 * is created as orphan.
2538 */
2539static int send_create_inode(struct send_ctx *sctx, u64 ino)
2540{
2541	int ret = 0;
2542	struct fs_path *p;
2543	int cmd;
2544	u64 gen;
2545	u64 mode;
2546	u64 rdev;
2547
2548verbose_printk("btrfs: send_create_inode %llu\n", ino);
2549
2550	p = fs_path_alloc();
2551	if (!p)
2552		return -ENOMEM;
2553
2554	if (ino != sctx->cur_ino) {
2555		ret = get_inode_info(sctx->send_root, ino, NULL, &gen, &mode,
2556				     NULL, NULL, &rdev);
2557		if (ret < 0)
2558			goto out;
2559	} else {
2560		gen = sctx->cur_inode_gen;
2561		mode = sctx->cur_inode_mode;
2562		rdev = sctx->cur_inode_rdev;
2563	}
2564
2565	if (S_ISREG(mode)) {
2566		cmd = BTRFS_SEND_C_MKFILE;
2567	} else if (S_ISDIR(mode)) {
2568		cmd = BTRFS_SEND_C_MKDIR;
2569	} else if (S_ISLNK(mode)) {
2570		cmd = BTRFS_SEND_C_SYMLINK;
2571	} else if (S_ISCHR(mode) || S_ISBLK(mode)) {
2572		cmd = BTRFS_SEND_C_MKNOD;
2573	} else if (S_ISFIFO(mode)) {
2574		cmd = BTRFS_SEND_C_MKFIFO;
2575	} else if (S_ISSOCK(mode)) {
2576		cmd = BTRFS_SEND_C_MKSOCK;
2577	} else {
2578		btrfs_warn(sctx->send_root->fs_info, "unexpected inode type %o",
2579				(int)(mode & S_IFMT));
2580		ret = -ENOTSUPP;
2581		goto out;
2582	}
2583
2584	ret = begin_cmd(sctx, cmd);
2585	if (ret < 0)
2586		goto out;
2587
2588	ret = gen_unique_name(sctx, ino, gen, p);
2589	if (ret < 0)
2590		goto out;
2591
2592	TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
2593	TLV_PUT_U64(sctx, BTRFS_SEND_A_INO, ino);
2594
2595	if (S_ISLNK(mode)) {
2596		fs_path_reset(p);
2597		ret = read_symlink(sctx->send_root, ino, p);
2598		if (ret < 0)
2599			goto out;
2600		TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH_LINK, p);
2601	} else if (S_ISCHR(mode) || S_ISBLK(mode) ||
2602		   S_ISFIFO(mode) || S_ISSOCK(mode)) {
2603		TLV_PUT_U64(sctx, BTRFS_SEND_A_RDEV, new_encode_dev(rdev));
2604		TLV_PUT_U64(sctx, BTRFS_SEND_A_MODE, mode);
2605	}
2606
2607	ret = send_cmd(sctx);
2608	if (ret < 0)
2609		goto out;
2610
2611
2612tlv_put_failure:
2613out:
2614	fs_path_free(p);
2615	return ret;
2616}
2617
2618/*
2619 * We need some special handling for inodes that get processed before the parent
2620 * directory got created. See process_recorded_refs for details.
2621 * This function does the check if we already created the dir out of order.
2622 */
2623static int did_create_dir(struct send_ctx *sctx, u64 dir)
2624{
2625	int ret = 0;
2626	struct btrfs_path *path = NULL;
2627	struct btrfs_key key;
2628	struct btrfs_key found_key;
2629	struct btrfs_key di_key;
2630	struct extent_buffer *eb;
2631	struct btrfs_dir_item *di;
2632	int slot;
2633
2634	path = alloc_path_for_send();
2635	if (!path) {
2636		ret = -ENOMEM;
2637		goto out;
2638	}
2639
2640	key.objectid = dir;
2641	key.type = BTRFS_DIR_INDEX_KEY;
2642	key.offset = 0;
2643	ret = btrfs_search_slot(NULL, sctx->send_root, &key, path, 0, 0);
2644	if (ret < 0)
2645		goto out;
2646
2647	while (1) {
2648		eb = path->nodes[0];
2649		slot = path->slots[0];
2650		if (slot >= btrfs_header_nritems(eb)) {
2651			ret = btrfs_next_leaf(sctx->send_root, path);
2652			if (ret < 0) {
2653				goto out;
2654			} else if (ret > 0) {
2655				ret = 0;
2656				break;
2657			}
2658			continue;
2659		}
2660
2661		btrfs_item_key_to_cpu(eb, &found_key, slot);
2662		if (found_key.objectid != key.objectid ||
2663		    found_key.type != key.type) {
2664			ret = 0;
2665			goto out;
2666		}
2667
2668		di = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);
2669		btrfs_dir_item_key_to_cpu(eb, di, &di_key);
2670
2671		if (di_key.type != BTRFS_ROOT_ITEM_KEY &&
2672		    di_key.objectid < sctx->send_progress) {
2673			ret = 1;
2674			goto out;
2675		}
2676
2677		path->slots[0]++;
2678	}
2679
2680out:
2681	btrfs_free_path(path);
2682	return ret;
2683}
2684
2685/*
2686 * Only creates the inode if it is:
2687 * 1. Not a directory
2688 * 2. Or a directory which was not created already due to out of order
2689 *    directories. See did_create_dir and process_recorded_refs for details.
2690 */
2691static int send_create_inode_if_needed(struct send_ctx *sctx)
2692{
2693	int ret;
2694
2695	if (S_ISDIR(sctx->cur_inode_mode)) {
2696		ret = did_create_dir(sctx, sctx->cur_ino);
2697		if (ret < 0)
2698			goto out;
2699		if (ret) {
2700			ret = 0;
2701			goto out;
2702		}
2703	}
2704
2705	ret = send_create_inode(sctx, sctx->cur_ino);
2706	if (ret < 0)
2707		goto out;
2708
2709out:
2710	return ret;
2711}
2712
2713struct recorded_ref {
2714	struct list_head list;
2715	char *dir_path;
2716	char *name;
2717	struct fs_path *full_path;
2718	u64 dir;
2719	u64 dir_gen;
2720	int dir_path_len;
2721	int name_len;
2722};
2723
2724/*
2725 * We need to process new refs before deleted refs, but compare_tree gives us
2726 * everything mixed. So we first record all refs and later process them.
2727 * This function is a helper to record one ref.
2728 */
2729static int __record_ref(struct list_head *head, u64 dir,
2730		      u64 dir_gen, struct fs_path *path)
2731{
2732	struct recorded_ref *ref;
2733
2734	ref = kmalloc(sizeof(*ref), GFP_KERNEL);
2735	if (!ref)
2736		return -ENOMEM;
2737
2738	ref->dir = dir;
2739	ref->dir_gen = dir_gen;
2740	ref->full_path = path;
2741
2742	ref->name = (char *)kbasename(ref->full_path->start);
2743	ref->name_len = ref->full_path->end - ref->name;
2744	ref->dir_path = ref->full_path->start;
2745	if (ref->name == ref->full_path->start)
2746		ref->dir_path_len = 0;
2747	else
2748		ref->dir_path_len = ref->full_path->end -
2749				ref->full_path->start - 1 - ref->name_len;
2750
2751	list_add_tail(&ref->list, head);
2752	return 0;
2753}
2754
2755static int dup_ref(struct recorded_ref *ref, struct list_head *list)
2756{
2757	struct recorded_ref *new;
2758
2759	new = kmalloc(sizeof(*ref), GFP_KERNEL);
2760	if (!new)
2761		return -ENOMEM;
2762
2763	new->dir = ref->dir;
2764	new->dir_gen = ref->dir_gen;
2765	new->full_path = NULL;
2766	INIT_LIST_HEAD(&new->list);
2767	list_add_tail(&new->list, list);
2768	return 0;
2769}
2770
2771static void __free_recorded_refs(struct list_head *head)
2772{
2773	struct recorded_ref *cur;
2774
2775	while (!list_empty(head)) {
2776		cur = list_entry(head->next, struct recorded_ref, list);
2777		fs_path_free(cur->full_path);
2778		list_del(&cur->list);
2779		kfree(cur);
2780	}
2781}
2782
2783static void free_recorded_refs(struct send_ctx *sctx)
2784{
2785	__free_recorded_refs(&sctx->new_refs);
2786	__free_recorded_refs(&sctx->deleted_refs);
2787}
2788
2789/*
2790 * Renames/moves a file/dir to its orphan name. Used when the first
2791 * ref of an unprocessed inode gets overwritten and for all non empty
2792 * directories.
2793 */
2794static int orphanize_inode(struct send_ctx *sctx, u64 ino, u64 gen,
2795			  struct fs_path *path)
2796{
2797	int ret;
2798	struct fs_path *orphan;
2799
2800	orphan = fs_path_alloc();
2801	if (!orphan)
2802		return -ENOMEM;
2803
2804	ret = gen_unique_name(sctx, ino, gen, orphan);
2805	if (ret < 0)
2806		goto out;
2807
2808	ret = send_rename(sctx, path, orphan);
2809
2810out:
2811	fs_path_free(orphan);
2812	return ret;
2813}
2814
2815static struct orphan_dir_info *
2816add_orphan_dir_info(struct send_ctx *sctx, u64 dir_ino)
2817{
2818	struct rb_node **p = &sctx->orphan_dirs.rb_node;
2819	struct rb_node *parent = NULL;
2820	struct orphan_dir_info *entry, *odi;
2821
2822	odi = kmalloc(sizeof(*odi), GFP_KERNEL);
2823	if (!odi)
2824		return ERR_PTR(-ENOMEM);
2825	odi->ino = dir_ino;
2826	odi->gen = 0;
2827
2828	while (*p) {
2829		parent = *p;
2830		entry = rb_entry(parent, struct orphan_dir_info, node);
2831		if (dir_ino < entry->ino) {
2832			p = &(*p)->rb_left;
2833		} else if (dir_ino > entry->ino) {
2834			p = &(*p)->rb_right;
2835		} else {
2836			kfree(odi);
2837			return entry;
2838		}
2839	}
2840
2841	rb_link_node(&odi->node, parent, p);
2842	rb_insert_color(&odi->node, &sctx->orphan_dirs);
2843	return odi;
2844}
2845
2846static struct orphan_dir_info *
2847get_orphan_dir_info(struct send_ctx *sctx, u64 dir_ino)
2848{
2849	struct rb_node *n = sctx->orphan_dirs.rb_node;
2850	struct orphan_dir_info *entry;
2851
2852	while (n) {
2853		entry = rb_entry(n, struct orphan_dir_info, node);
2854		if (dir_ino < entry->ino)
2855			n = n->rb_left;
2856		else if (dir_ino > entry->ino)
2857			n = n->rb_right;
2858		else
2859			return entry;
2860	}
2861	return NULL;
2862}
2863
2864static int is_waiting_for_rm(struct send_ctx *sctx, u64 dir_ino)
2865{
2866	struct orphan_dir_info *odi = get_orphan_dir_info(sctx, dir_ino);
2867
2868	return odi != NULL;
2869}
2870
2871static void free_orphan_dir_info(struct send_ctx *sctx,
2872				 struct orphan_dir_info *odi)
2873{
2874	if (!odi)
2875		return;
2876	rb_erase(&odi->node, &sctx->orphan_dirs);
2877	kfree(odi);
2878}
2879
2880/*
2881 * Returns 1 if a directory can be removed at this point in time.
2882 * We check this by iterating all dir items and checking if the inode behind
2883 * the dir item was already processed.
2884 */
2885static int can_rmdir(struct send_ctx *sctx, u64 dir, u64 dir_gen,
2886		     u64 send_progress)
2887{
2888	int ret = 0;
2889	struct btrfs_root *root = sctx->parent_root;
2890	struct btrfs_path *path;
2891	struct btrfs_key key;
2892	struct btrfs_key found_key;
2893	struct btrfs_key loc;
2894	struct btrfs_dir_item *di;
2895
2896	/*
2897	 * Don't try to rmdir the top/root subvolume dir.
2898	 */
2899	if (dir == BTRFS_FIRST_FREE_OBJECTID)
2900		return 0;
2901
2902	path = alloc_path_for_send();
2903	if (!path)
2904		return -ENOMEM;
2905
2906	key.objectid = dir;
2907	key.type = BTRFS_DIR_INDEX_KEY;
2908	key.offset = 0;
2909	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2910	if (ret < 0)
2911		goto out;
2912
2913	while (1) {
2914		struct waiting_dir_move *dm;
2915
2916		if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
2917			ret = btrfs_next_leaf(root, path);
2918			if (ret < 0)
2919				goto out;
2920			else if (ret > 0)
2921				break;
2922			continue;
2923		}
2924		btrfs_item_key_to_cpu(path->nodes[0], &found_key,
2925				      path->slots[0]);
2926		if (found_key.objectid != key.objectid ||
2927		    found_key.type != key.type)
2928			break;
2929
2930		di = btrfs_item_ptr(path->nodes[0], path->slots[0],
2931				struct btrfs_dir_item);
2932		btrfs_dir_item_key_to_cpu(path->nodes[0], di, &loc);
2933
2934		dm = get_waiting_dir_move(sctx, loc.objectid);
2935		if (dm) {
2936			struct orphan_dir_info *odi;
2937
2938			odi = add_orphan_dir_info(sctx, dir);
2939			if (IS_ERR(odi)) {
2940				ret = PTR_ERR(odi);
2941				goto out;
2942			}
2943			odi->gen = dir_gen;
2944			dm->rmdir_ino = dir;
2945			ret = 0;
2946			goto out;
2947		}
2948
2949		if (loc.objectid > send_progress) {
2950			ret = 0;
2951			goto out;
2952		}
2953
2954		path->slots[0]++;
2955	}
2956
2957	ret = 1;
2958
2959out:
2960	btrfs_free_path(path);
2961	return ret;
2962}
2963
2964static int is_waiting_for_move(struct send_ctx *sctx, u64 ino)
2965{
2966	struct waiting_dir_move *entry = get_waiting_dir_move(sctx, ino);
2967
2968	return entry != NULL;
2969}
2970
2971static int add_waiting_dir_move(struct send_ctx *sctx, u64 ino, bool orphanized)
2972{
2973	struct rb_node **p = &sctx->waiting_dir_moves.rb_node;
2974	struct rb_node *parent = NULL;
2975	struct waiting_dir_move *entry, *dm;
2976
2977	dm = kmalloc(sizeof(*dm), GFP_KERNEL);
2978	if (!dm)
2979		return -ENOMEM;
2980	dm->ino = ino;
2981	dm->rmdir_ino = 0;
2982	dm->orphanized = orphanized;
2983
2984	while (*p) {
2985		parent = *p;
2986		entry = rb_entry(parent, struct waiting_dir_move, node);
2987		if (ino < entry->ino) {
2988			p = &(*p)->rb_left;
2989		} else if (ino > entry->ino) {
2990			p = &(*p)->rb_right;
2991		} else {
2992			kfree(dm);
2993			return -EEXIST;
2994		}
2995	}
2996
2997	rb_link_node(&dm->node, parent, p);
2998	rb_insert_color(&dm->node, &sctx->waiting_dir_moves);
2999	return 0;
3000}
3001
3002static struct waiting_dir_move *
3003get_waiting_dir_move(struct send_ctx *sctx, u64 ino)
3004{
3005	struct rb_node *n = sctx->waiting_dir_moves.rb_node;
3006	struct waiting_dir_move *entry;
3007
3008	while (n) {
3009		entry = rb_entry(n, struct waiting_dir_move, node);
3010		if (ino < entry->ino)
3011			n = n->rb_left;
3012		else if (ino > entry->ino)
3013			n = n->rb_right;
3014		else
3015			return entry;
3016	}
3017	return NULL;
3018}
3019
3020static void free_waiting_dir_move(struct send_ctx *sctx,
3021				  struct waiting_dir_move *dm)
3022{
3023	if (!dm)
3024		return;
3025	rb_erase(&dm->node, &sctx->waiting_dir_moves);
3026	kfree(dm);
3027}
3028
3029static int add_pending_dir_move(struct send_ctx *sctx,
3030				u64 ino,
3031				u64 ino_gen,
3032				u64 parent_ino,
3033				struct list_head *new_refs,
3034				struct list_head *deleted_refs,
3035				const bool is_orphan)
3036{
3037	struct rb_node **p = &sctx->pending_dir_moves.rb_node;
3038	struct rb_node *parent = NULL;
3039	struct pending_dir_move *entry = NULL, *pm;
3040	struct recorded_ref *cur;
3041	int exists = 0;
3042	int ret;
3043
3044	pm = kmalloc(sizeof(*pm), GFP_KERNEL);
3045	if (!pm)
3046		return -ENOMEM;
3047	pm->parent_ino = parent_ino;
3048	pm->ino = ino;
3049	pm->gen = ino_gen;
3050	pm->is_orphan = is_orphan;
3051	INIT_LIST_HEAD(&pm->list);
3052	INIT_LIST_HEAD(&pm->update_refs);
3053	RB_CLEAR_NODE(&pm->node);
3054
3055	while (*p) {
3056		parent = *p;
3057		entry = rb_entry(parent, struct pending_dir_move, node);
3058		if (parent_ino < entry->parent_ino) {
3059			p = &(*p)->rb_left;
3060		} else if (parent_ino > entry->parent_ino) {
3061			p = &(*p)->rb_right;
3062		} else {
3063			exists = 1;
3064			break;
3065		}
3066	}
3067
3068	list_for_each_entry(cur, deleted_refs, list) {
3069		ret = dup_ref(cur, &pm->update_refs);
3070		if (ret < 0)
3071			goto out;
3072	}
3073	list_for_each_entry(cur, new_refs, list) {
3074		ret = dup_ref(cur, &pm->update_refs);
3075		if (ret < 0)
3076			goto out;
3077	}
3078
3079	ret = add_waiting_dir_move(sctx, pm->ino, is_orphan);
3080	if (ret)
3081		goto out;
3082
3083	if (exists) {
3084		list_add_tail(&pm->list, &entry->list);
3085	} else {
3086		rb_link_node(&pm->node, parent, p);
3087		rb_insert_color(&pm->node, &sctx->pending_dir_moves);
3088	}
3089	ret = 0;
3090out:
3091	if (ret) {
3092		__free_recorded_refs(&pm->update_refs);
3093		kfree(pm);
3094	}
3095	return ret;
3096}
3097
3098static struct pending_dir_move *get_pending_dir_moves(struct send_ctx *sctx,
3099						      u64 parent_ino)
3100{
3101	struct rb_node *n = sctx->pending_dir_moves.rb_node;
3102	struct pending_dir_move *entry;
3103
3104	while (n) {
3105		entry = rb_entry(n, struct pending_dir_move, node);
3106		if (parent_ino < entry->parent_ino)
3107			n = n->rb_left;
3108		else if (parent_ino > entry->parent_ino)
3109			n = n->rb_right;
3110		else
3111			return entry;
3112	}
3113	return NULL;
3114}
3115
3116static int apply_dir_move(struct send_ctx *sctx, struct pending_dir_move *pm)
3117{
3118	struct fs_path *from_path = NULL;
3119	struct fs_path *to_path = NULL;
3120	struct fs_path *name = NULL;
3121	u64 orig_progress = sctx->send_progress;
3122	struct recorded_ref *cur;
3123	u64 parent_ino, parent_gen;
3124	struct waiting_dir_move *dm = NULL;
3125	u64 rmdir_ino = 0;
3126	int ret;
3127
3128	name = fs_path_alloc();
3129	from_path = fs_path_alloc();
3130	if (!name || !from_path) {
3131		ret = -ENOMEM;
3132		goto out;
3133	}
3134
3135	dm = get_waiting_dir_move(sctx, pm->ino);
3136	ASSERT(dm);
3137	rmdir_ino = dm->rmdir_ino;
3138	free_waiting_dir_move(sctx, dm);
3139
3140	if (pm->is_orphan) {
3141		ret = gen_unique_name(sctx, pm->ino,
3142				      pm->gen, from_path);
3143	} else {
3144		ret = get_first_ref(sctx->parent_root, pm->ino,
3145				    &parent_ino, &parent_gen, name);
3146		if (ret < 0)
3147			goto out;
3148		ret = get_cur_path(sctx, parent_ino, parent_gen,
3149				   from_path);
3150		if (ret < 0)
3151			goto out;
3152		ret = fs_path_add_path(from_path, name);
3153	}
3154	if (ret < 0)
3155		goto out;
3156
3157	sctx->send_progress = sctx->cur_ino + 1;
3158	fs_path_reset(name);
3159	to_path = name;
3160	name = NULL;
3161	ret = get_cur_path(sctx, pm->ino, pm->gen, to_path);
3162	if (ret < 0)
3163		goto out;
3164
3165	ret = send_rename(sctx, from_path, to_path);
3166	if (ret < 0)
3167		goto out;
3168
3169	if (rmdir_ino) {
3170		struct orphan_dir_info *odi;
3171
3172		odi = get_orphan_dir_info(sctx, rmdir_ino);
3173		if (!odi) {
3174			/* already deleted */
3175			goto finish;
3176		}
3177		ret = can_rmdir(sctx, rmdir_ino, odi->gen, sctx->cur_ino + 1);
3178		if (ret < 0)
3179			goto out;
3180		if (!ret)
3181			goto finish;
3182
3183		name = fs_path_alloc();
3184		if (!name) {
3185			ret = -ENOMEM;
3186			goto out;
3187		}
3188		ret = get_cur_path(sctx, rmdir_ino, odi->gen, name);
3189		if (ret < 0)
3190			goto out;
3191		ret = send_rmdir(sctx, name);
3192		if (ret < 0)
3193			goto out;
3194		free_orphan_dir_info(sctx, odi);
3195	}
3196
3197finish:
3198	ret = send_utimes(sctx, pm->ino, pm->gen);
3199	if (ret < 0)
3200		goto out;
3201
3202	/*
3203	 * After rename/move, need to update the utimes of both new parent(s)
3204	 * and old parent(s).
3205	 */
3206	list_for_each_entry(cur, &pm->update_refs, list) {
3207		if (cur->dir == rmdir_ino)
3208			continue;
3209		ret = send_utimes(sctx, cur->dir, cur->dir_gen);
3210		if (ret < 0)
3211			goto out;
3212	}
3213
3214out:
3215	fs_path_free(name);
3216	fs_path_free(from_path);
3217	fs_path_free(to_path);
3218	sctx->send_progress = orig_progress;
3219
3220	return ret;
3221}
3222
3223static void free_pending_move(struct send_ctx *sctx, struct pending_dir_move *m)
3224{
3225	if (!list_empty(&m->list))
3226		list_del(&m->list);
3227	if (!RB_EMPTY_NODE(&m->node))
3228		rb_erase(&m->node, &sctx->pending_dir_moves);
3229	__free_recorded_refs(&m->update_refs);
3230	kfree(m);
3231}
3232
3233static void tail_append_pending_moves(struct pending_dir_move *moves,
3234				      struct list_head *stack)
3235{
3236	if (list_empty(&moves->list)) {
3237		list_add_tail(&moves->list, stack);
3238	} else {
3239		LIST_HEAD(list);
3240		list_splice_init(&moves->list, &list);
3241		list_add_tail(&moves->list, stack);
3242		list_splice_tail(&list, stack);
3243	}
3244}
3245
3246static int apply_children_dir_moves(struct send_ctx *sctx)
3247{
3248	struct pending_dir_move *pm;
3249	struct list_head stack;
3250	u64 parent_ino = sctx->cur_ino;
3251	int ret = 0;
3252
3253	pm = get_pending_dir_moves(sctx, parent_ino);
3254	if (!pm)
3255		return 0;
3256
3257	INIT_LIST_HEAD(&stack);
3258	tail_append_pending_moves(pm, &stack);
3259
3260	while (!list_empty(&stack)) {
3261		pm = list_first_entry(&stack, struct pending_dir_move, list);
3262		parent_ino = pm->ino;
3263		ret = apply_dir_move(sctx, pm);
3264		free_pending_move(sctx, pm);
3265		if (ret)
3266			goto out;
3267		pm = get_pending_dir_moves(sctx, parent_ino);
3268		if (pm)
3269			tail_append_pending_moves(pm, &stack);
3270	}
3271	return 0;
3272
3273out:
3274	while (!list_empty(&stack)) {
3275		pm = list_first_entry(&stack, struct pending_dir_move, list);
3276		free_pending_move(sctx, pm);
3277	}
3278	return ret;
3279}
3280
3281/*
3282 * We might need to delay a directory rename even when no ancestor directory
3283 * (in the send root) with a higher inode number than ours (sctx->cur_ino) was
3284 * renamed. This happens when we rename a directory to the old name (the name
3285 * in the parent root) of some other unrelated directory that got its rename
3286 * delayed due to some ancestor with higher number that got renamed.
3287 *
3288 * Example:
3289 *
3290 * Parent snapshot:
3291 * .                                       (ino 256)
3292 * |---- a/                                (ino 257)
3293 * |     |---- file                        (ino 260)
3294 * |
3295 * |---- b/                                (ino 258)
3296 * |---- c/                                (ino 259)
3297 *
3298 * Send snapshot:
3299 * .                                       (ino 256)
3300 * |---- a/                                (ino 258)
3301 * |---- x/                                (ino 259)
3302 *       |---- y/                          (ino 257)
3303 *             |----- file                 (ino 260)
3304 *
3305 * Here we can not rename 258 from 'b' to 'a' without the rename of inode 257
3306 * from 'a' to 'x/y' happening first, which in turn depends on the rename of
3307 * inode 259 from 'c' to 'x'. So the order of rename commands the send stream
3308 * must issue is:
3309 *
3310 * 1 - rename 259 from 'c' to 'x'
3311 * 2 - rename 257 from 'a' to 'x/y'
3312 * 3 - rename 258 from 'b' to 'a'
3313 *
3314 * Returns 1 if the rename of sctx->cur_ino needs to be delayed, 0 if it can
3315 * be done right away and < 0 on error.
3316 */
3317static int wait_for_dest_dir_move(struct send_ctx *sctx,
3318				  struct recorded_ref *parent_ref,
3319				  const bool is_orphan)
3320{
3321	struct btrfs_path *path;
3322	struct btrfs_key key;
3323	struct btrfs_key di_key;
3324	struct btrfs_dir_item *di;
3325	u64 left_gen;
3326	u64 right_gen;
3327	int ret = 0;
3328
3329	if (RB_EMPTY_ROOT(&sctx->waiting_dir_moves))
3330		return 0;
3331
3332	path = alloc_path_for_send();
3333	if (!path)
3334		return -ENOMEM;
3335
3336	key.objectid = parent_ref->dir;
3337	key.type = BTRFS_DIR_ITEM_KEY;
3338	key.offset = btrfs_name_hash(parent_ref->name, parent_ref->name_len);
3339
3340	ret = btrfs_search_slot(NULL, sctx->parent_root, &key, path, 0, 0);
3341	if (ret < 0) {
3342		goto out;
3343	} else if (ret > 0) {
3344		ret = 0;
3345		goto out;
3346	}
3347
3348	di = btrfs_match_dir_item_name(sctx->parent_root, path,
3349				       parent_ref->name, parent_ref->name_len);
3350	if (!di) {
3351		ret = 0;
3352		goto out;
3353	}
3354	/*
3355	 * di_key.objectid has the number of the inode that has a dentry in the
3356	 * parent directory with the same name that sctx->cur_ino is being
3357	 * renamed to. We need to check if that inode is in the send root as
3358	 * well and if it is currently marked as an inode with a pending rename,
3359	 * if it is, we need to delay the rename of sctx->cur_ino as well, so
3360	 * that it happens after that other inode is renamed.
3361	 */
3362	btrfs_dir_item_key_to_cpu(path->nodes[0], di, &di_key);
3363	if (di_key.type != BTRFS_INODE_ITEM_KEY) {
3364		ret = 0;
3365		goto out;
3366	}
3367
3368	ret = get_inode_info(sctx->parent_root, di_key.objectid, NULL,
3369			     &left_gen, NULL, NULL, NULL, NULL);
3370	if (ret < 0)
3371		goto out;
3372	ret = get_inode_info(sctx->send_root, di_key.objectid, NULL,
3373			     &right_gen, NULL, NULL, NULL, NULL);
3374	if (ret < 0) {
3375		if (ret == -ENOENT)
3376			ret = 0;
3377		goto out;
3378	}
3379
3380	/* Different inode, no need to delay the rename of sctx->cur_ino */
3381	if (right_gen != left_gen) {
3382		ret = 0;
3383		goto out;
3384	}
3385
3386	if (is_waiting_for_move(sctx, di_key.objectid)) {
3387		ret = add_pending_dir_move(sctx,
3388					   sctx->cur_ino,
3389					   sctx->cur_inode_gen,
3390					   di_key.objectid,
3391					   &sctx->new_refs,
3392					   &sctx->deleted_refs,
3393					   is_orphan);
3394		if (!ret)
3395			ret = 1;
3396	}
3397out:
3398	btrfs_free_path(path);
3399	return ret;
3400}
3401
3402/*
3403 * Check if ino ino1 is an ancestor of inode ino2 in the given root.
3404 * Return 1 if true, 0 if false and < 0 on error.
3405 */
3406static int is_ancestor(struct btrfs_root *root,
3407		       const u64 ino1,
3408		       const u64 ino1_gen,
3409		       const u64 ino2,
3410		       struct fs_path *fs_path)
3411{
3412	u64 ino = ino2;
3413
3414	while (ino > BTRFS_FIRST_FREE_OBJECTID) {
3415		int ret;
3416		u64 parent;
3417		u64 parent_gen;
3418
3419		fs_path_reset(fs_path);
3420		ret = get_first_ref(root, ino, &parent, &parent_gen, fs_path);
3421		if (ret < 0) {
3422			if (ret == -ENOENT && ino == ino2)
3423				ret = 0;
3424			return ret;
3425		}
3426		if (parent == ino1)
3427			return parent_gen == ino1_gen ? 1 : 0;
3428		ino = parent;
3429	}
3430	return 0;
3431}
3432
3433static int wait_for_parent_move(struct send_ctx *sctx,
3434				struct recorded_ref *parent_ref,
3435				const bool is_orphan)
3436{
3437	int ret = 0;
3438	u64 ino = parent_ref->dir;
3439	u64 parent_ino_before, parent_ino_after;
3440	struct fs_path *path_before = NULL;
3441	struct fs_path *path_after = NULL;
3442	int len1, len2;
3443
3444	path_after = fs_path_alloc();
3445	path_before = fs_path_alloc();
3446	if (!path_after || !path_before) {
3447		ret = -ENOMEM;
3448		goto out;
3449	}
3450
3451	/*
3452	 * Our current directory inode may not yet be renamed/moved because some
3453	 * ancestor (immediate or not) has to be renamed/moved first. So find if
3454	 * such ancestor exists and make sure our own rename/move happens after
3455	 * that ancestor is processed to avoid path build infinite loops (done
3456	 * at get_cur_path()).
3457	 */
3458	while (ino > BTRFS_FIRST_FREE_OBJECTID) {
3459		if (is_waiting_for_move(sctx, ino)) {
3460			/*
3461			 * If the current inode is an ancestor of ino in the
3462			 * parent root, we need to delay the rename of the
3463			 * current inode, otherwise don't delayed the rename
3464			 * because we can end up with a circular dependency
3465			 * of renames, resulting in some directories never
3466			 * getting the respective rename operations issued in
3467			 * the send stream or getting into infinite path build
3468			 * loops.
3469			 */
3470			ret = is_ancestor(sctx->parent_root,
3471					  sctx->cur_ino, sctx->cur_inode_gen,
3472					  ino, path_before);
3473			break;
3474		}
3475
3476		fs_path_reset(path_before);
3477		fs_path_reset(path_after);
3478
3479		ret = get_first_ref(sctx->send_root, ino, &parent_ino_after,
3480				    NULL, path_after);
3481		if (ret < 0)
3482			goto out;
3483		ret = get_first_ref(sctx->parent_root, ino, &parent_ino_before,
3484				    NULL, path_before);
3485		if (ret < 0 && ret != -ENOENT) {
3486			goto out;
3487		} else if (ret == -ENOENT) {
3488			ret = 0;
3489			break;
3490		}
3491
3492		len1 = fs_path_len(path_before);
3493		len2 = fs_path_len(path_after);
3494		if (ino > sctx->cur_ino &&
3495		    (parent_ino_before != parent_ino_after || len1 != len2 ||
3496		     memcmp(path_before->start, path_after->start, len1))) {
3497			ret = 1;
3498			break;
3499		}
3500		ino = parent_ino_after;
3501	}
3502
3503out:
3504	fs_path_free(path_before);
3505	fs_path_free(path_after);
3506
3507	if (ret == 1) {
3508		ret = add_pending_dir_move(sctx,
3509					   sctx->cur_ino,
3510					   sctx->cur_inode_gen,
3511					   ino,
3512					   &sctx->new_refs,
3513					   &sctx->deleted_refs,
3514					   is_orphan);
3515		if (!ret)
3516			ret = 1;
3517	}
3518
3519	return ret;
3520}
3521
3522/*
3523 * This does all the move/link/unlink/rmdir magic.
3524 */
3525static int process_recorded_refs(struct send_ctx *sctx, int *pending_move)
3526{
3527	int ret = 0;
3528	struct recorded_ref *cur;
3529	struct recorded_ref *cur2;
3530	struct list_head check_dirs;
3531	struct fs_path *valid_path = NULL;
3532	u64 ow_inode = 0;
3533	u64 ow_gen;
3534	int did_overwrite = 0;
3535	int is_orphan = 0;
3536	u64 last_dir_ino_rm = 0;
3537	bool can_rename = true;
3538
3539verbose_printk("btrfs: process_recorded_refs %llu\n", sctx->cur_ino);
3540
3541	/*
3542	 * This should never happen as the root dir always has the same ref
3543	 * which is always '..'
3544	 */
3545	BUG_ON(sctx->cur_ino <= BTRFS_FIRST_FREE_OBJECTID);
3546	INIT_LIST_HEAD(&check_dirs);
3547
3548	valid_path = fs_path_alloc();
3549	if (!valid_path) {
3550		ret = -ENOMEM;
3551		goto out;
3552	}
3553
3554	/*
3555	 * First, check if the first ref of the current inode was overwritten
3556	 * before. If yes, we know that the current inode was already orphanized
3557	 * and thus use the orphan name. If not, we can use get_cur_path to
3558	 * get the path of the first ref as it would like while receiving at
3559	 * this point in time.
3560	 * New inodes are always orphan at the beginning, so force to use the
3561	 * orphan name in this case.
3562	 * The first ref is stored in valid_path and will be updated if it
3563	 * gets moved around.
3564	 */
3565	if (!sctx->cur_inode_new) {
3566		ret = did_overwrite_first_ref(sctx, sctx->cur_ino,
3567				sctx->cur_inode_gen);
3568		if (ret < 0)
3569			goto out;
3570		if (ret)
3571			did_overwrite = 1;
3572	}
3573	if (sctx->cur_inode_new || did_overwrite) {
3574		ret = gen_unique_name(sctx, sctx->cur_ino,
3575				sctx->cur_inode_gen, valid_path);
3576		if (ret < 0)
3577			goto out;
3578		is_orphan = 1;
3579	} else {
3580		ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen,
3581				valid_path);
3582		if (ret < 0)
3583			goto out;
3584	}
3585
3586	list_for_each_entry(cur, &sctx->new_refs, list) {
3587		/*
3588		 * We may have refs where the parent directory does not exist
3589		 * yet. This happens if the parent directories inum is higher
3590		 * the the current inum. To handle this case, we create the
3591		 * parent directory out of order. But we need to check if this
3592		 * did already happen before due to other refs in the same dir.
3593		 */
3594		ret = get_cur_inode_state(sctx, cur->dir, cur->dir_gen);
3595		if (ret < 0)
3596			goto out;
3597		if (ret == inode_state_will_create) {
3598			ret = 0;
3599			/*
3600			 * First check if any of the current inodes refs did
3601			 * already create the dir.
3602			 */
3603			list_for_each_entry(cur2, &sctx->new_refs, list) {
3604				if (cur == cur2)
3605					break;
3606				if (cur2->dir == cur->dir) {
3607					ret = 1;
3608					break;
3609				}
3610			}
3611
3612			/*
3613			 * If that did not happen, check if a previous inode
3614			 * did already create the dir.
3615			 */
3616			if (!ret)
3617				ret = did_create_dir(sctx, cur->dir);
3618			if (ret < 0)
3619				goto out;
3620			if (!ret) {
3621				ret = send_create_inode(sctx, cur->dir);
3622				if (ret < 0)
3623					goto out;
3624			}
3625		}
3626
3627		/*
3628		 * Check if this new ref would overwrite the first ref of
3629		 * another unprocessed inode. If yes, orphanize the
3630		 * overwritten inode. If we find an overwritten ref that is
3631		 * not the first ref, simply unlink it.
3632		 */
3633		ret = will_overwrite_ref(sctx, cur->dir, cur->dir_gen,
3634				cur->name, cur->name_len,
3635				&ow_inode, &ow_gen);
3636		if (ret < 0)
3637			goto out;
3638		if (ret) {
3639			ret = is_first_ref(sctx->parent_root,
3640					   ow_inode, cur->dir, cur->name,
3641					   cur->name_len);
3642			if (ret < 0)
3643				goto out;
3644			if (ret) {
3645				struct name_cache_entry *nce;
3646
3647				ret = orphanize_inode(sctx, ow_inode, ow_gen,
3648						cur->full_path);
3649				if (ret < 0)
3650					goto out;
3651				/*
3652				 * Make sure we clear our orphanized inode's
3653				 * name from the name cache. This is because the
3654				 * inode ow_inode might be an ancestor of some
3655				 * other inode that will be orphanized as well
3656				 * later and has an inode number greater than
3657				 * sctx->send_progress. We need to prevent
3658				 * future name lookups from using the old name
3659				 * and get instead the orphan name.
3660				 */
3661				nce = name_cache_search(sctx, ow_inode, ow_gen);
3662				if (nce) {
3663					name_cache_delete(sctx, nce);
3664					kfree(nce);
3665				}
3666			} else {
3667				ret = send_unlink(sctx, cur->full_path);
3668				if (ret < 0)
3669					goto out;
3670			}
3671		}
3672
3673		if (S_ISDIR(sctx->cur_inode_mode) && sctx->parent_root) {
3674			ret = wait_for_dest_dir_move(sctx, cur, is_orphan);
3675			if (ret < 0)
3676				goto out;
3677			if (ret == 1) {
3678				can_rename = false;
3679				*pending_move = 1;
3680			}
3681		}
3682
3683		if (S_ISDIR(sctx->cur_inode_mode) && sctx->parent_root &&
3684		    can_rename) {
3685			ret = wait_for_parent_move(sctx, cur, is_orphan);
3686			if (ret < 0)
3687				goto out;
3688			if (ret == 1) {
3689				can_rename = false;
3690				*pending_move = 1;
3691			}
3692		}
3693
3694		/*
3695		 * link/move the ref to the new place. If we have an orphan
3696		 * inode, move it and update valid_path. If not, link or move
3697		 * it depending on the inode mode.
3698		 */
3699		if (is_orphan && can_rename) {
3700			ret = send_rename(sctx, valid_path, cur->full_path);
3701			if (ret < 0)
3702				goto out;
3703			is_orphan = 0;
3704			ret = fs_path_copy(valid_path, cur->full_path);
3705			if (ret < 0)
3706				goto out;
3707		} else if (can_rename) {
3708			if (S_ISDIR(sctx->cur_inode_mode)) {
3709				/*
3710				 * Dirs can't be linked, so move it. For moved
3711				 * dirs, we always have one new and one deleted
3712				 * ref. The deleted ref is ignored later.
3713				 */
3714				ret = send_rename(sctx, valid_path,
3715						  cur->full_path);
3716				if (!ret)
3717					ret = fs_path_copy(valid_path,
3718							   cur->full_path);
3719				if (ret < 0)
3720					goto out;
3721			} else {
3722				ret = send_link(sctx, cur->full_path,
3723						valid_path);
3724				if (ret < 0)
3725					goto out;
3726			}
3727		}
3728		ret = dup_ref(cur, &check_dirs);
3729		if (ret < 0)
3730			goto out;
3731	}
3732
3733	if (S_ISDIR(sctx->cur_inode_mode) && sctx->cur_inode_deleted) {
3734		/*
3735		 * Check if we can already rmdir the directory. If not,
3736		 * orphanize it. For every dir item inside that gets deleted
3737		 * later, we do this check again and rmdir it then if possible.
3738		 * See the use of check_dirs for more details.
3739		 */
3740		ret = can_rmdir(sctx, sctx->cur_ino, sctx->cur_inode_gen,
3741				sctx->cur_ino);
3742		if (ret < 0)
3743			goto out;
3744		if (ret) {
3745			ret = send_rmdir(sctx, valid_path);
3746			if (ret < 0)
3747				goto out;
3748		} else if (!is_orphan) {
3749			ret = orphanize_inode(sctx, sctx->cur_ino,
3750					sctx->cur_inode_gen, valid_path);
3751			if (ret < 0)
3752				goto out;
3753			is_orphan = 1;
3754		}
3755
3756		list_for_each_entry(cur, &sctx->deleted_refs, list) {
3757			ret = dup_ref(cur, &check_dirs);
3758			if (ret < 0)
3759				goto out;
3760		}
3761	} else if (S_ISDIR(sctx->cur_inode_mode) &&
3762		   !list_empty(&sctx->deleted_refs)) {
3763		/*
3764		 * We have a moved dir. Add the old parent to check_dirs
3765		 */
3766		cur = list_entry(sctx->deleted_refs.next, struct recorded_ref,
3767				list);
3768		ret = dup_ref(cur, &check_dirs);
3769		if (ret < 0)
3770			goto out;
3771	} else if (!S_ISDIR(sctx->cur_inode_mode)) {
3772		/*
3773		 * We have a non dir inode. Go through all deleted refs and
3774		 * unlink them if they were not already overwritten by other
3775		 * inodes.
3776		 */
3777		list_for_each_entry(cur, &sctx->deleted_refs, list) {
3778			ret = did_overwrite_ref(sctx, cur->dir, cur->dir_gen,
3779					sctx->cur_ino, sctx->cur_inode_gen,
3780					cur->name, cur->name_len);
3781			if (ret < 0)
3782				goto out;
3783			if (!ret) {
3784				ret = send_unlink(sctx, cur->full_path);
3785				if (ret < 0)
3786					goto out;
3787			}
3788			ret = dup_ref(cur, &check_dirs);
3789			if (ret < 0)
3790				goto out;
3791		}
3792		/*
3793		 * If the inode is still orphan, unlink the orphan. This may
3794		 * happen when a previous inode did overwrite the first ref
3795		 * of this inode and no new refs were added for the current
3796		 * inode. Unlinking does not mean that the inode is deleted in
3797		 * all cases. There may still be links to this inode in other
3798		 * places.
3799		 */
3800		if (is_orphan) {
3801			ret = send_unlink(sctx, valid_path);
3802			if (ret < 0)
3803				goto out;
3804		}
3805	}
3806
3807	/*
3808	 * We did collect all parent dirs where cur_inode was once located. We
3809	 * now go through all these dirs and check if they are pending for
3810	 * deletion and if it's finally possible to perform the rmdir now.
3811	 * We also update the inode stats of the parent dirs here.
3812	 */
3813	list_for_each_entry(cur, &check_dirs, list) {
3814		/*
3815		 * In case we had refs into dirs that were not processed yet,
3816		 * we don't need to do the utime and rmdir logic for these dirs.
3817		 * The dir will be processed later.
3818		 */
3819		if (cur->dir > sctx->cur_ino)
3820			continue;
3821
3822		ret = get_cur_inode_state(sctx, cur->dir, cur->dir_gen);
3823		if (ret < 0)
3824			goto out;
3825
3826		if (ret == inode_state_did_create ||
3827		    ret == inode_state_no_change) {
3828			/* TODO delayed utimes */
3829			ret = send_utimes(sctx, cur->dir, cur->dir_gen);
3830			if (ret < 0)
3831				goto out;
3832		} else if (ret == inode_state_did_delete &&
3833			   cur->dir != last_dir_ino_rm) {
3834			ret = can_rmdir(sctx, cur->dir, cur->dir_gen,
3835					sctx->cur_ino);
3836			if (ret < 0)
3837				goto out;
3838			if (ret) {
3839				ret = get_cur_path(sctx, cur->dir,
3840						   cur->dir_gen, valid_path);
3841				if (ret < 0)
3842					goto out;
3843				ret = send_rmdir(sctx, valid_path);
3844				if (ret < 0)
3845					goto out;
3846				last_dir_ino_rm = cur->dir;
3847			}
3848		}
3849	}
3850
3851	ret = 0;
3852
3853out:
3854	__free_recorded_refs(&check_dirs);
3855	free_recorded_refs(sctx);
3856	fs_path_free(valid_path);
3857	return ret;
3858}
3859
3860static int record_ref(struct btrfs_root *root, int num, u64 dir, int index,
3861		      struct fs_path *name, void *ctx, struct list_head *refs)
3862{
3863	int ret = 0;
3864	struct send_ctx *sctx = ctx;
3865	struct fs_path *p;
3866	u64 gen;
3867
3868	p = fs_path_alloc();
3869	if (!p)
3870		return -ENOMEM;
3871
3872	ret = get_inode_info(root, dir, NULL, &gen, NULL, NULL,
3873			NULL, NULL);
3874	if (ret < 0)
3875		goto out;
3876
3877	ret = get_cur_path(sctx, dir, gen, p);
3878	if (ret < 0)
3879		goto out;
3880	ret = fs_path_add_path(p, name);
3881	if (ret < 0)
3882		goto out;
3883
3884	ret = __record_ref(refs, dir, gen, p);
3885
3886out:
3887	if (ret)
3888		fs_path_free(p);
3889	return ret;
3890}
3891
3892static int __record_new_ref(int num, u64 dir, int index,
3893			    struct fs_path *name,
3894			    void *ctx)
3895{
3896	struct send_ctx *sctx = ctx;
3897	return record_ref(sctx->send_root, num, dir, index, name,
3898			  ctx, &sctx->new_refs);
3899}
3900
3901
3902static int __record_deleted_ref(int num, u64 dir, int index,
3903				struct fs_path *name,
3904				void *ctx)
3905{
3906	struct send_ctx *sctx = ctx;
3907	return record_ref(sctx->parent_root, num, dir, index, name,
3908			  ctx, &sctx->deleted_refs);
3909}
3910
3911static int record_new_ref(struct send_ctx *sctx)
3912{
3913	int ret;
3914
3915	ret = iterate_inode_ref(sctx->send_root, sctx->left_path,
3916				sctx->cmp_key, 0, __record_new_ref, sctx);
3917	if (ret < 0)
3918		goto out;
3919	ret = 0;
3920
3921out:
3922	return ret;
3923}
3924
3925static int record_deleted_ref(struct send_ctx *sctx)
3926{
3927	int ret;
3928
3929	ret = iterate_inode_ref(sctx->parent_root, sctx->right_path,
3930				sctx->cmp_key, 0, __record_deleted_ref, sctx);
3931	if (ret < 0)
3932		goto out;
3933	ret = 0;
3934
3935out:
3936	return ret;
3937}
3938
3939struct find_ref_ctx {
3940	u64 dir;
3941	u64 dir_gen;
3942	struct btrfs_root *root;
3943	struct fs_path *name;
3944	int found_idx;
3945};
3946
3947static int __find_iref(int num, u64 dir, int index,
3948		       struct fs_path *name,
3949		       void *ctx_)
3950{
3951	struct find_ref_ctx *ctx = ctx_;
3952	u64 dir_gen;
3953	int ret;
3954
3955	if (dir == ctx->dir && fs_path_len(name) == fs_path_len(ctx->name) &&
3956	    strncmp(name->start, ctx->name->start, fs_path_len(name)) == 0) {
3957		/*
3958		 * To avoid doing extra lookups we'll only do this if everything
3959		 * else matches.
3960		 */
3961		ret = get_inode_info(ctx->root, dir, NULL, &dir_gen, NULL,
3962				     NULL, NULL, NULL);
3963		if (ret)
3964			return ret;
3965		if (dir_gen != ctx->dir_gen)
3966			return 0;
3967		ctx->found_idx = num;
3968		return 1;
3969	}
3970	return 0;
3971}
3972
3973static int find_iref(struct btrfs_root *root,
3974		     struct btrfs_path *path,
3975		     struct btrfs_key *key,
3976		     u64 dir, u64 dir_gen, struct fs_path *name)
3977{
3978	int ret;
3979	struct find_ref_ctx ctx;
3980
3981	ctx.dir = dir;
3982	ctx.name = name;
3983	ctx.dir_gen = dir_gen;
3984	ctx.found_idx = -1;
3985	ctx.root = root;
3986
3987	ret = iterate_inode_ref(root, path, key, 0, __find_iref, &ctx);
3988	if (ret < 0)
3989		return ret;
3990
3991	if (ctx.found_idx == -1)
3992		return -ENOENT;
3993
3994	return ctx.found_idx;
3995}
3996
3997static int __record_changed_new_ref(int num, u64 dir, int index,
3998				    struct fs_path *name,
3999				    void *ctx)
4000{
4001	u64 dir_gen;
4002	int ret;
4003	struct send_ctx *sctx = ctx;
4004
4005	ret = get_inode_info(sctx->send_root, dir, NULL, &dir_gen, NULL,
4006			     NULL, NULL, NULL);
4007	if (ret)
4008		return ret;
4009
4010	ret = find_iref(sctx->parent_root, sctx->right_path,
4011			sctx->cmp_key, dir, dir_gen, name);
4012	if (ret == -ENOENT)
4013		ret = __record_new_ref(num, dir, index, name, sctx);
4014	else if (ret > 0)
4015		ret = 0;
4016
4017	return ret;
4018}
4019
4020static int __record_changed_deleted_ref(int num, u64 dir, int index,
4021					struct fs_path *name,
4022					void *ctx)
4023{
4024	u64 dir_gen;
4025	int ret;
4026	struct send_ctx *sctx = ctx;
4027
4028	ret = get_inode_info(sctx->parent_root, dir, NULL, &dir_gen, NULL,
4029			     NULL, NULL, NULL);
4030	if (ret)
4031		return ret;
4032
4033	ret = find_iref(sctx->send_root, sctx->left_path, sctx->cmp_key,
4034			dir, dir_gen, name);
4035	if (ret == -ENOENT)
4036		ret = __record_deleted_ref(num, dir, index, name, sctx);
4037	else if (ret > 0)
4038		ret = 0;
4039
4040	return ret;
4041}
4042
4043static int record_changed_ref(struct send_ctx *sctx)
4044{
4045	int ret = 0;
4046
4047	ret = iterate_inode_ref(sctx->send_root, sctx->left_path,
4048			sctx->cmp_key, 0, __record_changed_new_ref, sctx);
4049	if (ret < 0)
4050		goto out;
4051	ret = iterate_inode_ref(sctx->parent_root, sctx->right_path,
4052			sctx->cmp_key, 0, __record_changed_deleted_ref, sctx);
4053	if (ret < 0)
4054		goto out;
4055	ret = 0;
4056
4057out:
4058	return ret;
4059}
4060
4061/*
4062 * Record and process all refs at once. Needed when an inode changes the
4063 * generation number, which means that it was deleted and recreated.
4064 */
4065static int process_all_refs(struct send_ctx *sctx,
4066			    enum btrfs_compare_tree_result cmd)
4067{
4068	int ret;
4069	struct btrfs_root *root;
4070	struct btrfs_path *path;
4071	struct btrfs_key key;
4072	struct btrfs_key found_key;
4073	struct extent_buffer *eb;
4074	int slot;
4075	iterate_inode_ref_t cb;
4076	int pending_move = 0;
4077
4078	path = alloc_path_for_send();
4079	if (!path)
4080		return -ENOMEM;
4081
4082	if (cmd == BTRFS_COMPARE_TREE_NEW) {
4083		root = sctx->send_root;
4084		cb = __record_new_ref;
4085	} else if (cmd == BTRFS_COMPARE_TREE_DELETED) {
4086		root = sctx->parent_root;
4087		cb = __record_deleted_ref;
4088	} else {
4089		btrfs_err(sctx->send_root->fs_info,
4090				"Wrong command %d in process_all_refs", cmd);
4091		ret = -EINVAL;
4092		goto out;
4093	}
4094
4095	key.objectid = sctx->cmp_key->objectid;
4096	key.type = BTRFS_INODE_REF_KEY;
4097	key.offset = 0;
4098	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4099	if (ret < 0)
4100		goto out;
4101
4102	while (1) {
4103		eb = path->nodes[0];
4104		slot = path->slots[0];
4105		if (slot >= btrfs_header_nritems(eb)) {
4106			ret = btrfs_next_leaf(root, path);
4107			if (ret < 0)
4108				goto out;
4109			else if (ret > 0)
4110				break;
4111			continue;
4112		}
4113
4114		btrfs_item_key_to_cpu(eb, &found_key, slot);
4115
4116		if (found_key.objectid != key.objectid ||
4117		    (found_key.type != BTRFS_INODE_REF_KEY &&
4118		     found_key.type != BTRFS_INODE_EXTREF_KEY))
4119			break;
4120
4121		ret = iterate_inode_ref(root, path, &found_key, 0, cb, sctx);
4122		if (ret < 0)
4123			goto out;
4124
4125		path->slots[0]++;
4126	}
4127	btrfs_release_path(path);
4128
4129	ret = process_recorded_refs(sctx, &pending_move);
4130	/* Only applicable to an incremental send. */
4131	ASSERT(pending_move == 0);
4132
4133out:
4134	btrfs_free_path(path);
4135	return ret;
4136}
4137
4138static int send_set_xattr(struct send_ctx *sctx,
4139			  struct fs_path *path,
4140			  const char *name, int name_len,
4141			  const char *data, int data_len)
4142{
4143	int ret = 0;
4144
4145	ret = begin_cmd(sctx, BTRFS_SEND_C_SET_XATTR);
4146	if (ret < 0)
4147		goto out;
4148
4149	TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);
4150	TLV_PUT_STRING(sctx, BTRFS_SEND_A_XATTR_NAME, name, name_len);
4151	TLV_PUT(sctx, BTRFS_SEND_A_XATTR_DATA, data, data_len);
4152
4153	ret = send_cmd(sctx);
4154
4155tlv_put_failure:
4156out:
4157	return ret;
4158}
4159
4160static int send_remove_xattr(struct send_ctx *sctx,
4161			  struct fs_path *path,
4162			  const char *name, int name_len)
4163{
4164	int ret = 0;
4165
4166	ret = begin_cmd(sctx, BTRFS_SEND_C_REMOVE_XATTR);
4167	if (ret < 0)
4168		goto out;
4169
4170	TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);
4171	TLV_PUT_STRING(sctx, BTRFS_SEND_A_XATTR_NAME, name, name_len);
4172
4173	ret = send_cmd(sctx);
4174
4175tlv_put_failure:
4176out:
4177	return ret;
4178}
4179
4180static int __process_new_xattr(int num, struct btrfs_key *di_key,
4181			       const char *name, int name_len,
4182			       const char *data, int data_len,
4183			       u8 type, void *ctx)
4184{
4185	int ret;
4186	struct send_ctx *sctx = ctx;
4187	struct fs_path *p;
4188	posix_acl_xattr_header dummy_acl;
4189
4190	p = fs_path_alloc();
4191	if (!p)
4192		return -ENOMEM;
4193
4194	/*
4195	 * This hack is needed because empty acl's are stored as zero byte
4196	 * data in xattrs. Problem with that is, that receiving these zero byte
4197	 * acl's will fail later. To fix this, we send a dummy acl list that
4198	 * only contains the version number and no entries.
4199	 */
4200	if (!strncmp(name, XATTR_NAME_POSIX_ACL_ACCESS, name_len) ||
4201	    !strncmp(name, XATTR_NAME_POSIX_ACL_DEFAULT, name_len)) {
4202		if (data_len == 0) {
4203			dummy_acl.a_version =
4204					cpu_to_le32(POSIX_ACL_XATTR_VERSION);
4205			data = (char *)&dummy_acl;
4206			data_len = sizeof(dummy_acl);
4207		}
4208	}
4209
4210	ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
4211	if (ret < 0)
4212		goto out;
4213
4214	ret = send_set_xattr(sctx, p, name, name_len, data, data_len);
4215
4216out:
4217	fs_path_free(p);
4218	return ret;
4219}
4220
4221static int __process_deleted_xattr(int num, struct btrfs_key *di_key,
4222				   const char *name, int name_len,
4223				   const char *data, int data_len,
4224				   u8 type, void *ctx)
4225{
4226	int ret;
4227	struct send_ctx *sctx = ctx;
4228	struct fs_path *p;
4229
4230	p = fs_path_alloc();
4231	if (!p)
4232		return -ENOMEM;
4233
4234	ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
4235	if (ret < 0)
4236		goto out;
4237
4238	ret = send_remove_xattr(sctx, p, name, name_len);
4239
4240out:
4241	fs_path_free(p);
4242	return ret;
4243}
4244
4245static int process_new_xattr(struct send_ctx *sctx)
4246{
4247	int ret = 0;
4248
4249	ret = iterate_dir_item(sctx->send_root, sctx->left_path,
4250			       sctx->cmp_key, __process_new_xattr, sctx);
4251
4252	return ret;
4253}
4254
4255static int process_deleted_xattr(struct send_ctx *sctx)
4256{
4257	int ret;
4258
4259	ret = iterate_dir_item(sctx->parent_root, sctx->right_path,
4260			       sctx->cmp_key, __process_deleted_xattr, sctx);
4261
4262	return ret;
4263}
4264
4265struct find_xattr_ctx {
4266	const char *name;
4267	int name_len;
4268	int found_idx;
4269	char *found_data;
4270	int found_data_len;
4271};
4272
4273static int __find_xattr(int num, struct btrfs_key *di_key,
4274			const char *name, int name_len,
4275			const char *data, int data_len,
4276			u8 type, void *vctx)
4277{
4278	struct find_xattr_ctx *ctx = vctx;
4279
4280	if (name_len == ctx->name_len &&
4281	    strncmp(name, ctx->name, name_len) == 0) {
4282		ctx->found_idx = num;
4283		ctx->found_data_len = data_len;
4284		ctx->found_data = kmemdup(data, data_len, GFP_KERNEL);
4285		if (!ctx->found_data)
4286			return -ENOMEM;
4287		return 1;
4288	}
4289	return 0;
4290}
4291
4292static int find_xattr(struct btrfs_root *root,
4293		      struct btrfs_path *path,
4294		      struct btrfs_key *key,
4295		      const char *name, int name_len,
4296		      char **data, int *data_len)
4297{
4298	int ret;
4299	struct find_xattr_ctx ctx;
4300
4301	ctx.name = name;
4302	ctx.name_len = name_len;
4303	ctx.found_idx = -1;
4304	ctx.found_data = NULL;
4305	ctx.found_data_len = 0;
4306
4307	ret = iterate_dir_item(root, path, key, __find_xattr, &ctx);
4308	if (ret < 0)
4309		return ret;
4310
4311	if (ctx.found_idx == -1)
4312		return -ENOENT;
4313	if (data) {
4314		*data = ctx.found_data;
4315		*data_len = ctx.found_data_len;
4316	} else {
4317		kfree(ctx.found_data);
4318	}
4319	return ctx.found_idx;
4320}
4321
4322
4323static int __process_changed_new_xattr(int num, struct btrfs_key *di_key,
4324				       const char *name, int name_len,
4325				       const char *data, int data_len,
4326				       u8 type, void *ctx)
4327{
4328	int ret;
4329	struct send_ctx *sctx = ctx;
4330	char *found_data = NULL;
4331	int found_data_len  = 0;
4332
4333	ret = find_xattr(sctx->parent_root, sctx->right_path,
4334			 sctx->cmp_key, name, name_len, &found_data,
4335			 &found_data_len);
4336	if (ret == -ENOENT) {
4337		ret = __process_new_xattr(num, di_key, name, name_len, data,
4338				data_len, type, ctx);
4339	} else if (ret >= 0) {
4340		if (data_len != found_data_len ||
4341		    memcmp(data, found_data, data_len)) {
4342			ret = __process_new_xattr(num, di_key, name, name_len,
4343					data, data_len, type, ctx);
4344		} else {
4345			ret = 0;
4346		}
4347	}
4348
4349	kfree(found_data);
4350	return ret;
4351}
4352
4353static int __process_changed_deleted_xattr(int num, struct btrfs_key *di_key,
4354					   const char *name, int name_len,
4355					   const char *data, int data_len,
4356					   u8 type, void *ctx)
4357{
4358	int ret;
4359	struct send_ctx *sctx = ctx;
4360
4361	ret = find_xattr(sctx->send_root, sctx->left_path, sctx->cmp_key,
4362			 name, name_len, NULL, NULL);
4363	if (ret == -ENOENT)
4364		ret = __process_deleted_xattr(num, di_key, name, name_len, data,
4365				data_len, type, ctx);
4366	else if (ret >= 0)
4367		ret = 0;
4368
4369	return ret;
4370}
4371
4372static int process_changed_xattr(struct send_ctx *sctx)
4373{
4374	int ret = 0;
4375
4376	ret = iterate_dir_item(sctx->send_root, sctx->left_path,
4377			sctx->cmp_key, __process_changed_new_xattr, sctx);
4378	if (ret < 0)
4379		goto out;
4380	ret = iterate_dir_item(sctx->parent_root, sctx->right_path,
4381			sctx->cmp_key, __process_changed_deleted_xattr, sctx);
4382
4383out:
4384	return ret;
4385}
4386
4387static int process_all_new_xattrs(struct send_ctx *sctx)
4388{
4389	int ret;
4390	struct btrfs_root *root;
4391	struct btrfs_path *path;
4392	struct btrfs_key key;
4393	struct btrfs_key found_key;
4394	struct extent_buffer *eb;
4395	int slot;
4396
4397	path = alloc_path_for_send();
4398	if (!path)
4399		return -ENOMEM;
4400
4401	root = sctx->send_root;
4402
4403	key.objectid = sctx->cmp_key->objectid;
4404	key.type = BTRFS_XATTR_ITEM_KEY;
4405	key.offset = 0;
4406	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4407	if (ret < 0)
4408		goto out;
4409
4410	while (1) {
4411		eb = path->nodes[0];
4412		slot = path->slots[0];
4413		if (slot >= btrfs_header_nritems(eb)) {
4414			ret = btrfs_next_leaf(root, path);
4415			if (ret < 0) {
4416				goto out;
4417			} else if (ret > 0) {
4418				ret = 0;
4419				break;
4420			}
4421			continue;
4422		}
4423
4424		btrfs_item_key_to_cpu(eb, &found_key, slot);
4425		if (found_key.objectid != key.objectid ||
4426		    found_key.type != key.type) {
4427			ret = 0;
4428			goto out;
4429		}
4430
4431		ret = iterate_dir_item(root, path, &found_key,
4432				       __process_new_xattr, sctx);
4433		if (ret < 0)
4434			goto out;
4435
4436		path->slots[0]++;
4437	}
4438
4439out:
4440	btrfs_free_path(path);
4441	return ret;
4442}
4443
4444static ssize_t fill_read_buf(struct send_ctx *sctx, u64 offset, u32 len)
4445{
4446	struct btrfs_root *root = sctx->send_root;
4447	struct btrfs_fs_info *fs_info = root->fs_info;
4448	struct inode *inode;
4449	struct page *page;
4450	char *addr;
4451	struct btrfs_key key;
4452	pgoff_t index = offset >> PAGE_SHIFT;
4453	pgoff_t last_index;
4454	unsigned pg_offset = offset & ~PAGE_MASK;
4455	ssize_t ret = 0;
4456
4457	key.objectid = sctx->cur_ino;
4458	key.type = BTRFS_INODE_ITEM_KEY;
4459	key.offset = 0;
4460
4461	inode = btrfs_iget(fs_info->sb, &key, root, NULL);
4462	if (IS_ERR(inode))
4463		return PTR_ERR(inode);
4464
4465	if (offset + len > i_size_read(inode)) {
4466		if (offset > i_size_read(inode))
4467			len = 0;
4468		else
4469			len = offset - i_size_read(inode);
4470	}
4471	if (len == 0)
4472		goto out;
4473
4474	last_index = (offset + len - 1) >> PAGE_SHIFT;
4475
4476	/* initial readahead */
4477	memset(&sctx->ra, 0, sizeof(struct file_ra_state));
4478	file_ra_state_init(&sctx->ra, inode->i_mapping);
4479	btrfs_force_ra(inode->i_mapping, &sctx->ra, NULL, index,
4480		       last_index - index + 1);
4481
4482	while (index <= last_index) {
4483		unsigned cur_len = min_t(unsigned, len,
4484					 PAGE_SIZE - pg_offset);
4485		page = find_or_create_page(inode->i_mapping, index, GFP_KERNEL);
4486		if (!page) {
4487			ret = -ENOMEM;
4488			break;
4489		}
4490
4491		if (!PageUptodate(page)) {
4492			btrfs_readpage(NULL, page);
4493			lock_page(page);
4494			if (!PageUptodate(page)) {
4495				unlock_page(page);
4496				put_page(page);
4497				ret = -EIO;
4498				break;
4499			}
4500		}
4501
4502		addr = kmap(page);
4503		memcpy(sctx->read_buf + ret, addr + pg_offset, cur_len);
4504		kunmap(page);
4505		unlock_page(page);
4506		put_page(page);
4507		index++;
4508		pg_offset = 0;
4509		len -= cur_len;
4510		ret += cur_len;
4511	}
4512out:
4513	iput(inode);
4514	return ret;
4515}
4516
4517/*
4518 * Read some bytes from the current inode/file and send a write command to
4519 * user space.
4520 */
4521static int send_write(struct send_ctx *sctx, u64 offset, u32 len)
4522{
4523	int ret = 0;
4524	struct fs_path *p;
4525	ssize_t num_read = 0;
4526
4527	p = fs_path_alloc();
4528	if (!p)
4529		return -ENOMEM;
4530
4531verbose_printk("btrfs: send_write offset=%llu, len=%d\n", offset, len);
4532
4533	num_read = fill_read_buf(sctx, offset, len);
4534	if (num_read <= 0) {
4535		if (num_read < 0)
4536			ret = num_read;
4537		goto out;
4538	}
4539
4540	ret = begin_cmd(sctx, BTRFS_SEND_C_WRITE);
4541	if (ret < 0)
4542		goto out;
4543
4544	ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
4545	if (ret < 0)
4546		goto out;
4547
4548	TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
4549	TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset);
4550	TLV_PUT(sctx, BTRFS_SEND_A_DATA, sctx->read_buf, num_read);
4551
4552	ret = send_cmd(sctx);
4553
4554tlv_put_failure:
4555out:
4556	fs_path_free(p);
4557	if (ret < 0)
4558		return ret;
4559	return num_read;
4560}
4561
4562/*
4563 * Send a clone command to user space.
4564 */
4565static int send_clone(struct send_ctx *sctx,
4566		      u64 offset, u32 len,
4567		      struct clone_root *clone_root)
4568{
4569	int ret = 0;
4570	struct fs_path *p;
4571	u64 gen;
4572
4573verbose_printk("btrfs: send_clone offset=%llu, len=%d, clone_root=%llu, "
4574	       "clone_inode=%llu, clone_offset=%llu\n", offset, len,
4575		clone_root->root->objectid, clone_root->ino,
4576		clone_root->offset);
4577
4578	p = fs_path_alloc();
4579	if (!p)
4580		return -ENOMEM;
4581
4582	ret = begin_cmd(sctx, BTRFS_SEND_C_CLONE);
4583	if (ret < 0)
4584		goto out;
4585
4586	ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
4587	if (ret < 0)
4588		goto out;
4589
4590	TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset);
4591	TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_LEN, len);
4592	TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
4593
4594	if (clone_root->root == sctx->send_root) {
4595		ret = get_inode_info(sctx->send_root, clone_root->ino, NULL,
4596				&gen, NULL, NULL, NULL, NULL);
4597		if (ret < 0)
4598			goto out;
4599		ret = get_cur_path(sctx, clone_root->ino, gen, p);
4600	} else {
4601		ret = get_inode_path(clone_root->root, clone_root->ino, p);
4602	}
4603	if (ret < 0)
4604		goto out;
4605
4606	/*
4607	 * If the parent we're using has a received_uuid set then use that as
4608	 * our clone source as that is what we will look for when doing a
4609	 * receive.
4610	 *
4611	 * This covers the case that we create a snapshot off of a received
4612	 * subvolume and then use that as the parent and try to receive on a
4613	 * different host.
4614	 */
4615	if (!btrfs_is_empty_uuid(clone_root->root->root_item.received_uuid))
4616		TLV_PUT_UUID(sctx, BTRFS_SEND_A_CLONE_UUID,
4617			     clone_root->root->root_item.received_uuid);
4618	else
4619		TLV_PUT_UUID(sctx, BTRFS_SEND_A_CLONE_UUID,
4620			     clone_root->root->root_item.uuid);
4621	TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_CTRANSID,
4622		    le64_to_cpu(clone_root->root->root_item.ctransid));
4623	TLV_PUT_PATH(sctx, BTRFS_SEND_A_CLONE_PATH, p);
4624	TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_OFFSET,
4625			clone_root->offset);
4626
4627	ret = send_cmd(sctx);
4628
4629tlv_put_failure:
4630out:
4631	fs_path_free(p);
4632	return ret;
4633}
4634
4635/*
4636 * Send an update extent command to user space.
4637 */
4638static int send_update_extent(struct send_ctx *sctx,
4639			      u64 offset, u32 len)
4640{
4641	int ret = 0;
4642	struct fs_path *p;
4643
4644	p = fs_path_alloc();
4645	if (!p)
4646		return -ENOMEM;
4647
4648	ret = begin_cmd(sctx, BTRFS_SEND_C_UPDATE_EXTENT);
4649	if (ret < 0)
4650		goto out;
4651
4652	ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
4653	if (ret < 0)
4654		goto out;
4655
4656	TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
4657	TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset);
4658	TLV_PUT_U64(sctx, BTRFS_SEND_A_SIZE, len);
4659
4660	ret = send_cmd(sctx);
4661
4662tlv_put_failure:
4663out:
4664	fs_path_free(p);
4665	return ret;
4666}
4667
4668static int send_hole(struct send_ctx *sctx, u64 end)
4669{
4670	struct fs_path *p = NULL;
4671	u64 offset = sctx->cur_inode_last_extent;
4672	u64 len;
4673	int ret = 0;
4674
4675	p = fs_path_alloc();
4676	if (!p)
4677		return -ENOMEM;
4678	ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
4679	if (ret < 0)
4680		goto tlv_put_failure;
4681	memset(sctx->read_buf, 0, BTRFS_SEND_READ_SIZE);
4682	while (offset < end) {
4683		len = min_t(u64, end - offset, BTRFS_SEND_READ_SIZE);
4684
4685		ret = begin_cmd(sctx, BTRFS_SEND_C_WRITE);
4686		if (ret < 0)
4687			break;
4688		TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
4689		TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset);
4690		TLV_PUT(sctx, BTRFS_SEND_A_DATA, sctx->read_buf, len);
4691		ret = send_cmd(sctx);
4692		if (ret < 0)
4693			break;
4694		offset += len;
4695	}
4696tlv_put_failure:
4697	fs_path_free(p);
4698	return ret;
4699}
4700
4701static int send_extent_data(struct send_ctx *sctx,
4702			    const u64 offset,
4703			    const u64 len)
4704{
4705	u64 sent = 0;
4706
4707	if (sctx->flags & BTRFS_SEND_FLAG_NO_FILE_DATA)
4708		return send_update_extent(sctx, offset, len);
4709
4710	while (sent < len) {
4711		u64 size = len - sent;
4712		int ret;
4713
4714		if (size > BTRFS_SEND_READ_SIZE)
4715			size = BTRFS_SEND_READ_SIZE;
4716		ret = send_write(sctx, offset + sent, size);
4717		if (ret < 0)
4718			return ret;
4719		if (!ret)
4720			break;
4721		sent += ret;
4722	}
4723	return 0;
4724}
4725
4726static int clone_range(struct send_ctx *sctx,
4727		       struct clone_root *clone_root,
4728		       const u64 disk_byte,
4729		       u64 data_offset,
4730		       u64 offset,
4731		       u64 len)
4732{
4733	struct btrfs_path *path;
4734	struct btrfs_key key;
4735	int ret;
4736
4737	path = alloc_path_for_send();
4738	if (!path)
4739		return -ENOMEM;
4740
4741	/*
4742	 * We can't send a clone operation for the entire range if we find
4743	 * extent items in the respective range in the source file that
4744	 * refer to different extents or if we find holes.
4745	 * So check for that and do a mix of clone and regular write/copy
4746	 * operations if needed.
4747	 *
4748	 * Example:
4749	 *
4750	 * mkfs.btrfs -f /dev/sda
4751	 * mount /dev/sda /mnt
4752	 * xfs_io -f -c "pwrite -S 0xaa 0K 100K" /mnt/foo
4753	 * cp --reflink=always /mnt/foo /mnt/bar
4754	 * xfs_io -c "pwrite -S 0xbb 50K 50K" /mnt/foo
4755	 * btrfs subvolume snapshot -r /mnt /mnt/snap
4756	 *
4757	 * If when we send the snapshot and we are processing file bar (which
4758	 * has a higher inode number than foo) we blindly send a clone operation
4759	 * for the [0, 100K[ range from foo to bar, the receiver ends up getting
4760	 * a file bar that matches the content of file foo - iow, doesn't match
4761	 * the content from bar in the original filesystem.
4762	 */
4763	key.objectid = clone_root->ino;
4764	key.type = BTRFS_EXTENT_DATA_KEY;
4765	key.offset = clone_root->offset;
4766	ret = btrfs_search_slot(NULL, clone_root->root, &key, path, 0, 0);
4767	if (ret < 0)
4768		goto out;
4769	if (ret > 0 && path->slots[0] > 0) {
4770		btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0] - 1);
4771		if (key.objectid == clone_root->ino &&
4772		    key.type == BTRFS_EXTENT_DATA_KEY)
4773			path->slots[0]--;
4774	}
4775
4776	while (true) {
4777		struct extent_buffer *leaf = path->nodes[0];
4778		int slot = path->slots[0];
4779		struct btrfs_file_extent_item *ei;
4780		u8 type;
4781		u64 ext_len;
4782		u64 clone_len;
4783
4784		if (slot >= btrfs_header_nritems(leaf)) {
4785			ret = btrfs_next_leaf(clone_root->root, path);
4786			if (ret < 0)
4787				goto out;
4788			else if (ret > 0)
4789				break;
4790			continue;
4791		}
4792
4793		btrfs_item_key_to_cpu(leaf, &key, slot);
4794
4795		/*
4796		 * We might have an implicit trailing hole (NO_HOLES feature
4797		 * enabled). We deal with it after leaving this loop.
4798		 */
4799		if (key.objectid != clone_root->ino ||
4800		    key.type != BTRFS_EXTENT_DATA_KEY)
4801			break;
4802
4803		ei = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);
4804		type = btrfs_file_extent_type(leaf, ei);
4805		if (type == BTRFS_FILE_EXTENT_INLINE) {
4806			ext_len = btrfs_file_extent_inline_len(leaf, slot, ei);
4807			ext_len = PAGE_ALIGN(ext_len);
4808		} else {
4809			ext_len = btrfs_file_extent_num_bytes(leaf, ei);
4810		}
4811
4812		if (key.offset + ext_len <= clone_root->offset)
4813			goto next;
4814
4815		if (key.offset > clone_root->offset) {
4816			/* Implicit hole, NO_HOLES feature enabled. */
4817			u64 hole_len = key.offset - clone_root->offset;
4818
4819			if (hole_len > len)
4820				hole_len = len;
4821			ret = send_extent_data(sctx, offset, hole_len);
4822			if (ret < 0)
4823				goto out;
4824
4825			len -= hole_len;
4826			if (len == 0)
4827				break;
4828			offset += hole_len;
4829			clone_root->offset += hole_len;
4830			data_offset += hole_len;
4831		}
4832
4833		if (key.offset >= clone_root->offset + len)
4834			break;
4835
4836		clone_len = min_t(u64, ext_len, len);
4837
4838		if (btrfs_file_extent_disk_bytenr(leaf, ei) == disk_byte &&
4839		    btrfs_file_extent_offset(leaf, ei) == data_offset)
4840			ret = send_clone(sctx, offset, clone_len, clone_root);
4841		else
4842			ret = send_extent_data(sctx, offset, clone_len);
4843
4844		if (ret < 0)
4845			goto out;
4846
4847		len -= clone_len;
4848		if (len == 0)
4849			break;
4850		offset += clone_len;
4851		clone_root->offset += clone_len;
4852		data_offset += clone_len;
4853next:
4854		path->slots[0]++;
4855	}
4856
4857	if (len > 0)
4858		ret = send_extent_data(sctx, offset, len);
4859	else
4860		ret = 0;
4861out:
4862	btrfs_free_path(path);
4863	return ret;
4864}
4865
4866static int send_write_or_clone(struct send_ctx *sctx,
4867			       struct btrfs_path *path,
4868			       struct btrfs_key *key,
4869			       struct clone_root *clone_root)
4870{
4871	int ret = 0;
4872	struct btrfs_file_extent_item *ei;
4873	u64 offset = key->offset;
4874	u64 len;
4875	u8 type;
4876	u64 bs = sctx->send_root->fs_info->sb->s_blocksize;
4877
4878	ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
4879			struct btrfs_file_extent_item);
4880	type = btrfs_file_extent_type(path->nodes[0], ei);
4881	if (type == BTRFS_FILE_EXTENT_INLINE) {
4882		len = btrfs_file_extent_inline_len(path->nodes[0],
4883						   path->slots[0], ei);
4884		/*
4885		 * it is possible the inline item won't cover the whole page,
4886		 * but there may be items after this page.  Make
4887		 * sure to send the whole thing
4888		 */
4889		len = PAGE_ALIGN(len);
4890	} else {
4891		len = btrfs_file_extent_num_bytes(path->nodes[0], ei);
4892	}
4893
4894	if (offset + len > sctx->cur_inode_size)
4895		len = sctx->cur_inode_size - offset;
4896	if (len == 0) {
4897		ret = 0;
4898		goto out;
4899	}
4900
4901	if (clone_root && IS_ALIGNED(offset + len, bs)) {
4902		u64 disk_byte;
4903		u64 data_offset;
4904
4905		disk_byte = btrfs_file_extent_disk_bytenr(path->nodes[0], ei);
4906		data_offset = btrfs_file_extent_offset(path->nodes[0], ei);
4907		ret = clone_range(sctx, clone_root, disk_byte, data_offset,
4908				  offset, len);
4909	} else {
4910		ret = send_extent_data(sctx, offset, len);
4911	}
4912out:
4913	return ret;
4914}
4915
4916static int is_extent_unchanged(struct send_ctx *sctx,
4917			       struct btrfs_path *left_path,
4918			       struct btrfs_key *ekey)
4919{
4920	int ret = 0;
4921	struct btrfs_key key;
4922	struct btrfs_path *path = NULL;
4923	struct extent_buffer *eb;
4924	int slot;
4925	struct btrfs_key found_key;
4926	struct btrfs_file_extent_item *ei;
4927	u64 left_disknr;
4928	u64 right_disknr;
4929	u64 left_offset;
4930	u64 right_offset;
4931	u64 left_offset_fixed;
4932	u64 left_len;
4933	u64 right_len;
4934	u64 left_gen;
4935	u64 right_gen;
4936	u8 left_type;
4937	u8 right_type;
4938
4939	path = alloc_path_for_send();
4940	if (!path)
4941		return -ENOMEM;
4942
4943	eb = left_path->nodes[0];
4944	slot = left_path->slots[0];
4945	ei = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
4946	left_type = btrfs_file_extent_type(eb, ei);
4947
4948	if (left_type != BTRFS_FILE_EXTENT_REG) {
4949		ret = 0;
4950		goto out;
4951	}
4952	left_disknr = btrfs_file_extent_disk_bytenr(eb, ei);
4953	left_len = btrfs_file_extent_num_bytes(eb, ei);
4954	left_offset = btrfs_file_extent_offset(eb, ei);
4955	left_gen = btrfs_file_extent_generation(eb, ei);
4956
4957	/*
4958	 * Following comments will refer to these graphics. L is the left
4959	 * extents which we are checking at the moment. 1-8 are the right
4960	 * extents that we iterate.
4961	 *
4962	 *       |-----L-----|
4963	 * |-1-|-2a-|-3-|-4-|-5-|-6-|
4964	 *
4965	 *       |-----L-----|
4966	 * |--1--|-2b-|...(same as above)
4967	 *
4968	 * Alternative situation. Happens on files where extents got split.
4969	 *       |-----L-----|
4970	 * |-----------7-----------|-6-|
4971	 *
4972	 * Alternative situation. Happens on files which got larger.
4973	 *       |-----L-----|
4974	 * |-8-|
4975	 * Nothing follows after 8.
4976	 */
4977
4978	key.objectid = ekey->objectid;
4979	key.type = BTRFS_EXTENT_DATA_KEY;
4980	key.offset = ekey->offset;
4981	ret = btrfs_search_slot_for_read(sctx->parent_root, &key, path, 0, 0);
4982	if (ret < 0)
4983		goto out;
4984	if (ret) {
4985		ret = 0;
4986		goto out;
4987	}
4988
4989	/*
4990	 * Handle special case where the right side has no extents at all.
4991	 */
4992	eb = path->nodes[0];
4993	slot = path->slots[0];
4994	btrfs_item_key_to_cpu(eb, &found_key, slot);
4995	if (found_key.objectid != key.objectid ||
4996	    found_key.type != key.type) {
4997		/* If we're a hole then just pretend nothing changed */
4998		ret = (left_disknr) ? 0 : 1;
4999		goto out;
5000	}
5001
5002	/*
5003	 * We're now on 2a, 2b or 7.
5004	 */
5005	key = found_key;
5006	while (key.offset < ekey->offset + left_len) {
5007		ei = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
5008		right_type = btrfs_file_extent_type(eb, ei);
5009		if (right_type != BTRFS_FILE_EXTENT_REG) {
5010			ret = 0;
5011			goto out;
5012		}
5013
5014		right_disknr = btrfs_file_extent_disk_bytenr(eb, ei);
5015		right_len = btrfs_file_extent_num_bytes(eb, ei);
5016		right_offset = btrfs_file_extent_offset(eb, ei);
5017		right_gen = btrfs_file_extent_generation(eb, ei);
5018
5019		/*
5020		 * Are we at extent 8? If yes, we know the extent is changed.
5021		 * This may only happen on the first iteration.
5022		 */
5023		if (found_key.offset + right_len <= ekey->offset) {
5024			/* If we're a hole just pretend nothing changed */
5025			ret = (left_disknr) ? 0 : 1;
5026			goto out;
5027		}
5028
5029		left_offset_fixed = left_offset;
5030		if (key.offset < ekey->offset) {
5031			/* Fix the right offset for 2a and 7. */
5032			right_offset += ekey->offset - key.offset;
5033		} else {
5034			/* Fix the left offset for all behind 2a and 2b */
5035			left_offset_fixed += key.offset - ekey->offset;
5036		}
5037
5038		/*
5039		 * Check if we have the same extent.
5040		 */
5041		if (left_disknr != right_disknr ||
5042		    left_offset_fixed != right_offset ||
5043		    left_gen != right_gen) {
5044			ret = 0;
5045			goto out;
5046		}
5047
5048		/*
5049		 * Go to the next extent.
5050		 */
5051		ret = btrfs_next_item(sctx->parent_root, path);
5052		if (ret < 0)
5053			goto out;
5054		if (!ret) {
5055			eb = path->nodes[0];
5056			slot = path->slots[0];
5057			btrfs_item_key_to_cpu(eb, &found_key, slot);
5058		}
5059		if (ret || found_key.objectid != key.objectid ||
5060		    found_key.type != key.type) {
5061			key.offset += right_len;
5062			break;
5063		}
5064		if (found_key.offset != key.offset + right_len) {
5065			ret = 0;
5066			goto out;
5067		}
5068		key = found_key;
5069	}
5070
5071	/*
5072	 * We're now behind the left extent (treat as unchanged) or at the end
5073	 * of the right side (treat as changed).
5074	 */
5075	if (key.offset >= ekey->offset + left_len)
5076		ret = 1;
5077	else
5078		ret = 0;
5079
5080
5081out:
5082	btrfs_free_path(path);
5083	return ret;
5084}
5085
5086static int get_last_extent(struct send_ctx *sctx, u64 offset)
5087{
5088	struct btrfs_path *path;
5089	struct btrfs_root *root = sctx->send_root;
5090	struct btrfs_file_extent_item *fi;
5091	struct btrfs_key key;
5092	u64 extent_end;
5093	u8 type;
5094	int ret;
5095
5096	path = alloc_path_for_send();
5097	if (!path)
5098		return -ENOMEM;
5099
5100	sctx->cur_inode_last_extent = 0;
5101
5102	key.objectid = sctx->cur_ino;
5103	key.type = BTRFS_EXTENT_DATA_KEY;
5104	key.offset = offset;
5105	ret = btrfs_search_slot_for_read(root, &key, path, 0, 1);
5106	if (ret < 0)
5107		goto out;
5108	ret = 0;
5109	btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
5110	if (key.objectid != sctx->cur_ino || key.type != BTRFS_EXTENT_DATA_KEY)
5111		goto out;
5112
5113	fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
5114			    struct btrfs_file_extent_item);
5115	type = btrfs_file_extent_type(path->nodes[0], fi);
5116	if (type == BTRFS_FILE_EXTENT_INLINE) {
5117		u64 size = btrfs_file_extent_inline_len(path->nodes[0],
5118							path->slots[0], fi);
5119		extent_end = ALIGN(key.offset + size,
5120				   sctx->send_root->sectorsize);
5121	} else {
5122		extent_end = key.offset +
5123			btrfs_file_extent_num_bytes(path->nodes[0], fi);
5124	}
5125	sctx->cur_inode_last_extent = extent_end;
5126out:
5127	btrfs_free_path(path);
5128	return ret;
5129}
5130
5131static int maybe_send_hole(struct send_ctx *sctx, struct btrfs_path *path,
5132			   struct btrfs_key *key)
5133{
5134	struct btrfs_file_extent_item *fi;
5135	u64 extent_end;
5136	u8 type;
5137	int ret = 0;
5138
5139	if (sctx->cur_ino != key->objectid || !need_send_hole(sctx))
5140		return 0;
5141
5142	if (sctx->cur_inode_last_extent == (u64)-1) {
5143		ret = get_last_extent(sctx, key->offset - 1);
5144		if (ret)
5145			return ret;
5146	}
5147
5148	fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
5149			    struct btrfs_file_extent_item);
5150	type = btrfs_file_extent_type(path->nodes[0], fi);
5151	if (type == BTRFS_FILE_EXTENT_INLINE) {
5152		u64 size = btrfs_file_extent_inline_len(path->nodes[0],
5153							path->slots[0], fi);
5154		extent_end = ALIGN(key->offset + size,
5155				   sctx->send_root->sectorsize);
5156	} else {
5157		extent_end = key->offset +
5158			btrfs_file_extent_num_bytes(path->nodes[0], fi);
5159	}
5160
5161	if (path->slots[0] == 0 &&
5162	    sctx->cur_inode_last_extent < key->offset) {
5163		/*
5164		 * We might have skipped entire leafs that contained only
5165		 * file extent items for our current inode. These leafs have
5166		 * a generation number smaller (older) than the one in the
5167		 * current leaf and the leaf our last extent came from, and
5168		 * are located between these 2 leafs.
5169		 */
5170		ret = get_last_extent(sctx, key->offset - 1);
5171		if (ret)
5172			return ret;
5173	}
5174
5175	if (sctx->cur_inode_last_extent < key->offset)
5176		ret = send_hole(sctx, key->offset);
5177	sctx->cur_inode_last_extent = extent_end;
5178	return ret;
5179}
5180
5181static int process_extent(struct send_ctx *sctx,
5182			  struct btrfs_path *path,
5183			  struct btrfs_key *key)
5184{
5185	struct clone_root *found_clone = NULL;
5186	int ret = 0;
5187
5188	if (S_ISLNK(sctx->cur_inode_mode))
5189		return 0;
5190
5191	if (sctx->parent_root && !sctx->cur_inode_new) {
5192		ret = is_extent_unchanged(sctx, path, key);
5193		if (ret < 0)
5194			goto out;
5195		if (ret) {
5196			ret = 0;
5197			goto out_hole;
5198		}
5199	} else {
5200		struct btrfs_file_extent_item *ei;
5201		u8 type;
5202
5203		ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
5204				    struct btrfs_file_extent_item);
5205		type = btrfs_file_extent_type(path->nodes[0], ei);
5206		if (type == BTRFS_FILE_EXTENT_PREALLOC ||
5207		    type == BTRFS_FILE_EXTENT_REG) {
5208			/*
5209			 * The send spec does not have a prealloc command yet,
5210			 * so just leave a hole for prealloc'ed extents until
5211			 * we have enough commands queued up to justify rev'ing
5212			 * the send spec.
5213			 */
5214			if (type == BTRFS_FILE_EXTENT_PREALLOC) {
5215				ret = 0;
5216				goto out;
5217			}
5218
5219			/* Have a hole, just skip it. */
5220			if (btrfs_file_extent_disk_bytenr(path->nodes[0], ei) == 0) {
5221				ret = 0;
5222				goto out;
5223			}
5224		}
5225	}
5226
5227	ret = find_extent_clone(sctx, path, key->objectid, key->offset,
5228			sctx->cur_inode_size, &found_clone);
5229	if (ret != -ENOENT && ret < 0)
5230		goto out;
5231
5232	ret = send_write_or_clone(sctx, path, key, found_clone);
5233	if (ret)
5234		goto out;
5235out_hole:
5236	ret = maybe_send_hole(sctx, path, key);
5237out:
5238	return ret;
5239}
5240
5241static int process_all_extents(struct send_ctx *sctx)
5242{
5243	int ret;
5244	struct btrfs_root *root;
5245	struct btrfs_path *path;
5246	struct btrfs_key key;
5247	struct btrfs_key found_key;
5248	struct extent_buffer *eb;
5249	int slot;
5250
5251	root = sctx->send_root;
5252	path = alloc_path_for_send();
5253	if (!path)
5254		return -ENOMEM;
5255
5256	key.objectid = sctx->cmp_key->objectid;
5257	key.type = BTRFS_EXTENT_DATA_KEY;
5258	key.offset = 0;
5259	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
5260	if (ret < 0)
5261		goto out;
5262
5263	while (1) {
5264		eb = path->nodes[0];
5265		slot = path->slots[0];
5266
5267		if (slot >= btrfs_header_nritems(eb)) {
5268			ret = btrfs_next_leaf(root, path);
5269			if (ret < 0) {
5270				goto out;
5271			} else if (ret > 0) {
5272				ret = 0;
5273				break;
5274			}
5275			continue;
5276		}
5277
5278		btrfs_item_key_to_cpu(eb, &found_key, slot);
5279
5280		if (found_key.objectid != key.objectid ||
5281		    found_key.type != key.type) {
5282			ret = 0;
5283			goto out;
5284		}
5285
5286		ret = process_extent(sctx, path, &found_key);
5287		if (ret < 0)
5288			goto out;
5289
5290		path->slots[0]++;
5291	}
5292
5293out:
5294	btrfs_free_path(path);
5295	return ret;
5296}
5297
5298static int process_recorded_refs_if_needed(struct send_ctx *sctx, int at_end,
5299					   int *pending_move,
5300					   int *refs_processed)
5301{
5302	int ret = 0;
5303
5304	if (sctx->cur_ino == 0)
5305		goto out;
5306	if (!at_end && sctx->cur_ino == sctx->cmp_key->objectid &&
5307	    sctx->cmp_key->type <= BTRFS_INODE_EXTREF_KEY)
5308		goto out;
5309	if (list_empty(&sctx->new_refs) && list_empty(&sctx->deleted_refs))
5310		goto out;
5311
5312	ret = process_recorded_refs(sctx, pending_move);
5313	if (ret < 0)
5314		goto out;
5315
5316	*refs_processed = 1;
5317out:
5318	return ret;
5319}
5320
5321static int finish_inode_if_needed(struct send_ctx *sctx, int at_end)
5322{
5323	int ret = 0;
5324	u64 left_mode;
5325	u64 left_uid;
5326	u64 left_gid;
5327	u64 right_mode;
5328	u64 right_uid;
5329	u64 right_gid;
5330	int need_chmod = 0;
5331	int need_chown = 0;
5332	int pending_move = 0;
5333	int refs_processed = 0;
5334
5335	ret = process_recorded_refs_if_needed(sctx, at_end, &pending_move,
5336					      &refs_processed);
5337	if (ret < 0)
5338		goto out;
5339
5340	/*
5341	 * We have processed the refs and thus need to advance send_progress.
5342	 * Now, calls to get_cur_xxx will take the updated refs of the current
5343	 * inode into account.
5344	 *
5345	 * On the other hand, if our current inode is a directory and couldn't
5346	 * be moved/renamed because its parent was renamed/moved too and it has
5347	 * a higher inode number, we can only move/rename our current inode
5348	 * after we moved/renamed its parent. Therefore in this case operate on
5349	 * the old path (pre move/rename) of our current inode, and the
5350	 * move/rename will be performed later.
5351	 */
5352	if (refs_processed && !pending_move)
5353		sctx->send_progress = sctx->cur_ino + 1;
5354
5355	if (sctx->cur_ino == 0 || sctx->cur_inode_deleted)
5356		goto out;
5357	if (!at_end && sctx->cmp_key->objectid == sctx->cur_ino)
5358		goto out;
5359
5360	ret = get_inode_info(sctx->send_root, sctx->cur_ino, NULL, NULL,
5361			&left_mode, &left_uid, &left_gid, NULL);
5362	if (ret < 0)
5363		goto out;
5364
5365	if (!sctx->parent_root || sctx->cur_inode_new) {
5366		need_chown = 1;
5367		if (!S_ISLNK(sctx->cur_inode_mode))
5368			need_chmod = 1;
5369	} else {
5370		ret = get_inode_info(sctx->parent_root, sctx->cur_ino,
5371				NULL, NULL, &right_mode, &right_uid,
5372				&right_gid, NULL);
5373		if (ret < 0)
5374			goto out;
5375
5376		if (left_uid != right_uid || left_gid != right_gid)
5377			need_chown = 1;
5378		if (!S_ISLNK(sctx->cur_inode_mode) && left_mode != right_mode)
5379			need_chmod = 1;
5380	}
5381
5382	if (S_ISREG(sctx->cur_inode_mode)) {
5383		if (need_send_hole(sctx)) {
5384			if (sctx->cur_inode_last_extent == (u64)-1 ||
5385			    sctx->cur_inode_last_extent <
5386			    sctx->cur_inode_size) {
5387				ret = get_last_extent(sctx, (u64)-1);
5388				if (ret)
5389					goto out;
5390			}
5391			if (sctx->cur_inode_last_extent <
5392			    sctx->cur_inode_size) {
5393				ret = send_hole(sctx, sctx->cur_inode_size);
5394				if (ret)
5395					goto out;
5396			}
5397		}
5398		ret = send_truncate(sctx, sctx->cur_ino, sctx->cur_inode_gen,
5399				sctx->cur_inode_size);
5400		if (ret < 0)
5401			goto out;
5402	}
5403
5404	if (need_chown) {
5405		ret = send_chown(sctx, sctx->cur_ino, sctx->cur_inode_gen,
5406				left_uid, left_gid);
5407		if (ret < 0)
5408			goto out;
5409	}
5410	if (need_chmod) {
5411		ret = send_chmod(sctx, sctx->cur_ino, sctx->cur_inode_gen,
5412				left_mode);
5413		if (ret < 0)
5414			goto out;
5415	}
5416
5417	/*
5418	 * If other directory inodes depended on our current directory
5419	 * inode's move/rename, now do their move/rename operations.
5420	 */
5421	if (!is_waiting_for_move(sctx, sctx->cur_ino)) {
5422		ret = apply_children_dir_moves(sctx);
5423		if (ret)
5424			goto out;
5425		/*
5426		 * Need to send that every time, no matter if it actually
5427		 * changed between the two trees as we have done changes to
5428		 * the inode before. If our inode is a directory and it's
5429		 * waiting to be moved/renamed, we will send its utimes when
5430		 * it's moved/renamed, therefore we don't need to do it here.
5431		 */
5432		sctx->send_progress = sctx->cur_ino + 1;
5433		ret = send_utimes(sctx, sctx->cur_ino, sctx->cur_inode_gen);
5434		if (ret < 0)
5435			goto out;
5436	}
5437
5438out:
5439	return ret;
5440}
5441
5442static int changed_inode(struct send_ctx *sctx,
5443			 enum btrfs_compare_tree_result result)
5444{
5445	int ret = 0;
5446	struct btrfs_key *key = sctx->cmp_key;
5447	struct btrfs_inode_item *left_ii = NULL;
5448	struct btrfs_inode_item *right_ii = NULL;
5449	u64 left_gen = 0;
5450	u64 right_gen = 0;
5451
5452	sctx->cur_ino = key->objectid;
5453	sctx->cur_inode_new_gen = 0;
5454	sctx->cur_inode_last_extent = (u64)-1;
5455
5456	/*
5457	 * Set send_progress to current inode. This will tell all get_cur_xxx
5458	 * functions that the current inode's refs are not updated yet. Later,
5459	 * when process_recorded_refs is finished, it is set to cur_ino + 1.
5460	 */
5461	sctx->send_progress = sctx->cur_ino;
5462
5463	if (result == BTRFS_COMPARE_TREE_NEW ||
5464	    result == BTRFS_COMPARE_TREE_CHANGED) {
5465		left_ii = btrfs_item_ptr(sctx->left_path->nodes[0],
5466				sctx->left_path->slots[0],
5467				struct btrfs_inode_item);
5468		left_gen = btrfs_inode_generation(sctx->left_path->nodes[0],
5469				left_ii);
5470	} else {
5471		right_ii = btrfs_item_ptr(sctx->right_path->nodes[0],
5472				sctx->right_path->slots[0],
5473				struct btrfs_inode_item);
5474		right_gen = btrfs_inode_generation(sctx->right_path->nodes[0],
5475				right_ii);
5476	}
5477	if (result == BTRFS_COMPARE_TREE_CHANGED) {
5478		right_ii = btrfs_item_ptr(sctx->right_path->nodes[0],
5479				sctx->right_path->slots[0],
5480				struct btrfs_inode_item);
5481
5482		right_gen = btrfs_inode_generation(sctx->right_path->nodes[0],
5483				right_ii);
5484
5485		/*
5486		 * The cur_ino = root dir case is special here. We can't treat
5487		 * the inode as deleted+reused because it would generate a
5488		 * stream that tries to delete/mkdir the root dir.
5489		 */
5490		if (left_gen != right_gen &&
5491		    sctx->cur_ino != BTRFS_FIRST_FREE_OBJECTID)
5492			sctx->cur_inode_new_gen = 1;
5493	}
5494
5495	if (result == BTRFS_COMPARE_TREE_NEW) {
5496		sctx->cur_inode_gen = left_gen;
5497		sctx->cur_inode_new = 1;
5498		sctx->cur_inode_deleted = 0;
5499		sctx->cur_inode_size = btrfs_inode_size(
5500				sctx->left_path->nodes[0], left_ii);
5501		sctx->cur_inode_mode = btrfs_inode_mode(
5502				sctx->left_path->nodes[0], left_ii);
5503		sctx->cur_inode_rdev = btrfs_inode_rdev(
5504				sctx->left_path->nodes[0], left_ii);
5505		if (sctx->cur_ino != BTRFS_FIRST_FREE_OBJECTID)
5506			ret = send_create_inode_if_needed(sctx);
5507	} else if (result == BTRFS_COMPARE_TREE_DELETED) {
5508		sctx->cur_inode_gen = right_gen;
5509		sctx->cur_inode_new = 0;
5510		sctx->cur_inode_deleted = 1;
5511		sctx->cur_inode_size = btrfs_inode_size(
5512				sctx->right_path->nodes[0], right_ii);
5513		sctx->cur_inode_mode = btrfs_inode_mode(
5514				sctx->right_path->nodes[0], right_ii);
5515	} else if (result == BTRFS_COMPARE_TREE_CHANGED) {
5516		/*
5517		 * We need to do some special handling in case the inode was
5518		 * reported as changed with a changed generation number. This
5519		 * means that the original inode was deleted and new inode
5520		 * reused the same inum. So we have to treat the old inode as
5521		 * deleted and the new one as new.
5522		 */
5523		if (sctx->cur_inode_new_gen) {
5524			/*
5525			 * First, process the inode as if it was deleted.
5526			 */
5527			sctx->cur_inode_gen = right_gen;
5528			sctx->cur_inode_new = 0;
5529			sctx->cur_inode_deleted = 1;
5530			sctx->cur_inode_size = btrfs_inode_size(
5531					sctx->right_path->nodes[0], right_ii);
5532			sctx->cur_inode_mode = btrfs_inode_mode(
5533					sctx->right_path->nodes[0], right_ii);
5534			ret = process_all_refs(sctx,
5535					BTRFS_COMPARE_TREE_DELETED);
5536			if (ret < 0)
5537				goto out;
5538
5539			/*
5540			 * Now process the inode as if it was new.
5541			 */
5542			sctx->cur_inode_gen = left_gen;
5543			sctx->cur_inode_new = 1;
5544			sctx->cur_inode_deleted = 0;
5545			sctx->cur_inode_size = btrfs_inode_size(
5546					sctx->left_path->nodes[0], left_ii);
5547			sctx->cur_inode_mode = btrfs_inode_mode(
5548					sctx->left_path->nodes[0], left_ii);
5549			sctx->cur_inode_rdev = btrfs_inode_rdev(
5550					sctx->left_path->nodes[0], left_ii);
5551			ret = send_create_inode_if_needed(sctx);
5552			if (ret < 0)
5553				goto out;
5554
5555			ret = process_all_refs(sctx, BTRFS_COMPARE_TREE_NEW);
5556			if (ret < 0)
5557				goto out;
5558			/*
5559			 * Advance send_progress now as we did not get into
5560			 * process_recorded_refs_if_needed in the new_gen case.
5561			 */
5562			sctx->send_progress = sctx->cur_ino + 1;
5563
5564			/*
5565			 * Now process all extents and xattrs of the inode as if
5566			 * they were all new.
5567			 */
5568			ret = process_all_extents(sctx);
5569			if (ret < 0)
5570				goto out;
5571			ret = process_all_new_xattrs(sctx);
5572			if (ret < 0)
5573				goto out;
5574		} else {
5575			sctx->cur_inode_gen = left_gen;
5576			sctx->cur_inode_new = 0;
5577			sctx->cur_inode_new_gen = 0;
5578			sctx->cur_inode_deleted = 0;
5579			sctx->cur_inode_size = btrfs_inode_size(
5580					sctx->left_path->nodes[0], left_ii);
5581			sctx->cur_inode_mode = btrfs_inode_mode(
5582					sctx->left_path->nodes[0], left_ii);
5583		}
5584	}
5585
5586out:
5587	return ret;
5588}
5589
5590/*
5591 * We have to process new refs before deleted refs, but compare_trees gives us
5592 * the new and deleted refs mixed. To fix this, we record the new/deleted refs
5593 * first and later process them in process_recorded_refs.
5594 * For the cur_inode_new_gen case, we skip recording completely because
5595 * changed_inode did already initiate processing of refs. The reason for this is
5596 * that in this case, compare_tree actually compares the refs of 2 different
5597 * inodes. To fix this, process_all_refs is used in changed_inode to handle all
5598 * refs of the right tree as deleted and all refs of the left tree as new.
5599 */
5600static int changed_ref(struct send_ctx *sctx,
5601		       enum btrfs_compare_tree_result result)
5602{
5603	int ret = 0;
5604
5605	BUG_ON(sctx->cur_ino != sctx->cmp_key->objectid);
5606
5607	if (!sctx->cur_inode_new_gen &&
5608	    sctx->cur_ino != BTRFS_FIRST_FREE_OBJECTID) {
5609		if (result == BTRFS_COMPARE_TREE_NEW)
5610			ret = record_new_ref(sctx);
5611		else if (result == BTRFS_COMPARE_TREE_DELETED)
5612			ret = record_deleted_ref(sctx);
5613		else if (result == BTRFS_COMPARE_TREE_CHANGED)
5614			ret = record_changed_ref(sctx);
5615	}
5616
5617	return ret;
5618}
5619
5620/*
5621 * Process new/deleted/changed xattrs. We skip processing in the
5622 * cur_inode_new_gen case because changed_inode did already initiate processing
5623 * of xattrs. The reason is the same as in changed_ref
5624 */
5625static int changed_xattr(struct send_ctx *sctx,
5626			 enum btrfs_compare_tree_result result)
5627{
5628	int ret = 0;
5629
5630	BUG_ON(sctx->cur_ino != sctx->cmp_key->objectid);
5631
5632	if (!sctx->cur_inode_new_gen && !sctx->cur_inode_deleted) {
5633		if (result == BTRFS_COMPARE_TREE_NEW)
5634			ret = process_new_xattr(sctx);
5635		else if (result == BTRFS_COMPARE_TREE_DELETED)
5636			ret = process_deleted_xattr(sctx);
5637		else if (result == BTRFS_COMPARE_TREE_CHANGED)
5638			ret = process_changed_xattr(sctx);
5639	}
5640
5641	return ret;
5642}
5643
5644/*
5645 * Process new/deleted/changed extents. We skip processing in the
5646 * cur_inode_new_gen case because changed_inode did already initiate processing
5647 * of extents. The reason is the same as in changed_ref
5648 */
5649static int changed_extent(struct send_ctx *sctx,
5650			  enum btrfs_compare_tree_result result)
5651{
5652	int ret = 0;
5653
5654	BUG_ON(sctx->cur_ino != sctx->cmp_key->objectid);
5655
5656	if (!sctx->cur_inode_new_gen && !sctx->cur_inode_deleted) {
5657		if (result != BTRFS_COMPARE_TREE_DELETED)
5658			ret = process_extent(sctx, sctx->left_path,
5659					sctx->cmp_key);
5660	}
5661
5662	return ret;
5663}
5664
5665static int dir_changed(struct send_ctx *sctx, u64 dir)
5666{
5667	u64 orig_gen, new_gen;
5668	int ret;
5669
5670	ret = get_inode_info(sctx->send_root, dir, NULL, &new_gen, NULL, NULL,
5671			     NULL, NULL);
5672	if (ret)
5673		return ret;
5674
5675	ret = get_inode_info(sctx->parent_root, dir, NULL, &orig_gen, NULL,
5676			     NULL, NULL, NULL);
5677	if (ret)
5678		return ret;
5679
5680	return (orig_gen != new_gen) ? 1 : 0;
5681}
5682
5683static int compare_refs(struct send_ctx *sctx, struct btrfs_path *path,
5684			struct btrfs_key *key)
5685{
5686	struct btrfs_inode_extref *extref;
5687	struct extent_buffer *leaf;
5688	u64 dirid = 0, last_dirid = 0;
5689	unsigned long ptr;
5690	u32 item_size;
5691	u32 cur_offset = 0;
5692	int ref_name_len;
5693	int ret = 0;
5694
5695	/* Easy case, just check this one dirid */
5696	if (key->type == BTRFS_INODE_REF_KEY) {
5697		dirid = key->offset;
5698
5699		ret = dir_changed(sctx, dirid);
5700		goto out;
5701	}
5702
5703	leaf = path->nodes[0];
5704	item_size = btrfs_item_size_nr(leaf, path->slots[0]);
5705	ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
5706	while (cur_offset < item_size) {
5707		extref = (struct btrfs_inode_extref *)(ptr +
5708						       cur_offset);
5709		dirid = btrfs_inode_extref_parent(leaf, extref);
5710		ref_name_len = btrfs_inode_extref_name_len(leaf, extref);
5711		cur_offset += ref_name_len + sizeof(*extref);
5712		if (dirid == last_dirid)
5713			continue;
5714		ret = dir_changed(sctx, dirid);
5715		if (ret)
5716			break;
5717		last_dirid = dirid;
5718	}
5719out:
5720	return ret;
5721}
5722
5723/*
5724 * Updates compare related fields in sctx and simply forwards to the actual
5725 * changed_xxx functions.
5726 */
5727static int changed_cb(struct btrfs_root *left_root,
5728		      struct btrfs_root *right_root,
5729		      struct btrfs_path *left_path,
5730		      struct btrfs_path *right_path,
5731		      struct btrfs_key *key,
5732		      enum btrfs_compare_tree_result result,
5733		      void *ctx)
5734{
5735	int ret = 0;
5736	struct send_ctx *sctx = ctx;
5737
5738	if (result == BTRFS_COMPARE_TREE_SAME) {
5739		if (key->type == BTRFS_INODE_REF_KEY ||
5740		    key->type == BTRFS_INODE_EXTREF_KEY) {
5741			ret = compare_refs(sctx, left_path, key);
5742			if (!ret)
5743				return 0;
5744			if (ret < 0)
5745				return ret;
5746		} else if (key->type == BTRFS_EXTENT_DATA_KEY) {
5747			return maybe_send_hole(sctx, left_path, key);
5748		} else {
5749			return 0;
5750		}
5751		result = BTRFS_COMPARE_TREE_CHANGED;
5752		ret = 0;
5753	}
5754
5755	sctx->left_path = left_path;
5756	sctx->right_path = right_path;
5757	sctx->cmp_key = key;
5758
5759	ret = finish_inode_if_needed(sctx, 0);
5760	if (ret < 0)
5761		goto out;
5762
5763	/* Ignore non-FS objects */
5764	if (key->objectid == BTRFS_FREE_INO_OBJECTID ||
5765	    key->objectid == BTRFS_FREE_SPACE_OBJECTID)
5766		goto out;
5767
5768	if (key->type == BTRFS_INODE_ITEM_KEY)
5769		ret = changed_inode(sctx, result);
5770	else if (key->type == BTRFS_INODE_REF_KEY ||
5771		 key->type == BTRFS_INODE_EXTREF_KEY)
5772		ret = changed_ref(sctx, result);
5773	else if (key->type == BTRFS_XATTR_ITEM_KEY)
5774		ret = changed_xattr(sctx, result);
5775	else if (key->type == BTRFS_EXTENT_DATA_KEY)
5776		ret = changed_extent(sctx, result);
5777
5778out:
5779	return ret;
5780}
5781
5782static int full_send_tree(struct send_ctx *sctx)
5783{
5784	int ret;
5785	struct btrfs_root *send_root = sctx->send_root;
5786	struct btrfs_key key;
5787	struct btrfs_key found_key;
5788	struct btrfs_path *path;
5789	struct extent_buffer *eb;
5790	int slot;
5791
5792	path = alloc_path_for_send();
5793	if (!path)
5794		return -ENOMEM;
5795
5796	key.objectid = BTRFS_FIRST_FREE_OBJECTID;
5797	key.type = BTRFS_INODE_ITEM_KEY;
5798	key.offset = 0;
5799
5800	ret = btrfs_search_slot_for_read(send_root, &key, path, 1, 0);
5801	if (ret < 0)
5802		goto out;
5803	if (ret)
5804		goto out_finish;
5805
5806	while (1) {
5807		eb = path->nodes[0];
5808		slot = path->slots[0];
5809		btrfs_item_key_to_cpu(eb, &found_key, slot);
5810
5811		ret = changed_cb(send_root, NULL, path, NULL,
5812				&found_key, BTRFS_COMPARE_TREE_NEW, sctx);
5813		if (ret < 0)
5814			goto out;
5815
5816		key.objectid = found_key.objectid;
5817		key.type = found_key.type;
5818		key.offset = found_key.offset + 1;
5819
5820		ret = btrfs_next_item(send_root, path);
5821		if (ret < 0)
5822			goto out;
5823		if (ret) {
5824			ret  = 0;
5825			break;
5826		}
5827	}
5828
5829out_finish:
5830	ret = finish_inode_if_needed(sctx, 1);
5831
5832out:
5833	btrfs_free_path(path);
5834	return ret;
5835}
5836
5837static int send_subvol(struct send_ctx *sctx)
5838{
5839	int ret;
5840
5841	if (!(sctx->flags & BTRFS_SEND_FLAG_OMIT_STREAM_HEADER)) {
5842		ret = send_header(sctx);
5843		if (ret < 0)
5844			goto out;
5845	}
5846
5847	ret = send_subvol_begin(sctx);
5848	if (ret < 0)
5849		goto out;
5850
5851	if (sctx->parent_root) {
5852		ret = btrfs_compare_trees(sctx->send_root, sctx->parent_root,
5853				changed_cb, sctx);
5854		if (ret < 0)
5855			goto out;
5856		ret = finish_inode_if_needed(sctx, 1);
5857		if (ret < 0)
5858			goto out;
5859	} else {
5860		ret = full_send_tree(sctx);
5861		if (ret < 0)
5862			goto out;
5863	}
5864
5865out:
5866	free_recorded_refs(sctx);
5867	return ret;
5868}
5869
5870/*
5871 * If orphan cleanup did remove any orphans from a root, it means the tree
5872 * was modified and therefore the commit root is not the same as the current
5873 * root anymore. This is a problem, because send uses the commit root and
5874 * therefore can see inode items that don't exist in the current root anymore,
5875 * and for example make calls to btrfs_iget, which will do tree lookups based
5876 * on the current root and not on the commit root. Those lookups will fail,
5877 * returning a -ESTALE error, and making send fail with that error. So make
5878 * sure a send does not see any orphans we have just removed, and that it will
5879 * see the same inodes regardless of whether a transaction commit happened
5880 * before it started (meaning that the commit root will be the same as the
5881 * current root) or not.
5882 */
5883static int ensure_commit_roots_uptodate(struct send_ctx *sctx)
5884{
5885	int i;
5886	struct btrfs_trans_handle *trans = NULL;
5887
5888again:
5889	if (sctx->parent_root &&
5890	    sctx->parent_root->node != sctx->parent_root->commit_root)
5891		goto commit_trans;
5892
5893	for (i = 0; i < sctx->clone_roots_cnt; i++)
5894		if (sctx->clone_roots[i].root->node !=
5895		    sctx->clone_roots[i].root->commit_root)
5896			goto commit_trans;
5897
5898	if (trans)
5899		return btrfs_end_transaction(trans, sctx->send_root);
5900
5901	return 0;
5902
5903commit_trans:
5904	/* Use any root, all fs roots will get their commit roots updated. */
5905	if (!trans) {
5906		trans = btrfs_join_transaction(sctx->send_root);
5907		if (IS_ERR(trans))
5908			return PTR_ERR(trans);
5909		goto again;
5910	}
5911
5912	return btrfs_commit_transaction(trans, sctx->send_root);
5913}
5914
5915static void btrfs_root_dec_send_in_progress(struct btrfs_root* root)
5916{
5917	spin_lock(&root->root_item_lock);
5918	root->send_in_progress--;
5919	/*
5920	 * Not much left to do, we don't know why it's unbalanced and
5921	 * can't blindly reset it to 0.
5922	 */
5923	if (root->send_in_progress < 0)
5924		btrfs_err(root->fs_info,
5925			"send_in_progres unbalanced %d root %llu",
5926			root->send_in_progress, root->root_key.objectid);
5927	spin_unlock(&root->root_item_lock);
5928}
5929
5930long btrfs_ioctl_send(struct file *mnt_file, void __user *arg_)
5931{
5932	int ret = 0;
5933	struct btrfs_root *send_root;
5934	struct btrfs_root *clone_root;
5935	struct btrfs_fs_info *fs_info;
5936	struct btrfs_ioctl_send_args *arg = NULL;
5937	struct btrfs_key key;
5938	struct send_ctx *sctx = NULL;
5939	u32 i;
5940	u64 *clone_sources_tmp = NULL;
5941	int clone_sources_to_rollback = 0;
5942	int sort_clone_roots = 0;
5943	int index;
5944
5945	if (!capable(CAP_SYS_ADMIN))
5946		return -EPERM;
5947
5948	send_root = BTRFS_I(file_inode(mnt_file))->root;
5949	fs_info = send_root->fs_info;
5950
5951	/*
5952	 * The subvolume must remain read-only during send, protect against
5953	 * making it RW. This also protects against deletion.
5954	 */
5955	spin_lock(&send_root->root_item_lock);
5956	send_root->send_in_progress++;
5957	spin_unlock(&send_root->root_item_lock);
5958
5959	/*
5960	 * This is done when we lookup the root, it should already be complete
5961	 * by the time we get here.
5962	 */
5963	WARN_ON(send_root->orphan_cleanup_state != ORPHAN_CLEANUP_DONE);
5964
5965	/*
5966	 * Userspace tools do the checks and warn the user if it's
5967	 * not RO.
5968	 */
5969	if (!btrfs_root_readonly(send_root)) {
5970		ret = -EPERM;
5971		goto out;
5972	}
5973
5974	arg = memdup_user(arg_, sizeof(*arg));
5975	if (IS_ERR(arg)) {
5976		ret = PTR_ERR(arg);
5977		arg = NULL;
5978		goto out;
5979	}
5980
5981	if (!access_ok(VERIFY_READ, arg->clone_sources,
5982			sizeof(*arg->clone_sources) *
5983			arg->clone_sources_count)) {
5984		ret = -EFAULT;
5985		goto out;
5986	}
5987
5988	if (arg->flags & ~BTRFS_SEND_FLAG_MASK) {
5989		ret = -EINVAL;
5990		goto out;
5991	}
5992
5993	sctx = kzalloc(sizeof(struct send_ctx), GFP_KERNEL);
5994	if (!sctx) {
5995		ret = -ENOMEM;
5996		goto out;
5997	}
5998
5999	INIT_LIST_HEAD(&sctx->new_refs);
6000	INIT_LIST_HEAD(&sctx->deleted_refs);
6001	INIT_RADIX_TREE(&sctx->name_cache, GFP_KERNEL);
6002	INIT_LIST_HEAD(&sctx->name_cache_list);
6003
6004	sctx->flags = arg->flags;
6005
6006	sctx->send_filp = fget(arg->send_fd);
6007	if (!sctx->send_filp) {
6008		ret = -EBADF;
6009		goto out;
6010	}
6011
6012	sctx->send_root = send_root;
6013	/*
6014	 * Unlikely but possible, if the subvolume is marked for deletion but
6015	 * is slow to remove the directory entry, send can still be started
6016	 */
6017	if (btrfs_root_dead(sctx->send_root)) {
6018		ret = -EPERM;
6019		goto out;
6020	}
6021
6022	sctx->clone_roots_cnt = arg->clone_sources_count;
6023
6024	sctx->send_max_size = BTRFS_SEND_BUF_SIZE;
6025	sctx->send_buf = vmalloc(sctx->send_max_size);
6026	if (!sctx->send_buf) {
6027		ret = -ENOMEM;
6028		goto out;
6029	}
6030
6031	sctx->read_buf = vmalloc(BTRFS_SEND_READ_SIZE);
6032	if (!sctx->read_buf) {
6033		ret = -ENOMEM;
6034		goto out;
6035	}
6036
6037	sctx->pending_dir_moves = RB_ROOT;
6038	sctx->waiting_dir_moves = RB_ROOT;
6039	sctx->orphan_dirs = RB_ROOT;
6040
6041	sctx->clone_roots = vzalloc(sizeof(struct clone_root) *
6042			(arg->clone_sources_count + 1));
6043	if (!sctx->clone_roots) {
6044		ret = -ENOMEM;
6045		goto out;
6046	}
6047
6048	if (arg->clone_sources_count) {
6049		clone_sources_tmp = vmalloc(arg->clone_sources_count *
6050				sizeof(*arg->clone_sources));
6051		if (!clone_sources_tmp) {
6052			ret = -ENOMEM;
6053			goto out;
6054		}
6055
6056		ret = copy_from_user(clone_sources_tmp, arg->clone_sources,
6057				arg->clone_sources_count *
6058				sizeof(*arg->clone_sources));
6059		if (ret) {
6060			ret = -EFAULT;
6061			goto out;
6062		}
6063
6064		for (i = 0; i < arg->clone_sources_count; i++) {
6065			key.objectid = clone_sources_tmp[i];
6066			key.type = BTRFS_ROOT_ITEM_KEY;
6067			key.offset = (u64)-1;
6068
6069			index = srcu_read_lock(&fs_info->subvol_srcu);
6070
6071			clone_root = btrfs_read_fs_root_no_name(fs_info, &key);
6072			if (IS_ERR(clone_root)) {
6073				srcu_read_unlock(&fs_info->subvol_srcu, index);
6074				ret = PTR_ERR(clone_root);
6075				goto out;
6076			}
6077			spin_lock(&clone_root->root_item_lock);
6078			if (!btrfs_root_readonly(clone_root) ||
6079			    btrfs_root_dead(clone_root)) {
6080				spin_unlock(&clone_root->root_item_lock);
6081				srcu_read_unlock(&fs_info->subvol_srcu, index);
6082				ret = -EPERM;
6083				goto out;
6084			}
6085			clone_root->send_in_progress++;
6086			spin_unlock(&clone_root->root_item_lock);
6087			srcu_read_unlock(&fs_info->subvol_srcu, index);
6088
6089			sctx->clone_roots[i].root = clone_root;
6090			clone_sources_to_rollback = i + 1;
6091		}
6092		vfree(clone_sources_tmp);
6093		clone_sources_tmp = NULL;
6094	}
6095
6096	if (arg->parent_root) {
6097		key.objectid = arg->parent_root;
6098		key.type = BTRFS_ROOT_ITEM_KEY;
6099		key.offset = (u64)-1;
6100
6101		index = srcu_read_lock(&fs_info->subvol_srcu);
6102
6103		sctx->parent_root = btrfs_read_fs_root_no_name(fs_info, &key);
6104		if (IS_ERR(sctx->parent_root)) {
6105			srcu_read_unlock(&fs_info->subvol_srcu, index);
6106			ret = PTR_ERR(sctx->parent_root);
6107			goto out;
6108		}
6109
6110		spin_lock(&sctx->parent_root->root_item_lock);
6111		sctx->parent_root->send_in_progress++;
6112		if (!btrfs_root_readonly(sctx->parent_root) ||
6113				btrfs_root_dead(sctx->parent_root)) {
6114			spin_unlock(&sctx->parent_root->root_item_lock);
6115			srcu_read_unlock(&fs_info->subvol_srcu, index);
6116			ret = -EPERM;
6117			goto out;
6118		}
6119		spin_unlock(&sctx->parent_root->root_item_lock);
6120
6121		srcu_read_unlock(&fs_info->subvol_srcu, index);
6122	}
6123
6124	/*
6125	 * Clones from send_root are allowed, but only if the clone source
6126	 * is behind the current send position. This is checked while searching
6127	 * for possible clone sources.
6128	 */
6129	sctx->clone_roots[sctx->clone_roots_cnt++].root = sctx->send_root;
6130
6131	/* We do a bsearch later */
6132	sort(sctx->clone_roots, sctx->clone_roots_cnt,
6133			sizeof(*sctx->clone_roots), __clone_root_cmp_sort,
6134			NULL);
6135	sort_clone_roots = 1;
6136
6137	ret = ensure_commit_roots_uptodate(sctx);
6138	if (ret)
6139		goto out;
6140
6141	current->journal_info = BTRFS_SEND_TRANS_STUB;
6142	ret = send_subvol(sctx);
6143	current->journal_info = NULL;
6144	if (ret < 0)
6145		goto out;
6146
6147	if (!(sctx->flags & BTRFS_SEND_FLAG_OMIT_END_CMD)) {
6148		ret = begin_cmd(sctx, BTRFS_SEND_C_END);
6149		if (ret < 0)
6150			goto out;
6151		ret = send_cmd(sctx);
6152		if (ret < 0)
6153			goto out;
6154	}
6155
6156out:
6157	WARN_ON(sctx && !ret && !RB_EMPTY_ROOT(&sctx->pending_dir_moves));
6158	while (sctx && !RB_EMPTY_ROOT(&sctx->pending_dir_moves)) {
6159		struct rb_node *n;
6160		struct pending_dir_move *pm;
6161
6162		n = rb_first(&sctx->pending_dir_moves);
6163		pm = rb_entry(n, struct pending_dir_move, node);
6164		while (!list_empty(&pm->list)) {
6165			struct pending_dir_move *pm2;
6166
6167			pm2 = list_first_entry(&pm->list,
6168					       struct pending_dir_move, list);
6169			free_pending_move(sctx, pm2);
6170		}
6171		free_pending_move(sctx, pm);
6172	}
6173
6174	WARN_ON(sctx && !ret && !RB_EMPTY_ROOT(&sctx->waiting_dir_moves));
6175	while (sctx && !RB_EMPTY_ROOT(&sctx->waiting_dir_moves)) {
6176		struct rb_node *n;
6177		struct waiting_dir_move *dm;
6178
6179		n = rb_first(&sctx->waiting_dir_moves);
6180		dm = rb_entry(n, struct waiting_dir_move, node);
6181		rb_erase(&dm->node, &sctx->waiting_dir_moves);
6182		kfree(dm);
6183	}
6184
6185	WARN_ON(sctx && !ret && !RB_EMPTY_ROOT(&sctx->orphan_dirs));
6186	while (sctx && !RB_EMPTY_ROOT(&sctx->orphan_dirs)) {
6187		struct rb_node *n;
6188		struct orphan_dir_info *odi;
6189
6190		n = rb_first(&sctx->orphan_dirs);
6191		odi = rb_entry(n, struct orphan_dir_info, node);
6192		free_orphan_dir_info(sctx, odi);
6193	}
6194
6195	if (sort_clone_roots) {
6196		for (i = 0; i < sctx->clone_roots_cnt; i++)
6197			btrfs_root_dec_send_in_progress(
6198					sctx->clone_roots[i].root);
6199	} else {
6200		for (i = 0; sctx && i < clone_sources_to_rollback; i++)
6201			btrfs_root_dec_send_in_progress(
6202					sctx->clone_roots[i].root);
6203
6204		btrfs_root_dec_send_in_progress(send_root);
6205	}
6206	if (sctx && !IS_ERR_OR_NULL(sctx->parent_root))
6207		btrfs_root_dec_send_in_progress(sctx->parent_root);
6208
6209	kfree(arg);
6210	vfree(clone_sources_tmp);
6211
6212	if (sctx) {
6213		if (sctx->send_filp)
6214			fput(sctx->send_filp);
6215
6216		vfree(sctx->clone_roots);
6217		vfree(sctx->send_buf);
6218		vfree(sctx->read_buf);
6219
6220		name_cache_free(sctx);
6221
6222		kfree(sctx);
6223	}
6224
6225	return ret;
6226}