1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (C) 2012 Alexander Block. All rights reserved.
6 #include <linux/bsearch.h>
8 #include <linux/file.h>
9 #include <linux/sort.h>
10 #include <linux/mount.h>
11 #include <linux/xattr.h>
12 #include <linux/posix_acl_xattr.h>
13 #include <linux/radix-tree.h>
14 #include <linux/vmalloc.h>
15 #include <linux/string.h>
16 #include <linux/compat.h>
17 #include <linux/crc32c.h>
18 #include <linux/fsverity.h>
25 #include "btrfs_inode.h"
26 #include "transaction.h"
27 #include "compression.h"
29 #include "print-tree.h"
32 * Maximum number of references an extent can have in order for us to attempt to
33 * issue clone operations instead of write operations. This currently exists to
34 * avoid hitting limitations of the backreference walking code (taking a lot of
35 * time and using too much memory for extents with large number of references).
37 #define SEND_MAX_EXTENT_REFS 64
40 * A fs_path is a helper to dynamically build path names with unknown size.
41 * It reallocates the internal buffer on demand.
42 * It allows fast adding of path elements on the right side (normal path) and
43 * fast adding to the left side (reversed path). A reversed path can also be
44 * unreversed if needed.
53 unsigned short buf_len:15;
54 unsigned short reversed:1;
58 * Average path length does not exceed 200 bytes, we'll have
59 * better packing in the slab and higher chance to satisfy
60 * a allocation later during send.
65 #define FS_PATH_INLINE_SIZE \
66 (sizeof(struct fs_path) - offsetof(struct fs_path, inline_buf))
69 /* reused for each extent */
71 struct btrfs_root *root;
78 #define SEND_CTX_MAX_NAME_CACHE_SIZE 128
79 #define SEND_CTX_NAME_CACHE_CLEAN_SIZE (SEND_CTX_MAX_NAME_CACHE_SIZE * 2)
82 struct file *send_filp;
88 * Whether BTRFS_SEND_A_DATA attribute was already added to current
89 * command (since protocol v2, data must be the last attribute).
92 struct page **send_buf_pages;
93 u64 flags; /* 'flags' member of btrfs_ioctl_send_args is u64 */
94 /* Protocol version compatibility requested */
97 struct btrfs_root *send_root;
98 struct btrfs_root *parent_root;
99 struct clone_root *clone_roots;
102 /* current state of the compare_tree call */
103 struct btrfs_path *left_path;
104 struct btrfs_path *right_path;
105 struct btrfs_key *cmp_key;
108 * Keep track of the generation of the last transaction that was used
109 * for relocating a block group. This is periodically checked in order
110 * to detect if a relocation happened since the last check, so that we
111 * don't operate on stale extent buffers for nodes (level >= 1) or on
112 * stale disk_bytenr values of file extent items.
114 u64 last_reloc_trans;
117 * infos of the currently processed inode. In case of deleted inodes,
118 * these are the values from the deleted inode.
125 u64 cur_inode_last_extent;
126 u64 cur_inode_next_write_offset;
128 bool cur_inode_new_gen;
129 bool cur_inode_deleted;
130 bool ignore_cur_inode;
131 bool cur_inode_needs_verity;
132 void *verity_descriptor;
136 struct list_head new_refs;
137 struct list_head deleted_refs;
139 struct radix_tree_root name_cache;
140 struct list_head name_cache_list;
144 * The inode we are currently processing. It's not NULL only when we
145 * need to issue write commands for data extents from this inode.
147 struct inode *cur_inode;
148 struct file_ra_state ra;
149 u64 page_cache_clear_start;
150 bool clean_page_cache;
153 * We process inodes by their increasing order, so if before an
154 * incremental send we reverse the parent/child relationship of
155 * directories such that a directory with a lower inode number was
156 * the parent of a directory with a higher inode number, and the one
157 * becoming the new parent got renamed too, we can't rename/move the
158 * directory with lower inode number when we finish processing it - we
159 * must process the directory with higher inode number first, then
160 * rename/move it and then rename/move the directory with lower inode
161 * number. Example follows.
163 * Tree state when the first send was performed:
175 * Tree state when the second (incremental) send is performed:
184 * The sequence of steps that lead to the second state was:
186 * mv /a/b/c/d /a/b/c2/d2
187 * mv /a/b/c /a/b/c2/d2/cc
189 * "c" has lower inode number, but we can't move it (2nd mv operation)
190 * before we move "d", which has higher inode number.
192 * So we just memorize which move/rename operations must be performed
193 * later when their respective parent is processed and moved/renamed.
196 /* Indexed by parent directory inode number. */
197 struct rb_root pending_dir_moves;
200 * Reverse index, indexed by the inode number of a directory that
201 * is waiting for the move/rename of its immediate parent before its
202 * own move/rename can be performed.
204 struct rb_root waiting_dir_moves;
207 * A directory that is going to be rm'ed might have a child directory
208 * which is in the pending directory moves index above. In this case,
209 * the directory can only be removed after the move/rename of its child
210 * is performed. Example:
230 * Sequence of steps that lead to the send snapshot:
231 * rm -f /a/b/c/foo.txt
233 * mv /a/b/c/x /a/b/YY
236 * When the child is processed, its move/rename is delayed until its
237 * parent is processed (as explained above), but all other operations
238 * like update utimes, chown, chgrp, etc, are performed and the paths
239 * that it uses for those operations must use the orphanized name of
240 * its parent (the directory we're going to rm later), so we need to
241 * memorize that name.
243 * Indexed by the inode number of the directory to be deleted.
245 struct rb_root orphan_dirs;
247 struct rb_root rbtree_new_refs;
248 struct rb_root rbtree_deleted_refs;
251 struct pending_dir_move {
253 struct list_head list;
257 struct list_head update_refs;
260 struct waiting_dir_move {
264 * There might be some directory that could not be removed because it
265 * was waiting for this directory inode to be moved first. Therefore
266 * after this directory is moved, we can try to rmdir the ino rmdir_ino.
273 struct orphan_dir_info {
277 u64 last_dir_index_offset;
280 struct name_cache_entry {
281 struct list_head list;
283 * radix_tree has only 32bit entries but we need to handle 64bit inums.
284 * We use the lower 32bit of the 64bit inum to store it in the tree. If
285 * more then one inum would fall into the same entry, we use radix_list
286 * to store the additional entries. radix_list is also used to store
287 * entries where two entries have the same inum but different
290 struct list_head radix_list;
296 int need_later_update;
302 #define ADVANCE_ONLY_NEXT -1
304 enum btrfs_compare_tree_result {
305 BTRFS_COMPARE_TREE_NEW,
306 BTRFS_COMPARE_TREE_DELETED,
307 BTRFS_COMPARE_TREE_CHANGED,
308 BTRFS_COMPARE_TREE_SAME,
312 static void inconsistent_snapshot_error(struct send_ctx *sctx,
313 enum btrfs_compare_tree_result result,
316 const char *result_string;
319 case BTRFS_COMPARE_TREE_NEW:
320 result_string = "new";
322 case BTRFS_COMPARE_TREE_DELETED:
323 result_string = "deleted";
325 case BTRFS_COMPARE_TREE_CHANGED:
326 result_string = "updated";
328 case BTRFS_COMPARE_TREE_SAME:
330 result_string = "unchanged";
334 result_string = "unexpected";
337 btrfs_err(sctx->send_root->fs_info,
338 "Send: inconsistent snapshot, found %s %s for inode %llu without updated inode item, send root is %llu, parent root is %llu",
339 result_string, what, sctx->cmp_key->objectid,
340 sctx->send_root->root_key.objectid,
342 sctx->parent_root->root_key.objectid : 0));
346 static bool proto_cmd_ok(const struct send_ctx *sctx, int cmd)
348 switch (sctx->proto) {
349 case 1: return cmd <= BTRFS_SEND_C_MAX_V1;
350 case 2: return cmd <= BTRFS_SEND_C_MAX_V2;
351 case 3: return cmd <= BTRFS_SEND_C_MAX_V3;
352 default: return false;
356 static int is_waiting_for_move(struct send_ctx *sctx, u64 ino);
358 static struct waiting_dir_move *
359 get_waiting_dir_move(struct send_ctx *sctx, u64 ino);
361 static int is_waiting_for_rm(struct send_ctx *sctx, u64 dir_ino, u64 gen);
363 static int need_send_hole(struct send_ctx *sctx)
365 return (sctx->parent_root && !sctx->cur_inode_new &&
366 !sctx->cur_inode_new_gen && !sctx->cur_inode_deleted &&
367 S_ISREG(sctx->cur_inode_mode));
370 static void fs_path_reset(struct fs_path *p)
373 p->start = p->buf + p->buf_len - 1;
383 static struct fs_path *fs_path_alloc(void)
387 p = kmalloc(sizeof(*p), GFP_KERNEL);
391 p->buf = p->inline_buf;
392 p->buf_len = FS_PATH_INLINE_SIZE;
397 static struct fs_path *fs_path_alloc_reversed(void)
409 static void fs_path_free(struct fs_path *p)
413 if (p->buf != p->inline_buf)
418 static int fs_path_len(struct fs_path *p)
420 return p->end - p->start;
423 static int fs_path_ensure_buf(struct fs_path *p, int len)
431 if (p->buf_len >= len)
434 if (len > PATH_MAX) {
439 path_len = p->end - p->start;
440 old_buf_len = p->buf_len;
443 * First time the inline_buf does not suffice
445 if (p->buf == p->inline_buf) {
446 tmp_buf = kmalloc(len, GFP_KERNEL);
448 memcpy(tmp_buf, p->buf, old_buf_len);
450 tmp_buf = krealloc(p->buf, len, GFP_KERNEL);
456 * The real size of the buffer is bigger, this will let the fast path
457 * happen most of the time
459 p->buf_len = ksize(p->buf);
462 tmp_buf = p->buf + old_buf_len - path_len - 1;
463 p->end = p->buf + p->buf_len - 1;
464 p->start = p->end - path_len;
465 memmove(p->start, tmp_buf, path_len + 1);
468 p->end = p->start + path_len;
473 static int fs_path_prepare_for_add(struct fs_path *p, int name_len,
479 new_len = p->end - p->start + name_len;
480 if (p->start != p->end)
482 ret = fs_path_ensure_buf(p, new_len);
487 if (p->start != p->end)
489 p->start -= name_len;
490 *prepared = p->start;
492 if (p->start != p->end)
503 static int fs_path_add(struct fs_path *p, const char *name, int name_len)
508 ret = fs_path_prepare_for_add(p, name_len, &prepared);
511 memcpy(prepared, name, name_len);
517 static int fs_path_add_path(struct fs_path *p, struct fs_path *p2)
522 ret = fs_path_prepare_for_add(p, p2->end - p2->start, &prepared);
525 memcpy(prepared, p2->start, p2->end - p2->start);
531 static int fs_path_add_from_extent_buffer(struct fs_path *p,
532 struct extent_buffer *eb,
533 unsigned long off, int len)
538 ret = fs_path_prepare_for_add(p, len, &prepared);
542 read_extent_buffer(eb, prepared, off, len);
548 static int fs_path_copy(struct fs_path *p, struct fs_path *from)
550 p->reversed = from->reversed;
553 return fs_path_add_path(p, from);
556 static void fs_path_unreverse(struct fs_path *p)
565 len = p->end - p->start;
567 p->end = p->start + len;
568 memmove(p->start, tmp, len + 1);
572 static struct btrfs_path *alloc_path_for_send(void)
574 struct btrfs_path *path;
576 path = btrfs_alloc_path();
579 path->search_commit_root = 1;
580 path->skip_locking = 1;
581 path->need_commit_sem = 1;
585 static int write_buf(struct file *filp, const void *buf, u32 len, loff_t *off)
591 ret = kernel_write(filp, buf + pos, len - pos, off);
602 static int tlv_put(struct send_ctx *sctx, u16 attr, const void *data, int len)
604 struct btrfs_tlv_header *hdr;
605 int total_len = sizeof(*hdr) + len;
606 int left = sctx->send_max_size - sctx->send_size;
608 if (WARN_ON_ONCE(sctx->put_data))
611 if (unlikely(left < total_len))
614 hdr = (struct btrfs_tlv_header *) (sctx->send_buf + sctx->send_size);
615 put_unaligned_le16(attr, &hdr->tlv_type);
616 put_unaligned_le16(len, &hdr->tlv_len);
617 memcpy(hdr + 1, data, len);
618 sctx->send_size += total_len;
623 #define TLV_PUT_DEFINE_INT(bits) \
624 static int tlv_put_u##bits(struct send_ctx *sctx, \
625 u##bits attr, u##bits value) \
627 __le##bits __tmp = cpu_to_le##bits(value); \
628 return tlv_put(sctx, attr, &__tmp, sizeof(__tmp)); \
631 TLV_PUT_DEFINE_INT(8)
632 TLV_PUT_DEFINE_INT(32)
633 TLV_PUT_DEFINE_INT(64)
635 static int tlv_put_string(struct send_ctx *sctx, u16 attr,
636 const char *str, int len)
640 return tlv_put(sctx, attr, str, len);
643 static int tlv_put_uuid(struct send_ctx *sctx, u16 attr,
646 return tlv_put(sctx, attr, uuid, BTRFS_UUID_SIZE);
649 static int tlv_put_btrfs_timespec(struct send_ctx *sctx, u16 attr,
650 struct extent_buffer *eb,
651 struct btrfs_timespec *ts)
653 struct btrfs_timespec bts;
654 read_extent_buffer(eb, &bts, (unsigned long)ts, sizeof(bts));
655 return tlv_put(sctx, attr, &bts, sizeof(bts));
659 #define TLV_PUT(sctx, attrtype, data, attrlen) \
661 ret = tlv_put(sctx, attrtype, data, attrlen); \
663 goto tlv_put_failure; \
666 #define TLV_PUT_INT(sctx, attrtype, bits, value) \
668 ret = tlv_put_u##bits(sctx, attrtype, value); \
670 goto tlv_put_failure; \
673 #define TLV_PUT_U8(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 8, data)
674 #define TLV_PUT_U16(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 16, data)
675 #define TLV_PUT_U32(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 32, data)
676 #define TLV_PUT_U64(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 64, data)
677 #define TLV_PUT_STRING(sctx, attrtype, str, len) \
679 ret = tlv_put_string(sctx, attrtype, str, len); \
681 goto tlv_put_failure; \
683 #define TLV_PUT_PATH(sctx, attrtype, p) \
685 ret = tlv_put_string(sctx, attrtype, p->start, \
686 p->end - p->start); \
688 goto tlv_put_failure; \
690 #define TLV_PUT_UUID(sctx, attrtype, uuid) \
692 ret = tlv_put_uuid(sctx, attrtype, uuid); \
694 goto tlv_put_failure; \
696 #define TLV_PUT_BTRFS_TIMESPEC(sctx, attrtype, eb, ts) \
698 ret = tlv_put_btrfs_timespec(sctx, attrtype, eb, ts); \
700 goto tlv_put_failure; \
703 static int send_header(struct send_ctx *sctx)
705 struct btrfs_stream_header hdr;
707 strcpy(hdr.magic, BTRFS_SEND_STREAM_MAGIC);
708 hdr.version = cpu_to_le32(sctx->proto);
709 return write_buf(sctx->send_filp, &hdr, sizeof(hdr),
714 * For each command/item we want to send to userspace, we call this function.
716 static int begin_cmd(struct send_ctx *sctx, int cmd)
718 struct btrfs_cmd_header *hdr;
720 if (WARN_ON(!sctx->send_buf))
723 BUG_ON(sctx->send_size);
725 sctx->send_size += sizeof(*hdr);
726 hdr = (struct btrfs_cmd_header *)sctx->send_buf;
727 put_unaligned_le16(cmd, &hdr->cmd);
732 static int send_cmd(struct send_ctx *sctx)
735 struct btrfs_cmd_header *hdr;
738 hdr = (struct btrfs_cmd_header *)sctx->send_buf;
739 put_unaligned_le32(sctx->send_size - sizeof(*hdr), &hdr->len);
740 put_unaligned_le32(0, &hdr->crc);
742 crc = btrfs_crc32c(0, (unsigned char *)sctx->send_buf, sctx->send_size);
743 put_unaligned_le32(crc, &hdr->crc);
745 ret = write_buf(sctx->send_filp, sctx->send_buf, sctx->send_size,
749 sctx->put_data = false;
755 * Sends a move instruction to user space
757 static int send_rename(struct send_ctx *sctx,
758 struct fs_path *from, struct fs_path *to)
760 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;
763 btrfs_debug(fs_info, "send_rename %s -> %s", from->start, to->start);
765 ret = begin_cmd(sctx, BTRFS_SEND_C_RENAME);
769 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, from);
770 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH_TO, to);
772 ret = send_cmd(sctx);
780 * Sends a link instruction to user space
782 static int send_link(struct send_ctx *sctx,
783 struct fs_path *path, struct fs_path *lnk)
785 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;
788 btrfs_debug(fs_info, "send_link %s -> %s", path->start, lnk->start);
790 ret = begin_cmd(sctx, BTRFS_SEND_C_LINK);
794 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);
795 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH_LINK, lnk);
797 ret = send_cmd(sctx);
805 * Sends an unlink instruction to user space
807 static int send_unlink(struct send_ctx *sctx, struct fs_path *path)
809 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;
812 btrfs_debug(fs_info, "send_unlink %s", path->start);
814 ret = begin_cmd(sctx, BTRFS_SEND_C_UNLINK);
818 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);
820 ret = send_cmd(sctx);
828 * Sends a rmdir instruction to user space
830 static int send_rmdir(struct send_ctx *sctx, struct fs_path *path)
832 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;
835 btrfs_debug(fs_info, "send_rmdir %s", path->start);
837 ret = begin_cmd(sctx, BTRFS_SEND_C_RMDIR);
841 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);
843 ret = send_cmd(sctx);
850 struct btrfs_inode_info {
862 * Helper function to retrieve some fields from an inode item.
864 static int get_inode_info(struct btrfs_root *root, u64 ino,
865 struct btrfs_inode_info *info)
868 struct btrfs_path *path;
869 struct btrfs_inode_item *ii;
870 struct btrfs_key key;
872 path = alloc_path_for_send();
877 key.type = BTRFS_INODE_ITEM_KEY;
879 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
889 ii = btrfs_item_ptr(path->nodes[0], path->slots[0],
890 struct btrfs_inode_item);
891 info->size = btrfs_inode_size(path->nodes[0], ii);
892 info->gen = btrfs_inode_generation(path->nodes[0], ii);
893 info->mode = btrfs_inode_mode(path->nodes[0], ii);
894 info->uid = btrfs_inode_uid(path->nodes[0], ii);
895 info->gid = btrfs_inode_gid(path->nodes[0], ii);
896 info->rdev = btrfs_inode_rdev(path->nodes[0], ii);
897 info->nlink = btrfs_inode_nlink(path->nodes[0], ii);
899 * Transfer the unchanged u64 value of btrfs_inode_item::flags, that's
900 * otherwise logically split to 32/32 parts.
902 info->fileattr = btrfs_inode_flags(path->nodes[0], ii);
905 btrfs_free_path(path);
909 static int get_inode_gen(struct btrfs_root *root, u64 ino, u64 *gen)
912 struct btrfs_inode_info info;
917 ret = get_inode_info(root, ino, &info);
923 typedef int (*iterate_inode_ref_t)(int num, u64 dir, int index,
928 * Helper function to iterate the entries in ONE btrfs_inode_ref or
929 * btrfs_inode_extref.
930 * The iterate callback may return a non zero value to stop iteration. This can
931 * be a negative value for error codes or 1 to simply stop it.
933 * path must point to the INODE_REF or INODE_EXTREF when called.
935 static int iterate_inode_ref(struct btrfs_root *root, struct btrfs_path *path,
936 struct btrfs_key *found_key, int resolve,
937 iterate_inode_ref_t iterate, void *ctx)
939 struct extent_buffer *eb = path->nodes[0];
940 struct btrfs_inode_ref *iref;
941 struct btrfs_inode_extref *extref;
942 struct btrfs_path *tmp_path;
946 int slot = path->slots[0];
953 unsigned long name_off;
954 unsigned long elem_size;
957 p = fs_path_alloc_reversed();
961 tmp_path = alloc_path_for_send();
968 if (found_key->type == BTRFS_INODE_REF_KEY) {
969 ptr = (unsigned long)btrfs_item_ptr(eb, slot,
970 struct btrfs_inode_ref);
971 total = btrfs_item_size(eb, slot);
972 elem_size = sizeof(*iref);
974 ptr = btrfs_item_ptr_offset(eb, slot);
975 total = btrfs_item_size(eb, slot);
976 elem_size = sizeof(*extref);
979 while (cur < total) {
982 if (found_key->type == BTRFS_INODE_REF_KEY) {
983 iref = (struct btrfs_inode_ref *)(ptr + cur);
984 name_len = btrfs_inode_ref_name_len(eb, iref);
985 name_off = (unsigned long)(iref + 1);
986 index = btrfs_inode_ref_index(eb, iref);
987 dir = found_key->offset;
989 extref = (struct btrfs_inode_extref *)(ptr + cur);
990 name_len = btrfs_inode_extref_name_len(eb, extref);
991 name_off = (unsigned long)&extref->name;
992 index = btrfs_inode_extref_index(eb, extref);
993 dir = btrfs_inode_extref_parent(eb, extref);
997 start = btrfs_ref_to_path(root, tmp_path, name_len,
1000 if (IS_ERR(start)) {
1001 ret = PTR_ERR(start);
1004 if (start < p->buf) {
1005 /* overflow , try again with larger buffer */
1006 ret = fs_path_ensure_buf(p,
1007 p->buf_len + p->buf - start);
1010 start = btrfs_ref_to_path(root, tmp_path,
1013 p->buf, p->buf_len);
1014 if (IS_ERR(start)) {
1015 ret = PTR_ERR(start);
1018 BUG_ON(start < p->buf);
1022 ret = fs_path_add_from_extent_buffer(p, eb, name_off,
1028 cur += elem_size + name_len;
1029 ret = iterate(num, dir, index, p, ctx);
1036 btrfs_free_path(tmp_path);
1041 typedef int (*iterate_dir_item_t)(int num, struct btrfs_key *di_key,
1042 const char *name, int name_len,
1043 const char *data, int data_len,
1047 * Helper function to iterate the entries in ONE btrfs_dir_item.
1048 * The iterate callback may return a non zero value to stop iteration. This can
1049 * be a negative value for error codes or 1 to simply stop it.
1051 * path must point to the dir item when called.
1053 static int iterate_dir_item(struct btrfs_root *root, struct btrfs_path *path,
1054 iterate_dir_item_t iterate, void *ctx)
1057 struct extent_buffer *eb;
1058 struct btrfs_dir_item *di;
1059 struct btrfs_key di_key;
1071 * Start with a small buffer (1 page). If later we end up needing more
1072 * space, which can happen for xattrs on a fs with a leaf size greater
1073 * then the page size, attempt to increase the buffer. Typically xattr
1077 buf = kmalloc(buf_len, GFP_KERNEL);
1083 eb = path->nodes[0];
1084 slot = path->slots[0];
1085 di = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);
1088 total = btrfs_item_size(eb, slot);
1091 while (cur < total) {
1092 name_len = btrfs_dir_name_len(eb, di);
1093 data_len = btrfs_dir_data_len(eb, di);
1094 btrfs_dir_item_key_to_cpu(eb, di, &di_key);
1096 if (btrfs_dir_type(eb, di) == BTRFS_FT_XATTR) {
1097 if (name_len > XATTR_NAME_MAX) {
1098 ret = -ENAMETOOLONG;
1101 if (name_len + data_len >
1102 BTRFS_MAX_XATTR_SIZE(root->fs_info)) {
1110 if (name_len + data_len > PATH_MAX) {
1111 ret = -ENAMETOOLONG;
1116 if (name_len + data_len > buf_len) {
1117 buf_len = name_len + data_len;
1118 if (is_vmalloc_addr(buf)) {
1122 char *tmp = krealloc(buf, buf_len,
1123 GFP_KERNEL | __GFP_NOWARN);
1130 buf = kvmalloc(buf_len, GFP_KERNEL);
1138 read_extent_buffer(eb, buf, (unsigned long)(di + 1),
1139 name_len + data_len);
1141 len = sizeof(*di) + name_len + data_len;
1142 di = (struct btrfs_dir_item *)((char *)di + len);
1145 ret = iterate(num, &di_key, buf, name_len, buf + name_len,
1162 static int __copy_first_ref(int num, u64 dir, int index,
1163 struct fs_path *p, void *ctx)
1166 struct fs_path *pt = ctx;
1168 ret = fs_path_copy(pt, p);
1172 /* we want the first only */
1177 * Retrieve the first path of an inode. If an inode has more then one
1178 * ref/hardlink, this is ignored.
1180 static int get_inode_path(struct btrfs_root *root,
1181 u64 ino, struct fs_path *path)
1184 struct btrfs_key key, found_key;
1185 struct btrfs_path *p;
1187 p = alloc_path_for_send();
1191 fs_path_reset(path);
1194 key.type = BTRFS_INODE_REF_KEY;
1197 ret = btrfs_search_slot_for_read(root, &key, p, 1, 0);
1204 btrfs_item_key_to_cpu(p->nodes[0], &found_key, p->slots[0]);
1205 if (found_key.objectid != ino ||
1206 (found_key.type != BTRFS_INODE_REF_KEY &&
1207 found_key.type != BTRFS_INODE_EXTREF_KEY)) {
1212 ret = iterate_inode_ref(root, p, &found_key, 1,
1213 __copy_first_ref, path);
1223 struct backref_ctx {
1224 struct send_ctx *sctx;
1226 /* number of total found references */
1230 * used for clones found in send_root. clones found behind cur_objectid
1231 * and cur_offset are not considered as allowed clones.
1236 /* may be truncated in case it's the last extent in a file */
1239 /* Just to check for bugs in backref resolving */
1243 static int __clone_root_cmp_bsearch(const void *key, const void *elt)
1245 u64 root = (u64)(uintptr_t)key;
1246 const struct clone_root *cr = elt;
1248 if (root < cr->root->root_key.objectid)
1250 if (root > cr->root->root_key.objectid)
1255 static int __clone_root_cmp_sort(const void *e1, const void *e2)
1257 const struct clone_root *cr1 = e1;
1258 const struct clone_root *cr2 = e2;
1260 if (cr1->root->root_key.objectid < cr2->root->root_key.objectid)
1262 if (cr1->root->root_key.objectid > cr2->root->root_key.objectid)
1268 * Called for every backref that is found for the current extent.
1269 * Results are collected in sctx->clone_roots->ino/offset/found_refs
1271 static int __iterate_backrefs(u64 ino, u64 offset, u64 root, void *ctx_)
1273 struct backref_ctx *bctx = ctx_;
1274 struct clone_root *found;
1276 /* First check if the root is in the list of accepted clone sources */
1277 found = bsearch((void *)(uintptr_t)root, bctx->sctx->clone_roots,
1278 bctx->sctx->clone_roots_cnt,
1279 sizeof(struct clone_root),
1280 __clone_root_cmp_bsearch);
1284 if (found->root == bctx->sctx->send_root &&
1285 ino == bctx->cur_objectid &&
1286 offset == bctx->cur_offset) {
1287 bctx->found_itself = 1;
1291 * Make sure we don't consider clones from send_root that are
1292 * behind the current inode/offset.
1294 if (found->root == bctx->sctx->send_root) {
1296 * If the source inode was not yet processed we can't issue a
1297 * clone operation, as the source extent does not exist yet at
1298 * the destination of the stream.
1300 if (ino > bctx->cur_objectid)
1303 * We clone from the inode currently being sent as long as the
1304 * source extent is already processed, otherwise we could try
1305 * to clone from an extent that does not exist yet at the
1306 * destination of the stream.
1308 if (ino == bctx->cur_objectid &&
1309 offset + bctx->extent_len >
1310 bctx->sctx->cur_inode_next_write_offset)
1315 found->found_refs++;
1316 if (ino < found->ino) {
1318 found->offset = offset;
1319 } else if (found->ino == ino) {
1321 * same extent found more then once in the same file.
1323 if (found->offset > offset + bctx->extent_len)
1324 found->offset = offset;
1331 * Given an inode, offset and extent item, it finds a good clone for a clone
1332 * instruction. Returns -ENOENT when none could be found. The function makes
1333 * sure that the returned clone is usable at the point where sending is at the
1334 * moment. This means, that no clones are accepted which lie behind the current
1337 * path must point to the extent item when called.
1339 static int find_extent_clone(struct send_ctx *sctx,
1340 struct btrfs_path *path,
1341 u64 ino, u64 data_offset,
1343 struct clone_root **found)
1345 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;
1351 u64 extent_item_pos;
1353 struct btrfs_file_extent_item *fi;
1354 struct extent_buffer *eb = path->nodes[0];
1355 struct backref_ctx backref_ctx = {0};
1356 struct clone_root *cur_clone_root;
1357 struct btrfs_key found_key;
1358 struct btrfs_path *tmp_path;
1359 struct btrfs_extent_item *ei;
1363 tmp_path = alloc_path_for_send();
1367 /* We only use this path under the commit sem */
1368 tmp_path->need_commit_sem = 0;
1370 if (data_offset >= ino_size) {
1372 * There may be extents that lie behind the file's size.
1373 * I at least had this in combination with snapshotting while
1374 * writing large files.
1380 fi = btrfs_item_ptr(eb, path->slots[0],
1381 struct btrfs_file_extent_item);
1382 extent_type = btrfs_file_extent_type(eb, fi);
1383 if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
1387 compressed = btrfs_file_extent_compression(eb, fi);
1389 num_bytes = btrfs_file_extent_num_bytes(eb, fi);
1390 disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);
1391 if (disk_byte == 0) {
1395 logical = disk_byte + btrfs_file_extent_offset(eb, fi);
1397 down_read(&fs_info->commit_root_sem);
1398 ret = extent_from_logical(fs_info, disk_byte, tmp_path,
1399 &found_key, &flags);
1400 up_read(&fs_info->commit_root_sem);
1404 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
1409 ei = btrfs_item_ptr(tmp_path->nodes[0], tmp_path->slots[0],
1410 struct btrfs_extent_item);
1412 * Backreference walking (iterate_extent_inodes() below) is currently
1413 * too expensive when an extent has a large number of references, both
1414 * in time spent and used memory. So for now just fallback to write
1415 * operations instead of clone operations when an extent has more than
1416 * a certain amount of references.
1418 if (btrfs_extent_refs(tmp_path->nodes[0], ei) > SEND_MAX_EXTENT_REFS) {
1422 btrfs_release_path(tmp_path);
1425 * Setup the clone roots.
1427 for (i = 0; i < sctx->clone_roots_cnt; i++) {
1428 cur_clone_root = sctx->clone_roots + i;
1429 cur_clone_root->ino = (u64)-1;
1430 cur_clone_root->offset = 0;
1431 cur_clone_root->found_refs = 0;
1434 backref_ctx.sctx = sctx;
1435 backref_ctx.found = 0;
1436 backref_ctx.cur_objectid = ino;
1437 backref_ctx.cur_offset = data_offset;
1438 backref_ctx.found_itself = 0;
1439 backref_ctx.extent_len = num_bytes;
1442 * The last extent of a file may be too large due to page alignment.
1443 * We need to adjust extent_len in this case so that the checks in
1444 * __iterate_backrefs work.
1446 if (data_offset + num_bytes >= ino_size)
1447 backref_ctx.extent_len = ino_size - data_offset;
1450 * Now collect all backrefs.
1452 if (compressed == BTRFS_COMPRESS_NONE)
1453 extent_item_pos = logical - found_key.objectid;
1455 extent_item_pos = 0;
1456 ret = iterate_extent_inodes(fs_info, found_key.objectid,
1457 extent_item_pos, 1, __iterate_backrefs,
1458 &backref_ctx, false);
1463 down_read(&fs_info->commit_root_sem);
1464 if (fs_info->last_reloc_trans > sctx->last_reloc_trans) {
1466 * A transaction commit for a transaction in which block group
1467 * relocation was done just happened.
1468 * The disk_bytenr of the file extent item we processed is
1469 * possibly stale, referring to the extent's location before
1470 * relocation. So act as if we haven't found any clone sources
1471 * and fallback to write commands, which will read the correct
1472 * data from the new extent location. Otherwise we will fail
1473 * below because we haven't found our own back reference or we
1474 * could be getting incorrect sources in case the old extent
1475 * was already reallocated after the relocation.
1477 up_read(&fs_info->commit_root_sem);
1481 up_read(&fs_info->commit_root_sem);
1483 if (!backref_ctx.found_itself) {
1484 /* found a bug in backref code? */
1487 "did not find backref in send_root. inode=%llu, offset=%llu, disk_byte=%llu found extent=%llu",
1488 ino, data_offset, disk_byte, found_key.objectid);
1492 btrfs_debug(fs_info,
1493 "find_extent_clone: data_offset=%llu, ino=%llu, num_bytes=%llu, logical=%llu",
1494 data_offset, ino, num_bytes, logical);
1496 if (!backref_ctx.found)
1497 btrfs_debug(fs_info, "no clones found");
1499 cur_clone_root = NULL;
1500 for (i = 0; i < sctx->clone_roots_cnt; i++) {
1501 if (sctx->clone_roots[i].found_refs) {
1502 if (!cur_clone_root)
1503 cur_clone_root = sctx->clone_roots + i;
1504 else if (sctx->clone_roots[i].root == sctx->send_root)
1505 /* prefer clones from send_root over others */
1506 cur_clone_root = sctx->clone_roots + i;
1511 if (cur_clone_root) {
1512 *found = cur_clone_root;
1519 btrfs_free_path(tmp_path);
1523 static int read_symlink(struct btrfs_root *root,
1525 struct fs_path *dest)
1528 struct btrfs_path *path;
1529 struct btrfs_key key;
1530 struct btrfs_file_extent_item *ei;
1536 path = alloc_path_for_send();
1541 key.type = BTRFS_EXTENT_DATA_KEY;
1543 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1548 * An empty symlink inode. Can happen in rare error paths when
1549 * creating a symlink (transaction committed before the inode
1550 * eviction handler removed the symlink inode items and a crash
1551 * happened in between or the subvol was snapshoted in between).
1552 * Print an informative message to dmesg/syslog so that the user
1553 * can delete the symlink.
1555 btrfs_err(root->fs_info,
1556 "Found empty symlink inode %llu at root %llu",
1557 ino, root->root_key.objectid);
1562 ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
1563 struct btrfs_file_extent_item);
1564 type = btrfs_file_extent_type(path->nodes[0], ei);
1565 compression = btrfs_file_extent_compression(path->nodes[0], ei);
1566 BUG_ON(type != BTRFS_FILE_EXTENT_INLINE);
1567 BUG_ON(compression);
1569 off = btrfs_file_extent_inline_start(ei);
1570 len = btrfs_file_extent_ram_bytes(path->nodes[0], ei);
1572 ret = fs_path_add_from_extent_buffer(dest, path->nodes[0], off, len);
1575 btrfs_free_path(path);
1580 * Helper function to generate a file name that is unique in the root of
1581 * send_root and parent_root. This is used to generate names for orphan inodes.
1583 static int gen_unique_name(struct send_ctx *sctx,
1585 struct fs_path *dest)
1588 struct btrfs_path *path;
1589 struct btrfs_dir_item *di;
1594 path = alloc_path_for_send();
1599 len = snprintf(tmp, sizeof(tmp), "o%llu-%llu-%llu",
1601 ASSERT(len < sizeof(tmp));
1603 di = btrfs_lookup_dir_item(NULL, sctx->send_root,
1604 path, BTRFS_FIRST_FREE_OBJECTID,
1605 tmp, strlen(tmp), 0);
1606 btrfs_release_path(path);
1612 /* not unique, try again */
1617 if (!sctx->parent_root) {
1623 di = btrfs_lookup_dir_item(NULL, sctx->parent_root,
1624 path, BTRFS_FIRST_FREE_OBJECTID,
1625 tmp, strlen(tmp), 0);
1626 btrfs_release_path(path);
1632 /* not unique, try again */
1640 ret = fs_path_add(dest, tmp, strlen(tmp));
1643 btrfs_free_path(path);
1648 inode_state_no_change,
1649 inode_state_will_create,
1650 inode_state_did_create,
1651 inode_state_will_delete,
1652 inode_state_did_delete,
1655 static int get_cur_inode_state(struct send_ctx *sctx, u64 ino, u64 gen)
1662 struct btrfs_inode_info info;
1664 ret = get_inode_info(sctx->send_root, ino, &info);
1665 if (ret < 0 && ret != -ENOENT)
1667 left_ret = (info.nlink == 0) ? -ENOENT : ret;
1668 left_gen = info.gen;
1670 if (!sctx->parent_root) {
1671 right_ret = -ENOENT;
1673 ret = get_inode_info(sctx->parent_root, ino, &info);
1674 if (ret < 0 && ret != -ENOENT)
1676 right_ret = (info.nlink == 0) ? -ENOENT : ret;
1677 right_gen = info.gen;
1680 if (!left_ret && !right_ret) {
1681 if (left_gen == gen && right_gen == gen) {
1682 ret = inode_state_no_change;
1683 } else if (left_gen == gen) {
1684 if (ino < sctx->send_progress)
1685 ret = inode_state_did_create;
1687 ret = inode_state_will_create;
1688 } else if (right_gen == gen) {
1689 if (ino < sctx->send_progress)
1690 ret = inode_state_did_delete;
1692 ret = inode_state_will_delete;
1696 } else if (!left_ret) {
1697 if (left_gen == gen) {
1698 if (ino < sctx->send_progress)
1699 ret = inode_state_did_create;
1701 ret = inode_state_will_create;
1705 } else if (!right_ret) {
1706 if (right_gen == gen) {
1707 if (ino < sctx->send_progress)
1708 ret = inode_state_did_delete;
1710 ret = inode_state_will_delete;
1722 static int is_inode_existent(struct send_ctx *sctx, u64 ino, u64 gen)
1726 if (ino == BTRFS_FIRST_FREE_OBJECTID)
1729 ret = get_cur_inode_state(sctx, ino, gen);
1733 if (ret == inode_state_no_change ||
1734 ret == inode_state_did_create ||
1735 ret == inode_state_will_delete)
1745 * Helper function to lookup a dir item in a dir.
1747 static int lookup_dir_item_inode(struct btrfs_root *root,
1748 u64 dir, const char *name, int name_len,
1752 struct btrfs_dir_item *di;
1753 struct btrfs_key key;
1754 struct btrfs_path *path;
1756 path = alloc_path_for_send();
1760 di = btrfs_lookup_dir_item(NULL, root, path,
1761 dir, name, name_len, 0);
1762 if (IS_ERR_OR_NULL(di)) {
1763 ret = di ? PTR_ERR(di) : -ENOENT;
1766 btrfs_dir_item_key_to_cpu(path->nodes[0], di, &key);
1767 if (key.type == BTRFS_ROOT_ITEM_KEY) {
1771 *found_inode = key.objectid;
1774 btrfs_free_path(path);
1779 * Looks up the first btrfs_inode_ref of a given ino. It returns the parent dir,
1780 * generation of the parent dir and the name of the dir entry.
1782 static int get_first_ref(struct btrfs_root *root, u64 ino,
1783 u64 *dir, u64 *dir_gen, struct fs_path *name)
1786 struct btrfs_key key;
1787 struct btrfs_key found_key;
1788 struct btrfs_path *path;
1792 path = alloc_path_for_send();
1797 key.type = BTRFS_INODE_REF_KEY;
1800 ret = btrfs_search_slot_for_read(root, &key, path, 1, 0);
1804 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
1806 if (ret || found_key.objectid != ino ||
1807 (found_key.type != BTRFS_INODE_REF_KEY &&
1808 found_key.type != BTRFS_INODE_EXTREF_KEY)) {
1813 if (found_key.type == BTRFS_INODE_REF_KEY) {
1814 struct btrfs_inode_ref *iref;
1815 iref = btrfs_item_ptr(path->nodes[0], path->slots[0],
1816 struct btrfs_inode_ref);
1817 len = btrfs_inode_ref_name_len(path->nodes[0], iref);
1818 ret = fs_path_add_from_extent_buffer(name, path->nodes[0],
1819 (unsigned long)(iref + 1),
1821 parent_dir = found_key.offset;
1823 struct btrfs_inode_extref *extref;
1824 extref = btrfs_item_ptr(path->nodes[0], path->slots[0],
1825 struct btrfs_inode_extref);
1826 len = btrfs_inode_extref_name_len(path->nodes[0], extref);
1827 ret = fs_path_add_from_extent_buffer(name, path->nodes[0],
1828 (unsigned long)&extref->name, len);
1829 parent_dir = btrfs_inode_extref_parent(path->nodes[0], extref);
1833 btrfs_release_path(path);
1836 ret = get_inode_gen(root, parent_dir, dir_gen);
1844 btrfs_free_path(path);
1848 static int is_first_ref(struct btrfs_root *root,
1850 const char *name, int name_len)
1853 struct fs_path *tmp_name;
1856 tmp_name = fs_path_alloc();
1860 ret = get_first_ref(root, ino, &tmp_dir, NULL, tmp_name);
1864 if (dir != tmp_dir || name_len != fs_path_len(tmp_name)) {
1869 ret = !memcmp(tmp_name->start, name, name_len);
1872 fs_path_free(tmp_name);
1877 * Used by process_recorded_refs to determine if a new ref would overwrite an
1878 * already existing ref. In case it detects an overwrite, it returns the
1879 * inode/gen in who_ino/who_gen.
1880 * When an overwrite is detected, process_recorded_refs does proper orphanizing
1881 * to make sure later references to the overwritten inode are possible.
1882 * Orphanizing is however only required for the first ref of an inode.
1883 * process_recorded_refs does an additional is_first_ref check to see if
1884 * orphanizing is really required.
1886 static int will_overwrite_ref(struct send_ctx *sctx, u64 dir, u64 dir_gen,
1887 const char *name, int name_len,
1888 u64 *who_ino, u64 *who_gen, u64 *who_mode)
1892 u64 other_inode = 0;
1893 struct btrfs_inode_info info;
1895 if (!sctx->parent_root)
1898 ret = is_inode_existent(sctx, dir, dir_gen);
1903 * If we have a parent root we need to verify that the parent dir was
1904 * not deleted and then re-created, if it was then we have no overwrite
1905 * and we can just unlink this entry.
1907 if (sctx->parent_root && dir != BTRFS_FIRST_FREE_OBJECTID) {
1908 ret = get_inode_gen(sctx->parent_root, dir, &gen);
1909 if (ret < 0 && ret != -ENOENT)
1919 ret = lookup_dir_item_inode(sctx->parent_root, dir, name, name_len,
1921 if (ret < 0 && ret != -ENOENT)
1929 * Check if the overwritten ref was already processed. If yes, the ref
1930 * was already unlinked/moved, so we can safely assume that we will not
1931 * overwrite anything at this point in time.
1933 if (other_inode > sctx->send_progress ||
1934 is_waiting_for_move(sctx, other_inode)) {
1935 ret = get_inode_info(sctx->parent_root, other_inode, &info);
1940 *who_ino = other_inode;
1941 *who_gen = info.gen;
1942 *who_mode = info.mode;
1952 * Checks if the ref was overwritten by an already processed inode. This is
1953 * used by __get_cur_name_and_parent to find out if the ref was orphanized and
1954 * thus the orphan name needs be used.
1955 * process_recorded_refs also uses it to avoid unlinking of refs that were
1958 static int did_overwrite_ref(struct send_ctx *sctx,
1959 u64 dir, u64 dir_gen,
1960 u64 ino, u64 ino_gen,
1961 const char *name, int name_len)
1967 if (!sctx->parent_root)
1970 ret = is_inode_existent(sctx, dir, dir_gen);
1974 if (dir != BTRFS_FIRST_FREE_OBJECTID) {
1975 ret = get_inode_gen(sctx->send_root, dir, &gen);
1976 if (ret < 0 && ret != -ENOENT)
1986 /* check if the ref was overwritten by another ref */
1987 ret = lookup_dir_item_inode(sctx->send_root, dir, name, name_len,
1989 if (ret < 0 && ret != -ENOENT)
1992 /* was never and will never be overwritten */
1997 ret = get_inode_gen(sctx->send_root, ow_inode, &gen);
2001 if (ow_inode == ino && gen == ino_gen) {
2007 * We know that it is or will be overwritten. Check this now.
2008 * The current inode being processed might have been the one that caused
2009 * inode 'ino' to be orphanized, therefore check if ow_inode matches
2010 * the current inode being processed.
2012 if ((ow_inode < sctx->send_progress) ||
2013 (ino != sctx->cur_ino && ow_inode == sctx->cur_ino &&
2014 gen == sctx->cur_inode_gen))
2024 * Same as did_overwrite_ref, but also checks if it is the first ref of an inode
2025 * that got overwritten. This is used by process_recorded_refs to determine
2026 * if it has to use the path as returned by get_cur_path or the orphan name.
2028 static int did_overwrite_first_ref(struct send_ctx *sctx, u64 ino, u64 gen)
2031 struct fs_path *name = NULL;
2035 if (!sctx->parent_root)
2038 name = fs_path_alloc();
2042 ret = get_first_ref(sctx->parent_root, ino, &dir, &dir_gen, name);
2046 ret = did_overwrite_ref(sctx, dir, dir_gen, ino, gen,
2047 name->start, fs_path_len(name));
2055 * Insert a name cache entry. On 32bit kernels the radix tree index is 32bit,
2056 * so we need to do some special handling in case we have clashes. This function
2057 * takes care of this with the help of name_cache_entry::radix_list.
2058 * In case of error, nce is kfreed.
2060 static int name_cache_insert(struct send_ctx *sctx,
2061 struct name_cache_entry *nce)
2064 struct list_head *nce_head;
2066 nce_head = radix_tree_lookup(&sctx->name_cache,
2067 (unsigned long)nce->ino);
2069 nce_head = kmalloc(sizeof(*nce_head), GFP_KERNEL);
2074 INIT_LIST_HEAD(nce_head);
2076 ret = radix_tree_insert(&sctx->name_cache, nce->ino, nce_head);
2083 list_add_tail(&nce->radix_list, nce_head);
2084 list_add_tail(&nce->list, &sctx->name_cache_list);
2085 sctx->name_cache_size++;
2090 static void name_cache_delete(struct send_ctx *sctx,
2091 struct name_cache_entry *nce)
2093 struct list_head *nce_head;
2095 nce_head = radix_tree_lookup(&sctx->name_cache,
2096 (unsigned long)nce->ino);
2098 btrfs_err(sctx->send_root->fs_info,
2099 "name_cache_delete lookup failed ino %llu cache size %d, leaking memory",
2100 nce->ino, sctx->name_cache_size);
2103 list_del(&nce->radix_list);
2104 list_del(&nce->list);
2105 sctx->name_cache_size--;
2108 * We may not get to the final release of nce_head if the lookup fails
2110 if (nce_head && list_empty(nce_head)) {
2111 radix_tree_delete(&sctx->name_cache, (unsigned long)nce->ino);
2116 static struct name_cache_entry *name_cache_search(struct send_ctx *sctx,
2119 struct list_head *nce_head;
2120 struct name_cache_entry *cur;
2122 nce_head = radix_tree_lookup(&sctx->name_cache, (unsigned long)ino);
2126 list_for_each_entry(cur, nce_head, radix_list) {
2127 if (cur->ino == ino && cur->gen == gen)
2134 * Remove some entries from the beginning of name_cache_list.
2136 static void name_cache_clean_unused(struct send_ctx *sctx)
2138 struct name_cache_entry *nce;
2140 if (sctx->name_cache_size < SEND_CTX_NAME_CACHE_CLEAN_SIZE)
2143 while (sctx->name_cache_size > SEND_CTX_MAX_NAME_CACHE_SIZE) {
2144 nce = list_entry(sctx->name_cache_list.next,
2145 struct name_cache_entry, list);
2146 name_cache_delete(sctx, nce);
2151 static void name_cache_free(struct send_ctx *sctx)
2153 struct name_cache_entry *nce;
2155 while (!list_empty(&sctx->name_cache_list)) {
2156 nce = list_entry(sctx->name_cache_list.next,
2157 struct name_cache_entry, list);
2158 name_cache_delete(sctx, nce);
2164 * Used by get_cur_path for each ref up to the root.
2165 * Returns 0 if it succeeded.
2166 * Returns 1 if the inode is not existent or got overwritten. In that case, the
2167 * name is an orphan name. This instructs get_cur_path to stop iterating. If 1
2168 * is returned, parent_ino/parent_gen are not guaranteed to be valid.
2169 * Returns <0 in case of error.
2171 static int __get_cur_name_and_parent(struct send_ctx *sctx,
2175 struct fs_path *dest)
2179 struct name_cache_entry *nce = NULL;
2182 * First check if we already did a call to this function with the same
2183 * ino/gen. If yes, check if the cache entry is still up-to-date. If yes
2184 * return the cached result.
2186 nce = name_cache_search(sctx, ino, gen);
2188 if (ino < sctx->send_progress && nce->need_later_update) {
2189 name_cache_delete(sctx, nce);
2194 * Removes the entry from the list and adds it back to
2195 * the end. This marks the entry as recently used so
2196 * that name_cache_clean_unused does not remove it.
2198 list_move_tail(&nce->list, &sctx->name_cache_list);
2200 *parent_ino = nce->parent_ino;
2201 *parent_gen = nce->parent_gen;
2202 ret = fs_path_add(dest, nce->name, nce->name_len);
2211 * If the inode is not existent yet, add the orphan name and return 1.
2212 * This should only happen for the parent dir that we determine in
2213 * record_new_ref_if_needed().
2215 ret = is_inode_existent(sctx, ino, gen);
2220 ret = gen_unique_name(sctx, ino, gen, dest);
2228 * Depending on whether the inode was already processed or not, use
2229 * send_root or parent_root for ref lookup.
2231 if (ino < sctx->send_progress)
2232 ret = get_first_ref(sctx->send_root, ino,
2233 parent_ino, parent_gen, dest);
2235 ret = get_first_ref(sctx->parent_root, ino,
2236 parent_ino, parent_gen, dest);
2241 * Check if the ref was overwritten by an inode's ref that was processed
2242 * earlier. If yes, treat as orphan and return 1.
2244 ret = did_overwrite_ref(sctx, *parent_ino, *parent_gen, ino, gen,
2245 dest->start, dest->end - dest->start);
2249 fs_path_reset(dest);
2250 ret = gen_unique_name(sctx, ino, gen, dest);
2258 * Store the result of the lookup in the name cache.
2260 nce = kmalloc(sizeof(*nce) + fs_path_len(dest) + 1, GFP_KERNEL);
2268 nce->parent_ino = *parent_ino;
2269 nce->parent_gen = *parent_gen;
2270 nce->name_len = fs_path_len(dest);
2272 strcpy(nce->name, dest->start);
2274 if (ino < sctx->send_progress)
2275 nce->need_later_update = 0;
2277 nce->need_later_update = 1;
2279 nce_ret = name_cache_insert(sctx, nce);
2282 name_cache_clean_unused(sctx);
2289 * Magic happens here. This function returns the first ref to an inode as it
2290 * would look like while receiving the stream at this point in time.
2291 * We walk the path up to the root. For every inode in between, we check if it
2292 * was already processed/sent. If yes, we continue with the parent as found
2293 * in send_root. If not, we continue with the parent as found in parent_root.
2294 * If we encounter an inode that was deleted at this point in time, we use the
2295 * inodes "orphan" name instead of the real name and stop. Same with new inodes
2296 * that were not created yet and overwritten inodes/refs.
2298 * When do we have orphan inodes:
2299 * 1. When an inode is freshly created and thus no valid refs are available yet
2300 * 2. When a directory lost all it's refs (deleted) but still has dir items
2301 * inside which were not processed yet (pending for move/delete). If anyone
2302 * tried to get the path to the dir items, it would get a path inside that
2304 * 3. When an inode is moved around or gets new links, it may overwrite the ref
2305 * of an unprocessed inode. If in that case the first ref would be
2306 * overwritten, the overwritten inode gets "orphanized". Later when we
2307 * process this overwritten inode, it is restored at a new place by moving
2310 * sctx->send_progress tells this function at which point in time receiving
2313 static int get_cur_path(struct send_ctx *sctx, u64 ino, u64 gen,
2314 struct fs_path *dest)
2317 struct fs_path *name = NULL;
2318 u64 parent_inode = 0;
2322 name = fs_path_alloc();
2329 fs_path_reset(dest);
2331 while (!stop && ino != BTRFS_FIRST_FREE_OBJECTID) {
2332 struct waiting_dir_move *wdm;
2334 fs_path_reset(name);
2336 if (is_waiting_for_rm(sctx, ino, gen)) {
2337 ret = gen_unique_name(sctx, ino, gen, name);
2340 ret = fs_path_add_path(dest, name);
2344 wdm = get_waiting_dir_move(sctx, ino);
2345 if (wdm && wdm->orphanized) {
2346 ret = gen_unique_name(sctx, ino, gen, name);
2349 ret = get_first_ref(sctx->parent_root, ino,
2350 &parent_inode, &parent_gen, name);
2352 ret = __get_cur_name_and_parent(sctx, ino, gen,
2362 ret = fs_path_add_path(dest, name);
2373 fs_path_unreverse(dest);
2378 * Sends a BTRFS_SEND_C_SUBVOL command/item to userspace
2380 static int send_subvol_begin(struct send_ctx *sctx)
2383 struct btrfs_root *send_root = sctx->send_root;
2384 struct btrfs_root *parent_root = sctx->parent_root;
2385 struct btrfs_path *path;
2386 struct btrfs_key key;
2387 struct btrfs_root_ref *ref;
2388 struct extent_buffer *leaf;
2392 path = btrfs_alloc_path();
2396 name = kmalloc(BTRFS_PATH_NAME_MAX, GFP_KERNEL);
2398 btrfs_free_path(path);
2402 key.objectid = send_root->root_key.objectid;
2403 key.type = BTRFS_ROOT_BACKREF_KEY;
2406 ret = btrfs_search_slot_for_read(send_root->fs_info->tree_root,
2415 leaf = path->nodes[0];
2416 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
2417 if (key.type != BTRFS_ROOT_BACKREF_KEY ||
2418 key.objectid != send_root->root_key.objectid) {
2422 ref = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_root_ref);
2423 namelen = btrfs_root_ref_name_len(leaf, ref);
2424 read_extent_buffer(leaf, name, (unsigned long)(ref + 1), namelen);
2425 btrfs_release_path(path);
2428 ret = begin_cmd(sctx, BTRFS_SEND_C_SNAPSHOT);
2432 ret = begin_cmd(sctx, BTRFS_SEND_C_SUBVOL);
2437 TLV_PUT_STRING(sctx, BTRFS_SEND_A_PATH, name, namelen);
2439 if (!btrfs_is_empty_uuid(sctx->send_root->root_item.received_uuid))
2440 TLV_PUT_UUID(sctx, BTRFS_SEND_A_UUID,
2441 sctx->send_root->root_item.received_uuid);
2443 TLV_PUT_UUID(sctx, BTRFS_SEND_A_UUID,
2444 sctx->send_root->root_item.uuid);
2446 TLV_PUT_U64(sctx, BTRFS_SEND_A_CTRANSID,
2447 btrfs_root_ctransid(&sctx->send_root->root_item));
2449 if (!btrfs_is_empty_uuid(parent_root->root_item.received_uuid))
2450 TLV_PUT_UUID(sctx, BTRFS_SEND_A_CLONE_UUID,
2451 parent_root->root_item.received_uuid);
2453 TLV_PUT_UUID(sctx, BTRFS_SEND_A_CLONE_UUID,
2454 parent_root->root_item.uuid);
2455 TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_CTRANSID,
2456 btrfs_root_ctransid(&sctx->parent_root->root_item));
2459 ret = send_cmd(sctx);
2463 btrfs_free_path(path);
2468 static int send_truncate(struct send_ctx *sctx, u64 ino, u64 gen, u64 size)
2470 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;
2474 btrfs_debug(fs_info, "send_truncate %llu size=%llu", ino, size);
2476 p = fs_path_alloc();
2480 ret = begin_cmd(sctx, BTRFS_SEND_C_TRUNCATE);
2484 ret = get_cur_path(sctx, ino, gen, p);
2487 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
2488 TLV_PUT_U64(sctx, BTRFS_SEND_A_SIZE, size);
2490 ret = send_cmd(sctx);
2498 static int send_chmod(struct send_ctx *sctx, u64 ino, u64 gen, u64 mode)
2500 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;
2504 btrfs_debug(fs_info, "send_chmod %llu mode=%llu", ino, mode);
2506 p = fs_path_alloc();
2510 ret = begin_cmd(sctx, BTRFS_SEND_C_CHMOD);
2514 ret = get_cur_path(sctx, ino, gen, p);
2517 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
2518 TLV_PUT_U64(sctx, BTRFS_SEND_A_MODE, mode & 07777);
2520 ret = send_cmd(sctx);
2528 static int send_fileattr(struct send_ctx *sctx, u64 ino, u64 gen, u64 fileattr)
2530 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;
2534 if (sctx->proto < 2)
2537 btrfs_debug(fs_info, "send_fileattr %llu fileattr=%llu", ino, fileattr);
2539 p = fs_path_alloc();
2543 ret = begin_cmd(sctx, BTRFS_SEND_C_FILEATTR);
2547 ret = get_cur_path(sctx, ino, gen, p);
2550 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
2551 TLV_PUT_U64(sctx, BTRFS_SEND_A_FILEATTR, fileattr);
2553 ret = send_cmd(sctx);
2561 static int send_chown(struct send_ctx *sctx, u64 ino, u64 gen, u64 uid, u64 gid)
2563 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;
2567 btrfs_debug(fs_info, "send_chown %llu uid=%llu, gid=%llu",
2570 p = fs_path_alloc();
2574 ret = begin_cmd(sctx, BTRFS_SEND_C_CHOWN);
2578 ret = get_cur_path(sctx, ino, gen, p);
2581 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
2582 TLV_PUT_U64(sctx, BTRFS_SEND_A_UID, uid);
2583 TLV_PUT_U64(sctx, BTRFS_SEND_A_GID, gid);
2585 ret = send_cmd(sctx);
2593 static int send_utimes(struct send_ctx *sctx, u64 ino, u64 gen)
2595 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;
2597 struct fs_path *p = NULL;
2598 struct btrfs_inode_item *ii;
2599 struct btrfs_path *path = NULL;
2600 struct extent_buffer *eb;
2601 struct btrfs_key key;
2604 btrfs_debug(fs_info, "send_utimes %llu", ino);
2606 p = fs_path_alloc();
2610 path = alloc_path_for_send();
2617 key.type = BTRFS_INODE_ITEM_KEY;
2619 ret = btrfs_search_slot(NULL, sctx->send_root, &key, path, 0, 0);
2625 eb = path->nodes[0];
2626 slot = path->slots[0];
2627 ii = btrfs_item_ptr(eb, slot, struct btrfs_inode_item);
2629 ret = begin_cmd(sctx, BTRFS_SEND_C_UTIMES);
2633 ret = get_cur_path(sctx, ino, gen, p);
2636 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
2637 TLV_PUT_BTRFS_TIMESPEC(sctx, BTRFS_SEND_A_ATIME, eb, &ii->atime);
2638 TLV_PUT_BTRFS_TIMESPEC(sctx, BTRFS_SEND_A_MTIME, eb, &ii->mtime);
2639 TLV_PUT_BTRFS_TIMESPEC(sctx, BTRFS_SEND_A_CTIME, eb, &ii->ctime);
2640 if (sctx->proto >= 2)
2641 TLV_PUT_BTRFS_TIMESPEC(sctx, BTRFS_SEND_A_OTIME, eb, &ii->otime);
2643 ret = send_cmd(sctx);
2648 btrfs_free_path(path);
2653 * Sends a BTRFS_SEND_C_MKXXX or SYMLINK command to user space. We don't have
2654 * a valid path yet because we did not process the refs yet. So, the inode
2655 * is created as orphan.
2657 static int send_create_inode(struct send_ctx *sctx, u64 ino)
2659 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;
2663 struct btrfs_inode_info info;
2668 btrfs_debug(fs_info, "send_create_inode %llu", ino);
2670 p = fs_path_alloc();
2674 if (ino != sctx->cur_ino) {
2675 ret = get_inode_info(sctx->send_root, ino, &info);
2682 gen = sctx->cur_inode_gen;
2683 mode = sctx->cur_inode_mode;
2684 rdev = sctx->cur_inode_rdev;
2687 if (S_ISREG(mode)) {
2688 cmd = BTRFS_SEND_C_MKFILE;
2689 } else if (S_ISDIR(mode)) {
2690 cmd = BTRFS_SEND_C_MKDIR;
2691 } else if (S_ISLNK(mode)) {
2692 cmd = BTRFS_SEND_C_SYMLINK;
2693 } else if (S_ISCHR(mode) || S_ISBLK(mode)) {
2694 cmd = BTRFS_SEND_C_MKNOD;
2695 } else if (S_ISFIFO(mode)) {
2696 cmd = BTRFS_SEND_C_MKFIFO;
2697 } else if (S_ISSOCK(mode)) {
2698 cmd = BTRFS_SEND_C_MKSOCK;
2700 btrfs_warn(sctx->send_root->fs_info, "unexpected inode type %o",
2701 (int)(mode & S_IFMT));
2706 ret = begin_cmd(sctx, cmd);
2710 ret = gen_unique_name(sctx, ino, gen, p);
2714 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
2715 TLV_PUT_U64(sctx, BTRFS_SEND_A_INO, ino);
2717 if (S_ISLNK(mode)) {
2719 ret = read_symlink(sctx->send_root, ino, p);
2722 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH_LINK, p);
2723 } else if (S_ISCHR(mode) || S_ISBLK(mode) ||
2724 S_ISFIFO(mode) || S_ISSOCK(mode)) {
2725 TLV_PUT_U64(sctx, BTRFS_SEND_A_RDEV, new_encode_dev(rdev));
2726 TLV_PUT_U64(sctx, BTRFS_SEND_A_MODE, mode);
2729 ret = send_cmd(sctx);
2741 * We need some special handling for inodes that get processed before the parent
2742 * directory got created. See process_recorded_refs for details.
2743 * This function does the check if we already created the dir out of order.
2745 static int did_create_dir(struct send_ctx *sctx, u64 dir)
2749 struct btrfs_path *path = NULL;
2750 struct btrfs_key key;
2751 struct btrfs_key found_key;
2752 struct btrfs_key di_key;
2753 struct btrfs_dir_item *di;
2755 path = alloc_path_for_send();
2760 key.type = BTRFS_DIR_INDEX_KEY;
2763 btrfs_for_each_slot(sctx->send_root, &key, &found_key, path, iter_ret) {
2764 struct extent_buffer *eb = path->nodes[0];
2766 if (found_key.objectid != key.objectid ||
2767 found_key.type != key.type) {
2772 di = btrfs_item_ptr(eb, path->slots[0], struct btrfs_dir_item);
2773 btrfs_dir_item_key_to_cpu(eb, di, &di_key);
2775 if (di_key.type != BTRFS_ROOT_ITEM_KEY &&
2776 di_key.objectid < sctx->send_progress) {
2781 /* Catch error found during iteration */
2785 btrfs_free_path(path);
2790 * Only creates the inode if it is:
2791 * 1. Not a directory
2792 * 2. Or a directory which was not created already due to out of order
2793 * directories. See did_create_dir and process_recorded_refs for details.
2795 static int send_create_inode_if_needed(struct send_ctx *sctx)
2799 if (S_ISDIR(sctx->cur_inode_mode)) {
2800 ret = did_create_dir(sctx, sctx->cur_ino);
2807 return send_create_inode(sctx, sctx->cur_ino);
2810 struct recorded_ref {
2811 struct list_head list;
2813 struct fs_path *full_path;
2817 struct rb_node node;
2818 struct rb_root *root;
2821 static struct recorded_ref *recorded_ref_alloc(void)
2823 struct recorded_ref *ref;
2825 ref = kzalloc(sizeof(*ref), GFP_KERNEL);
2828 RB_CLEAR_NODE(&ref->node);
2829 INIT_LIST_HEAD(&ref->list);
2833 static void recorded_ref_free(struct recorded_ref *ref)
2837 if (!RB_EMPTY_NODE(&ref->node))
2838 rb_erase(&ref->node, ref->root);
2839 list_del(&ref->list);
2840 fs_path_free(ref->full_path);
2844 static void set_ref_path(struct recorded_ref *ref, struct fs_path *path)
2846 ref->full_path = path;
2847 ref->name = (char *)kbasename(ref->full_path->start);
2848 ref->name_len = ref->full_path->end - ref->name;
2851 static int dup_ref(struct recorded_ref *ref, struct list_head *list)
2853 struct recorded_ref *new;
2855 new = recorded_ref_alloc();
2859 new->dir = ref->dir;
2860 new->dir_gen = ref->dir_gen;
2861 list_add_tail(&new->list, list);
2865 static void __free_recorded_refs(struct list_head *head)
2867 struct recorded_ref *cur;
2869 while (!list_empty(head)) {
2870 cur = list_entry(head->next, struct recorded_ref, list);
2871 recorded_ref_free(cur);
2875 static void free_recorded_refs(struct send_ctx *sctx)
2877 __free_recorded_refs(&sctx->new_refs);
2878 __free_recorded_refs(&sctx->deleted_refs);
2882 * Renames/moves a file/dir to its orphan name. Used when the first
2883 * ref of an unprocessed inode gets overwritten and for all non empty
2886 static int orphanize_inode(struct send_ctx *sctx, u64 ino, u64 gen,
2887 struct fs_path *path)
2890 struct fs_path *orphan;
2892 orphan = fs_path_alloc();
2896 ret = gen_unique_name(sctx, ino, gen, orphan);
2900 ret = send_rename(sctx, path, orphan);
2903 fs_path_free(orphan);
2907 static struct orphan_dir_info *add_orphan_dir_info(struct send_ctx *sctx,
2908 u64 dir_ino, u64 dir_gen)
2910 struct rb_node **p = &sctx->orphan_dirs.rb_node;
2911 struct rb_node *parent = NULL;
2912 struct orphan_dir_info *entry, *odi;
2916 entry = rb_entry(parent, struct orphan_dir_info, node);
2917 if (dir_ino < entry->ino)
2919 else if (dir_ino > entry->ino)
2920 p = &(*p)->rb_right;
2921 else if (dir_gen < entry->gen)
2923 else if (dir_gen > entry->gen)
2924 p = &(*p)->rb_right;
2929 odi = kmalloc(sizeof(*odi), GFP_KERNEL);
2931 return ERR_PTR(-ENOMEM);
2934 odi->last_dir_index_offset = 0;
2936 rb_link_node(&odi->node, parent, p);
2937 rb_insert_color(&odi->node, &sctx->orphan_dirs);
2941 static struct orphan_dir_info *get_orphan_dir_info(struct send_ctx *sctx,
2942 u64 dir_ino, u64 gen)
2944 struct rb_node *n = sctx->orphan_dirs.rb_node;
2945 struct orphan_dir_info *entry;
2948 entry = rb_entry(n, struct orphan_dir_info, node);
2949 if (dir_ino < entry->ino)
2951 else if (dir_ino > entry->ino)
2953 else if (gen < entry->gen)
2955 else if (gen > entry->gen)
2963 static int is_waiting_for_rm(struct send_ctx *sctx, u64 dir_ino, u64 gen)
2965 struct orphan_dir_info *odi = get_orphan_dir_info(sctx, dir_ino, gen);
2970 static void free_orphan_dir_info(struct send_ctx *sctx,
2971 struct orphan_dir_info *odi)
2975 rb_erase(&odi->node, &sctx->orphan_dirs);
2980 * Returns 1 if a directory can be removed at this point in time.
2981 * We check this by iterating all dir items and checking if the inode behind
2982 * the dir item was already processed.
2984 static int can_rmdir(struct send_ctx *sctx, u64 dir, u64 dir_gen,
2989 struct btrfs_root *root = sctx->parent_root;
2990 struct btrfs_path *path;
2991 struct btrfs_key key;
2992 struct btrfs_key found_key;
2993 struct btrfs_key loc;
2994 struct btrfs_dir_item *di;
2995 struct orphan_dir_info *odi = NULL;
2998 * Don't try to rmdir the top/root subvolume dir.
3000 if (dir == BTRFS_FIRST_FREE_OBJECTID)
3003 path = alloc_path_for_send();
3008 key.type = BTRFS_DIR_INDEX_KEY;
3011 odi = get_orphan_dir_info(sctx, dir, dir_gen);
3013 key.offset = odi->last_dir_index_offset;
3015 btrfs_for_each_slot(root, &key, &found_key, path, iter_ret) {
3016 struct waiting_dir_move *dm;
3018 if (found_key.objectid != key.objectid ||
3019 found_key.type != key.type)
3022 di = btrfs_item_ptr(path->nodes[0], path->slots[0],
3023 struct btrfs_dir_item);
3024 btrfs_dir_item_key_to_cpu(path->nodes[0], di, &loc);
3026 dm = get_waiting_dir_move(sctx, loc.objectid);
3028 odi = add_orphan_dir_info(sctx, dir, dir_gen);
3034 odi->last_dir_index_offset = found_key.offset;
3035 dm->rmdir_ino = dir;
3036 dm->rmdir_gen = dir_gen;
3041 if (loc.objectid > send_progress) {
3042 odi = add_orphan_dir_info(sctx, dir, dir_gen);
3048 odi->last_dir_index_offset = found_key.offset;
3057 free_orphan_dir_info(sctx, odi);
3062 btrfs_free_path(path);
3066 static int is_waiting_for_move(struct send_ctx *sctx, u64 ino)
3068 struct waiting_dir_move *entry = get_waiting_dir_move(sctx, ino);
3070 return entry != NULL;
3073 static int add_waiting_dir_move(struct send_ctx *sctx, u64 ino, bool orphanized)
3075 struct rb_node **p = &sctx->waiting_dir_moves.rb_node;
3076 struct rb_node *parent = NULL;
3077 struct waiting_dir_move *entry, *dm;
3079 dm = kmalloc(sizeof(*dm), GFP_KERNEL);
3085 dm->orphanized = orphanized;
3089 entry = rb_entry(parent, struct waiting_dir_move, node);
3090 if (ino < entry->ino) {
3092 } else if (ino > entry->ino) {
3093 p = &(*p)->rb_right;
3100 rb_link_node(&dm->node, parent, p);
3101 rb_insert_color(&dm->node, &sctx->waiting_dir_moves);
3105 static struct waiting_dir_move *
3106 get_waiting_dir_move(struct send_ctx *sctx, u64 ino)
3108 struct rb_node *n = sctx->waiting_dir_moves.rb_node;
3109 struct waiting_dir_move *entry;
3112 entry = rb_entry(n, struct waiting_dir_move, node);
3113 if (ino < entry->ino)
3115 else if (ino > entry->ino)
3123 static void free_waiting_dir_move(struct send_ctx *sctx,
3124 struct waiting_dir_move *dm)
3128 rb_erase(&dm->node, &sctx->waiting_dir_moves);
3132 static int add_pending_dir_move(struct send_ctx *sctx,
3136 struct list_head *new_refs,
3137 struct list_head *deleted_refs,
3138 const bool is_orphan)
3140 struct rb_node **p = &sctx->pending_dir_moves.rb_node;
3141 struct rb_node *parent = NULL;
3142 struct pending_dir_move *entry = NULL, *pm;
3143 struct recorded_ref *cur;
3147 pm = kmalloc(sizeof(*pm), GFP_KERNEL);
3150 pm->parent_ino = parent_ino;
3153 INIT_LIST_HEAD(&pm->list);
3154 INIT_LIST_HEAD(&pm->update_refs);
3155 RB_CLEAR_NODE(&pm->node);
3159 entry = rb_entry(parent, struct pending_dir_move, node);
3160 if (parent_ino < entry->parent_ino) {
3162 } else if (parent_ino > entry->parent_ino) {
3163 p = &(*p)->rb_right;
3170 list_for_each_entry(cur, deleted_refs, list) {
3171 ret = dup_ref(cur, &pm->update_refs);
3175 list_for_each_entry(cur, new_refs, list) {
3176 ret = dup_ref(cur, &pm->update_refs);
3181 ret = add_waiting_dir_move(sctx, pm->ino, is_orphan);
3186 list_add_tail(&pm->list, &entry->list);
3188 rb_link_node(&pm->node, parent, p);
3189 rb_insert_color(&pm->node, &sctx->pending_dir_moves);
3194 __free_recorded_refs(&pm->update_refs);
3200 static struct pending_dir_move *get_pending_dir_moves(struct send_ctx *sctx,
3203 struct rb_node *n = sctx->pending_dir_moves.rb_node;
3204 struct pending_dir_move *entry;
3207 entry = rb_entry(n, struct pending_dir_move, node);
3208 if (parent_ino < entry->parent_ino)
3210 else if (parent_ino > entry->parent_ino)
3218 static int path_loop(struct send_ctx *sctx, struct fs_path *name,
3219 u64 ino, u64 gen, u64 *ancestor_ino)
3222 u64 parent_inode = 0;
3224 u64 start_ino = ino;
3227 while (ino != BTRFS_FIRST_FREE_OBJECTID) {
3228 fs_path_reset(name);
3230 if (is_waiting_for_rm(sctx, ino, gen))
3232 if (is_waiting_for_move(sctx, ino)) {
3233 if (*ancestor_ino == 0)
3234 *ancestor_ino = ino;
3235 ret = get_first_ref(sctx->parent_root, ino,
3236 &parent_inode, &parent_gen, name);
3238 ret = __get_cur_name_and_parent(sctx, ino, gen,
3248 if (parent_inode == start_ino) {
3250 if (*ancestor_ino == 0)
3251 *ancestor_ino = ino;
3260 static int apply_dir_move(struct send_ctx *sctx, struct pending_dir_move *pm)
3262 struct fs_path *from_path = NULL;
3263 struct fs_path *to_path = NULL;
3264 struct fs_path *name = NULL;
3265 u64 orig_progress = sctx->send_progress;
3266 struct recorded_ref *cur;
3267 u64 parent_ino, parent_gen;
3268 struct waiting_dir_move *dm = NULL;
3275 name = fs_path_alloc();
3276 from_path = fs_path_alloc();
3277 if (!name || !from_path) {
3282 dm = get_waiting_dir_move(sctx, pm->ino);
3284 rmdir_ino = dm->rmdir_ino;
3285 rmdir_gen = dm->rmdir_gen;
3286 is_orphan = dm->orphanized;
3287 free_waiting_dir_move(sctx, dm);
3290 ret = gen_unique_name(sctx, pm->ino,
3291 pm->gen, from_path);
3293 ret = get_first_ref(sctx->parent_root, pm->ino,
3294 &parent_ino, &parent_gen, name);
3297 ret = get_cur_path(sctx, parent_ino, parent_gen,
3301 ret = fs_path_add_path(from_path, name);
3306 sctx->send_progress = sctx->cur_ino + 1;
3307 ret = path_loop(sctx, name, pm->ino, pm->gen, &ancestor);
3311 LIST_HEAD(deleted_refs);
3312 ASSERT(ancestor > BTRFS_FIRST_FREE_OBJECTID);
3313 ret = add_pending_dir_move(sctx, pm->ino, pm->gen, ancestor,
3314 &pm->update_refs, &deleted_refs,
3319 dm = get_waiting_dir_move(sctx, pm->ino);
3321 dm->rmdir_ino = rmdir_ino;
3322 dm->rmdir_gen = rmdir_gen;
3326 fs_path_reset(name);
3329 ret = get_cur_path(sctx, pm->ino, pm->gen, to_path);
3333 ret = send_rename(sctx, from_path, to_path);
3338 struct orphan_dir_info *odi;
3341 odi = get_orphan_dir_info(sctx, rmdir_ino, rmdir_gen);
3343 /* already deleted */
3348 ret = can_rmdir(sctx, rmdir_ino, gen, sctx->cur_ino);
3354 name = fs_path_alloc();
3359 ret = get_cur_path(sctx, rmdir_ino, gen, name);
3362 ret = send_rmdir(sctx, name);
3368 ret = send_utimes(sctx, pm->ino, pm->gen);
3373 * After rename/move, need to update the utimes of both new parent(s)
3374 * and old parent(s).
3376 list_for_each_entry(cur, &pm->update_refs, list) {
3378 * The parent inode might have been deleted in the send snapshot
3380 ret = get_inode_info(sctx->send_root, cur->dir, NULL);
3381 if (ret == -ENOENT) {
3388 ret = send_utimes(sctx, cur->dir, cur->dir_gen);
3395 fs_path_free(from_path);
3396 fs_path_free(to_path);
3397 sctx->send_progress = orig_progress;
3402 static void free_pending_move(struct send_ctx *sctx, struct pending_dir_move *m)
3404 if (!list_empty(&m->list))
3406 if (!RB_EMPTY_NODE(&m->node))
3407 rb_erase(&m->node, &sctx->pending_dir_moves);
3408 __free_recorded_refs(&m->update_refs);
3412 static void tail_append_pending_moves(struct send_ctx *sctx,
3413 struct pending_dir_move *moves,
3414 struct list_head *stack)
3416 if (list_empty(&moves->list)) {
3417 list_add_tail(&moves->list, stack);
3420 list_splice_init(&moves->list, &list);
3421 list_add_tail(&moves->list, stack);
3422 list_splice_tail(&list, stack);
3424 if (!RB_EMPTY_NODE(&moves->node)) {
3425 rb_erase(&moves->node, &sctx->pending_dir_moves);
3426 RB_CLEAR_NODE(&moves->node);
3430 static int apply_children_dir_moves(struct send_ctx *sctx)
3432 struct pending_dir_move *pm;
3433 struct list_head stack;
3434 u64 parent_ino = sctx->cur_ino;
3437 pm = get_pending_dir_moves(sctx, parent_ino);
3441 INIT_LIST_HEAD(&stack);
3442 tail_append_pending_moves(sctx, pm, &stack);
3444 while (!list_empty(&stack)) {
3445 pm = list_first_entry(&stack, struct pending_dir_move, list);
3446 parent_ino = pm->ino;
3447 ret = apply_dir_move(sctx, pm);
3448 free_pending_move(sctx, pm);
3451 pm = get_pending_dir_moves(sctx, parent_ino);
3453 tail_append_pending_moves(sctx, pm, &stack);
3458 while (!list_empty(&stack)) {
3459 pm = list_first_entry(&stack, struct pending_dir_move, list);
3460 free_pending_move(sctx, pm);
3466 * We might need to delay a directory rename even when no ancestor directory
3467 * (in the send root) with a higher inode number than ours (sctx->cur_ino) was
3468 * renamed. This happens when we rename a directory to the old name (the name
3469 * in the parent root) of some other unrelated directory that got its rename
3470 * delayed due to some ancestor with higher number that got renamed.
3476 * |---- a/ (ino 257)
3477 * | |---- file (ino 260)
3479 * |---- b/ (ino 258)
3480 * |---- c/ (ino 259)
3484 * |---- a/ (ino 258)
3485 * |---- x/ (ino 259)
3486 * |---- y/ (ino 257)
3487 * |----- file (ino 260)
3489 * Here we can not rename 258 from 'b' to 'a' without the rename of inode 257
3490 * from 'a' to 'x/y' happening first, which in turn depends on the rename of
3491 * inode 259 from 'c' to 'x'. So the order of rename commands the send stream
3494 * 1 - rename 259 from 'c' to 'x'
3495 * 2 - rename 257 from 'a' to 'x/y'
3496 * 3 - rename 258 from 'b' to 'a'
3498 * Returns 1 if the rename of sctx->cur_ino needs to be delayed, 0 if it can
3499 * be done right away and < 0 on error.
3501 static int wait_for_dest_dir_move(struct send_ctx *sctx,
3502 struct recorded_ref *parent_ref,
3503 const bool is_orphan)
3505 struct btrfs_fs_info *fs_info = sctx->parent_root->fs_info;
3506 struct btrfs_path *path;
3507 struct btrfs_key key;
3508 struct btrfs_key di_key;
3509 struct btrfs_dir_item *di;
3513 struct waiting_dir_move *wdm;
3515 if (RB_EMPTY_ROOT(&sctx->waiting_dir_moves))
3518 path = alloc_path_for_send();
3522 key.objectid = parent_ref->dir;
3523 key.type = BTRFS_DIR_ITEM_KEY;
3524 key.offset = btrfs_name_hash(parent_ref->name, parent_ref->name_len);
3526 ret = btrfs_search_slot(NULL, sctx->parent_root, &key, path, 0, 0);
3529 } else if (ret > 0) {
3534 di = btrfs_match_dir_item_name(fs_info, path, parent_ref->name,
3535 parent_ref->name_len);
3541 * di_key.objectid has the number of the inode that has a dentry in the
3542 * parent directory with the same name that sctx->cur_ino is being
3543 * renamed to. We need to check if that inode is in the send root as
3544 * well and if it is currently marked as an inode with a pending rename,
3545 * if it is, we need to delay the rename of sctx->cur_ino as well, so
3546 * that it happens after that other inode is renamed.
3548 btrfs_dir_item_key_to_cpu(path->nodes[0], di, &di_key);
3549 if (di_key.type != BTRFS_INODE_ITEM_KEY) {
3554 ret = get_inode_gen(sctx->parent_root, di_key.objectid, &left_gen);
3557 ret = get_inode_gen(sctx->send_root, di_key.objectid, &right_gen);
3564 /* Different inode, no need to delay the rename of sctx->cur_ino */
3565 if (right_gen != left_gen) {
3570 wdm = get_waiting_dir_move(sctx, di_key.objectid);
3571 if (wdm && !wdm->orphanized) {
3572 ret = add_pending_dir_move(sctx,
3574 sctx->cur_inode_gen,
3577 &sctx->deleted_refs,
3583 btrfs_free_path(path);
3588 * Check if inode ino2, or any of its ancestors, is inode ino1.
3589 * Return 1 if true, 0 if false and < 0 on error.
3591 static int check_ino_in_path(struct btrfs_root *root,
3596 struct fs_path *fs_path)
3601 return ino1_gen == ino2_gen;
3603 while (ino > BTRFS_FIRST_FREE_OBJECTID) {
3608 fs_path_reset(fs_path);
3609 ret = get_first_ref(root, ino, &parent, &parent_gen, fs_path);
3613 return parent_gen == ino1_gen;
3620 * Check if inode ino1 is an ancestor of inode ino2 in the given root for any
3621 * possible path (in case ino2 is not a directory and has multiple hard links).
3622 * Return 1 if true, 0 if false and < 0 on error.
3624 static int is_ancestor(struct btrfs_root *root,
3628 struct fs_path *fs_path)
3630 bool free_fs_path = false;
3633 struct btrfs_path *path = NULL;
3634 struct btrfs_key key;
3637 fs_path = fs_path_alloc();
3640 free_fs_path = true;
3643 path = alloc_path_for_send();
3649 key.objectid = ino2;
3650 key.type = BTRFS_INODE_REF_KEY;
3653 btrfs_for_each_slot(root, &key, &key, path, iter_ret) {
3654 struct extent_buffer *leaf = path->nodes[0];
3655 int slot = path->slots[0];
3659 if (key.objectid != ino2)
3661 if (key.type != BTRFS_INODE_REF_KEY &&
3662 key.type != BTRFS_INODE_EXTREF_KEY)
3665 item_size = btrfs_item_size(leaf, slot);
3666 while (cur_offset < item_size) {
3670 if (key.type == BTRFS_INODE_EXTREF_KEY) {
3672 struct btrfs_inode_extref *extref;
3674 ptr = btrfs_item_ptr_offset(leaf, slot);
3675 extref = (struct btrfs_inode_extref *)
3677 parent = btrfs_inode_extref_parent(leaf,
3679 cur_offset += sizeof(*extref);
3680 cur_offset += btrfs_inode_extref_name_len(leaf,
3683 parent = key.offset;
3684 cur_offset = item_size;
3687 ret = get_inode_gen(root, parent, &parent_gen);
3690 ret = check_ino_in_path(root, ino1, ino1_gen,
3691 parent, parent_gen, fs_path);
3701 btrfs_free_path(path);
3703 fs_path_free(fs_path);
3707 static int wait_for_parent_move(struct send_ctx *sctx,
3708 struct recorded_ref *parent_ref,
3709 const bool is_orphan)
3712 u64 ino = parent_ref->dir;
3713 u64 ino_gen = parent_ref->dir_gen;
3714 u64 parent_ino_before, parent_ino_after;
3715 struct fs_path *path_before = NULL;
3716 struct fs_path *path_after = NULL;
3719 path_after = fs_path_alloc();
3720 path_before = fs_path_alloc();
3721 if (!path_after || !path_before) {
3727 * Our current directory inode may not yet be renamed/moved because some
3728 * ancestor (immediate or not) has to be renamed/moved first. So find if
3729 * such ancestor exists and make sure our own rename/move happens after
3730 * that ancestor is processed to avoid path build infinite loops (done
3731 * at get_cur_path()).
3733 while (ino > BTRFS_FIRST_FREE_OBJECTID) {
3734 u64 parent_ino_after_gen;
3736 if (is_waiting_for_move(sctx, ino)) {
3738 * If the current inode is an ancestor of ino in the
3739 * parent root, we need to delay the rename of the
3740 * current inode, otherwise don't delayed the rename
3741 * because we can end up with a circular dependency
3742 * of renames, resulting in some directories never
3743 * getting the respective rename operations issued in
3744 * the send stream or getting into infinite path build
3747 ret = is_ancestor(sctx->parent_root,
3748 sctx->cur_ino, sctx->cur_inode_gen,
3754 fs_path_reset(path_before);
3755 fs_path_reset(path_after);
3757 ret = get_first_ref(sctx->send_root, ino, &parent_ino_after,
3758 &parent_ino_after_gen, path_after);
3761 ret = get_first_ref(sctx->parent_root, ino, &parent_ino_before,
3763 if (ret < 0 && ret != -ENOENT) {
3765 } else if (ret == -ENOENT) {
3770 len1 = fs_path_len(path_before);
3771 len2 = fs_path_len(path_after);
3772 if (ino > sctx->cur_ino &&
3773 (parent_ino_before != parent_ino_after || len1 != len2 ||
3774 memcmp(path_before->start, path_after->start, len1))) {
3777 ret = get_inode_gen(sctx->parent_root, ino, &parent_ino_gen);
3780 if (ino_gen == parent_ino_gen) {
3785 ino = parent_ino_after;
3786 ino_gen = parent_ino_after_gen;
3790 fs_path_free(path_before);
3791 fs_path_free(path_after);
3794 ret = add_pending_dir_move(sctx,
3796 sctx->cur_inode_gen,
3799 &sctx->deleted_refs,
3808 static int update_ref_path(struct send_ctx *sctx, struct recorded_ref *ref)
3811 struct fs_path *new_path;
3814 * Our reference's name member points to its full_path member string, so
3815 * we use here a new path.
3817 new_path = fs_path_alloc();
3821 ret = get_cur_path(sctx, ref->dir, ref->dir_gen, new_path);
3823 fs_path_free(new_path);
3826 ret = fs_path_add(new_path, ref->name, ref->name_len);
3828 fs_path_free(new_path);
3832 fs_path_free(ref->full_path);
3833 set_ref_path(ref, new_path);
3839 * When processing the new references for an inode we may orphanize an existing
3840 * directory inode because its old name conflicts with one of the new references
3841 * of the current inode. Later, when processing another new reference of our
3842 * inode, we might need to orphanize another inode, but the path we have in the
3843 * reference reflects the pre-orphanization name of the directory we previously
3844 * orphanized. For example:
3846 * parent snapshot looks like:
3849 * |----- f1 (ino 257)
3850 * |----- f2 (ino 258)
3851 * |----- d1/ (ino 259)
3852 * |----- d2/ (ino 260)
3854 * send snapshot looks like:
3857 * |----- d1 (ino 258)
3858 * |----- f2/ (ino 259)
3859 * |----- f2_link/ (ino 260)
3860 * | |----- f1 (ino 257)
3862 * |----- d2 (ino 258)
3864 * When processing inode 257 we compute the name for inode 259 as "d1", and we
3865 * cache it in the name cache. Later when we start processing inode 258, when
3866 * collecting all its new references we set a full path of "d1/d2" for its new
3867 * reference with name "d2". When we start processing the new references we
3868 * start by processing the new reference with name "d1", and this results in
3869 * orphanizing inode 259, since its old reference causes a conflict. Then we
3870 * move on the next new reference, with name "d2", and we find out we must
3871 * orphanize inode 260, as its old reference conflicts with ours - but for the
3872 * orphanization we use a source path corresponding to the path we stored in the
3873 * new reference, which is "d1/d2" and not "o259-6-0/d2" - this makes the
3874 * receiver fail since the path component "d1/" no longer exists, it was renamed
3875 * to "o259-6-0/" when processing the previous new reference. So in this case we
3876 * must recompute the path in the new reference and use it for the new
3877 * orphanization operation.
3879 static int refresh_ref_path(struct send_ctx *sctx, struct recorded_ref *ref)
3884 name = kmemdup(ref->name, ref->name_len, GFP_KERNEL);
3888 fs_path_reset(ref->full_path);
3889 ret = get_cur_path(sctx, ref->dir, ref->dir_gen, ref->full_path);
3893 ret = fs_path_add(ref->full_path, name, ref->name_len);
3897 /* Update the reference's base name pointer. */
3898 set_ref_path(ref, ref->full_path);
3905 * This does all the move/link/unlink/rmdir magic.
3907 static int process_recorded_refs(struct send_ctx *sctx, int *pending_move)
3909 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;
3911 struct recorded_ref *cur;
3912 struct recorded_ref *cur2;
3913 struct list_head check_dirs;
3914 struct fs_path *valid_path = NULL;
3918 int did_overwrite = 0;
3920 u64 last_dir_ino_rm = 0;
3921 bool can_rename = true;
3922 bool orphanized_dir = false;
3923 bool orphanized_ancestor = false;
3925 btrfs_debug(fs_info, "process_recorded_refs %llu", sctx->cur_ino);
3928 * This should never happen as the root dir always has the same ref
3929 * which is always '..'
3931 BUG_ON(sctx->cur_ino <= BTRFS_FIRST_FREE_OBJECTID);
3932 INIT_LIST_HEAD(&check_dirs);
3934 valid_path = fs_path_alloc();
3941 * First, check if the first ref of the current inode was overwritten
3942 * before. If yes, we know that the current inode was already orphanized
3943 * and thus use the orphan name. If not, we can use get_cur_path to
3944 * get the path of the first ref as it would like while receiving at
3945 * this point in time.
3946 * New inodes are always orphan at the beginning, so force to use the
3947 * orphan name in this case.
3948 * The first ref is stored in valid_path and will be updated if it
3949 * gets moved around.
3951 if (!sctx->cur_inode_new) {
3952 ret = did_overwrite_first_ref(sctx, sctx->cur_ino,
3953 sctx->cur_inode_gen);
3959 if (sctx->cur_inode_new || did_overwrite) {
3960 ret = gen_unique_name(sctx, sctx->cur_ino,
3961 sctx->cur_inode_gen, valid_path);
3966 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen,
3973 * Before doing any rename and link operations, do a first pass on the
3974 * new references to orphanize any unprocessed inodes that may have a
3975 * reference that conflicts with one of the new references of the current
3976 * inode. This needs to happen first because a new reference may conflict
3977 * with the old reference of a parent directory, so we must make sure
3978 * that the path used for link and rename commands don't use an
3979 * orphanized name when an ancestor was not yet orphanized.
3986 * |----- testdir/ (ino 259)
3987 * | |----- a (ino 257)
3989 * |----- b (ino 258)
3994 * |----- testdir_2/ (ino 259)
3995 * | |----- a (ino 260)
3997 * |----- testdir (ino 257)
3998 * |----- b (ino 257)
3999 * |----- b2 (ino 258)
4001 * Processing the new reference for inode 257 with name "b" may happen
4002 * before processing the new reference with name "testdir". If so, we
4003 * must make sure that by the time we send a link command to create the
4004 * hard link "b", inode 259 was already orphanized, since the generated
4005 * path in "valid_path" already contains the orphanized name for 259.
4006 * We are processing inode 257, so only later when processing 259 we do
4007 * the rename operation to change its temporary (orphanized) name to
4010 list_for_each_entry(cur, &sctx->new_refs, list) {
4011 ret = get_cur_inode_state(sctx, cur->dir, cur->dir_gen);
4014 if (ret == inode_state_will_create)
4018 * Check if this new ref would overwrite the first ref of another
4019 * unprocessed inode. If yes, orphanize the overwritten inode.
4020 * If we find an overwritten ref that is not the first ref,
4023 ret = will_overwrite_ref(sctx, cur->dir, cur->dir_gen,
4024 cur->name, cur->name_len,
4025 &ow_inode, &ow_gen, &ow_mode);
4029 ret = is_first_ref(sctx->parent_root,
4030 ow_inode, cur->dir, cur->name,
4035 struct name_cache_entry *nce;
4036 struct waiting_dir_move *wdm;
4038 if (orphanized_dir) {
4039 ret = refresh_ref_path(sctx, cur);
4044 ret = orphanize_inode(sctx, ow_inode, ow_gen,
4048 if (S_ISDIR(ow_mode))
4049 orphanized_dir = true;
4052 * If ow_inode has its rename operation delayed
4053 * make sure that its orphanized name is used in
4054 * the source path when performing its rename
4057 if (is_waiting_for_move(sctx, ow_inode)) {
4058 wdm = get_waiting_dir_move(sctx,
4061 wdm->orphanized = true;
4065 * Make sure we clear our orphanized inode's
4066 * name from the name cache. This is because the
4067 * inode ow_inode might be an ancestor of some
4068 * other inode that will be orphanized as well
4069 * later and has an inode number greater than
4070 * sctx->send_progress. We need to prevent
4071 * future name lookups from using the old name
4072 * and get instead the orphan name.
4074 nce = name_cache_search(sctx, ow_inode, ow_gen);
4076 name_cache_delete(sctx, nce);
4081 * ow_inode might currently be an ancestor of
4082 * cur_ino, therefore compute valid_path (the
4083 * current path of cur_ino) again because it
4084 * might contain the pre-orphanization name of
4085 * ow_inode, which is no longer valid.
4087 ret = is_ancestor(sctx->parent_root,
4089 sctx->cur_ino, NULL);
4091 orphanized_ancestor = true;
4092 fs_path_reset(valid_path);
4093 ret = get_cur_path(sctx, sctx->cur_ino,
4094 sctx->cur_inode_gen,
4101 * If we previously orphanized a directory that
4102 * collided with a new reference that we already
4103 * processed, recompute the current path because
4104 * that directory may be part of the path.
4106 if (orphanized_dir) {
4107 ret = refresh_ref_path(sctx, cur);
4111 ret = send_unlink(sctx, cur->full_path);
4119 list_for_each_entry(cur, &sctx->new_refs, list) {
4121 * We may have refs where the parent directory does not exist
4122 * yet. This happens if the parent directories inum is higher
4123 * than the current inum. To handle this case, we create the
4124 * parent directory out of order. But we need to check if this
4125 * did already happen before due to other refs in the same dir.
4127 ret = get_cur_inode_state(sctx, cur->dir, cur->dir_gen);
4130 if (ret == inode_state_will_create) {
4133 * First check if any of the current inodes refs did
4134 * already create the dir.
4136 list_for_each_entry(cur2, &sctx->new_refs, list) {
4139 if (cur2->dir == cur->dir) {
4146 * If that did not happen, check if a previous inode
4147 * did already create the dir.
4150 ret = did_create_dir(sctx, cur->dir);
4154 ret = send_create_inode(sctx, cur->dir);
4160 if (S_ISDIR(sctx->cur_inode_mode) && sctx->parent_root) {
4161 ret = wait_for_dest_dir_move(sctx, cur, is_orphan);
4170 if (S_ISDIR(sctx->cur_inode_mode) && sctx->parent_root &&
4172 ret = wait_for_parent_move(sctx, cur, is_orphan);
4182 * link/move the ref to the new place. If we have an orphan
4183 * inode, move it and update valid_path. If not, link or move
4184 * it depending on the inode mode.
4186 if (is_orphan && can_rename) {
4187 ret = send_rename(sctx, valid_path, cur->full_path);
4191 ret = fs_path_copy(valid_path, cur->full_path);
4194 } else if (can_rename) {
4195 if (S_ISDIR(sctx->cur_inode_mode)) {
4197 * Dirs can't be linked, so move it. For moved
4198 * dirs, we always have one new and one deleted
4199 * ref. The deleted ref is ignored later.
4201 ret = send_rename(sctx, valid_path,
4204 ret = fs_path_copy(valid_path,
4210 * We might have previously orphanized an inode
4211 * which is an ancestor of our current inode,
4212 * so our reference's full path, which was
4213 * computed before any such orphanizations, must
4216 if (orphanized_dir) {
4217 ret = update_ref_path(sctx, cur);
4221 ret = send_link(sctx, cur->full_path,
4227 ret = dup_ref(cur, &check_dirs);
4232 if (S_ISDIR(sctx->cur_inode_mode) && sctx->cur_inode_deleted) {
4234 * Check if we can already rmdir the directory. If not,
4235 * orphanize it. For every dir item inside that gets deleted
4236 * later, we do this check again and rmdir it then if possible.
4237 * See the use of check_dirs for more details.
4239 ret = can_rmdir(sctx, sctx->cur_ino, sctx->cur_inode_gen,
4244 ret = send_rmdir(sctx, valid_path);
4247 } else if (!is_orphan) {
4248 ret = orphanize_inode(sctx, sctx->cur_ino,
4249 sctx->cur_inode_gen, valid_path);
4255 list_for_each_entry(cur, &sctx->deleted_refs, list) {
4256 ret = dup_ref(cur, &check_dirs);
4260 } else if (S_ISDIR(sctx->cur_inode_mode) &&
4261 !list_empty(&sctx->deleted_refs)) {
4263 * We have a moved dir. Add the old parent to check_dirs
4265 cur = list_entry(sctx->deleted_refs.next, struct recorded_ref,
4267 ret = dup_ref(cur, &check_dirs);
4270 } else if (!S_ISDIR(sctx->cur_inode_mode)) {
4272 * We have a non dir inode. Go through all deleted refs and
4273 * unlink them if they were not already overwritten by other
4276 list_for_each_entry(cur, &sctx->deleted_refs, list) {
4277 ret = did_overwrite_ref(sctx, cur->dir, cur->dir_gen,
4278 sctx->cur_ino, sctx->cur_inode_gen,
4279 cur->name, cur->name_len);
4284 * If we orphanized any ancestor before, we need
4285 * to recompute the full path for deleted names,
4286 * since any such path was computed before we
4287 * processed any references and orphanized any
4290 if (orphanized_ancestor) {
4291 ret = update_ref_path(sctx, cur);
4295 ret = send_unlink(sctx, cur->full_path);
4299 ret = dup_ref(cur, &check_dirs);
4304 * If the inode is still orphan, unlink the orphan. This may
4305 * happen when a previous inode did overwrite the first ref
4306 * of this inode and no new refs were added for the current
4307 * inode. Unlinking does not mean that the inode is deleted in
4308 * all cases. There may still be links to this inode in other
4312 ret = send_unlink(sctx, valid_path);
4319 * We did collect all parent dirs where cur_inode was once located. We
4320 * now go through all these dirs and check if they are pending for
4321 * deletion and if it's finally possible to perform the rmdir now.
4322 * We also update the inode stats of the parent dirs here.
4324 list_for_each_entry(cur, &check_dirs, list) {
4326 * In case we had refs into dirs that were not processed yet,
4327 * we don't need to do the utime and rmdir logic for these dirs.
4328 * The dir will be processed later.
4330 if (cur->dir > sctx->cur_ino)
4333 ret = get_cur_inode_state(sctx, cur->dir, cur->dir_gen);
4337 if (ret == inode_state_did_create ||
4338 ret == inode_state_no_change) {
4339 /* TODO delayed utimes */
4340 ret = send_utimes(sctx, cur->dir, cur->dir_gen);
4343 } else if (ret == inode_state_did_delete &&
4344 cur->dir != last_dir_ino_rm) {
4345 ret = can_rmdir(sctx, cur->dir, cur->dir_gen,
4350 ret = get_cur_path(sctx, cur->dir,
4351 cur->dir_gen, valid_path);
4354 ret = send_rmdir(sctx, valid_path);
4357 last_dir_ino_rm = cur->dir;
4365 __free_recorded_refs(&check_dirs);
4366 free_recorded_refs(sctx);
4367 fs_path_free(valid_path);
4371 static int rbtree_ref_comp(const void *k, const struct rb_node *node)
4373 const struct recorded_ref *data = k;
4374 const struct recorded_ref *ref = rb_entry(node, struct recorded_ref, node);
4377 if (data->dir > ref->dir)
4379 if (data->dir < ref->dir)
4381 if (data->dir_gen > ref->dir_gen)
4383 if (data->dir_gen < ref->dir_gen)
4385 if (data->name_len > ref->name_len)
4387 if (data->name_len < ref->name_len)
4389 result = strcmp(data->name, ref->name);
4397 static bool rbtree_ref_less(struct rb_node *node, const struct rb_node *parent)
4399 const struct recorded_ref *entry = rb_entry(node, struct recorded_ref, node);
4401 return rbtree_ref_comp(entry, parent) < 0;
4404 static int record_ref_in_tree(struct rb_root *root, struct list_head *refs,
4405 struct fs_path *name, u64 dir, u64 dir_gen,
4406 struct send_ctx *sctx)
4409 struct fs_path *path = NULL;
4410 struct recorded_ref *ref = NULL;
4412 path = fs_path_alloc();
4418 ref = recorded_ref_alloc();
4424 ret = get_cur_path(sctx, dir, dir_gen, path);
4427 ret = fs_path_add_path(path, name);
4432 ref->dir_gen = dir_gen;
4433 set_ref_path(ref, path);
4434 list_add_tail(&ref->list, refs);
4435 rb_add(&ref->node, root, rbtree_ref_less);
4439 if (path && (!ref || !ref->full_path))
4441 recorded_ref_free(ref);
4446 static int record_new_ref_if_needed(int num, u64 dir, int index,
4447 struct fs_path *name, void *ctx)
4450 struct send_ctx *sctx = ctx;
4451 struct rb_node *node = NULL;
4452 struct recorded_ref data;
4453 struct recorded_ref *ref;
4456 ret = get_inode_gen(sctx->send_root, dir, &dir_gen);
4461 data.dir_gen = dir_gen;
4462 set_ref_path(&data, name);
4463 node = rb_find(&data, &sctx->rbtree_deleted_refs, rbtree_ref_comp);
4465 ref = rb_entry(node, struct recorded_ref, node);
4466 recorded_ref_free(ref);
4468 ret = record_ref_in_tree(&sctx->rbtree_new_refs,
4469 &sctx->new_refs, name, dir, dir_gen,
4476 static int record_deleted_ref_if_needed(int num, u64 dir, int index,
4477 struct fs_path *name, void *ctx)
4480 struct send_ctx *sctx = ctx;
4481 struct rb_node *node = NULL;
4482 struct recorded_ref data;
4483 struct recorded_ref *ref;
4486 ret = get_inode_gen(sctx->parent_root, dir, &dir_gen);
4491 data.dir_gen = dir_gen;
4492 set_ref_path(&data, name);
4493 node = rb_find(&data, &sctx->rbtree_new_refs, rbtree_ref_comp);
4495 ref = rb_entry(node, struct recorded_ref, node);
4496 recorded_ref_free(ref);
4498 ret = record_ref_in_tree(&sctx->rbtree_deleted_refs,
4499 &sctx->deleted_refs, name, dir,
4506 static int record_new_ref(struct send_ctx *sctx)
4510 ret = iterate_inode_ref(sctx->send_root, sctx->left_path,
4511 sctx->cmp_key, 0, record_new_ref_if_needed, sctx);
4520 static int record_deleted_ref(struct send_ctx *sctx)
4524 ret = iterate_inode_ref(sctx->parent_root, sctx->right_path,
4525 sctx->cmp_key, 0, record_deleted_ref_if_needed,
4535 static int record_changed_ref(struct send_ctx *sctx)
4539 ret = iterate_inode_ref(sctx->send_root, sctx->left_path,
4540 sctx->cmp_key, 0, record_new_ref_if_needed, sctx);
4543 ret = iterate_inode_ref(sctx->parent_root, sctx->right_path,
4544 sctx->cmp_key, 0, record_deleted_ref_if_needed, sctx);
4554 * Record and process all refs at once. Needed when an inode changes the
4555 * generation number, which means that it was deleted and recreated.
4557 static int process_all_refs(struct send_ctx *sctx,
4558 enum btrfs_compare_tree_result cmd)
4562 struct btrfs_root *root;
4563 struct btrfs_path *path;
4564 struct btrfs_key key;
4565 struct btrfs_key found_key;
4566 iterate_inode_ref_t cb;
4567 int pending_move = 0;
4569 path = alloc_path_for_send();
4573 if (cmd == BTRFS_COMPARE_TREE_NEW) {
4574 root = sctx->send_root;
4575 cb = record_new_ref_if_needed;
4576 } else if (cmd == BTRFS_COMPARE_TREE_DELETED) {
4577 root = sctx->parent_root;
4578 cb = record_deleted_ref_if_needed;
4580 btrfs_err(sctx->send_root->fs_info,
4581 "Wrong command %d in process_all_refs", cmd);
4586 key.objectid = sctx->cmp_key->objectid;
4587 key.type = BTRFS_INODE_REF_KEY;
4589 btrfs_for_each_slot(root, &key, &found_key, path, iter_ret) {
4590 if (found_key.objectid != key.objectid ||
4591 (found_key.type != BTRFS_INODE_REF_KEY &&
4592 found_key.type != BTRFS_INODE_EXTREF_KEY))
4595 ret = iterate_inode_ref(root, path, &found_key, 0, cb, sctx);
4599 /* Catch error found during iteration */
4604 btrfs_release_path(path);
4607 * We don't actually care about pending_move as we are simply
4608 * re-creating this inode and will be rename'ing it into place once we
4609 * rename the parent directory.
4611 ret = process_recorded_refs(sctx, &pending_move);
4613 btrfs_free_path(path);
4617 static int send_set_xattr(struct send_ctx *sctx,
4618 struct fs_path *path,
4619 const char *name, int name_len,
4620 const char *data, int data_len)
4624 ret = begin_cmd(sctx, BTRFS_SEND_C_SET_XATTR);
4628 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);
4629 TLV_PUT_STRING(sctx, BTRFS_SEND_A_XATTR_NAME, name, name_len);
4630 TLV_PUT(sctx, BTRFS_SEND_A_XATTR_DATA, data, data_len);
4632 ret = send_cmd(sctx);
4639 static int send_remove_xattr(struct send_ctx *sctx,
4640 struct fs_path *path,
4641 const char *name, int name_len)
4645 ret = begin_cmd(sctx, BTRFS_SEND_C_REMOVE_XATTR);
4649 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);
4650 TLV_PUT_STRING(sctx, BTRFS_SEND_A_XATTR_NAME, name, name_len);
4652 ret = send_cmd(sctx);
4659 static int __process_new_xattr(int num, struct btrfs_key *di_key,
4660 const char *name, int name_len, const char *data,
4661 int data_len, void *ctx)
4664 struct send_ctx *sctx = ctx;
4666 struct posix_acl_xattr_header dummy_acl;
4668 /* Capabilities are emitted by finish_inode_if_needed */
4669 if (!strncmp(name, XATTR_NAME_CAPS, name_len))
4672 p = fs_path_alloc();
4677 * This hack is needed because empty acls are stored as zero byte
4678 * data in xattrs. Problem with that is, that receiving these zero byte
4679 * acls will fail later. To fix this, we send a dummy acl list that
4680 * only contains the version number and no entries.
4682 if (!strncmp(name, XATTR_NAME_POSIX_ACL_ACCESS, name_len) ||
4683 !strncmp(name, XATTR_NAME_POSIX_ACL_DEFAULT, name_len)) {
4684 if (data_len == 0) {
4685 dummy_acl.a_version =
4686 cpu_to_le32(POSIX_ACL_XATTR_VERSION);
4687 data = (char *)&dummy_acl;
4688 data_len = sizeof(dummy_acl);
4692 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
4696 ret = send_set_xattr(sctx, p, name, name_len, data, data_len);
4703 static int __process_deleted_xattr(int num, struct btrfs_key *di_key,
4704 const char *name, int name_len,
4705 const char *data, int data_len, void *ctx)
4708 struct send_ctx *sctx = ctx;
4711 p = fs_path_alloc();
4715 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
4719 ret = send_remove_xattr(sctx, p, name, name_len);
4726 static int process_new_xattr(struct send_ctx *sctx)
4730 ret = iterate_dir_item(sctx->send_root, sctx->left_path,
4731 __process_new_xattr, sctx);
4736 static int process_deleted_xattr(struct send_ctx *sctx)
4738 return iterate_dir_item(sctx->parent_root, sctx->right_path,
4739 __process_deleted_xattr, sctx);
4742 struct find_xattr_ctx {
4750 static int __find_xattr(int num, struct btrfs_key *di_key, const char *name,
4751 int name_len, const char *data, int data_len, void *vctx)
4753 struct find_xattr_ctx *ctx = vctx;
4755 if (name_len == ctx->name_len &&
4756 strncmp(name, ctx->name, name_len) == 0) {
4757 ctx->found_idx = num;
4758 ctx->found_data_len = data_len;
4759 ctx->found_data = kmemdup(data, data_len, GFP_KERNEL);
4760 if (!ctx->found_data)
4767 static int find_xattr(struct btrfs_root *root,
4768 struct btrfs_path *path,
4769 struct btrfs_key *key,
4770 const char *name, int name_len,
4771 char **data, int *data_len)
4774 struct find_xattr_ctx ctx;
4777 ctx.name_len = name_len;
4779 ctx.found_data = NULL;
4780 ctx.found_data_len = 0;
4782 ret = iterate_dir_item(root, path, __find_xattr, &ctx);
4786 if (ctx.found_idx == -1)
4789 *data = ctx.found_data;
4790 *data_len = ctx.found_data_len;
4792 kfree(ctx.found_data);
4794 return ctx.found_idx;
4798 static int __process_changed_new_xattr(int num, struct btrfs_key *di_key,
4799 const char *name, int name_len,
4800 const char *data, int data_len,
4804 struct send_ctx *sctx = ctx;
4805 char *found_data = NULL;
4806 int found_data_len = 0;
4808 ret = find_xattr(sctx->parent_root, sctx->right_path,
4809 sctx->cmp_key, name, name_len, &found_data,
4811 if (ret == -ENOENT) {
4812 ret = __process_new_xattr(num, di_key, name, name_len, data,
4814 } else if (ret >= 0) {
4815 if (data_len != found_data_len ||
4816 memcmp(data, found_data, data_len)) {
4817 ret = __process_new_xattr(num, di_key, name, name_len,
4818 data, data_len, ctx);
4828 static int __process_changed_deleted_xattr(int num, struct btrfs_key *di_key,
4829 const char *name, int name_len,
4830 const char *data, int data_len,
4834 struct send_ctx *sctx = ctx;
4836 ret = find_xattr(sctx->send_root, sctx->left_path, sctx->cmp_key,
4837 name, name_len, NULL, NULL);
4839 ret = __process_deleted_xattr(num, di_key, name, name_len, data,
4847 static int process_changed_xattr(struct send_ctx *sctx)
4851 ret = iterate_dir_item(sctx->send_root, sctx->left_path,
4852 __process_changed_new_xattr, sctx);
4855 ret = iterate_dir_item(sctx->parent_root, sctx->right_path,
4856 __process_changed_deleted_xattr, sctx);
4862 static int process_all_new_xattrs(struct send_ctx *sctx)
4866 struct btrfs_root *root;
4867 struct btrfs_path *path;
4868 struct btrfs_key key;
4869 struct btrfs_key found_key;
4871 path = alloc_path_for_send();
4875 root = sctx->send_root;
4877 key.objectid = sctx->cmp_key->objectid;
4878 key.type = BTRFS_XATTR_ITEM_KEY;
4880 btrfs_for_each_slot(root, &key, &found_key, path, iter_ret) {
4881 if (found_key.objectid != key.objectid ||
4882 found_key.type != key.type) {
4887 ret = iterate_dir_item(root, path, __process_new_xattr, sctx);
4891 /* Catch error found during iteration */
4895 btrfs_free_path(path);
4899 static int send_verity(struct send_ctx *sctx, struct fs_path *path,
4900 struct fsverity_descriptor *desc)
4904 ret = begin_cmd(sctx, BTRFS_SEND_C_ENABLE_VERITY);
4908 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);
4909 TLV_PUT_U8(sctx, BTRFS_SEND_A_VERITY_ALGORITHM,
4910 le8_to_cpu(desc->hash_algorithm));
4911 TLV_PUT_U32(sctx, BTRFS_SEND_A_VERITY_BLOCK_SIZE,
4912 1U << le8_to_cpu(desc->log_blocksize));
4913 TLV_PUT(sctx, BTRFS_SEND_A_VERITY_SALT_DATA, desc->salt,
4914 le8_to_cpu(desc->salt_size));
4915 TLV_PUT(sctx, BTRFS_SEND_A_VERITY_SIG_DATA, desc->signature,
4916 le32_to_cpu(desc->sig_size));
4918 ret = send_cmd(sctx);
4925 static int process_verity(struct send_ctx *sctx)
4928 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;
4929 struct inode *inode;
4932 inode = btrfs_iget(fs_info->sb, sctx->cur_ino, sctx->send_root);
4934 return PTR_ERR(inode);
4936 ret = btrfs_get_verity_descriptor(inode, NULL, 0);
4940 if (ret > FS_VERITY_MAX_DESCRIPTOR_SIZE) {
4944 if (!sctx->verity_descriptor) {
4945 sctx->verity_descriptor = kvmalloc(FS_VERITY_MAX_DESCRIPTOR_SIZE,
4947 if (!sctx->verity_descriptor) {
4953 ret = btrfs_get_verity_descriptor(inode, sctx->verity_descriptor, ret);
4957 p = fs_path_alloc();
4962 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
4966 ret = send_verity(sctx, p, sctx->verity_descriptor);
4977 static inline u64 max_send_read_size(const struct send_ctx *sctx)
4979 return sctx->send_max_size - SZ_16K;
4982 static int put_data_header(struct send_ctx *sctx, u32 len)
4984 if (WARN_ON_ONCE(sctx->put_data))
4986 sctx->put_data = true;
4987 if (sctx->proto >= 2) {
4989 * Since v2, the data attribute header doesn't include a length,
4990 * it is implicitly to the end of the command.
4992 if (sctx->send_max_size - sctx->send_size < sizeof(__le16) + len)
4994 put_unaligned_le16(BTRFS_SEND_A_DATA, sctx->send_buf + sctx->send_size);
4995 sctx->send_size += sizeof(__le16);
4997 struct btrfs_tlv_header *hdr;
4999 if (sctx->send_max_size - sctx->send_size < sizeof(*hdr) + len)
5001 hdr = (struct btrfs_tlv_header *)(sctx->send_buf + sctx->send_size);
5002 put_unaligned_le16(BTRFS_SEND_A_DATA, &hdr->tlv_type);
5003 put_unaligned_le16(len, &hdr->tlv_len);
5004 sctx->send_size += sizeof(*hdr);
5009 static int put_file_data(struct send_ctx *sctx, u64 offset, u32 len)
5011 struct btrfs_root *root = sctx->send_root;
5012 struct btrfs_fs_info *fs_info = root->fs_info;
5014 pgoff_t index = offset >> PAGE_SHIFT;
5016 unsigned pg_offset = offset_in_page(offset);
5019 ret = put_data_header(sctx, len);
5023 last_index = (offset + len - 1) >> PAGE_SHIFT;
5025 while (index <= last_index) {
5026 unsigned cur_len = min_t(unsigned, len,
5027 PAGE_SIZE - pg_offset);
5029 page = find_lock_page(sctx->cur_inode->i_mapping, index);
5031 page_cache_sync_readahead(sctx->cur_inode->i_mapping,
5032 &sctx->ra, NULL, index,
5033 last_index + 1 - index);
5035 page = find_or_create_page(sctx->cur_inode->i_mapping,
5043 if (PageReadahead(page))
5044 page_cache_async_readahead(sctx->cur_inode->i_mapping,
5045 &sctx->ra, NULL, page_folio(page),
5046 index, last_index + 1 - index);
5048 if (!PageUptodate(page)) {
5049 btrfs_read_folio(NULL, page_folio(page));
5051 if (!PageUptodate(page)) {
5054 "send: IO error at offset %llu for inode %llu root %llu",
5055 page_offset(page), sctx->cur_ino,
5056 sctx->send_root->root_key.objectid);
5063 memcpy_from_page(sctx->send_buf + sctx->send_size, page,
5064 pg_offset, cur_len);
5070 sctx->send_size += cur_len;
5077 * Read some bytes from the current inode/file and send a write command to
5080 static int send_write(struct send_ctx *sctx, u64 offset, u32 len)
5082 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;
5086 p = fs_path_alloc();
5090 btrfs_debug(fs_info, "send_write offset=%llu, len=%d", offset, len);
5092 ret = begin_cmd(sctx, BTRFS_SEND_C_WRITE);
5096 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
5100 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
5101 TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset);
5102 ret = put_file_data(sctx, offset, len);
5106 ret = send_cmd(sctx);
5115 * Send a clone command to user space.
5117 static int send_clone(struct send_ctx *sctx,
5118 u64 offset, u32 len,
5119 struct clone_root *clone_root)
5125 btrfs_debug(sctx->send_root->fs_info,
5126 "send_clone offset=%llu, len=%d, clone_root=%llu, clone_inode=%llu, clone_offset=%llu",
5127 offset, len, clone_root->root->root_key.objectid,
5128 clone_root->ino, clone_root->offset);
5130 p = fs_path_alloc();
5134 ret = begin_cmd(sctx, BTRFS_SEND_C_CLONE);
5138 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
5142 TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset);
5143 TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_LEN, len);
5144 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
5146 if (clone_root->root == sctx->send_root) {
5147 ret = get_inode_gen(sctx->send_root, clone_root->ino, &gen);
5150 ret = get_cur_path(sctx, clone_root->ino, gen, p);
5152 ret = get_inode_path(clone_root->root, clone_root->ino, p);
5158 * If the parent we're using has a received_uuid set then use that as
5159 * our clone source as that is what we will look for when doing a
5162 * This covers the case that we create a snapshot off of a received
5163 * subvolume and then use that as the parent and try to receive on a
5166 if (!btrfs_is_empty_uuid(clone_root->root->root_item.received_uuid))
5167 TLV_PUT_UUID(sctx, BTRFS_SEND_A_CLONE_UUID,
5168 clone_root->root->root_item.received_uuid);
5170 TLV_PUT_UUID(sctx, BTRFS_SEND_A_CLONE_UUID,
5171 clone_root->root->root_item.uuid);
5172 TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_CTRANSID,
5173 btrfs_root_ctransid(&clone_root->root->root_item));
5174 TLV_PUT_PATH(sctx, BTRFS_SEND_A_CLONE_PATH, p);
5175 TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_OFFSET,
5176 clone_root->offset);
5178 ret = send_cmd(sctx);
5187 * Send an update extent command to user space.
5189 static int send_update_extent(struct send_ctx *sctx,
5190 u64 offset, u32 len)
5195 p = fs_path_alloc();
5199 ret = begin_cmd(sctx, BTRFS_SEND_C_UPDATE_EXTENT);
5203 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
5207 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
5208 TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset);
5209 TLV_PUT_U64(sctx, BTRFS_SEND_A_SIZE, len);
5211 ret = send_cmd(sctx);
5219 static int send_hole(struct send_ctx *sctx, u64 end)
5221 struct fs_path *p = NULL;
5222 u64 read_size = max_send_read_size(sctx);
5223 u64 offset = sctx->cur_inode_last_extent;
5227 * A hole that starts at EOF or beyond it. Since we do not yet support
5228 * fallocate (for extent preallocation and hole punching), sending a
5229 * write of zeroes starting at EOF or beyond would later require issuing
5230 * a truncate operation which would undo the write and achieve nothing.
5232 if (offset >= sctx->cur_inode_size)
5236 * Don't go beyond the inode's i_size due to prealloc extents that start
5239 end = min_t(u64, end, sctx->cur_inode_size);
5241 if (sctx->flags & BTRFS_SEND_FLAG_NO_FILE_DATA)
5242 return send_update_extent(sctx, offset, end - offset);
5244 p = fs_path_alloc();
5247 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);
5249 goto tlv_put_failure;
5250 while (offset < end) {
5251 u64 len = min(end - offset, read_size);
5253 ret = begin_cmd(sctx, BTRFS_SEND_C_WRITE);
5256 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);
5257 TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset);
5258 ret = put_data_header(sctx, len);
5261 memset(sctx->send_buf + sctx->send_size, 0, len);
5262 sctx->send_size += len;
5263 ret = send_cmd(sctx);
5268 sctx->cur_inode_next_write_offset = offset;
5274 static int send_encoded_inline_extent(struct send_ctx *sctx,
5275 struct btrfs_path *path, u64 offset,
5278 struct btrfs_root *root = sctx->send_root;
5279 struct btrfs_fs_info *fs_info = root->fs_info;
5280 struct inode *inode;
5281 struct fs_path *fspath;
5282 struct extent_buffer *leaf = path->nodes[0];
5283 struct btrfs_key key;
5284 struct btrfs_file_extent_item *ei;
5289 inode = btrfs_iget(fs_info->sb, sctx->cur_ino, root);
5291 return PTR_ERR(inode);
5293 fspath = fs_path_alloc();
5299 ret = begin_cmd(sctx, BTRFS_SEND_C_ENCODED_WRITE);
5303 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, fspath);
5307 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
5308 ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_file_extent_item);
5309 ram_bytes = btrfs_file_extent_ram_bytes(leaf, ei);
5310 inline_size = btrfs_file_extent_inline_item_len(leaf, path->slots[0]);
5312 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, fspath);
5313 TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset);
5314 TLV_PUT_U64(sctx, BTRFS_SEND_A_UNENCODED_FILE_LEN,
5315 min(key.offset + ram_bytes - offset, len));
5316 TLV_PUT_U64(sctx, BTRFS_SEND_A_UNENCODED_LEN, ram_bytes);
5317 TLV_PUT_U64(sctx, BTRFS_SEND_A_UNENCODED_OFFSET, offset - key.offset);
5318 ret = btrfs_encoded_io_compression_from_extent(fs_info,
5319 btrfs_file_extent_compression(leaf, ei));
5322 TLV_PUT_U32(sctx, BTRFS_SEND_A_COMPRESSION, ret);
5324 ret = put_data_header(sctx, inline_size);
5327 read_extent_buffer(leaf, sctx->send_buf + sctx->send_size,
5328 btrfs_file_extent_inline_start(ei), inline_size);
5329 sctx->send_size += inline_size;
5331 ret = send_cmd(sctx);
5335 fs_path_free(fspath);
5340 static int send_encoded_extent(struct send_ctx *sctx, struct btrfs_path *path,
5341 u64 offset, u64 len)
5343 struct btrfs_root *root = sctx->send_root;
5344 struct btrfs_fs_info *fs_info = root->fs_info;
5345 struct inode *inode;
5346 struct fs_path *fspath;
5347 struct extent_buffer *leaf = path->nodes[0];
5348 struct btrfs_key key;
5349 struct btrfs_file_extent_item *ei;
5350 u64 disk_bytenr, disk_num_bytes;
5352 struct btrfs_cmd_header *hdr;
5356 inode = btrfs_iget(fs_info->sb, sctx->cur_ino, root);
5358 return PTR_ERR(inode);
5360 fspath = fs_path_alloc();
5366 ret = begin_cmd(sctx, BTRFS_SEND_C_ENCODED_WRITE);
5370 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, fspath);
5374 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
5375 ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_file_extent_item);
5376 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, ei);
5377 disk_num_bytes = btrfs_file_extent_disk_num_bytes(leaf, ei);
5379 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, fspath);
5380 TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset);
5381 TLV_PUT_U64(sctx, BTRFS_SEND_A_UNENCODED_FILE_LEN,
5382 min(key.offset + btrfs_file_extent_num_bytes(leaf, ei) - offset,
5384 TLV_PUT_U64(sctx, BTRFS_SEND_A_UNENCODED_LEN,
5385 btrfs_file_extent_ram_bytes(leaf, ei));
5386 TLV_PUT_U64(sctx, BTRFS_SEND_A_UNENCODED_OFFSET,
5387 offset - key.offset + btrfs_file_extent_offset(leaf, ei));
5388 ret = btrfs_encoded_io_compression_from_extent(fs_info,
5389 btrfs_file_extent_compression(leaf, ei));
5392 TLV_PUT_U32(sctx, BTRFS_SEND_A_COMPRESSION, ret);
5393 TLV_PUT_U32(sctx, BTRFS_SEND_A_ENCRYPTION, 0);
5395 ret = put_data_header(sctx, disk_num_bytes);
5400 * We want to do I/O directly into the send buffer, so get the next page
5401 * boundary in the send buffer. This means that there may be a gap
5402 * between the beginning of the command and the file data.
5404 data_offset = ALIGN(sctx->send_size, PAGE_SIZE);
5405 if (data_offset > sctx->send_max_size ||
5406 sctx->send_max_size - data_offset < disk_num_bytes) {
5412 * Note that send_buf is a mapping of send_buf_pages, so this is really
5413 * reading into send_buf.
5415 ret = btrfs_encoded_read_regular_fill_pages(BTRFS_I(inode), offset,
5416 disk_bytenr, disk_num_bytes,
5417 sctx->send_buf_pages +
5418 (data_offset >> PAGE_SHIFT));
5422 hdr = (struct btrfs_cmd_header *)sctx->send_buf;
5423 hdr->len = cpu_to_le32(sctx->send_size + disk_num_bytes - sizeof(*hdr));
5425 crc = btrfs_crc32c(0, sctx->send_buf, sctx->send_size);
5426 crc = btrfs_crc32c(crc, sctx->send_buf + data_offset, disk_num_bytes);
5427 hdr->crc = cpu_to_le32(crc);
5429 ret = write_buf(sctx->send_filp, sctx->send_buf, sctx->send_size,
5432 ret = write_buf(sctx->send_filp, sctx->send_buf + data_offset,
5433 disk_num_bytes, &sctx->send_off);
5435 sctx->send_size = 0;
5436 sctx->put_data = false;
5440 fs_path_free(fspath);
5445 static int send_extent_data(struct send_ctx *sctx, struct btrfs_path *path,
5446 const u64 offset, const u64 len)
5448 const u64 end = offset + len;
5449 struct extent_buffer *leaf = path->nodes[0];
5450 struct btrfs_file_extent_item *ei;
5451 u64 read_size = max_send_read_size(sctx);
5454 if (sctx->flags & BTRFS_SEND_FLAG_NO_FILE_DATA)
5455 return send_update_extent(sctx, offset, len);
5457 ei = btrfs_item_ptr(leaf, path->slots[0],
5458 struct btrfs_file_extent_item);
5459 if ((sctx->flags & BTRFS_SEND_FLAG_COMPRESSED) &&
5460 btrfs_file_extent_compression(leaf, ei) != BTRFS_COMPRESS_NONE) {
5461 bool is_inline = (btrfs_file_extent_type(leaf, ei) ==
5462 BTRFS_FILE_EXTENT_INLINE);
5465 * Send the compressed extent unless the compressed data is
5466 * larger than the decompressed data. This can happen if we're
5467 * not sending the entire extent, either because it has been
5468 * partially overwritten/truncated or because this is a part of
5469 * the extent that we couldn't clone in clone_range().
5472 btrfs_file_extent_inline_item_len(leaf,
5473 path->slots[0]) <= len) {
5474 return send_encoded_inline_extent(sctx, path, offset,
5476 } else if (!is_inline &&
5477 btrfs_file_extent_disk_num_bytes(leaf, ei) <= len) {
5478 return send_encoded_extent(sctx, path, offset, len);
5482 if (sctx->cur_inode == NULL) {
5483 struct btrfs_root *root = sctx->send_root;
5485 sctx->cur_inode = btrfs_iget(root->fs_info->sb, sctx->cur_ino, root);
5486 if (IS_ERR(sctx->cur_inode)) {
5487 int err = PTR_ERR(sctx->cur_inode);
5489 sctx->cur_inode = NULL;
5492 memset(&sctx->ra, 0, sizeof(struct file_ra_state));
5493 file_ra_state_init(&sctx->ra, sctx->cur_inode->i_mapping);
5496 * It's very likely there are no pages from this inode in the page
5497 * cache, so after reading extents and sending their data, we clean
5498 * the page cache to avoid trashing the page cache (adding pressure
5499 * to the page cache and forcing eviction of other data more useful
5500 * for applications).
5502 * We decide if we should clean the page cache simply by checking
5503 * if the inode's mapping nrpages is 0 when we first open it, and
5504 * not by using something like filemap_range_has_page() before
5505 * reading an extent because when we ask the readahead code to
5506 * read a given file range, it may (and almost always does) read
5507 * pages from beyond that range (see the documentation for
5508 * page_cache_sync_readahead()), so it would not be reliable,
5509 * because after reading the first extent future calls to
5510 * filemap_range_has_page() would return true because the readahead
5511 * on the previous extent resulted in reading pages of the current
5514 sctx->clean_page_cache = (sctx->cur_inode->i_mapping->nrpages == 0);
5515 sctx->page_cache_clear_start = round_down(offset, PAGE_SIZE);
5518 while (sent < len) {
5519 u64 size = min(len - sent, read_size);
5522 ret = send_write(sctx, offset + sent, size);
5528 if (sctx->clean_page_cache && IS_ALIGNED(end, PAGE_SIZE)) {
5530 * Always operate only on ranges that are a multiple of the page
5531 * size. This is not only to prevent zeroing parts of a page in
5532 * the case of subpage sector size, but also to guarantee we evict
5533 * pages, as passing a range that is smaller than page size does
5534 * not evict the respective page (only zeroes part of its content).
5536 * Always start from the end offset of the last range cleared.
5537 * This is because the readahead code may (and very often does)
5538 * reads pages beyond the range we request for readahead. So if
5539 * we have an extent layout like this:
5541 * [ extent A ] [ extent B ] [ extent C ]
5543 * When we ask page_cache_sync_readahead() to read extent A, it
5544 * may also trigger reads for pages of extent B. If we are doing
5545 * an incremental send and extent B has not changed between the
5546 * parent and send snapshots, some or all of its pages may end
5547 * up being read and placed in the page cache. So when truncating
5548 * the page cache we always start from the end offset of the
5549 * previously processed extent up to the end of the current
5552 truncate_inode_pages_range(&sctx->cur_inode->i_data,
5553 sctx->page_cache_clear_start,
5555 sctx->page_cache_clear_start = end;
5562 * Search for a capability xattr related to sctx->cur_ino. If the capability is
5563 * found, call send_set_xattr function to emit it.
5565 * Return 0 if there isn't a capability, or when the capability was emitted
5566 * successfully, or < 0 if an error occurred.
5568 static int send_capabilities(struct send_ctx *sctx)
5570 struct fs_path *fspath = NULL;
5571 struct btrfs_path *path;
5572 struct btrfs_dir_item *di;
5573 struct extent_buffer *leaf;
5574 unsigned long data_ptr;
5579 path = alloc_path_for_send();
5583 di = btrfs_lookup_xattr(NULL, sctx->send_root, path, sctx->cur_ino,
5584 XATTR_NAME_CAPS, strlen(XATTR_NAME_CAPS), 0);
5586 /* There is no xattr for this inode */
5588 } else if (IS_ERR(di)) {
5593 leaf = path->nodes[0];
5594 buf_len = btrfs_dir_data_len(leaf, di);
5596 fspath = fs_path_alloc();
5597 buf = kmalloc(buf_len, GFP_KERNEL);
5598 if (!fspath || !buf) {
5603 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, fspath);
5607 data_ptr = (unsigned long)(di + 1) + btrfs_dir_name_len(leaf, di);
5608 read_extent_buffer(leaf, buf, data_ptr, buf_len);
5610 ret = send_set_xattr(sctx, fspath, XATTR_NAME_CAPS,
5611 strlen(XATTR_NAME_CAPS), buf, buf_len);
5614 fs_path_free(fspath);
5615 btrfs_free_path(path);
5619 static int clone_range(struct send_ctx *sctx, struct btrfs_path *dst_path,
5620 struct clone_root *clone_root, const u64 disk_byte,
5621 u64 data_offset, u64 offset, u64 len)
5623 struct btrfs_path *path;
5624 struct btrfs_key key;
5626 struct btrfs_inode_info info;
5627 u64 clone_src_i_size = 0;
5630 * Prevent cloning from a zero offset with a length matching the sector
5631 * size because in some scenarios this will make the receiver fail.
5633 * For example, if in the source filesystem the extent at offset 0
5634 * has a length of sectorsize and it was written using direct IO, then
5635 * it can never be an inline extent (even if compression is enabled).
5636 * Then this extent can be cloned in the original filesystem to a non
5637 * zero file offset, but it may not be possible to clone in the
5638 * destination filesystem because it can be inlined due to compression
5639 * on the destination filesystem (as the receiver's write operations are
5640 * always done using buffered IO). The same happens when the original
5641 * filesystem does not have compression enabled but the destination
5644 if (clone_root->offset == 0 &&
5645 len == sctx->send_root->fs_info->sectorsize)
5646 return send_extent_data(sctx, dst_path, offset, len);
5648 path = alloc_path_for_send();
5653 * There are inodes that have extents that lie behind its i_size. Don't
5654 * accept clones from these extents.
5656 ret = get_inode_info(clone_root->root, clone_root->ino, &info);
5657 btrfs_release_path(path);
5660 clone_src_i_size = info.size;
5663 * We can't send a clone operation for the entire range if we find
5664 * extent items in the respective range in the source file that
5665 * refer to different extents or if we find holes.
5666 * So check for that and do a mix of clone and regular write/copy
5667 * operations if needed.
5671 * mkfs.btrfs -f /dev/sda
5672 * mount /dev/sda /mnt
5673 * xfs_io -f -c "pwrite -S 0xaa 0K 100K" /mnt/foo
5674 * cp --reflink=always /mnt/foo /mnt/bar
5675 * xfs_io -c "pwrite -S 0xbb 50K 50K" /mnt/foo
5676 * btrfs subvolume snapshot -r /mnt /mnt/snap
5678 * If when we send the snapshot and we are processing file bar (which
5679 * has a higher inode number than foo) we blindly send a clone operation
5680 * for the [0, 100K[ range from foo to bar, the receiver ends up getting
5681 * a file bar that matches the content of file foo - iow, doesn't match
5682 * the content from bar in the original filesystem.
5684 key.objectid = clone_root->ino;
5685 key.type = BTRFS_EXTENT_DATA_KEY;
5686 key.offset = clone_root->offset;
5687 ret = btrfs_search_slot(NULL, clone_root->root, &key, path, 0, 0);
5690 if (ret > 0 && path->slots[0] > 0) {
5691 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0] - 1);
5692 if (key.objectid == clone_root->ino &&
5693 key.type == BTRFS_EXTENT_DATA_KEY)
5698 struct extent_buffer *leaf = path->nodes[0];
5699 int slot = path->slots[0];
5700 struct btrfs_file_extent_item *ei;
5704 u64 clone_data_offset;
5705 bool crossed_src_i_size = false;
5707 if (slot >= btrfs_header_nritems(leaf)) {
5708 ret = btrfs_next_leaf(clone_root->root, path);
5716 btrfs_item_key_to_cpu(leaf, &key, slot);
5719 * We might have an implicit trailing hole (NO_HOLES feature
5720 * enabled). We deal with it after leaving this loop.
5722 if (key.objectid != clone_root->ino ||
5723 key.type != BTRFS_EXTENT_DATA_KEY)
5726 ei = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);
5727 type = btrfs_file_extent_type(leaf, ei);
5728 if (type == BTRFS_FILE_EXTENT_INLINE) {
5729 ext_len = btrfs_file_extent_ram_bytes(leaf, ei);
5730 ext_len = PAGE_ALIGN(ext_len);
5732 ext_len = btrfs_file_extent_num_bytes(leaf, ei);
5735 if (key.offset + ext_len <= clone_root->offset)
5738 if (key.offset > clone_root->offset) {
5739 /* Implicit hole, NO_HOLES feature enabled. */
5740 u64 hole_len = key.offset - clone_root->offset;
5744 ret = send_extent_data(sctx, dst_path, offset,
5753 clone_root->offset += hole_len;
5754 data_offset += hole_len;
5757 if (key.offset >= clone_root->offset + len)
5760 if (key.offset >= clone_src_i_size)
5763 if (key.offset + ext_len > clone_src_i_size) {
5764 ext_len = clone_src_i_size - key.offset;
5765 crossed_src_i_size = true;
5768 clone_data_offset = btrfs_file_extent_offset(leaf, ei);
5769 if (btrfs_file_extent_disk_bytenr(leaf, ei) == disk_byte) {
5770 clone_root->offset = key.offset;
5771 if (clone_data_offset < data_offset &&
5772 clone_data_offset + ext_len > data_offset) {
5775 extent_offset = data_offset - clone_data_offset;
5776 ext_len -= extent_offset;
5777 clone_data_offset += extent_offset;
5778 clone_root->offset += extent_offset;
5782 clone_len = min_t(u64, ext_len, len);
5784 if (btrfs_file_extent_disk_bytenr(leaf, ei) == disk_byte &&
5785 clone_data_offset == data_offset) {
5786 const u64 src_end = clone_root->offset + clone_len;
5787 const u64 sectorsize = SZ_64K;
5790 * We can't clone the last block, when its size is not
5791 * sector size aligned, into the middle of a file. If we
5792 * do so, the receiver will get a failure (-EINVAL) when
5793 * trying to clone or will silently corrupt the data in
5794 * the destination file if it's on a kernel without the
5795 * fix introduced by commit ac765f83f1397646
5796 * ("Btrfs: fix data corruption due to cloning of eof
5799 * So issue a clone of the aligned down range plus a
5800 * regular write for the eof block, if we hit that case.
5802 * Also, we use the maximum possible sector size, 64K,
5803 * because we don't know what's the sector size of the
5804 * filesystem that receives the stream, so we have to
5805 * assume the largest possible sector size.
5807 if (src_end == clone_src_i_size &&
5808 !IS_ALIGNED(src_end, sectorsize) &&
5809 offset + clone_len < sctx->cur_inode_size) {
5812 slen = ALIGN_DOWN(src_end - clone_root->offset,
5815 ret = send_clone(sctx, offset, slen,
5820 ret = send_extent_data(sctx, dst_path,
5824 ret = send_clone(sctx, offset, clone_len,
5827 } else if (crossed_src_i_size && clone_len < len) {
5829 * If we are at i_size of the clone source inode and we
5830 * can not clone from it, terminate the loop. This is
5831 * to avoid sending two write operations, one with a
5832 * length matching clone_len and the final one after
5833 * this loop with a length of len - clone_len.
5835 * When using encoded writes (BTRFS_SEND_FLAG_COMPRESSED
5836 * was passed to the send ioctl), this helps avoid
5837 * sending an encoded write for an offset that is not
5838 * sector size aligned, in case the i_size of the source
5839 * inode is not sector size aligned. That will make the
5840 * receiver fallback to decompression of the data and
5841 * writing it using regular buffered IO, therefore while
5842 * not incorrect, it's not optimal due decompression and
5843 * possible re-compression at the receiver.
5847 ret = send_extent_data(sctx, dst_path, offset,
5857 offset += clone_len;
5858 clone_root->offset += clone_len;
5861 * If we are cloning from the file we are currently processing,
5862 * and using the send root as the clone root, we must stop once
5863 * the current clone offset reaches the current eof of the file
5864 * at the receiver, otherwise we would issue an invalid clone
5865 * operation (source range going beyond eof) and cause the
5866 * receiver to fail. So if we reach the current eof, bail out
5867 * and fallback to a regular write.
5869 if (clone_root->root == sctx->send_root &&
5870 clone_root->ino == sctx->cur_ino &&
5871 clone_root->offset >= sctx->cur_inode_next_write_offset)
5874 data_offset += clone_len;
5880 ret = send_extent_data(sctx, dst_path, offset, len);
5884 btrfs_free_path(path);
5888 static int send_write_or_clone(struct send_ctx *sctx,
5889 struct btrfs_path *path,
5890 struct btrfs_key *key,
5891 struct clone_root *clone_root)
5894 u64 offset = key->offset;
5896 u64 bs = sctx->send_root->fs_info->sb->s_blocksize;
5898 end = min_t(u64, btrfs_file_extent_end(path), sctx->cur_inode_size);
5902 if (clone_root && IS_ALIGNED(end, bs)) {
5903 struct btrfs_file_extent_item *ei;
5907 ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
5908 struct btrfs_file_extent_item);
5909 disk_byte = btrfs_file_extent_disk_bytenr(path->nodes[0], ei);
5910 data_offset = btrfs_file_extent_offset(path->nodes[0], ei);
5911 ret = clone_range(sctx, path, clone_root, disk_byte,
5912 data_offset, offset, end - offset);
5914 ret = send_extent_data(sctx, path, offset, end - offset);
5916 sctx->cur_inode_next_write_offset = end;
5920 static int is_extent_unchanged(struct send_ctx *sctx,
5921 struct btrfs_path *left_path,
5922 struct btrfs_key *ekey)
5925 struct btrfs_key key;
5926 struct btrfs_path *path = NULL;
5927 struct extent_buffer *eb;
5929 struct btrfs_key found_key;
5930 struct btrfs_file_extent_item *ei;
5935 u64 left_offset_fixed;
5943 path = alloc_path_for_send();
5947 eb = left_path->nodes[0];
5948 slot = left_path->slots[0];
5949 ei = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
5950 left_type = btrfs_file_extent_type(eb, ei);
5952 if (left_type != BTRFS_FILE_EXTENT_REG) {
5956 left_disknr = btrfs_file_extent_disk_bytenr(eb, ei);
5957 left_len = btrfs_file_extent_num_bytes(eb, ei);
5958 left_offset = btrfs_file_extent_offset(eb, ei);
5959 left_gen = btrfs_file_extent_generation(eb, ei);
5962 * Following comments will refer to these graphics. L is the left
5963 * extents which we are checking at the moment. 1-8 are the right
5964 * extents that we iterate.
5967 * |-1-|-2a-|-3-|-4-|-5-|-6-|
5970 * |--1--|-2b-|...(same as above)
5972 * Alternative situation. Happens on files where extents got split.
5974 * |-----------7-----------|-6-|
5976 * Alternative situation. Happens on files which got larger.
5979 * Nothing follows after 8.
5982 key.objectid = ekey->objectid;
5983 key.type = BTRFS_EXTENT_DATA_KEY;
5984 key.offset = ekey->offset;
5985 ret = btrfs_search_slot_for_read(sctx->parent_root, &key, path, 0, 0);
5994 * Handle special case where the right side has no extents at all.
5996 eb = path->nodes[0];
5997 slot = path->slots[0];
5998 btrfs_item_key_to_cpu(eb, &found_key, slot);
5999 if (found_key.objectid != key.objectid ||
6000 found_key.type != key.type) {
6001 /* If we're a hole then just pretend nothing changed */
6002 ret = (left_disknr) ? 0 : 1;
6007 * We're now on 2a, 2b or 7.
6010 while (key.offset < ekey->offset + left_len) {
6011 ei = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
6012 right_type = btrfs_file_extent_type(eb, ei);
6013 if (right_type != BTRFS_FILE_EXTENT_REG &&
6014 right_type != BTRFS_FILE_EXTENT_INLINE) {
6019 if (right_type == BTRFS_FILE_EXTENT_INLINE) {
6020 right_len = btrfs_file_extent_ram_bytes(eb, ei);
6021 right_len = PAGE_ALIGN(right_len);
6023 right_len = btrfs_file_extent_num_bytes(eb, ei);
6027 * Are we at extent 8? If yes, we know the extent is changed.
6028 * This may only happen on the first iteration.
6030 if (found_key.offset + right_len <= ekey->offset) {
6031 /* If we're a hole just pretend nothing changed */
6032 ret = (left_disknr) ? 0 : 1;
6037 * We just wanted to see if when we have an inline extent, what
6038 * follows it is a regular extent (wanted to check the above
6039 * condition for inline extents too). This should normally not
6040 * happen but it's possible for example when we have an inline
6041 * compressed extent representing data with a size matching
6042 * the page size (currently the same as sector size).
6044 if (right_type == BTRFS_FILE_EXTENT_INLINE) {
6049 right_disknr = btrfs_file_extent_disk_bytenr(eb, ei);
6050 right_offset = btrfs_file_extent_offset(eb, ei);
6051 right_gen = btrfs_file_extent_generation(eb, ei);
6053 left_offset_fixed = left_offset;
6054 if (key.offset < ekey->offset) {
6055 /* Fix the right offset for 2a and 7. */
6056 right_offset += ekey->offset - key.offset;
6058 /* Fix the left offset for all behind 2a and 2b */
6059 left_offset_fixed += key.offset - ekey->offset;
6063 * Check if we have the same extent.
6065 if (left_disknr != right_disknr ||
6066 left_offset_fixed != right_offset ||
6067 left_gen != right_gen) {
6073 * Go to the next extent.
6075 ret = btrfs_next_item(sctx->parent_root, path);
6079 eb = path->nodes[0];
6080 slot = path->slots[0];
6081 btrfs_item_key_to_cpu(eb, &found_key, slot);
6083 if (ret || found_key.objectid != key.objectid ||
6084 found_key.type != key.type) {
6085 key.offset += right_len;
6088 if (found_key.offset != key.offset + right_len) {
6096 * We're now behind the left extent (treat as unchanged) or at the end
6097 * of the right side (treat as changed).
6099 if (key.offset >= ekey->offset + left_len)
6106 btrfs_free_path(path);
6110 static int get_last_extent(struct send_ctx *sctx, u64 offset)
6112 struct btrfs_path *path;
6113 struct btrfs_root *root = sctx->send_root;
6114 struct btrfs_key key;
6117 path = alloc_path_for_send();
6121 sctx->cur_inode_last_extent = 0;
6123 key.objectid = sctx->cur_ino;
6124 key.type = BTRFS_EXTENT_DATA_KEY;
6125 key.offset = offset;
6126 ret = btrfs_search_slot_for_read(root, &key, path, 0, 1);
6130 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
6131 if (key.objectid != sctx->cur_ino || key.type != BTRFS_EXTENT_DATA_KEY)
6134 sctx->cur_inode_last_extent = btrfs_file_extent_end(path);
6136 btrfs_free_path(path);
6140 static int range_is_hole_in_parent(struct send_ctx *sctx,
6144 struct btrfs_path *path;
6145 struct btrfs_key key;
6146 struct btrfs_root *root = sctx->parent_root;
6147 u64 search_start = start;
6150 path = alloc_path_for_send();
6154 key.objectid = sctx->cur_ino;
6155 key.type = BTRFS_EXTENT_DATA_KEY;
6156 key.offset = search_start;
6157 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
6160 if (ret > 0 && path->slots[0] > 0)
6163 while (search_start < end) {
6164 struct extent_buffer *leaf = path->nodes[0];
6165 int slot = path->slots[0];
6166 struct btrfs_file_extent_item *fi;
6169 if (slot >= btrfs_header_nritems(leaf)) {
6170 ret = btrfs_next_leaf(root, path);
6178 btrfs_item_key_to_cpu(leaf, &key, slot);
6179 if (key.objectid < sctx->cur_ino ||
6180 key.type < BTRFS_EXTENT_DATA_KEY)
6182 if (key.objectid > sctx->cur_ino ||
6183 key.type > BTRFS_EXTENT_DATA_KEY ||
6187 fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);
6188 extent_end = btrfs_file_extent_end(path);
6189 if (extent_end <= start)
6191 if (btrfs_file_extent_disk_bytenr(leaf, fi) == 0) {
6192 search_start = extent_end;
6202 btrfs_free_path(path);
6206 static int maybe_send_hole(struct send_ctx *sctx, struct btrfs_path *path,
6207 struct btrfs_key *key)
6211 if (sctx->cur_ino != key->objectid || !need_send_hole(sctx))
6214 if (sctx->cur_inode_last_extent == (u64)-1) {
6215 ret = get_last_extent(sctx, key->offset - 1);
6220 if (path->slots[0] == 0 &&
6221 sctx->cur_inode_last_extent < key->offset) {
6223 * We might have skipped entire leafs that contained only
6224 * file extent items for our current inode. These leafs have
6225 * a generation number smaller (older) than the one in the
6226 * current leaf and the leaf our last extent came from, and
6227 * are located between these 2 leafs.
6229 ret = get_last_extent(sctx, key->offset - 1);
6234 if (sctx->cur_inode_last_extent < key->offset) {
6235 ret = range_is_hole_in_parent(sctx,
6236 sctx->cur_inode_last_extent,
6241 ret = send_hole(sctx, key->offset);
6245 sctx->cur_inode_last_extent = btrfs_file_extent_end(path);
6249 static int process_extent(struct send_ctx *sctx,
6250 struct btrfs_path *path,
6251 struct btrfs_key *key)
6253 struct clone_root *found_clone = NULL;
6256 if (S_ISLNK(sctx->cur_inode_mode))
6259 if (sctx->parent_root && !sctx->cur_inode_new) {
6260 ret = is_extent_unchanged(sctx, path, key);
6268 struct btrfs_file_extent_item *ei;
6271 ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
6272 struct btrfs_file_extent_item);
6273 type = btrfs_file_extent_type(path->nodes[0], ei);
6274 if (type == BTRFS_FILE_EXTENT_PREALLOC ||
6275 type == BTRFS_FILE_EXTENT_REG) {
6277 * The send spec does not have a prealloc command yet,
6278 * so just leave a hole for prealloc'ed extents until
6279 * we have enough commands queued up to justify rev'ing
6282 if (type == BTRFS_FILE_EXTENT_PREALLOC) {
6287 /* Have a hole, just skip it. */
6288 if (btrfs_file_extent_disk_bytenr(path->nodes[0], ei) == 0) {
6295 ret = find_extent_clone(sctx, path, key->objectid, key->offset,
6296 sctx->cur_inode_size, &found_clone);
6297 if (ret != -ENOENT && ret < 0)
6300 ret = send_write_or_clone(sctx, path, key, found_clone);
6304 ret = maybe_send_hole(sctx, path, key);
6309 static int process_all_extents(struct send_ctx *sctx)
6313 struct btrfs_root *root;
6314 struct btrfs_path *path;
6315 struct btrfs_key key;
6316 struct btrfs_key found_key;
6318 root = sctx->send_root;
6319 path = alloc_path_for_send();
6323 key.objectid = sctx->cmp_key->objectid;
6324 key.type = BTRFS_EXTENT_DATA_KEY;
6326 btrfs_for_each_slot(root, &key, &found_key, path, iter_ret) {
6327 if (found_key.objectid != key.objectid ||
6328 found_key.type != key.type) {
6333 ret = process_extent(sctx, path, &found_key);
6337 /* Catch error found during iteration */
6341 btrfs_free_path(path);
6345 static int process_recorded_refs_if_needed(struct send_ctx *sctx, int at_end,
6347 int *refs_processed)
6351 if (sctx->cur_ino == 0)
6353 if (!at_end && sctx->cur_ino == sctx->cmp_key->objectid &&
6354 sctx->cmp_key->type <= BTRFS_INODE_EXTREF_KEY)
6356 if (list_empty(&sctx->new_refs) && list_empty(&sctx->deleted_refs))
6359 ret = process_recorded_refs(sctx, pending_move);
6363 *refs_processed = 1;
6368 static int finish_inode_if_needed(struct send_ctx *sctx, int at_end)
6371 struct btrfs_inode_info info;
6382 bool need_fileattr = false;
6383 int need_truncate = 1;
6384 int pending_move = 0;
6385 int refs_processed = 0;
6387 if (sctx->ignore_cur_inode)
6390 ret = process_recorded_refs_if_needed(sctx, at_end, &pending_move,
6396 * We have processed the refs and thus need to advance send_progress.
6397 * Now, calls to get_cur_xxx will take the updated refs of the current
6398 * inode into account.
6400 * On the other hand, if our current inode is a directory and couldn't
6401 * be moved/renamed because its parent was renamed/moved too and it has
6402 * a higher inode number, we can only move/rename our current inode
6403 * after we moved/renamed its parent. Therefore in this case operate on
6404 * the old path (pre move/rename) of our current inode, and the
6405 * move/rename will be performed later.
6407 if (refs_processed && !pending_move)
6408 sctx->send_progress = sctx->cur_ino + 1;
6410 if (sctx->cur_ino == 0 || sctx->cur_inode_deleted)
6412 if (!at_end && sctx->cmp_key->objectid == sctx->cur_ino)
6414 ret = get_inode_info(sctx->send_root, sctx->cur_ino, &info);
6417 left_mode = info.mode;
6418 left_uid = info.uid;
6419 left_gid = info.gid;
6420 left_fileattr = info.fileattr;
6422 if (!sctx->parent_root || sctx->cur_inode_new) {
6424 if (!S_ISLNK(sctx->cur_inode_mode))
6426 if (sctx->cur_inode_next_write_offset == sctx->cur_inode_size)
6431 ret = get_inode_info(sctx->parent_root, sctx->cur_ino, &info);
6434 old_size = info.size;
6435 right_mode = info.mode;
6436 right_uid = info.uid;
6437 right_gid = info.gid;
6438 right_fileattr = info.fileattr;
6440 if (left_uid != right_uid || left_gid != right_gid)
6442 if (!S_ISLNK(sctx->cur_inode_mode) && left_mode != right_mode)
6444 if (!S_ISLNK(sctx->cur_inode_mode) && left_fileattr != right_fileattr)
6445 need_fileattr = true;
6446 if ((old_size == sctx->cur_inode_size) ||
6447 (sctx->cur_inode_size > old_size &&
6448 sctx->cur_inode_next_write_offset == sctx->cur_inode_size))
6452 if (S_ISREG(sctx->cur_inode_mode)) {
6453 if (need_send_hole(sctx)) {
6454 if (sctx->cur_inode_last_extent == (u64)-1 ||
6455 sctx->cur_inode_last_extent <
6456 sctx->cur_inode_size) {
6457 ret = get_last_extent(sctx, (u64)-1);
6461 if (sctx->cur_inode_last_extent <
6462 sctx->cur_inode_size) {
6463 ret = send_hole(sctx, sctx->cur_inode_size);
6468 if (need_truncate) {
6469 ret = send_truncate(sctx, sctx->cur_ino,
6470 sctx->cur_inode_gen,
6471 sctx->cur_inode_size);
6478 ret = send_chown(sctx, sctx->cur_ino, sctx->cur_inode_gen,
6479 left_uid, left_gid);
6484 ret = send_chmod(sctx, sctx->cur_ino, sctx->cur_inode_gen,
6489 if (need_fileattr) {
6490 ret = send_fileattr(sctx, sctx->cur_ino, sctx->cur_inode_gen,
6496 if (proto_cmd_ok(sctx, BTRFS_SEND_C_ENABLE_VERITY)
6497 && sctx->cur_inode_needs_verity) {
6498 ret = process_verity(sctx);
6503 ret = send_capabilities(sctx);
6508 * If other directory inodes depended on our current directory
6509 * inode's move/rename, now do their move/rename operations.
6511 if (!is_waiting_for_move(sctx, sctx->cur_ino)) {
6512 ret = apply_children_dir_moves(sctx);
6516 * Need to send that every time, no matter if it actually
6517 * changed between the two trees as we have done changes to
6518 * the inode before. If our inode is a directory and it's
6519 * waiting to be moved/renamed, we will send its utimes when
6520 * it's moved/renamed, therefore we don't need to do it here.
6522 sctx->send_progress = sctx->cur_ino + 1;
6523 ret = send_utimes(sctx, sctx->cur_ino, sctx->cur_inode_gen);
6532 static void close_current_inode(struct send_ctx *sctx)
6536 if (sctx->cur_inode == NULL)
6539 i_size = i_size_read(sctx->cur_inode);
6542 * If we are doing an incremental send, we may have extents between the
6543 * last processed extent and the i_size that have not been processed
6544 * because they haven't changed but we may have read some of their pages
6545 * through readahead, see the comments at send_extent_data().
6547 if (sctx->clean_page_cache && sctx->page_cache_clear_start < i_size)
6548 truncate_inode_pages_range(&sctx->cur_inode->i_data,
6549 sctx->page_cache_clear_start,
6550 round_up(i_size, PAGE_SIZE) - 1);
6552 iput(sctx->cur_inode);
6553 sctx->cur_inode = NULL;
6556 static int changed_inode(struct send_ctx *sctx,
6557 enum btrfs_compare_tree_result result)
6560 struct btrfs_key *key = sctx->cmp_key;
6561 struct btrfs_inode_item *left_ii = NULL;
6562 struct btrfs_inode_item *right_ii = NULL;
6566 close_current_inode(sctx);
6568 sctx->cur_ino = key->objectid;
6569 sctx->cur_inode_new_gen = false;
6570 sctx->cur_inode_last_extent = (u64)-1;
6571 sctx->cur_inode_next_write_offset = 0;
6572 sctx->ignore_cur_inode = false;
6575 * Set send_progress to current inode. This will tell all get_cur_xxx
6576 * functions that the current inode's refs are not updated yet. Later,
6577 * when process_recorded_refs is finished, it is set to cur_ino + 1.
6579 sctx->send_progress = sctx->cur_ino;
6581 if (result == BTRFS_COMPARE_TREE_NEW ||
6582 result == BTRFS_COMPARE_TREE_CHANGED) {
6583 left_ii = btrfs_item_ptr(sctx->left_path->nodes[0],
6584 sctx->left_path->slots[0],
6585 struct btrfs_inode_item);
6586 left_gen = btrfs_inode_generation(sctx->left_path->nodes[0],
6589 right_ii = btrfs_item_ptr(sctx->right_path->nodes[0],
6590 sctx->right_path->slots[0],
6591 struct btrfs_inode_item);
6592 right_gen = btrfs_inode_generation(sctx->right_path->nodes[0],
6595 if (result == BTRFS_COMPARE_TREE_CHANGED) {
6596 right_ii = btrfs_item_ptr(sctx->right_path->nodes[0],
6597 sctx->right_path->slots[0],
6598 struct btrfs_inode_item);
6600 right_gen = btrfs_inode_generation(sctx->right_path->nodes[0],
6604 * The cur_ino = root dir case is special here. We can't treat
6605 * the inode as deleted+reused because it would generate a
6606 * stream that tries to delete/mkdir the root dir.
6608 if (left_gen != right_gen &&
6609 sctx->cur_ino != BTRFS_FIRST_FREE_OBJECTID)
6610 sctx->cur_inode_new_gen = true;
6614 * Normally we do not find inodes with a link count of zero (orphans)
6615 * because the most common case is to create a snapshot and use it
6616 * for a send operation. However other less common use cases involve
6617 * using a subvolume and send it after turning it to RO mode just
6618 * after deleting all hard links of a file while holding an open
6619 * file descriptor against it or turning a RO snapshot into RW mode,
6620 * keep an open file descriptor against a file, delete it and then
6621 * turn the snapshot back to RO mode before using it for a send
6622 * operation. The former is what the receiver operation does.
6623 * Therefore, if we want to send these snapshots soon after they're
6624 * received, we need to handle orphan inodes as well. Moreover, orphans
6625 * can appear not only in the send snapshot but also in the parent
6626 * snapshot. Here are several cases:
6628 * Case 1: BTRFS_COMPARE_TREE_NEW
6629 * | send snapshot | action
6630 * --------------------------------
6631 * nlink | 0 | ignore
6633 * Case 2: BTRFS_COMPARE_TREE_DELETED
6634 * | parent snapshot | action
6635 * ----------------------------------
6636 * nlink | 0 | as usual
6637 * Note: No unlinks will be sent because there're no paths for it.
6639 * Case 3: BTRFS_COMPARE_TREE_CHANGED
6640 * | | parent snapshot | send snapshot | action
6641 * -----------------------------------------------------------------------
6642 * subcase 1 | nlink | 0 | 0 | ignore
6643 * subcase 2 | nlink | >0 | 0 | new_gen(deletion)
6644 * subcase 3 | nlink | 0 | >0 | new_gen(creation)
6647 if (result == BTRFS_COMPARE_TREE_NEW) {
6648 if (btrfs_inode_nlink(sctx->left_path->nodes[0], left_ii) == 0) {
6649 sctx->ignore_cur_inode = true;
6652 sctx->cur_inode_gen = left_gen;
6653 sctx->cur_inode_new = true;
6654 sctx->cur_inode_deleted = false;
6655 sctx->cur_inode_size = btrfs_inode_size(
6656 sctx->left_path->nodes[0], left_ii);
6657 sctx->cur_inode_mode = btrfs_inode_mode(
6658 sctx->left_path->nodes[0], left_ii);
6659 sctx->cur_inode_rdev = btrfs_inode_rdev(
6660 sctx->left_path->nodes[0], left_ii);
6661 if (sctx->cur_ino != BTRFS_FIRST_FREE_OBJECTID)
6662 ret = send_create_inode_if_needed(sctx);
6663 } else if (result == BTRFS_COMPARE_TREE_DELETED) {
6664 sctx->cur_inode_gen = right_gen;
6665 sctx->cur_inode_new = false;
6666 sctx->cur_inode_deleted = true;
6667 sctx->cur_inode_size = btrfs_inode_size(
6668 sctx->right_path->nodes[0], right_ii);
6669 sctx->cur_inode_mode = btrfs_inode_mode(
6670 sctx->right_path->nodes[0], right_ii);
6671 } else if (result == BTRFS_COMPARE_TREE_CHANGED) {
6672 u32 new_nlinks, old_nlinks;
6674 new_nlinks = btrfs_inode_nlink(sctx->left_path->nodes[0], left_ii);
6675 old_nlinks = btrfs_inode_nlink(sctx->right_path->nodes[0], right_ii);
6676 if (new_nlinks == 0 && old_nlinks == 0) {
6677 sctx->ignore_cur_inode = true;
6679 } else if (new_nlinks == 0 || old_nlinks == 0) {
6680 sctx->cur_inode_new_gen = 1;
6683 * We need to do some special handling in case the inode was
6684 * reported as changed with a changed generation number. This
6685 * means that the original inode was deleted and new inode
6686 * reused the same inum. So we have to treat the old inode as
6687 * deleted and the new one as new.
6689 if (sctx->cur_inode_new_gen) {
6691 * First, process the inode as if it was deleted.
6693 if (old_nlinks > 0) {
6694 sctx->cur_inode_gen = right_gen;
6695 sctx->cur_inode_new = false;
6696 sctx->cur_inode_deleted = true;
6697 sctx->cur_inode_size = btrfs_inode_size(
6698 sctx->right_path->nodes[0], right_ii);
6699 sctx->cur_inode_mode = btrfs_inode_mode(
6700 sctx->right_path->nodes[0], right_ii);
6701 ret = process_all_refs(sctx,
6702 BTRFS_COMPARE_TREE_DELETED);
6708 * Now process the inode as if it was new.
6710 if (new_nlinks > 0) {
6711 sctx->cur_inode_gen = left_gen;
6712 sctx->cur_inode_new = true;
6713 sctx->cur_inode_deleted = false;
6714 sctx->cur_inode_size = btrfs_inode_size(
6715 sctx->left_path->nodes[0],
6717 sctx->cur_inode_mode = btrfs_inode_mode(
6718 sctx->left_path->nodes[0],
6720 sctx->cur_inode_rdev = btrfs_inode_rdev(
6721 sctx->left_path->nodes[0],
6723 ret = send_create_inode_if_needed(sctx);
6727 ret = process_all_refs(sctx, BTRFS_COMPARE_TREE_NEW);
6731 * Advance send_progress now as we did not get
6732 * into process_recorded_refs_if_needed in the
6735 sctx->send_progress = sctx->cur_ino + 1;
6738 * Now process all extents and xattrs of the
6739 * inode as if they were all new.
6741 ret = process_all_extents(sctx);
6744 ret = process_all_new_xattrs(sctx);
6749 sctx->cur_inode_gen = left_gen;
6750 sctx->cur_inode_new = false;
6751 sctx->cur_inode_new_gen = false;
6752 sctx->cur_inode_deleted = false;
6753 sctx->cur_inode_size = btrfs_inode_size(
6754 sctx->left_path->nodes[0], left_ii);
6755 sctx->cur_inode_mode = btrfs_inode_mode(
6756 sctx->left_path->nodes[0], left_ii);
6765 * We have to process new refs before deleted refs, but compare_trees gives us
6766 * the new and deleted refs mixed. To fix this, we record the new/deleted refs
6767 * first and later process them in process_recorded_refs.
6768 * For the cur_inode_new_gen case, we skip recording completely because
6769 * changed_inode did already initiate processing of refs. The reason for this is
6770 * that in this case, compare_tree actually compares the refs of 2 different
6771 * inodes. To fix this, process_all_refs is used in changed_inode to handle all
6772 * refs of the right tree as deleted and all refs of the left tree as new.
6774 static int changed_ref(struct send_ctx *sctx,
6775 enum btrfs_compare_tree_result result)
6779 if (sctx->cur_ino != sctx->cmp_key->objectid) {
6780 inconsistent_snapshot_error(sctx, result, "reference");
6784 if (!sctx->cur_inode_new_gen &&
6785 sctx->cur_ino != BTRFS_FIRST_FREE_OBJECTID) {
6786 if (result == BTRFS_COMPARE_TREE_NEW)
6787 ret = record_new_ref(sctx);
6788 else if (result == BTRFS_COMPARE_TREE_DELETED)
6789 ret = record_deleted_ref(sctx);
6790 else if (result == BTRFS_COMPARE_TREE_CHANGED)
6791 ret = record_changed_ref(sctx);
6798 * Process new/deleted/changed xattrs. We skip processing in the
6799 * cur_inode_new_gen case because changed_inode did already initiate processing
6800 * of xattrs. The reason is the same as in changed_ref
6802 static int changed_xattr(struct send_ctx *sctx,
6803 enum btrfs_compare_tree_result result)
6807 if (sctx->cur_ino != sctx->cmp_key->objectid) {
6808 inconsistent_snapshot_error(sctx, result, "xattr");
6812 if (!sctx->cur_inode_new_gen && !sctx->cur_inode_deleted) {
6813 if (result == BTRFS_COMPARE_TREE_NEW)
6814 ret = process_new_xattr(sctx);
6815 else if (result == BTRFS_COMPARE_TREE_DELETED)
6816 ret = process_deleted_xattr(sctx);
6817 else if (result == BTRFS_COMPARE_TREE_CHANGED)
6818 ret = process_changed_xattr(sctx);
6825 * Process new/deleted/changed extents. We skip processing in the
6826 * cur_inode_new_gen case because changed_inode did already initiate processing
6827 * of extents. The reason is the same as in changed_ref
6829 static int changed_extent(struct send_ctx *sctx,
6830 enum btrfs_compare_tree_result result)
6835 * We have found an extent item that changed without the inode item
6836 * having changed. This can happen either after relocation (where the
6837 * disk_bytenr of an extent item is replaced at
6838 * relocation.c:replace_file_extents()) or after deduplication into a
6839 * file in both the parent and send snapshots (where an extent item can
6840 * get modified or replaced with a new one). Note that deduplication
6841 * updates the inode item, but it only changes the iversion (sequence
6842 * field in the inode item) of the inode, so if a file is deduplicated
6843 * the same amount of times in both the parent and send snapshots, its
6844 * iversion becomes the same in both snapshots, whence the inode item is
6845 * the same on both snapshots.
6847 if (sctx->cur_ino != sctx->cmp_key->objectid)
6850 if (!sctx->cur_inode_new_gen && !sctx->cur_inode_deleted) {
6851 if (result != BTRFS_COMPARE_TREE_DELETED)
6852 ret = process_extent(sctx, sctx->left_path,
6859 static int changed_verity(struct send_ctx *sctx, enum btrfs_compare_tree_result result)
6863 if (!sctx->cur_inode_new_gen && !sctx->cur_inode_deleted) {
6864 if (result == BTRFS_COMPARE_TREE_NEW)
6865 sctx->cur_inode_needs_verity = true;
6870 static int dir_changed(struct send_ctx *sctx, u64 dir)
6872 u64 orig_gen, new_gen;
6875 ret = get_inode_gen(sctx->send_root, dir, &new_gen);
6879 ret = get_inode_gen(sctx->parent_root, dir, &orig_gen);
6883 return (orig_gen != new_gen) ? 1 : 0;
6886 static int compare_refs(struct send_ctx *sctx, struct btrfs_path *path,
6887 struct btrfs_key *key)
6889 struct btrfs_inode_extref *extref;
6890 struct extent_buffer *leaf;
6891 u64 dirid = 0, last_dirid = 0;
6898 /* Easy case, just check this one dirid */
6899 if (key->type == BTRFS_INODE_REF_KEY) {
6900 dirid = key->offset;
6902 ret = dir_changed(sctx, dirid);
6906 leaf = path->nodes[0];
6907 item_size = btrfs_item_size(leaf, path->slots[0]);
6908 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
6909 while (cur_offset < item_size) {
6910 extref = (struct btrfs_inode_extref *)(ptr +
6912 dirid = btrfs_inode_extref_parent(leaf, extref);
6913 ref_name_len = btrfs_inode_extref_name_len(leaf, extref);
6914 cur_offset += ref_name_len + sizeof(*extref);
6915 if (dirid == last_dirid)
6917 ret = dir_changed(sctx, dirid);
6927 * Updates compare related fields in sctx and simply forwards to the actual
6928 * changed_xxx functions.
6930 static int changed_cb(struct btrfs_path *left_path,
6931 struct btrfs_path *right_path,
6932 struct btrfs_key *key,
6933 enum btrfs_compare_tree_result result,
6934 struct send_ctx *sctx)
6939 * We can not hold the commit root semaphore here. This is because in
6940 * the case of sending and receiving to the same filesystem, using a
6941 * pipe, could result in a deadlock:
6943 * 1) The task running send blocks on the pipe because it's full;
6945 * 2) The task running receive, which is the only consumer of the pipe,
6946 * is waiting for a transaction commit (for example due to a space
6947 * reservation when doing a write or triggering a transaction commit
6948 * when creating a subvolume);
6950 * 3) The transaction is waiting to write lock the commit root semaphore,
6951 * but can not acquire it since it's being held at 1).
6953 * Down this call chain we write to the pipe through kernel_write().
6954 * The same type of problem can also happen when sending to a file that
6955 * is stored in the same filesystem - when reserving space for a write
6956 * into the file, we can trigger a transaction commit.
6958 * Our caller has supplied us with clones of leaves from the send and
6959 * parent roots, so we're safe here from a concurrent relocation and
6960 * further reallocation of metadata extents while we are here. Below we
6961 * also assert that the leaves are clones.
6963 lockdep_assert_not_held(&sctx->send_root->fs_info->commit_root_sem);
6966 * We always have a send root, so left_path is never NULL. We will not
6967 * have a leaf when we have reached the end of the send root but have
6968 * not yet reached the end of the parent root.
6970 if (left_path->nodes[0])
6971 ASSERT(test_bit(EXTENT_BUFFER_UNMAPPED,
6972 &left_path->nodes[0]->bflags));
6974 * When doing a full send we don't have a parent root, so right_path is
6975 * NULL. When doing an incremental send, we may have reached the end of
6976 * the parent root already, so we don't have a leaf at right_path.
6978 if (right_path && right_path->nodes[0])
6979 ASSERT(test_bit(EXTENT_BUFFER_UNMAPPED,
6980 &right_path->nodes[0]->bflags));
6982 if (result == BTRFS_COMPARE_TREE_SAME) {
6983 if (key->type == BTRFS_INODE_REF_KEY ||
6984 key->type == BTRFS_INODE_EXTREF_KEY) {
6985 ret = compare_refs(sctx, left_path, key);
6990 } else if (key->type == BTRFS_EXTENT_DATA_KEY) {
6991 return maybe_send_hole(sctx, left_path, key);
6995 result = BTRFS_COMPARE_TREE_CHANGED;
6999 sctx->left_path = left_path;
7000 sctx->right_path = right_path;
7001 sctx->cmp_key = key;
7003 ret = finish_inode_if_needed(sctx, 0);
7007 /* Ignore non-FS objects */
7008 if (key->objectid == BTRFS_FREE_INO_OBJECTID ||
7009 key->objectid == BTRFS_FREE_SPACE_OBJECTID)
7012 if (key->type == BTRFS_INODE_ITEM_KEY) {
7013 ret = changed_inode(sctx, result);
7014 } else if (!sctx->ignore_cur_inode) {
7015 if (key->type == BTRFS_INODE_REF_KEY ||
7016 key->type == BTRFS_INODE_EXTREF_KEY)
7017 ret = changed_ref(sctx, result);
7018 else if (key->type == BTRFS_XATTR_ITEM_KEY)
7019 ret = changed_xattr(sctx, result);
7020 else if (key->type == BTRFS_EXTENT_DATA_KEY)
7021 ret = changed_extent(sctx, result);
7022 else if (key->type == BTRFS_VERITY_DESC_ITEM_KEY &&
7024 ret = changed_verity(sctx, result);
7031 static int search_key_again(const struct send_ctx *sctx,
7032 struct btrfs_root *root,
7033 struct btrfs_path *path,
7034 const struct btrfs_key *key)
7038 if (!path->need_commit_sem)
7039 lockdep_assert_held_read(&root->fs_info->commit_root_sem);
7042 * Roots used for send operations are readonly and no one can add,
7043 * update or remove keys from them, so we should be able to find our
7044 * key again. The only exception is deduplication, which can operate on
7045 * readonly roots and add, update or remove keys to/from them - but at
7046 * the moment we don't allow it to run in parallel with send.
7048 ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
7051 btrfs_print_tree(path->nodes[path->lowest_level], false);
7052 btrfs_err(root->fs_info,
7053 "send: key (%llu %u %llu) not found in %s root %llu, lowest_level %d, slot %d",
7054 key->objectid, key->type, key->offset,
7055 (root == sctx->parent_root ? "parent" : "send"),
7056 root->root_key.objectid, path->lowest_level,
7057 path->slots[path->lowest_level]);
7064 static int full_send_tree(struct send_ctx *sctx)
7067 struct btrfs_root *send_root = sctx->send_root;
7068 struct btrfs_key key;
7069 struct btrfs_fs_info *fs_info = send_root->fs_info;
7070 struct btrfs_path *path;
7072 path = alloc_path_for_send();
7075 path->reada = READA_FORWARD_ALWAYS;
7077 key.objectid = BTRFS_FIRST_FREE_OBJECTID;
7078 key.type = BTRFS_INODE_ITEM_KEY;
7081 down_read(&fs_info->commit_root_sem);
7082 sctx->last_reloc_trans = fs_info->last_reloc_trans;
7083 up_read(&fs_info->commit_root_sem);
7085 ret = btrfs_search_slot_for_read(send_root, &key, path, 1, 0);
7092 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
7094 ret = changed_cb(path, NULL, &key,
7095 BTRFS_COMPARE_TREE_NEW, sctx);
7099 down_read(&fs_info->commit_root_sem);
7100 if (fs_info->last_reloc_trans > sctx->last_reloc_trans) {
7101 sctx->last_reloc_trans = fs_info->last_reloc_trans;
7102 up_read(&fs_info->commit_root_sem);
7104 * A transaction used for relocating a block group was
7105 * committed or is about to finish its commit. Release
7106 * our path (leaf) and restart the search, so that we
7107 * avoid operating on any file extent items that are
7108 * stale, with a disk_bytenr that reflects a pre
7109 * relocation value. This way we avoid as much as
7110 * possible to fallback to regular writes when checking
7111 * if we can clone file ranges.
7113 btrfs_release_path(path);
7114 ret = search_key_again(sctx, send_root, path, &key);
7118 up_read(&fs_info->commit_root_sem);
7121 ret = btrfs_next_item(send_root, path);
7131 ret = finish_inode_if_needed(sctx, 1);
7134 btrfs_free_path(path);
7138 static int replace_node_with_clone(struct btrfs_path *path, int level)
7140 struct extent_buffer *clone;
7142 clone = btrfs_clone_extent_buffer(path->nodes[level]);
7146 free_extent_buffer(path->nodes[level]);
7147 path->nodes[level] = clone;
7152 static int tree_move_down(struct btrfs_path *path, int *level, u64 reada_min_gen)
7154 struct extent_buffer *eb;
7155 struct extent_buffer *parent = path->nodes[*level];
7156 int slot = path->slots[*level];
7157 const int nritems = btrfs_header_nritems(parent);
7161 lockdep_assert_held_read(&parent->fs_info->commit_root_sem);
7163 BUG_ON(*level == 0);
7164 eb = btrfs_read_node_slot(parent, slot);
7169 * Trigger readahead for the next leaves we will process, so that it is
7170 * very likely that when we need them they are already in memory and we
7171 * will not block on disk IO. For nodes we only do readahead for one,
7172 * since the time window between processing nodes is typically larger.
7174 reada_max = (*level == 1 ? SZ_128K : eb->fs_info->nodesize);
7176 for (slot++; slot < nritems && reada_done < reada_max; slot++) {
7177 if (btrfs_node_ptr_generation(parent, slot) > reada_min_gen) {
7178 btrfs_readahead_node_child(parent, slot);
7179 reada_done += eb->fs_info->nodesize;
7183 path->nodes[*level - 1] = eb;
7184 path->slots[*level - 1] = 0;
7188 return replace_node_with_clone(path, 0);
7193 static int tree_move_next_or_upnext(struct btrfs_path *path,
7194 int *level, int root_level)
7198 nritems = btrfs_header_nritems(path->nodes[*level]);
7200 path->slots[*level]++;
7202 while (path->slots[*level] >= nritems) {
7203 if (*level == root_level) {
7204 path->slots[*level] = nritems - 1;
7209 path->slots[*level] = 0;
7210 free_extent_buffer(path->nodes[*level]);
7211 path->nodes[*level] = NULL;
7213 path->slots[*level]++;
7215 nritems = btrfs_header_nritems(path->nodes[*level]);
7222 * Returns 1 if it had to move up and next. 0 is returned if it moved only next
7225 static int tree_advance(struct btrfs_path *path,
7226 int *level, int root_level,
7228 struct btrfs_key *key,
7233 if (*level == 0 || !allow_down) {
7234 ret = tree_move_next_or_upnext(path, level, root_level);
7236 ret = tree_move_down(path, level, reada_min_gen);
7240 * Even if we have reached the end of a tree, ret is -1, update the key
7241 * anyway, so that in case we need to restart due to a block group
7242 * relocation, we can assert that the last key of the root node still
7243 * exists in the tree.
7246 btrfs_item_key_to_cpu(path->nodes[*level], key,
7247 path->slots[*level]);
7249 btrfs_node_key_to_cpu(path->nodes[*level], key,
7250 path->slots[*level]);
7255 static int tree_compare_item(struct btrfs_path *left_path,
7256 struct btrfs_path *right_path,
7261 unsigned long off1, off2;
7263 len1 = btrfs_item_size(left_path->nodes[0], left_path->slots[0]);
7264 len2 = btrfs_item_size(right_path->nodes[0], right_path->slots[0]);
7268 off1 = btrfs_item_ptr_offset(left_path->nodes[0], left_path->slots[0]);
7269 off2 = btrfs_item_ptr_offset(right_path->nodes[0],
7270 right_path->slots[0]);
7272 read_extent_buffer(left_path->nodes[0], tmp_buf, off1, len1);
7274 cmp = memcmp_extent_buffer(right_path->nodes[0], tmp_buf, off2, len1);
7281 * A transaction used for relocating a block group was committed or is about to
7282 * finish its commit. Release our paths and restart the search, so that we are
7283 * not using stale extent buffers:
7285 * 1) For levels > 0, we are only holding references of extent buffers, without
7286 * any locks on them, which does not prevent them from having been relocated
7287 * and reallocated after the last time we released the commit root semaphore.
7288 * The exception are the root nodes, for which we always have a clone, see
7289 * the comment at btrfs_compare_trees();
7291 * 2) For leaves, level 0, we are holding copies (clones) of extent buffers, so
7292 * we are safe from the concurrent relocation and reallocation. However they
7293 * can have file extent items with a pre relocation disk_bytenr value, so we
7294 * restart the start from the current commit roots and clone the new leaves so
7295 * that we get the post relocation disk_bytenr values. Not doing so, could
7296 * make us clone the wrong data in case there are new extents using the old
7297 * disk_bytenr that happen to be shared.
7299 static int restart_after_relocation(struct btrfs_path *left_path,
7300 struct btrfs_path *right_path,
7301 const struct btrfs_key *left_key,
7302 const struct btrfs_key *right_key,
7305 const struct send_ctx *sctx)
7310 lockdep_assert_held_read(&sctx->send_root->fs_info->commit_root_sem);
7312 btrfs_release_path(left_path);
7313 btrfs_release_path(right_path);
7316 * Since keys can not be added or removed to/from our roots because they
7317 * are readonly and we do not allow deduplication to run in parallel
7318 * (which can add, remove or change keys), the layout of the trees should
7321 left_path->lowest_level = left_level;
7322 ret = search_key_again(sctx, sctx->send_root, left_path, left_key);
7326 right_path->lowest_level = right_level;
7327 ret = search_key_again(sctx, sctx->parent_root, right_path, right_key);
7332 * If the lowest level nodes are leaves, clone them so that they can be
7333 * safely used by changed_cb() while not under the protection of the
7334 * commit root semaphore, even if relocation and reallocation happens in
7337 if (left_level == 0) {
7338 ret = replace_node_with_clone(left_path, 0);
7343 if (right_level == 0) {
7344 ret = replace_node_with_clone(right_path, 0);
7350 * Now clone the root nodes (unless they happen to be the leaves we have
7351 * already cloned). This is to protect against concurrent snapshotting of
7352 * the send and parent roots (see the comment at btrfs_compare_trees()).
7354 root_level = btrfs_header_level(sctx->send_root->commit_root);
7355 if (root_level > 0) {
7356 ret = replace_node_with_clone(left_path, root_level);
7361 root_level = btrfs_header_level(sctx->parent_root->commit_root);
7362 if (root_level > 0) {
7363 ret = replace_node_with_clone(right_path, root_level);
7372 * This function compares two trees and calls the provided callback for
7373 * every changed/new/deleted item it finds.
7374 * If shared tree blocks are encountered, whole subtrees are skipped, making
7375 * the compare pretty fast on snapshotted subvolumes.
7377 * This currently works on commit roots only. As commit roots are read only,
7378 * we don't do any locking. The commit roots are protected with transactions.
7379 * Transactions are ended and rejoined when a commit is tried in between.
7381 * This function checks for modifications done to the trees while comparing.
7382 * If it detects a change, it aborts immediately.
7384 static int btrfs_compare_trees(struct btrfs_root *left_root,
7385 struct btrfs_root *right_root, struct send_ctx *sctx)
7387 struct btrfs_fs_info *fs_info = left_root->fs_info;
7390 struct btrfs_path *left_path = NULL;
7391 struct btrfs_path *right_path = NULL;
7392 struct btrfs_key left_key;
7393 struct btrfs_key right_key;
7394 char *tmp_buf = NULL;
7395 int left_root_level;
7396 int right_root_level;
7399 int left_end_reached = 0;
7400 int right_end_reached = 0;
7401 int advance_left = 0;
7402 int advance_right = 0;
7409 left_path = btrfs_alloc_path();
7414 right_path = btrfs_alloc_path();
7420 tmp_buf = kvmalloc(fs_info->nodesize, GFP_KERNEL);
7426 left_path->search_commit_root = 1;
7427 left_path->skip_locking = 1;
7428 right_path->search_commit_root = 1;
7429 right_path->skip_locking = 1;
7432 * Strategy: Go to the first items of both trees. Then do
7434 * If both trees are at level 0
7435 * Compare keys of current items
7436 * If left < right treat left item as new, advance left tree
7438 * If left > right treat right item as deleted, advance right tree
7440 * If left == right do deep compare of items, treat as changed if
7441 * needed, advance both trees and repeat
7442 * If both trees are at the same level but not at level 0
7443 * Compare keys of current nodes/leafs
7444 * If left < right advance left tree and repeat
7445 * If left > right advance right tree and repeat
7446 * If left == right compare blockptrs of the next nodes/leafs
7447 * If they match advance both trees but stay at the same level
7449 * If they don't match advance both trees while allowing to go
7451 * If tree levels are different
7452 * Advance the tree that needs it and repeat
7454 * Advancing a tree means:
7455 * If we are at level 0, try to go to the next slot. If that's not
7456 * possible, go one level up and repeat. Stop when we found a level
7457 * where we could go to the next slot. We may at this point be on a
7460 * If we are not at level 0 and not on shared tree blocks, go one
7463 * If we are not at level 0 and on shared tree blocks, go one slot to
7464 * the right if possible or go up and right.
7467 down_read(&fs_info->commit_root_sem);
7468 left_level = btrfs_header_level(left_root->commit_root);
7469 left_root_level = left_level;
7471 * We clone the root node of the send and parent roots to prevent races
7472 * with snapshot creation of these roots. Snapshot creation COWs the
7473 * root node of a tree, so after the transaction is committed the old
7474 * extent can be reallocated while this send operation is still ongoing.
7475 * So we clone them, under the commit root semaphore, to be race free.
7477 left_path->nodes[left_level] =
7478 btrfs_clone_extent_buffer(left_root->commit_root);
7479 if (!left_path->nodes[left_level]) {
7484 right_level = btrfs_header_level(right_root->commit_root);
7485 right_root_level = right_level;
7486 right_path->nodes[right_level] =
7487 btrfs_clone_extent_buffer(right_root->commit_root);
7488 if (!right_path->nodes[right_level]) {
7493 * Our right root is the parent root, while the left root is the "send"
7494 * root. We know that all new nodes/leaves in the left root must have
7495 * a generation greater than the right root's generation, so we trigger
7496 * readahead for those nodes and leaves of the left root, as we know we
7497 * will need to read them at some point.
7499 reada_min_gen = btrfs_header_generation(right_root->commit_root);
7501 if (left_level == 0)
7502 btrfs_item_key_to_cpu(left_path->nodes[left_level],
7503 &left_key, left_path->slots[left_level]);
7505 btrfs_node_key_to_cpu(left_path->nodes[left_level],
7506 &left_key, left_path->slots[left_level]);
7507 if (right_level == 0)
7508 btrfs_item_key_to_cpu(right_path->nodes[right_level],
7509 &right_key, right_path->slots[right_level]);
7511 btrfs_node_key_to_cpu(right_path->nodes[right_level],
7512 &right_key, right_path->slots[right_level]);
7514 sctx->last_reloc_trans = fs_info->last_reloc_trans;
7517 if (need_resched() ||
7518 rwsem_is_contended(&fs_info->commit_root_sem)) {
7519 up_read(&fs_info->commit_root_sem);
7521 down_read(&fs_info->commit_root_sem);
7524 if (fs_info->last_reloc_trans > sctx->last_reloc_trans) {
7525 ret = restart_after_relocation(left_path, right_path,
7526 &left_key, &right_key,
7527 left_level, right_level,
7531 sctx->last_reloc_trans = fs_info->last_reloc_trans;
7534 if (advance_left && !left_end_reached) {
7535 ret = tree_advance(left_path, &left_level,
7537 advance_left != ADVANCE_ONLY_NEXT,
7538 &left_key, reada_min_gen);
7540 left_end_reached = ADVANCE;
7545 if (advance_right && !right_end_reached) {
7546 ret = tree_advance(right_path, &right_level,
7548 advance_right != ADVANCE_ONLY_NEXT,
7549 &right_key, reada_min_gen);
7551 right_end_reached = ADVANCE;
7557 if (left_end_reached && right_end_reached) {
7560 } else if (left_end_reached) {
7561 if (right_level == 0) {
7562 up_read(&fs_info->commit_root_sem);
7563 ret = changed_cb(left_path, right_path,
7565 BTRFS_COMPARE_TREE_DELETED,
7569 down_read(&fs_info->commit_root_sem);
7571 advance_right = ADVANCE;
7573 } else if (right_end_reached) {
7574 if (left_level == 0) {
7575 up_read(&fs_info->commit_root_sem);
7576 ret = changed_cb(left_path, right_path,
7578 BTRFS_COMPARE_TREE_NEW,
7582 down_read(&fs_info->commit_root_sem);
7584 advance_left = ADVANCE;
7588 if (left_level == 0 && right_level == 0) {
7589 up_read(&fs_info->commit_root_sem);
7590 cmp = btrfs_comp_cpu_keys(&left_key, &right_key);
7592 ret = changed_cb(left_path, right_path,
7594 BTRFS_COMPARE_TREE_NEW,
7596 advance_left = ADVANCE;
7597 } else if (cmp > 0) {
7598 ret = changed_cb(left_path, right_path,
7600 BTRFS_COMPARE_TREE_DELETED,
7602 advance_right = ADVANCE;
7604 enum btrfs_compare_tree_result result;
7606 WARN_ON(!extent_buffer_uptodate(left_path->nodes[0]));
7607 ret = tree_compare_item(left_path, right_path,
7610 result = BTRFS_COMPARE_TREE_CHANGED;
7612 result = BTRFS_COMPARE_TREE_SAME;
7613 ret = changed_cb(left_path, right_path,
7614 &left_key, result, sctx);
7615 advance_left = ADVANCE;
7616 advance_right = ADVANCE;
7621 down_read(&fs_info->commit_root_sem);
7622 } else if (left_level == right_level) {
7623 cmp = btrfs_comp_cpu_keys(&left_key, &right_key);
7625 advance_left = ADVANCE;
7626 } else if (cmp > 0) {
7627 advance_right = ADVANCE;
7629 left_blockptr = btrfs_node_blockptr(
7630 left_path->nodes[left_level],
7631 left_path->slots[left_level]);
7632 right_blockptr = btrfs_node_blockptr(
7633 right_path->nodes[right_level],
7634 right_path->slots[right_level]);
7635 left_gen = btrfs_node_ptr_generation(
7636 left_path->nodes[left_level],
7637 left_path->slots[left_level]);
7638 right_gen = btrfs_node_ptr_generation(
7639 right_path->nodes[right_level],
7640 right_path->slots[right_level]);
7641 if (left_blockptr == right_blockptr &&
7642 left_gen == right_gen) {
7644 * As we're on a shared block, don't
7645 * allow to go deeper.
7647 advance_left = ADVANCE_ONLY_NEXT;
7648 advance_right = ADVANCE_ONLY_NEXT;
7650 advance_left = ADVANCE;
7651 advance_right = ADVANCE;
7654 } else if (left_level < right_level) {
7655 advance_right = ADVANCE;
7657 advance_left = ADVANCE;
7662 up_read(&fs_info->commit_root_sem);
7664 btrfs_free_path(left_path);
7665 btrfs_free_path(right_path);
7670 static int send_subvol(struct send_ctx *sctx)
7674 if (!(sctx->flags & BTRFS_SEND_FLAG_OMIT_STREAM_HEADER)) {
7675 ret = send_header(sctx);
7680 ret = send_subvol_begin(sctx);
7684 if (sctx->parent_root) {
7685 ret = btrfs_compare_trees(sctx->send_root, sctx->parent_root, sctx);
7688 ret = finish_inode_if_needed(sctx, 1);
7692 ret = full_send_tree(sctx);
7698 free_recorded_refs(sctx);
7703 * If orphan cleanup did remove any orphans from a root, it means the tree
7704 * was modified and therefore the commit root is not the same as the current
7705 * root anymore. This is a problem, because send uses the commit root and
7706 * therefore can see inode items that don't exist in the current root anymore,
7707 * and for example make calls to btrfs_iget, which will do tree lookups based
7708 * on the current root and not on the commit root. Those lookups will fail,
7709 * returning a -ESTALE error, and making send fail with that error. So make
7710 * sure a send does not see any orphans we have just removed, and that it will
7711 * see the same inodes regardless of whether a transaction commit happened
7712 * before it started (meaning that the commit root will be the same as the
7713 * current root) or not.
7715 static int ensure_commit_roots_uptodate(struct send_ctx *sctx)
7718 struct btrfs_trans_handle *trans = NULL;
7721 if (sctx->parent_root &&
7722 sctx->parent_root->node != sctx->parent_root->commit_root)
7725 for (i = 0; i < sctx->clone_roots_cnt; i++)
7726 if (sctx->clone_roots[i].root->node !=
7727 sctx->clone_roots[i].root->commit_root)
7731 return btrfs_end_transaction(trans);
7736 /* Use any root, all fs roots will get their commit roots updated. */
7738 trans = btrfs_join_transaction(sctx->send_root);
7740 return PTR_ERR(trans);
7744 return btrfs_commit_transaction(trans);
7748 * Make sure any existing dellaloc is flushed for any root used by a send
7749 * operation so that we do not miss any data and we do not race with writeback
7750 * finishing and changing a tree while send is using the tree. This could
7751 * happen if a subvolume is in RW mode, has delalloc, is turned to RO mode and
7752 * a send operation then uses the subvolume.
7753 * After flushing delalloc ensure_commit_roots_uptodate() must be called.
7755 static int flush_delalloc_roots(struct send_ctx *sctx)
7757 struct btrfs_root *root = sctx->parent_root;
7762 ret = btrfs_start_delalloc_snapshot(root, false);
7765 btrfs_wait_ordered_extents(root, U64_MAX, 0, U64_MAX);
7768 for (i = 0; i < sctx->clone_roots_cnt; i++) {
7769 root = sctx->clone_roots[i].root;
7770 ret = btrfs_start_delalloc_snapshot(root, false);
7773 btrfs_wait_ordered_extents(root, U64_MAX, 0, U64_MAX);
7779 static void btrfs_root_dec_send_in_progress(struct btrfs_root* root)
7781 spin_lock(&root->root_item_lock);
7782 root->send_in_progress--;
7784 * Not much left to do, we don't know why it's unbalanced and
7785 * can't blindly reset it to 0.
7787 if (root->send_in_progress < 0)
7788 btrfs_err(root->fs_info,
7789 "send_in_progress unbalanced %d root %llu",
7790 root->send_in_progress, root->root_key.objectid);
7791 spin_unlock(&root->root_item_lock);
7794 static void dedupe_in_progress_warn(const struct btrfs_root *root)
7796 btrfs_warn_rl(root->fs_info,
7797 "cannot use root %llu for send while deduplications on it are in progress (%d in progress)",
7798 root->root_key.objectid, root->dedupe_in_progress);
7801 long btrfs_ioctl_send(struct inode *inode, struct btrfs_ioctl_send_args *arg)
7804 struct btrfs_root *send_root = BTRFS_I(inode)->root;
7805 struct btrfs_fs_info *fs_info = send_root->fs_info;
7806 struct btrfs_root *clone_root;
7807 struct send_ctx *sctx = NULL;
7809 u64 *clone_sources_tmp = NULL;
7810 int clone_sources_to_rollback = 0;
7812 int sort_clone_roots = 0;
7814 if (!capable(CAP_SYS_ADMIN))
7818 * The subvolume must remain read-only during send, protect against
7819 * making it RW. This also protects against deletion.
7821 spin_lock(&send_root->root_item_lock);
7822 if (btrfs_root_readonly(send_root) && send_root->dedupe_in_progress) {
7823 dedupe_in_progress_warn(send_root);
7824 spin_unlock(&send_root->root_item_lock);
7827 send_root->send_in_progress++;
7828 spin_unlock(&send_root->root_item_lock);
7831 * Userspace tools do the checks and warn the user if it's
7834 if (!btrfs_root_readonly(send_root)) {
7840 * Check that we don't overflow at later allocations, we request
7841 * clone_sources_count + 1 items, and compare to unsigned long inside
7844 if (arg->clone_sources_count >
7845 ULONG_MAX / sizeof(struct clone_root) - 1) {
7850 if (arg->flags & ~BTRFS_SEND_FLAG_MASK) {
7855 sctx = kzalloc(sizeof(struct send_ctx), GFP_KERNEL);
7861 INIT_LIST_HEAD(&sctx->new_refs);
7862 INIT_LIST_HEAD(&sctx->deleted_refs);
7863 INIT_RADIX_TREE(&sctx->name_cache, GFP_KERNEL);
7864 INIT_LIST_HEAD(&sctx->name_cache_list);
7866 sctx->flags = arg->flags;
7868 if (arg->flags & BTRFS_SEND_FLAG_VERSION) {
7869 if (arg->version > BTRFS_SEND_STREAM_VERSION) {
7873 /* Zero means "use the highest version" */
7874 sctx->proto = arg->version ?: BTRFS_SEND_STREAM_VERSION;
7878 if ((arg->flags & BTRFS_SEND_FLAG_COMPRESSED) && sctx->proto < 2) {
7883 sctx->send_filp = fget(arg->send_fd);
7884 if (!sctx->send_filp) {
7889 sctx->send_root = send_root;
7891 * Unlikely but possible, if the subvolume is marked for deletion but
7892 * is slow to remove the directory entry, send can still be started
7894 if (btrfs_root_dead(sctx->send_root)) {
7899 sctx->clone_roots_cnt = arg->clone_sources_count;
7901 if (sctx->proto >= 2) {
7902 u32 send_buf_num_pages;
7904 sctx->send_max_size = ALIGN(SZ_16K + BTRFS_MAX_COMPRESSED, PAGE_SIZE);
7905 sctx->send_buf = vmalloc(sctx->send_max_size);
7906 if (!sctx->send_buf) {
7910 send_buf_num_pages = sctx->send_max_size >> PAGE_SHIFT;
7911 sctx->send_buf_pages = kcalloc(send_buf_num_pages,
7912 sizeof(*sctx->send_buf_pages),
7914 if (!sctx->send_buf_pages) {
7918 for (i = 0; i < send_buf_num_pages; i++) {
7919 sctx->send_buf_pages[i] =
7920 vmalloc_to_page(sctx->send_buf + (i << PAGE_SHIFT));
7923 sctx->send_max_size = BTRFS_SEND_BUF_SIZE_V1;
7924 sctx->send_buf = kvmalloc(sctx->send_max_size, GFP_KERNEL);
7926 if (!sctx->send_buf) {
7931 sctx->pending_dir_moves = RB_ROOT;
7932 sctx->waiting_dir_moves = RB_ROOT;
7933 sctx->orphan_dirs = RB_ROOT;
7934 sctx->rbtree_new_refs = RB_ROOT;
7935 sctx->rbtree_deleted_refs = RB_ROOT;
7937 sctx->clone_roots = kvcalloc(sizeof(*sctx->clone_roots),
7938 arg->clone_sources_count + 1,
7940 if (!sctx->clone_roots) {
7945 alloc_size = array_size(sizeof(*arg->clone_sources),
7946 arg->clone_sources_count);
7948 if (arg->clone_sources_count) {
7949 clone_sources_tmp = kvmalloc(alloc_size, GFP_KERNEL);
7950 if (!clone_sources_tmp) {
7955 ret = copy_from_user(clone_sources_tmp, arg->clone_sources,
7962 for (i = 0; i < arg->clone_sources_count; i++) {
7963 clone_root = btrfs_get_fs_root(fs_info,
7964 clone_sources_tmp[i], true);
7965 if (IS_ERR(clone_root)) {
7966 ret = PTR_ERR(clone_root);
7969 spin_lock(&clone_root->root_item_lock);
7970 if (!btrfs_root_readonly(clone_root) ||
7971 btrfs_root_dead(clone_root)) {
7972 spin_unlock(&clone_root->root_item_lock);
7973 btrfs_put_root(clone_root);
7977 if (clone_root->dedupe_in_progress) {
7978 dedupe_in_progress_warn(clone_root);
7979 spin_unlock(&clone_root->root_item_lock);
7980 btrfs_put_root(clone_root);
7984 clone_root->send_in_progress++;
7985 spin_unlock(&clone_root->root_item_lock);
7987 sctx->clone_roots[i].root = clone_root;
7988 clone_sources_to_rollback = i + 1;
7990 kvfree(clone_sources_tmp);
7991 clone_sources_tmp = NULL;
7994 if (arg->parent_root) {
7995 sctx->parent_root = btrfs_get_fs_root(fs_info, arg->parent_root,
7997 if (IS_ERR(sctx->parent_root)) {
7998 ret = PTR_ERR(sctx->parent_root);
8002 spin_lock(&sctx->parent_root->root_item_lock);
8003 sctx->parent_root->send_in_progress++;
8004 if (!btrfs_root_readonly(sctx->parent_root) ||
8005 btrfs_root_dead(sctx->parent_root)) {
8006 spin_unlock(&sctx->parent_root->root_item_lock);
8010 if (sctx->parent_root->dedupe_in_progress) {
8011 dedupe_in_progress_warn(sctx->parent_root);
8012 spin_unlock(&sctx->parent_root->root_item_lock);
8016 spin_unlock(&sctx->parent_root->root_item_lock);
8020 * Clones from send_root are allowed, but only if the clone source
8021 * is behind the current send position. This is checked while searching
8022 * for possible clone sources.
8024 sctx->clone_roots[sctx->clone_roots_cnt++].root =
8025 btrfs_grab_root(sctx->send_root);
8027 /* We do a bsearch later */
8028 sort(sctx->clone_roots, sctx->clone_roots_cnt,
8029 sizeof(*sctx->clone_roots), __clone_root_cmp_sort,
8031 sort_clone_roots = 1;
8033 ret = flush_delalloc_roots(sctx);
8037 ret = ensure_commit_roots_uptodate(sctx);
8041 ret = send_subvol(sctx);
8045 if (!(sctx->flags & BTRFS_SEND_FLAG_OMIT_END_CMD)) {
8046 ret = begin_cmd(sctx, BTRFS_SEND_C_END);
8049 ret = send_cmd(sctx);
8055 WARN_ON(sctx && !ret && !RB_EMPTY_ROOT(&sctx->pending_dir_moves));
8056 while (sctx && !RB_EMPTY_ROOT(&sctx->pending_dir_moves)) {
8058 struct pending_dir_move *pm;
8060 n = rb_first(&sctx->pending_dir_moves);
8061 pm = rb_entry(n, struct pending_dir_move, node);
8062 while (!list_empty(&pm->list)) {
8063 struct pending_dir_move *pm2;
8065 pm2 = list_first_entry(&pm->list,
8066 struct pending_dir_move, list);
8067 free_pending_move(sctx, pm2);
8069 free_pending_move(sctx, pm);
8072 WARN_ON(sctx && !ret && !RB_EMPTY_ROOT(&sctx->waiting_dir_moves));
8073 while (sctx && !RB_EMPTY_ROOT(&sctx->waiting_dir_moves)) {
8075 struct waiting_dir_move *dm;
8077 n = rb_first(&sctx->waiting_dir_moves);
8078 dm = rb_entry(n, struct waiting_dir_move, node);
8079 rb_erase(&dm->node, &sctx->waiting_dir_moves);
8083 WARN_ON(sctx && !ret && !RB_EMPTY_ROOT(&sctx->orphan_dirs));
8084 while (sctx && !RB_EMPTY_ROOT(&sctx->orphan_dirs)) {
8086 struct orphan_dir_info *odi;
8088 n = rb_first(&sctx->orphan_dirs);
8089 odi = rb_entry(n, struct orphan_dir_info, node);
8090 free_orphan_dir_info(sctx, odi);
8093 if (sort_clone_roots) {
8094 for (i = 0; i < sctx->clone_roots_cnt; i++) {
8095 btrfs_root_dec_send_in_progress(
8096 sctx->clone_roots[i].root);
8097 btrfs_put_root(sctx->clone_roots[i].root);
8100 for (i = 0; sctx && i < clone_sources_to_rollback; i++) {
8101 btrfs_root_dec_send_in_progress(
8102 sctx->clone_roots[i].root);
8103 btrfs_put_root(sctx->clone_roots[i].root);
8106 btrfs_root_dec_send_in_progress(send_root);
8108 if (sctx && !IS_ERR_OR_NULL(sctx->parent_root)) {
8109 btrfs_root_dec_send_in_progress(sctx->parent_root);
8110 btrfs_put_root(sctx->parent_root);
8113 kvfree(clone_sources_tmp);
8116 if (sctx->send_filp)
8117 fput(sctx->send_filp);
8119 kvfree(sctx->clone_roots);
8120 kfree(sctx->send_buf_pages);
8121 kvfree(sctx->send_buf);
8122 kvfree(sctx->verity_descriptor);
8124 name_cache_free(sctx);
8126 close_current_inode(sctx);