8467 lines · c
1// SPDX-License-Identifier: GPL-2.02/*3 * Copyright (C) 2012 Alexander Block. All rights reserved.4 */5 6#include <linux/bsearch.h>7#include <linux/fs.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>19 20#include "send.h"21#include "ctree.h"22#include "backref.h"23#include "locking.h"24#include "disk-io.h"25#include "btrfs_inode.h"26#include "transaction.h"27#include "compression.h"28#include "print-tree.h"29#include "accessors.h"30#include "dir-item.h"31#include "file-item.h"32#include "ioctl.h"33#include "verity.h"34#include "lru_cache.h"35 36/*37 * Maximum number of references an extent can have in order for us to attempt to38 * issue clone operations instead of write operations. This currently exists to39 * avoid hitting limitations of the backreference walking code (taking a lot of40 * time and using too much memory for extents with large number of references).41 */42#define SEND_MAX_EXTENT_REFS 102443 44/*45 * A fs_path is a helper to dynamically build path names with unknown size.46 * It reallocates the internal buffer on demand.47 * It allows fast adding of path elements on the right side (normal path) and48 * fast adding to the left side (reversed path). A reversed path can also be49 * unreversed if needed.50 */51struct fs_path {52 union {53 struct {54 char *start;55 char *end;56 57 char *buf;58 unsigned short buf_len:15;59 unsigned short reversed:1;60 char inline_buf[];61 };62 /*63 * Average path length does not exceed 200 bytes, we'll have64 * better packing in the slab and higher chance to satisfy65 * an allocation later during send.66 */67 char pad[256];68 };69};70#define FS_PATH_INLINE_SIZE \71 (sizeof(struct fs_path) - offsetof(struct fs_path, inline_buf))72 73 74/* reused for each extent */75struct clone_root {76 struct btrfs_root *root;77 u64 ino;78 u64 offset;79 u64 num_bytes;80 bool found_ref;81};82 83#define SEND_MAX_NAME_CACHE_SIZE 25684 85/*86 * Limit the root_ids array of struct backref_cache_entry to 17 elements.87 * This makes the size of a cache entry to be exactly 192 bytes on x86_64, which88 * can be satisfied from the kmalloc-192 slab, without wasting any space.89 * The most common case is to have a single root for cloning, which corresponds90 * to the send root. Having the user specify more than 16 clone roots is not91 * common, and in such rare cases we simply don't use caching if the number of92 * cloning roots that lead down to a leaf is more than 17.93 */94#define SEND_MAX_BACKREF_CACHE_ROOTS 1795 96/*97 * Max number of entries in the cache.98 * With SEND_MAX_BACKREF_CACHE_ROOTS as 17, the size in bytes, excluding99 * maple tree's internal nodes, is 24K.100 */101#define SEND_MAX_BACKREF_CACHE_SIZE 128102 103/*104 * A backref cache entry maps a leaf to a list of IDs of roots from which the105 * leaf is accessible and we can use for clone operations.106 * With SEND_MAX_BACKREF_CACHE_ROOTS as 12, each cache entry is 128 bytes (on107 * x86_64).108 */109struct backref_cache_entry {110 struct btrfs_lru_cache_entry entry;111 u64 root_ids[SEND_MAX_BACKREF_CACHE_ROOTS];112 /* Number of valid elements in the root_ids array. */113 int num_roots;114};115 116/* See the comment at lru_cache.h about struct btrfs_lru_cache_entry. */117static_assert(offsetof(struct backref_cache_entry, entry) == 0);118 119/*120 * Max number of entries in the cache that stores directories that were already121 * created. The cache uses raw struct btrfs_lru_cache_entry entries, so it uses122 * at most 4096 bytes - sizeof(struct btrfs_lru_cache_entry) is 48 bytes, but123 * the kmalloc-64 slab is used, so we get 4096 bytes (64 bytes * 64).124 */125#define SEND_MAX_DIR_CREATED_CACHE_SIZE 64126 127/*128 * Max number of entries in the cache that stores directories that were already129 * created. The cache uses raw struct btrfs_lru_cache_entry entries, so it uses130 * at most 4096 bytes - sizeof(struct btrfs_lru_cache_entry) is 48 bytes, but131 * the kmalloc-64 slab is used, so we get 4096 bytes (64 bytes * 64).132 */133#define SEND_MAX_DIR_UTIMES_CACHE_SIZE 64134 135struct send_ctx {136 struct file *send_filp;137 loff_t send_off;138 char *send_buf;139 u32 send_size;140 u32 send_max_size;141 /*142 * Whether BTRFS_SEND_A_DATA attribute was already added to current143 * command (since protocol v2, data must be the last attribute).144 */145 bool put_data;146 struct page **send_buf_pages;147 u64 flags; /* 'flags' member of btrfs_ioctl_send_args is u64 */148 /* Protocol version compatibility requested */149 u32 proto;150 151 struct btrfs_root *send_root;152 struct btrfs_root *parent_root;153 struct clone_root *clone_roots;154 int clone_roots_cnt;155 156 /* current state of the compare_tree call */157 struct btrfs_path *left_path;158 struct btrfs_path *right_path;159 struct btrfs_key *cmp_key;160 161 /*162 * Keep track of the generation of the last transaction that was used163 * for relocating a block group. This is periodically checked in order164 * to detect if a relocation happened since the last check, so that we165 * don't operate on stale extent buffers for nodes (level >= 1) or on166 * stale disk_bytenr values of file extent items.167 */168 u64 last_reloc_trans;169 170 /*171 * infos of the currently processed inode. In case of deleted inodes,172 * these are the values from the deleted inode.173 */174 u64 cur_ino;175 u64 cur_inode_gen;176 u64 cur_inode_size;177 u64 cur_inode_mode;178 u64 cur_inode_rdev;179 u64 cur_inode_last_extent;180 u64 cur_inode_next_write_offset;181 bool cur_inode_new;182 bool cur_inode_new_gen;183 bool cur_inode_deleted;184 bool ignore_cur_inode;185 bool cur_inode_needs_verity;186 void *verity_descriptor;187 188 u64 send_progress;189 190 struct list_head new_refs;191 struct list_head deleted_refs;192 193 struct btrfs_lru_cache name_cache;194 195 /*196 * The inode we are currently processing. It's not NULL only when we197 * need to issue write commands for data extents from this inode.198 */199 struct inode *cur_inode;200 struct file_ra_state ra;201 u64 page_cache_clear_start;202 bool clean_page_cache;203 204 /*205 * We process inodes by their increasing order, so if before an206 * incremental send we reverse the parent/child relationship of207 * directories such that a directory with a lower inode number was208 * the parent of a directory with a higher inode number, and the one209 * becoming the new parent got renamed too, we can't rename/move the210 * directory with lower inode number when we finish processing it - we211 * must process the directory with higher inode number first, then212 * rename/move it and then rename/move the directory with lower inode213 * number. Example follows.214 *215 * Tree state when the first send was performed:216 *217 * .218 * |-- a (ino 257)219 * |-- b (ino 258)220 * |221 * |222 * |-- c (ino 259)223 * | |-- d (ino 260)224 * |225 * |-- c2 (ino 261)226 *227 * Tree state when the second (incremental) send is performed:228 *229 * .230 * |-- a (ino 257)231 * |-- b (ino 258)232 * |-- c2 (ino 261)233 * |-- d2 (ino 260)234 * |-- cc (ino 259)235 *236 * The sequence of steps that lead to the second state was:237 *238 * mv /a/b/c/d /a/b/c2/d2239 * mv /a/b/c /a/b/c2/d2/cc240 *241 * "c" has lower inode number, but we can't move it (2nd mv operation)242 * before we move "d", which has higher inode number.243 *244 * So we just memorize which move/rename operations must be performed245 * later when their respective parent is processed and moved/renamed.246 */247 248 /* Indexed by parent directory inode number. */249 struct rb_root pending_dir_moves;250 251 /*252 * Reverse index, indexed by the inode number of a directory that253 * is waiting for the move/rename of its immediate parent before its254 * own move/rename can be performed.255 */256 struct rb_root waiting_dir_moves;257 258 /*259 * A directory that is going to be rm'ed might have a child directory260 * which is in the pending directory moves index above. In this case,261 * the directory can only be removed after the move/rename of its child262 * is performed. Example:263 *264 * Parent snapshot:265 *266 * . (ino 256)267 * |-- a/ (ino 257)268 * |-- b/ (ino 258)269 * |-- c/ (ino 259)270 * | |-- x/ (ino 260)271 * |272 * |-- y/ (ino 261)273 *274 * Send snapshot:275 *276 * . (ino 256)277 * |-- a/ (ino 257)278 * |-- b/ (ino 258)279 * |-- YY/ (ino 261)280 * |-- x/ (ino 260)281 *282 * Sequence of steps that lead to the send snapshot:283 * rm -f /a/b/c/foo.txt284 * mv /a/b/y /a/b/YY285 * mv /a/b/c/x /a/b/YY286 * rmdir /a/b/c287 *288 * When the child is processed, its move/rename is delayed until its289 * parent is processed (as explained above), but all other operations290 * like update utimes, chown, chgrp, etc, are performed and the paths291 * that it uses for those operations must use the orphanized name of292 * its parent (the directory we're going to rm later), so we need to293 * memorize that name.294 *295 * Indexed by the inode number of the directory to be deleted.296 */297 struct rb_root orphan_dirs;298 299 struct rb_root rbtree_new_refs;300 struct rb_root rbtree_deleted_refs;301 302 struct btrfs_lru_cache backref_cache;303 u64 backref_cache_last_reloc_trans;304 305 struct btrfs_lru_cache dir_created_cache;306 struct btrfs_lru_cache dir_utimes_cache;307};308 309struct pending_dir_move {310 struct rb_node node;311 struct list_head list;312 u64 parent_ino;313 u64 ino;314 u64 gen;315 struct list_head update_refs;316};317 318struct waiting_dir_move {319 struct rb_node node;320 u64 ino;321 /*322 * There might be some directory that could not be removed because it323 * was waiting for this directory inode to be moved first. Therefore324 * after this directory is moved, we can try to rmdir the ino rmdir_ino.325 */326 u64 rmdir_ino;327 u64 rmdir_gen;328 bool orphanized;329};330 331struct orphan_dir_info {332 struct rb_node node;333 u64 ino;334 u64 gen;335 u64 last_dir_index_offset;336 u64 dir_high_seq_ino;337};338 339struct name_cache_entry {340 /*341 * The key in the entry is an inode number, and the generation matches342 * the inode's generation.343 */344 struct btrfs_lru_cache_entry entry;345 u64 parent_ino;346 u64 parent_gen;347 int ret;348 int need_later_update;349 /* Name length without NUL terminator. */350 int name_len;351 /* Not NUL terminated. */352 char name[] __counted_by(name_len) __nonstring;353};354 355/* See the comment at lru_cache.h about struct btrfs_lru_cache_entry. */356static_assert(offsetof(struct name_cache_entry, entry) == 0);357 358#define ADVANCE 1359#define ADVANCE_ONLY_NEXT -1360 361enum btrfs_compare_tree_result {362 BTRFS_COMPARE_TREE_NEW,363 BTRFS_COMPARE_TREE_DELETED,364 BTRFS_COMPARE_TREE_CHANGED,365 BTRFS_COMPARE_TREE_SAME,366};367 368__cold369static void inconsistent_snapshot_error(struct send_ctx *sctx,370 enum btrfs_compare_tree_result result,371 const char *what)372{373 const char *result_string;374 375 switch (result) {376 case BTRFS_COMPARE_TREE_NEW:377 result_string = "new";378 break;379 case BTRFS_COMPARE_TREE_DELETED:380 result_string = "deleted";381 break;382 case BTRFS_COMPARE_TREE_CHANGED:383 result_string = "updated";384 break;385 case BTRFS_COMPARE_TREE_SAME:386 ASSERT(0);387 result_string = "unchanged";388 break;389 default:390 ASSERT(0);391 result_string = "unexpected";392 }393 394 btrfs_err(sctx->send_root->fs_info,395 "Send: inconsistent snapshot, found %s %s for inode %llu without updated inode item, send root is %llu, parent root is %llu",396 result_string, what, sctx->cmp_key->objectid,397 btrfs_root_id(sctx->send_root),398 (sctx->parent_root ? btrfs_root_id(sctx->parent_root) : 0));399}400 401__maybe_unused402static bool proto_cmd_ok(const struct send_ctx *sctx, int cmd)403{404 switch (sctx->proto) {405 case 1: return cmd <= BTRFS_SEND_C_MAX_V1;406 case 2: return cmd <= BTRFS_SEND_C_MAX_V2;407 case 3: return cmd <= BTRFS_SEND_C_MAX_V3;408 default: return false;409 }410}411 412static int is_waiting_for_move(struct send_ctx *sctx, u64 ino);413 414static struct waiting_dir_move *415get_waiting_dir_move(struct send_ctx *sctx, u64 ino);416 417static int is_waiting_for_rm(struct send_ctx *sctx, u64 dir_ino, u64 gen);418 419static int need_send_hole(struct send_ctx *sctx)420{421 return (sctx->parent_root && !sctx->cur_inode_new &&422 !sctx->cur_inode_new_gen && !sctx->cur_inode_deleted &&423 S_ISREG(sctx->cur_inode_mode));424}425 426static void fs_path_reset(struct fs_path *p)427{428 if (p->reversed) {429 p->start = p->buf + p->buf_len - 1;430 p->end = p->start;431 *p->start = 0;432 } else {433 p->start = p->buf;434 p->end = p->start;435 *p->start = 0;436 }437}438 439static struct fs_path *fs_path_alloc(void)440{441 struct fs_path *p;442 443 p = kmalloc(sizeof(*p), GFP_KERNEL);444 if (!p)445 return NULL;446 p->reversed = 0;447 p->buf = p->inline_buf;448 p->buf_len = FS_PATH_INLINE_SIZE;449 fs_path_reset(p);450 return p;451}452 453static struct fs_path *fs_path_alloc_reversed(void)454{455 struct fs_path *p;456 457 p = fs_path_alloc();458 if (!p)459 return NULL;460 p->reversed = 1;461 fs_path_reset(p);462 return p;463}464 465static void fs_path_free(struct fs_path *p)466{467 if (!p)468 return;469 if (p->buf != p->inline_buf)470 kfree(p->buf);471 kfree(p);472}473 474static int fs_path_len(struct fs_path *p)475{476 return p->end - p->start;477}478 479static int fs_path_ensure_buf(struct fs_path *p, int len)480{481 char *tmp_buf;482 int path_len;483 int old_buf_len;484 485 len++;486 487 if (p->buf_len >= len)488 return 0;489 490 if (len > PATH_MAX) {491 WARN_ON(1);492 return -ENOMEM;493 }494 495 path_len = p->end - p->start;496 old_buf_len = p->buf_len;497 498 /*499 * Allocate to the next largest kmalloc bucket size, to let500 * the fast path happen most of the time.501 */502 len = kmalloc_size_roundup(len);503 /*504 * First time the inline_buf does not suffice505 */506 if (p->buf == p->inline_buf) {507 tmp_buf = kmalloc(len, GFP_KERNEL);508 if (tmp_buf)509 memcpy(tmp_buf, p->buf, old_buf_len);510 } else {511 tmp_buf = krealloc(p->buf, len, GFP_KERNEL);512 }513 if (!tmp_buf)514 return -ENOMEM;515 p->buf = tmp_buf;516 p->buf_len = len;517 518 if (p->reversed) {519 tmp_buf = p->buf + old_buf_len - path_len - 1;520 p->end = p->buf + p->buf_len - 1;521 p->start = p->end - path_len;522 memmove(p->start, tmp_buf, path_len + 1);523 } else {524 p->start = p->buf;525 p->end = p->start + path_len;526 }527 return 0;528}529 530static int fs_path_prepare_for_add(struct fs_path *p, int name_len,531 char **prepared)532{533 int ret;534 int new_len;535 536 new_len = p->end - p->start + name_len;537 if (p->start != p->end)538 new_len++;539 ret = fs_path_ensure_buf(p, new_len);540 if (ret < 0)541 goto out;542 543 if (p->reversed) {544 if (p->start != p->end)545 *--p->start = '/';546 p->start -= name_len;547 *prepared = p->start;548 } else {549 if (p->start != p->end)550 *p->end++ = '/';551 *prepared = p->end;552 p->end += name_len;553 *p->end = 0;554 }555 556out:557 return ret;558}559 560static int fs_path_add(struct fs_path *p, const char *name, int name_len)561{562 int ret;563 char *prepared;564 565 ret = fs_path_prepare_for_add(p, name_len, &prepared);566 if (ret < 0)567 goto out;568 memcpy(prepared, name, name_len);569 570out:571 return ret;572}573 574static int fs_path_add_path(struct fs_path *p, struct fs_path *p2)575{576 int ret;577 char *prepared;578 579 ret = fs_path_prepare_for_add(p, p2->end - p2->start, &prepared);580 if (ret < 0)581 goto out;582 memcpy(prepared, p2->start, p2->end - p2->start);583 584out:585 return ret;586}587 588static int fs_path_add_from_extent_buffer(struct fs_path *p,589 struct extent_buffer *eb,590 unsigned long off, int len)591{592 int ret;593 char *prepared;594 595 ret = fs_path_prepare_for_add(p, len, &prepared);596 if (ret < 0)597 goto out;598 599 read_extent_buffer(eb, prepared, off, len);600 601out:602 return ret;603}604 605static int fs_path_copy(struct fs_path *p, struct fs_path *from)606{607 p->reversed = from->reversed;608 fs_path_reset(p);609 610 return fs_path_add_path(p, from);611}612 613static void fs_path_unreverse(struct fs_path *p)614{615 char *tmp;616 int len;617 618 if (!p->reversed)619 return;620 621 tmp = p->start;622 len = p->end - p->start;623 p->start = p->buf;624 p->end = p->start + len;625 memmove(p->start, tmp, len + 1);626 p->reversed = 0;627}628 629static struct btrfs_path *alloc_path_for_send(void)630{631 struct btrfs_path *path;632 633 path = btrfs_alloc_path();634 if (!path)635 return NULL;636 path->search_commit_root = 1;637 path->skip_locking = 1;638 path->need_commit_sem = 1;639 return path;640}641 642static int write_buf(struct file *filp, const void *buf, u32 len, loff_t *off)643{644 int ret;645 u32 pos = 0;646 647 while (pos < len) {648 ret = kernel_write(filp, buf + pos, len - pos, off);649 if (ret < 0)650 return ret;651 if (ret == 0)652 return -EIO;653 pos += ret;654 }655 656 return 0;657}658 659static int tlv_put(struct send_ctx *sctx, u16 attr, const void *data, int len)660{661 struct btrfs_tlv_header *hdr;662 int total_len = sizeof(*hdr) + len;663 int left = sctx->send_max_size - sctx->send_size;664 665 if (WARN_ON_ONCE(sctx->put_data))666 return -EINVAL;667 668 if (unlikely(left < total_len))669 return -EOVERFLOW;670 671 hdr = (struct btrfs_tlv_header *) (sctx->send_buf + sctx->send_size);672 put_unaligned_le16(attr, &hdr->tlv_type);673 put_unaligned_le16(len, &hdr->tlv_len);674 memcpy(hdr + 1, data, len);675 sctx->send_size += total_len;676 677 return 0;678}679 680#define TLV_PUT_DEFINE_INT(bits) \681 static int tlv_put_u##bits(struct send_ctx *sctx, \682 u##bits attr, u##bits value) \683 { \684 __le##bits __tmp = cpu_to_le##bits(value); \685 return tlv_put(sctx, attr, &__tmp, sizeof(__tmp)); \686 }687 688TLV_PUT_DEFINE_INT(8)689TLV_PUT_DEFINE_INT(32)690TLV_PUT_DEFINE_INT(64)691 692static int tlv_put_string(struct send_ctx *sctx, u16 attr,693 const char *str, int len)694{695 if (len == -1)696 len = strlen(str);697 return tlv_put(sctx, attr, str, len);698}699 700static int tlv_put_uuid(struct send_ctx *sctx, u16 attr,701 const u8 *uuid)702{703 return tlv_put(sctx, attr, uuid, BTRFS_UUID_SIZE);704}705 706static int tlv_put_btrfs_timespec(struct send_ctx *sctx, u16 attr,707 struct extent_buffer *eb,708 struct btrfs_timespec *ts)709{710 struct btrfs_timespec bts;711 read_extent_buffer(eb, &bts, (unsigned long)ts, sizeof(bts));712 return tlv_put(sctx, attr, &bts, sizeof(bts));713}714 715 716#define TLV_PUT(sctx, attrtype, data, attrlen) \717 do { \718 ret = tlv_put(sctx, attrtype, data, attrlen); \719 if (ret < 0) \720 goto tlv_put_failure; \721 } while (0)722 723#define TLV_PUT_INT(sctx, attrtype, bits, value) \724 do { \725 ret = tlv_put_u##bits(sctx, attrtype, value); \726 if (ret < 0) \727 goto tlv_put_failure; \728 } while (0)729 730#define TLV_PUT_U8(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 8, data)731#define TLV_PUT_U16(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 16, data)732#define TLV_PUT_U32(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 32, data)733#define TLV_PUT_U64(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 64, data)734#define TLV_PUT_STRING(sctx, attrtype, str, len) \735 do { \736 ret = tlv_put_string(sctx, attrtype, str, len); \737 if (ret < 0) \738 goto tlv_put_failure; \739 } while (0)740#define TLV_PUT_PATH(sctx, attrtype, p) \741 do { \742 ret = tlv_put_string(sctx, attrtype, p->start, \743 p->end - p->start); \744 if (ret < 0) \745 goto tlv_put_failure; \746 } while(0)747#define TLV_PUT_UUID(sctx, attrtype, uuid) \748 do { \749 ret = tlv_put_uuid(sctx, attrtype, uuid); \750 if (ret < 0) \751 goto tlv_put_failure; \752 } while (0)753#define TLV_PUT_BTRFS_TIMESPEC(sctx, attrtype, eb, ts) \754 do { \755 ret = tlv_put_btrfs_timespec(sctx, attrtype, eb, ts); \756 if (ret < 0) \757 goto tlv_put_failure; \758 } while (0)759 760static int send_header(struct send_ctx *sctx)761{762 struct btrfs_stream_header hdr;763 764 strcpy(hdr.magic, BTRFS_SEND_STREAM_MAGIC);765 hdr.version = cpu_to_le32(sctx->proto);766 return write_buf(sctx->send_filp, &hdr, sizeof(hdr),767 &sctx->send_off);768}769 770/*771 * For each command/item we want to send to userspace, we call this function.772 */773static int begin_cmd(struct send_ctx *sctx, int cmd)774{775 struct btrfs_cmd_header *hdr;776 777 if (WARN_ON(!sctx->send_buf))778 return -EINVAL;779 780 if (unlikely(sctx->send_size != 0)) {781 btrfs_err(sctx->send_root->fs_info,782 "send: command header buffer not empty cmd %d offset %llu",783 cmd, sctx->send_off);784 return -EINVAL;785 }786 787 sctx->send_size += sizeof(*hdr);788 hdr = (struct btrfs_cmd_header *)sctx->send_buf;789 put_unaligned_le16(cmd, &hdr->cmd);790 791 return 0;792}793 794static int send_cmd(struct send_ctx *sctx)795{796 int ret;797 struct btrfs_cmd_header *hdr;798 u32 crc;799 800 hdr = (struct btrfs_cmd_header *)sctx->send_buf;801 put_unaligned_le32(sctx->send_size - sizeof(*hdr), &hdr->len);802 put_unaligned_le32(0, &hdr->crc);803 804 crc = crc32c(0, (unsigned char *)sctx->send_buf, sctx->send_size);805 put_unaligned_le32(crc, &hdr->crc);806 807 ret = write_buf(sctx->send_filp, sctx->send_buf, sctx->send_size,808 &sctx->send_off);809 810 sctx->send_size = 0;811 sctx->put_data = false;812 813 return ret;814}815 816/*817 * Sends a move instruction to user space818 */819static int send_rename(struct send_ctx *sctx,820 struct fs_path *from, struct fs_path *to)821{822 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;823 int ret;824 825 btrfs_debug(fs_info, "send_rename %s -> %s", from->start, to->start);826 827 ret = begin_cmd(sctx, BTRFS_SEND_C_RENAME);828 if (ret < 0)829 goto out;830 831 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, from);832 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH_TO, to);833 834 ret = send_cmd(sctx);835 836tlv_put_failure:837out:838 return ret;839}840 841/*842 * Sends a link instruction to user space843 */844static int send_link(struct send_ctx *sctx,845 struct fs_path *path, struct fs_path *lnk)846{847 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;848 int ret;849 850 btrfs_debug(fs_info, "send_link %s -> %s", path->start, lnk->start);851 852 ret = begin_cmd(sctx, BTRFS_SEND_C_LINK);853 if (ret < 0)854 goto out;855 856 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);857 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH_LINK, lnk);858 859 ret = send_cmd(sctx);860 861tlv_put_failure:862out:863 return ret;864}865 866/*867 * Sends an unlink instruction to user space868 */869static int send_unlink(struct send_ctx *sctx, struct fs_path *path)870{871 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;872 int ret;873 874 btrfs_debug(fs_info, "send_unlink %s", path->start);875 876 ret = begin_cmd(sctx, BTRFS_SEND_C_UNLINK);877 if (ret < 0)878 goto out;879 880 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);881 882 ret = send_cmd(sctx);883 884tlv_put_failure:885out:886 return ret;887}888 889/*890 * Sends a rmdir instruction to user space891 */892static int send_rmdir(struct send_ctx *sctx, struct fs_path *path)893{894 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;895 int ret;896 897 btrfs_debug(fs_info, "send_rmdir %s", path->start);898 899 ret = begin_cmd(sctx, BTRFS_SEND_C_RMDIR);900 if (ret < 0)901 goto out;902 903 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);904 905 ret = send_cmd(sctx);906 907tlv_put_failure:908out:909 return ret;910}911 912struct btrfs_inode_info {913 u64 size;914 u64 gen;915 u64 mode;916 u64 uid;917 u64 gid;918 u64 rdev;919 u64 fileattr;920 u64 nlink;921};922 923/*924 * Helper function to retrieve some fields from an inode item.925 */926static int get_inode_info(struct btrfs_root *root, u64 ino,927 struct btrfs_inode_info *info)928{929 int ret;930 struct btrfs_path *path;931 struct btrfs_inode_item *ii;932 struct btrfs_key key;933 934 path = alloc_path_for_send();935 if (!path)936 return -ENOMEM;937 938 key.objectid = ino;939 key.type = BTRFS_INODE_ITEM_KEY;940 key.offset = 0;941 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);942 if (ret) {943 if (ret > 0)944 ret = -ENOENT;945 goto out;946 }947 948 if (!info)949 goto out;950 951 ii = btrfs_item_ptr(path->nodes[0], path->slots[0],952 struct btrfs_inode_item);953 info->size = btrfs_inode_size(path->nodes[0], ii);954 info->gen = btrfs_inode_generation(path->nodes[0], ii);955 info->mode = btrfs_inode_mode(path->nodes[0], ii);956 info->uid = btrfs_inode_uid(path->nodes[0], ii);957 info->gid = btrfs_inode_gid(path->nodes[0], ii);958 info->rdev = btrfs_inode_rdev(path->nodes[0], ii);959 info->nlink = btrfs_inode_nlink(path->nodes[0], ii);960 /*961 * Transfer the unchanged u64 value of btrfs_inode_item::flags, that's962 * otherwise logically split to 32/32 parts.963 */964 info->fileattr = btrfs_inode_flags(path->nodes[0], ii);965 966out:967 btrfs_free_path(path);968 return ret;969}970 971static int get_inode_gen(struct btrfs_root *root, u64 ino, u64 *gen)972{973 int ret;974 struct btrfs_inode_info info = { 0 };975 976 ASSERT(gen);977 978 ret = get_inode_info(root, ino, &info);979 *gen = info.gen;980 return ret;981}982 983typedef int (*iterate_inode_ref_t)(int num, u64 dir, int index,984 struct fs_path *p,985 void *ctx);986 987/*988 * Helper function to iterate the entries in ONE btrfs_inode_ref or989 * btrfs_inode_extref.990 * The iterate callback may return a non zero value to stop iteration. This can991 * be a negative value for error codes or 1 to simply stop it.992 *993 * path must point to the INODE_REF or INODE_EXTREF when called.994 */995static int iterate_inode_ref(struct btrfs_root *root, struct btrfs_path *path,996 struct btrfs_key *found_key, int resolve,997 iterate_inode_ref_t iterate, void *ctx)998{999 struct extent_buffer *eb = path->nodes[0];1000 struct btrfs_inode_ref *iref;1001 struct btrfs_inode_extref *extref;1002 struct btrfs_path *tmp_path;1003 struct fs_path *p;1004 u32 cur = 0;1005 u32 total;1006 int slot = path->slots[0];1007 u32 name_len;1008 char *start;1009 int ret = 0;1010 int num = 0;1011 int index;1012 u64 dir;1013 unsigned long name_off;1014 unsigned long elem_size;1015 unsigned long ptr;1016 1017 p = fs_path_alloc_reversed();1018 if (!p)1019 return -ENOMEM;1020 1021 tmp_path = alloc_path_for_send();1022 if (!tmp_path) {1023 fs_path_free(p);1024 return -ENOMEM;1025 }1026 1027 1028 if (found_key->type == BTRFS_INODE_REF_KEY) {1029 ptr = (unsigned long)btrfs_item_ptr(eb, slot,1030 struct btrfs_inode_ref);1031 total = btrfs_item_size(eb, slot);1032 elem_size = sizeof(*iref);1033 } else {1034 ptr = btrfs_item_ptr_offset(eb, slot);1035 total = btrfs_item_size(eb, slot);1036 elem_size = sizeof(*extref);1037 }1038 1039 while (cur < total) {1040 fs_path_reset(p);1041 1042 if (found_key->type == BTRFS_INODE_REF_KEY) {1043 iref = (struct btrfs_inode_ref *)(ptr + cur);1044 name_len = btrfs_inode_ref_name_len(eb, iref);1045 name_off = (unsigned long)(iref + 1);1046 index = btrfs_inode_ref_index(eb, iref);1047 dir = found_key->offset;1048 } else {1049 extref = (struct btrfs_inode_extref *)(ptr + cur);1050 name_len = btrfs_inode_extref_name_len(eb, extref);1051 name_off = (unsigned long)&extref->name;1052 index = btrfs_inode_extref_index(eb, extref);1053 dir = btrfs_inode_extref_parent(eb, extref);1054 }1055 1056 if (resolve) {1057 start = btrfs_ref_to_path(root, tmp_path, name_len,1058 name_off, eb, dir,1059 p->buf, p->buf_len);1060 if (IS_ERR(start)) {1061 ret = PTR_ERR(start);1062 goto out;1063 }1064 if (start < p->buf) {1065 /* overflow , try again with larger buffer */1066 ret = fs_path_ensure_buf(p,1067 p->buf_len + p->buf - start);1068 if (ret < 0)1069 goto out;1070 start = btrfs_ref_to_path(root, tmp_path,1071 name_len, name_off,1072 eb, dir,1073 p->buf, p->buf_len);1074 if (IS_ERR(start)) {1075 ret = PTR_ERR(start);1076 goto out;1077 }1078 if (unlikely(start < p->buf)) {1079 btrfs_err(root->fs_info,1080 "send: path ref buffer underflow for key (%llu %u %llu)",1081 found_key->objectid,1082 found_key->type,1083 found_key->offset);1084 ret = -EINVAL;1085 goto out;1086 }1087 }1088 p->start = start;1089 } else {1090 ret = fs_path_add_from_extent_buffer(p, eb, name_off,1091 name_len);1092 if (ret < 0)1093 goto out;1094 }1095 1096 cur += elem_size + name_len;1097 ret = iterate(num, dir, index, p, ctx);1098 if (ret)1099 goto out;1100 num++;1101 }1102 1103out:1104 btrfs_free_path(tmp_path);1105 fs_path_free(p);1106 return ret;1107}1108 1109typedef int (*iterate_dir_item_t)(int num, struct btrfs_key *di_key,1110 const char *name, int name_len,1111 const char *data, int data_len,1112 void *ctx);1113 1114/*1115 * Helper function to iterate the entries in ONE btrfs_dir_item.1116 * The iterate callback may return a non zero value to stop iteration. This can1117 * be a negative value for error codes or 1 to simply stop it.1118 *1119 * path must point to the dir item when called.1120 */1121static int iterate_dir_item(struct btrfs_root *root, struct btrfs_path *path,1122 iterate_dir_item_t iterate, void *ctx)1123{1124 int ret = 0;1125 struct extent_buffer *eb;1126 struct btrfs_dir_item *di;1127 struct btrfs_key di_key;1128 char *buf = NULL;1129 int buf_len;1130 u32 name_len;1131 u32 data_len;1132 u32 cur;1133 u32 len;1134 u32 total;1135 int slot;1136 int num;1137 1138 /*1139 * Start with a small buffer (1 page). If later we end up needing more1140 * space, which can happen for xattrs on a fs with a leaf size greater1141 * than the page size, attempt to increase the buffer. Typically xattr1142 * values are small.1143 */1144 buf_len = PATH_MAX;1145 buf = kmalloc(buf_len, GFP_KERNEL);1146 if (!buf) {1147 ret = -ENOMEM;1148 goto out;1149 }1150 1151 eb = path->nodes[0];1152 slot = path->slots[0];1153 di = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);1154 cur = 0;1155 len = 0;1156 total = btrfs_item_size(eb, slot);1157 1158 num = 0;1159 while (cur < total) {1160 name_len = btrfs_dir_name_len(eb, di);1161 data_len = btrfs_dir_data_len(eb, di);1162 btrfs_dir_item_key_to_cpu(eb, di, &di_key);1163 1164 if (btrfs_dir_ftype(eb, di) == BTRFS_FT_XATTR) {1165 if (name_len > XATTR_NAME_MAX) {1166 ret = -ENAMETOOLONG;1167 goto out;1168 }1169 if (name_len + data_len >1170 BTRFS_MAX_XATTR_SIZE(root->fs_info)) {1171 ret = -E2BIG;1172 goto out;1173 }1174 } else {1175 /*1176 * Path too long1177 */1178 if (name_len + data_len > PATH_MAX) {1179 ret = -ENAMETOOLONG;1180 goto out;1181 }1182 }1183 1184 if (name_len + data_len > buf_len) {1185 buf_len = name_len + data_len;1186 if (is_vmalloc_addr(buf)) {1187 vfree(buf);1188 buf = NULL;1189 } else {1190 char *tmp = krealloc(buf, buf_len,1191 GFP_KERNEL | __GFP_NOWARN);1192 1193 if (!tmp)1194 kfree(buf);1195 buf = tmp;1196 }1197 if (!buf) {1198 buf = kvmalloc(buf_len, GFP_KERNEL);1199 if (!buf) {1200 ret = -ENOMEM;1201 goto out;1202 }1203 }1204 }1205 1206 read_extent_buffer(eb, buf, (unsigned long)(di + 1),1207 name_len + data_len);1208 1209 len = sizeof(*di) + name_len + data_len;1210 di = (struct btrfs_dir_item *)((char *)di + len);1211 cur += len;1212 1213 ret = iterate(num, &di_key, buf, name_len, buf + name_len,1214 data_len, ctx);1215 if (ret < 0)1216 goto out;1217 if (ret) {1218 ret = 0;1219 goto out;1220 }1221 1222 num++;1223 }1224 1225out:1226 kvfree(buf);1227 return ret;1228}1229 1230static int __copy_first_ref(int num, u64 dir, int index,1231 struct fs_path *p, void *ctx)1232{1233 int ret;1234 struct fs_path *pt = ctx;1235 1236 ret = fs_path_copy(pt, p);1237 if (ret < 0)1238 return ret;1239 1240 /* we want the first only */1241 return 1;1242}1243 1244/*1245 * Retrieve the first path of an inode. If an inode has more then one1246 * ref/hardlink, this is ignored.1247 */1248static int get_inode_path(struct btrfs_root *root,1249 u64 ino, struct fs_path *path)1250{1251 int ret;1252 struct btrfs_key key, found_key;1253 struct btrfs_path *p;1254 1255 p = alloc_path_for_send();1256 if (!p)1257 return -ENOMEM;1258 1259 fs_path_reset(path);1260 1261 key.objectid = ino;1262 key.type = BTRFS_INODE_REF_KEY;1263 key.offset = 0;1264 1265 ret = btrfs_search_slot_for_read(root, &key, p, 1, 0);1266 if (ret < 0)1267 goto out;1268 if (ret) {1269 ret = 1;1270 goto out;1271 }1272 btrfs_item_key_to_cpu(p->nodes[0], &found_key, p->slots[0]);1273 if (found_key.objectid != ino ||1274 (found_key.type != BTRFS_INODE_REF_KEY &&1275 found_key.type != BTRFS_INODE_EXTREF_KEY)) {1276 ret = -ENOENT;1277 goto out;1278 }1279 1280 ret = iterate_inode_ref(root, p, &found_key, 1,1281 __copy_first_ref, path);1282 if (ret < 0)1283 goto out;1284 ret = 0;1285 1286out:1287 btrfs_free_path(p);1288 return ret;1289}1290 1291struct backref_ctx {1292 struct send_ctx *sctx;1293 1294 /* number of total found references */1295 u64 found;1296 1297 /*1298 * used for clones found in send_root. clones found behind cur_objectid1299 * and cur_offset are not considered as allowed clones.1300 */1301 u64 cur_objectid;1302 u64 cur_offset;1303 1304 /* may be truncated in case it's the last extent in a file */1305 u64 extent_len;1306 1307 /* The bytenr the file extent item we are processing refers to. */1308 u64 bytenr;1309 /* The owner (root id) of the data backref for the current extent. */1310 u64 backref_owner;1311 /* The offset of the data backref for the current extent. */1312 u64 backref_offset;1313};1314 1315static int __clone_root_cmp_bsearch(const void *key, const void *elt)1316{1317 u64 root = (u64)(uintptr_t)key;1318 const struct clone_root *cr = elt;1319 1320 if (root < btrfs_root_id(cr->root))1321 return -1;1322 if (root > btrfs_root_id(cr->root))1323 return 1;1324 return 0;1325}1326 1327static int __clone_root_cmp_sort(const void *e1, const void *e2)1328{1329 const struct clone_root *cr1 = e1;1330 const struct clone_root *cr2 = e2;1331 1332 if (btrfs_root_id(cr1->root) < btrfs_root_id(cr2->root))1333 return -1;1334 if (btrfs_root_id(cr1->root) > btrfs_root_id(cr2->root))1335 return 1;1336 return 0;1337}1338 1339/*1340 * Called for every backref that is found for the current extent.1341 * Results are collected in sctx->clone_roots->ino/offset.1342 */1343static int iterate_backrefs(u64 ino, u64 offset, u64 num_bytes, u64 root_id,1344 void *ctx_)1345{1346 struct backref_ctx *bctx = ctx_;1347 struct clone_root *clone_root;1348 1349 /* First check if the root is in the list of accepted clone sources */1350 clone_root = bsearch((void *)(uintptr_t)root_id, bctx->sctx->clone_roots,1351 bctx->sctx->clone_roots_cnt,1352 sizeof(struct clone_root),1353 __clone_root_cmp_bsearch);1354 if (!clone_root)1355 return 0;1356 1357 /* This is our own reference, bail out as we can't clone from it. */1358 if (clone_root->root == bctx->sctx->send_root &&1359 ino == bctx->cur_objectid &&1360 offset == bctx->cur_offset)1361 return 0;1362 1363 /*1364 * Make sure we don't consider clones from send_root that are1365 * behind the current inode/offset.1366 */1367 if (clone_root->root == bctx->sctx->send_root) {1368 /*1369 * If the source inode was not yet processed we can't issue a1370 * clone operation, as the source extent does not exist yet at1371 * the destination of the stream.1372 */1373 if (ino > bctx->cur_objectid)1374 return 0;1375 /*1376 * We clone from the inode currently being sent as long as the1377 * source extent is already processed, otherwise we could try1378 * to clone from an extent that does not exist yet at the1379 * destination of the stream.1380 */1381 if (ino == bctx->cur_objectid &&1382 offset + bctx->extent_len >1383 bctx->sctx->cur_inode_next_write_offset)1384 return 0;1385 }1386 1387 bctx->found++;1388 clone_root->found_ref = true;1389 1390 /*1391 * If the given backref refers to a file extent item with a larger1392 * number of bytes than what we found before, use the new one so that1393 * we clone more optimally and end up doing less writes and getting1394 * less exclusive, non-shared extents at the destination.1395 */1396 if (num_bytes > clone_root->num_bytes) {1397 clone_root->ino = ino;1398 clone_root->offset = offset;1399 clone_root->num_bytes = num_bytes;1400 1401 /*1402 * Found a perfect candidate, so there's no need to continue1403 * backref walking.1404 */1405 if (num_bytes >= bctx->extent_len)1406 return BTRFS_ITERATE_EXTENT_INODES_STOP;1407 }1408 1409 return 0;1410}1411 1412static bool lookup_backref_cache(u64 leaf_bytenr, void *ctx,1413 const u64 **root_ids_ret, int *root_count_ret)1414{1415 struct backref_ctx *bctx = ctx;1416 struct send_ctx *sctx = bctx->sctx;1417 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;1418 const u64 key = leaf_bytenr >> fs_info->sectorsize_bits;1419 struct btrfs_lru_cache_entry *raw_entry;1420 struct backref_cache_entry *entry;1421 1422 if (sctx->backref_cache.size == 0)1423 return false;1424 1425 /*1426 * If relocation happened since we first filled the cache, then we must1427 * empty the cache and can not use it, because even though we operate on1428 * read-only roots, their leaves and nodes may have been reallocated and1429 * now be used for different nodes/leaves of the same tree or some other1430 * tree.1431 *1432 * We are called from iterate_extent_inodes() while either holding a1433 * transaction handle or holding fs_info->commit_root_sem, so no need1434 * to take any lock here.1435 */1436 if (fs_info->last_reloc_trans > sctx->backref_cache_last_reloc_trans) {1437 btrfs_lru_cache_clear(&sctx->backref_cache);1438 return false;1439 }1440 1441 raw_entry = btrfs_lru_cache_lookup(&sctx->backref_cache, key, 0);1442 if (!raw_entry)1443 return false;1444 1445 entry = container_of(raw_entry, struct backref_cache_entry, entry);1446 *root_ids_ret = entry->root_ids;1447 *root_count_ret = entry->num_roots;1448 1449 return true;1450}1451 1452static void store_backref_cache(u64 leaf_bytenr, const struct ulist *root_ids,1453 void *ctx)1454{1455 struct backref_ctx *bctx = ctx;1456 struct send_ctx *sctx = bctx->sctx;1457 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;1458 struct backref_cache_entry *new_entry;1459 struct ulist_iterator uiter;1460 struct ulist_node *node;1461 int ret;1462 1463 /*1464 * We're called while holding a transaction handle or while holding1465 * fs_info->commit_root_sem (at iterate_extent_inodes()), so must do a1466 * NOFS allocation.1467 */1468 new_entry = kmalloc(sizeof(struct backref_cache_entry), GFP_NOFS);1469 /* No worries, cache is optional. */1470 if (!new_entry)1471 return;1472 1473 new_entry->entry.key = leaf_bytenr >> fs_info->sectorsize_bits;1474 new_entry->entry.gen = 0;1475 new_entry->num_roots = 0;1476 ULIST_ITER_INIT(&uiter);1477 while ((node = ulist_next(root_ids, &uiter)) != NULL) {1478 const u64 root_id = node->val;1479 struct clone_root *root;1480 1481 root = bsearch((void *)(uintptr_t)root_id, sctx->clone_roots,1482 sctx->clone_roots_cnt, sizeof(struct clone_root),1483 __clone_root_cmp_bsearch);1484 if (!root)1485 continue;1486 1487 /* Too many roots, just exit, no worries as caching is optional. */1488 if (new_entry->num_roots >= SEND_MAX_BACKREF_CACHE_ROOTS) {1489 kfree(new_entry);1490 return;1491 }1492 1493 new_entry->root_ids[new_entry->num_roots] = root_id;1494 new_entry->num_roots++;1495 }1496 1497 /*1498 * We may have not added any roots to the new cache entry, which means1499 * none of the roots is part of the list of roots from which we are1500 * allowed to clone. Cache the new entry as it's still useful to avoid1501 * backref walking to determine which roots have a path to the leaf.1502 *1503 * Also use GFP_NOFS because we're called while holding a transaction1504 * handle or while holding fs_info->commit_root_sem.1505 */1506 ret = btrfs_lru_cache_store(&sctx->backref_cache, &new_entry->entry,1507 GFP_NOFS);1508 ASSERT(ret == 0 || ret == -ENOMEM);1509 if (ret) {1510 /* Caching is optional, no worries. */1511 kfree(new_entry);1512 return;1513 }1514 1515 /*1516 * We are called from iterate_extent_inodes() while either holding a1517 * transaction handle or holding fs_info->commit_root_sem, so no need1518 * to take any lock here.1519 */1520 if (sctx->backref_cache.size == 1)1521 sctx->backref_cache_last_reloc_trans = fs_info->last_reloc_trans;1522}1523 1524static int check_extent_item(u64 bytenr, const struct btrfs_extent_item *ei,1525 const struct extent_buffer *leaf, void *ctx)1526{1527 const u64 refs = btrfs_extent_refs(leaf, ei);1528 const struct backref_ctx *bctx = ctx;1529 const struct send_ctx *sctx = bctx->sctx;1530 1531 if (bytenr == bctx->bytenr) {1532 const u64 flags = btrfs_extent_flags(leaf, ei);1533 1534 if (WARN_ON(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK))1535 return -EUCLEAN;1536 1537 /*1538 * If we have only one reference and only the send root as a1539 * clone source - meaning no clone roots were given in the1540 * struct btrfs_ioctl_send_args passed to the send ioctl - then1541 * it's our reference and there's no point in doing backref1542 * walking which is expensive, so exit early.1543 */1544 if (refs == 1 && sctx->clone_roots_cnt == 1)1545 return -ENOENT;1546 }1547 1548 /*1549 * Backreference walking (iterate_extent_inodes() below) is currently1550 * too expensive when an extent has a large number of references, both1551 * in time spent and used memory. So for now just fallback to write1552 * operations instead of clone operations when an extent has more than1553 * a certain amount of references.1554 */1555 if (refs > SEND_MAX_EXTENT_REFS)1556 return -ENOENT;1557 1558 return 0;1559}1560 1561static bool skip_self_data_ref(u64 root, u64 ino, u64 offset, void *ctx)1562{1563 const struct backref_ctx *bctx = ctx;1564 1565 if (ino == bctx->cur_objectid &&1566 root == bctx->backref_owner &&1567 offset == bctx->backref_offset)1568 return true;1569 1570 return false;1571}1572 1573/*1574 * Given an inode, offset and extent item, it finds a good clone for a clone1575 * instruction. Returns -ENOENT when none could be found. The function makes1576 * sure that the returned clone is usable at the point where sending is at the1577 * moment. This means, that no clones are accepted which lie behind the current1578 * inode+offset.1579 *1580 * path must point to the extent item when called.1581 */1582static int find_extent_clone(struct send_ctx *sctx,1583 struct btrfs_path *path,1584 u64 ino, u64 data_offset,1585 u64 ino_size,1586 struct clone_root **found)1587{1588 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;1589 int ret;1590 int extent_type;1591 u64 logical;1592 u64 disk_byte;1593 u64 num_bytes;1594 struct btrfs_file_extent_item *fi;1595 struct extent_buffer *eb = path->nodes[0];1596 struct backref_ctx backref_ctx = { 0 };1597 struct btrfs_backref_walk_ctx backref_walk_ctx = { 0 };1598 struct clone_root *cur_clone_root;1599 int compressed;1600 u32 i;1601 1602 /*1603 * With fallocate we can get prealloc extents beyond the inode's i_size,1604 * so we don't do anything here because clone operations can not clone1605 * to a range beyond i_size without increasing the i_size of the1606 * destination inode.1607 */1608 if (data_offset >= ino_size)1609 return 0;1610 1611 fi = btrfs_item_ptr(eb, path->slots[0], struct btrfs_file_extent_item);1612 extent_type = btrfs_file_extent_type(eb, fi);1613 if (extent_type == BTRFS_FILE_EXTENT_INLINE)1614 return -ENOENT;1615 1616 disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);1617 if (disk_byte == 0)1618 return -ENOENT;1619 1620 compressed = btrfs_file_extent_compression(eb, fi);1621 num_bytes = btrfs_file_extent_num_bytes(eb, fi);1622 logical = disk_byte + btrfs_file_extent_offset(eb, fi);1623 1624 /*1625 * Setup the clone roots.1626 */1627 for (i = 0; i < sctx->clone_roots_cnt; i++) {1628 cur_clone_root = sctx->clone_roots + i;1629 cur_clone_root->ino = (u64)-1;1630 cur_clone_root->offset = 0;1631 cur_clone_root->num_bytes = 0;1632 cur_clone_root->found_ref = false;1633 }1634 1635 backref_ctx.sctx = sctx;1636 backref_ctx.cur_objectid = ino;1637 backref_ctx.cur_offset = data_offset;1638 backref_ctx.bytenr = disk_byte;1639 /*1640 * Use the header owner and not the send root's id, because in case of a1641 * snapshot we can have shared subtrees.1642 */1643 backref_ctx.backref_owner = btrfs_header_owner(eb);1644 backref_ctx.backref_offset = data_offset - btrfs_file_extent_offset(eb, fi);1645 1646 /*1647 * The last extent of a file may be too large due to page alignment.1648 * We need to adjust extent_len in this case so that the checks in1649 * iterate_backrefs() work.1650 */1651 if (data_offset + num_bytes >= ino_size)1652 backref_ctx.extent_len = ino_size - data_offset;1653 else1654 backref_ctx.extent_len = num_bytes;1655 1656 /*1657 * Now collect all backrefs.1658 */1659 backref_walk_ctx.bytenr = disk_byte;1660 if (compressed == BTRFS_COMPRESS_NONE)1661 backref_walk_ctx.extent_item_pos = btrfs_file_extent_offset(eb, fi);1662 backref_walk_ctx.fs_info = fs_info;1663 backref_walk_ctx.cache_lookup = lookup_backref_cache;1664 backref_walk_ctx.cache_store = store_backref_cache;1665 backref_walk_ctx.indirect_ref_iterator = iterate_backrefs;1666 backref_walk_ctx.check_extent_item = check_extent_item;1667 backref_walk_ctx.user_ctx = &backref_ctx;1668 1669 /*1670 * If have a single clone root, then it's the send root and we can tell1671 * the backref walking code to skip our own backref and not resolve it,1672 * since we can not use it for cloning - the source and destination1673 * ranges can't overlap and in case the leaf is shared through a subtree1674 * due to snapshots, we can't use those other roots since they are not1675 * in the list of clone roots.1676 */1677 if (sctx->clone_roots_cnt == 1)1678 backref_walk_ctx.skip_data_ref = skip_self_data_ref;1679 1680 ret = iterate_extent_inodes(&backref_walk_ctx, true, iterate_backrefs,1681 &backref_ctx);1682 if (ret < 0)1683 return ret;1684 1685 down_read(&fs_info->commit_root_sem);1686 if (fs_info->last_reloc_trans > sctx->last_reloc_trans) {1687 /*1688 * A transaction commit for a transaction in which block group1689 * relocation was done just happened.1690 * The disk_bytenr of the file extent item we processed is1691 * possibly stale, referring to the extent's location before1692 * relocation. So act as if we haven't found any clone sources1693 * and fallback to write commands, which will read the correct1694 * data from the new extent location. Otherwise we will fail1695 * below because we haven't found our own back reference or we1696 * could be getting incorrect sources in case the old extent1697 * was already reallocated after the relocation.1698 */1699 up_read(&fs_info->commit_root_sem);1700 return -ENOENT;1701 }1702 up_read(&fs_info->commit_root_sem);1703 1704 btrfs_debug(fs_info,1705 "find_extent_clone: data_offset=%llu, ino=%llu, num_bytes=%llu, logical=%llu",1706 data_offset, ino, num_bytes, logical);1707 1708 if (!backref_ctx.found) {1709 btrfs_debug(fs_info, "no clones found");1710 return -ENOENT;1711 }1712 1713 cur_clone_root = NULL;1714 for (i = 0; i < sctx->clone_roots_cnt; i++) {1715 struct clone_root *clone_root = &sctx->clone_roots[i];1716 1717 if (!clone_root->found_ref)1718 continue;1719 1720 /*1721 * Choose the root from which we can clone more bytes, to1722 * minimize write operations and therefore have more extent1723 * sharing at the destination (the same as in the source).1724 */1725 if (!cur_clone_root ||1726 clone_root->num_bytes > cur_clone_root->num_bytes) {1727 cur_clone_root = clone_root;1728 1729 /*1730 * We found an optimal clone candidate (any inode from1731 * any root is fine), so we're done.1732 */1733 if (clone_root->num_bytes >= backref_ctx.extent_len)1734 break;1735 }1736 }1737 1738 if (cur_clone_root) {1739 *found = cur_clone_root;1740 ret = 0;1741 } else {1742 ret = -ENOENT;1743 }1744 1745 return ret;1746}1747 1748static int read_symlink(struct btrfs_root *root,1749 u64 ino,1750 struct fs_path *dest)1751{1752 int ret;1753 struct btrfs_path *path;1754 struct btrfs_key key;1755 struct btrfs_file_extent_item *ei;1756 u8 type;1757 u8 compression;1758 unsigned long off;1759 int len;1760 1761 path = alloc_path_for_send();1762 if (!path)1763 return -ENOMEM;1764 1765 key.objectid = ino;1766 key.type = BTRFS_EXTENT_DATA_KEY;1767 key.offset = 0;1768 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);1769 if (ret < 0)1770 goto out;1771 if (ret) {1772 /*1773 * An empty symlink inode. Can happen in rare error paths when1774 * creating a symlink (transaction committed before the inode1775 * eviction handler removed the symlink inode items and a crash1776 * happened in between or the subvol was snapshoted in between).1777 * Print an informative message to dmesg/syslog so that the user1778 * can delete the symlink.1779 */1780 btrfs_err(root->fs_info,1781 "Found empty symlink inode %llu at root %llu",1782 ino, btrfs_root_id(root));1783 ret = -EIO;1784 goto out;1785 }1786 1787 ei = btrfs_item_ptr(path->nodes[0], path->slots[0],1788 struct btrfs_file_extent_item);1789 type = btrfs_file_extent_type(path->nodes[0], ei);1790 if (unlikely(type != BTRFS_FILE_EXTENT_INLINE)) {1791 ret = -EUCLEAN;1792 btrfs_crit(root->fs_info,1793"send: found symlink extent that is not inline, ino %llu root %llu extent type %d",1794 ino, btrfs_root_id(root), type);1795 goto out;1796 }1797 compression = btrfs_file_extent_compression(path->nodes[0], ei);1798 if (unlikely(compression != BTRFS_COMPRESS_NONE)) {1799 ret = -EUCLEAN;1800 btrfs_crit(root->fs_info,1801"send: found symlink extent with compression, ino %llu root %llu compression type %d",1802 ino, btrfs_root_id(root), compression);1803 goto out;1804 }1805 1806 off = btrfs_file_extent_inline_start(ei);1807 len = btrfs_file_extent_ram_bytes(path->nodes[0], ei);1808 1809 ret = fs_path_add_from_extent_buffer(dest, path->nodes[0], off, len);1810 1811out:1812 btrfs_free_path(path);1813 return ret;1814}1815 1816/*1817 * Helper function to generate a file name that is unique in the root of1818 * send_root and parent_root. This is used to generate names for orphan inodes.1819 */1820static int gen_unique_name(struct send_ctx *sctx,1821 u64 ino, u64 gen,1822 struct fs_path *dest)1823{1824 int ret = 0;1825 struct btrfs_path *path;1826 struct btrfs_dir_item *di;1827 char tmp[64];1828 int len;1829 u64 idx = 0;1830 1831 path = alloc_path_for_send();1832 if (!path)1833 return -ENOMEM;1834 1835 while (1) {1836 struct fscrypt_str tmp_name;1837 1838 len = snprintf(tmp, sizeof(tmp), "o%llu-%llu-%llu",1839 ino, gen, idx);1840 ASSERT(len < sizeof(tmp));1841 tmp_name.name = tmp;1842 tmp_name.len = strlen(tmp);1843 1844 di = btrfs_lookup_dir_item(NULL, sctx->send_root,1845 path, BTRFS_FIRST_FREE_OBJECTID,1846 &tmp_name, 0);1847 btrfs_release_path(path);1848 if (IS_ERR(di)) {1849 ret = PTR_ERR(di);1850 goto out;1851 }1852 if (di) {1853 /* not unique, try again */1854 idx++;1855 continue;1856 }1857 1858 if (!sctx->parent_root) {1859 /* unique */1860 ret = 0;1861 break;1862 }1863 1864 di = btrfs_lookup_dir_item(NULL, sctx->parent_root,1865 path, BTRFS_FIRST_FREE_OBJECTID,1866 &tmp_name, 0);1867 btrfs_release_path(path);1868 if (IS_ERR(di)) {1869 ret = PTR_ERR(di);1870 goto out;1871 }1872 if (di) {1873 /* not unique, try again */1874 idx++;1875 continue;1876 }1877 /* unique */1878 break;1879 }1880 1881 ret = fs_path_add(dest, tmp, strlen(tmp));1882 1883out:1884 btrfs_free_path(path);1885 return ret;1886}1887 1888enum inode_state {1889 inode_state_no_change,1890 inode_state_will_create,1891 inode_state_did_create,1892 inode_state_will_delete,1893 inode_state_did_delete,1894};1895 1896static int get_cur_inode_state(struct send_ctx *sctx, u64 ino, u64 gen,1897 u64 *send_gen, u64 *parent_gen)1898{1899 int ret;1900 int left_ret;1901 int right_ret;1902 u64 left_gen;1903 u64 right_gen = 0;1904 struct btrfs_inode_info info;1905 1906 ret = get_inode_info(sctx->send_root, ino, &info);1907 if (ret < 0 && ret != -ENOENT)1908 goto out;1909 left_ret = (info.nlink == 0) ? -ENOENT : ret;1910 left_gen = info.gen;1911 if (send_gen)1912 *send_gen = ((left_ret == -ENOENT) ? 0 : info.gen);1913 1914 if (!sctx->parent_root) {1915 right_ret = -ENOENT;1916 } else {1917 ret = get_inode_info(sctx->parent_root, ino, &info);1918 if (ret < 0 && ret != -ENOENT)1919 goto out;1920 right_ret = (info.nlink == 0) ? -ENOENT : ret;1921 right_gen = info.gen;1922 if (parent_gen)1923 *parent_gen = ((right_ret == -ENOENT) ? 0 : info.gen);1924 }1925 1926 if (!left_ret && !right_ret) {1927 if (left_gen == gen && right_gen == gen) {1928 ret = inode_state_no_change;1929 } else if (left_gen == gen) {1930 if (ino < sctx->send_progress)1931 ret = inode_state_did_create;1932 else1933 ret = inode_state_will_create;1934 } else if (right_gen == gen) {1935 if (ino < sctx->send_progress)1936 ret = inode_state_did_delete;1937 else1938 ret = inode_state_will_delete;1939 } else {1940 ret = -ENOENT;1941 }1942 } else if (!left_ret) {1943 if (left_gen == gen) {1944 if (ino < sctx->send_progress)1945 ret = inode_state_did_create;1946 else1947 ret = inode_state_will_create;1948 } else {1949 ret = -ENOENT;1950 }1951 } else if (!right_ret) {1952 if (right_gen == gen) {1953 if (ino < sctx->send_progress)1954 ret = inode_state_did_delete;1955 else1956 ret = inode_state_will_delete;1957 } else {1958 ret = -ENOENT;1959 }1960 } else {1961 ret = -ENOENT;1962 }1963 1964out:1965 return ret;1966}1967 1968static int is_inode_existent(struct send_ctx *sctx, u64 ino, u64 gen,1969 u64 *send_gen, u64 *parent_gen)1970{1971 int ret;1972 1973 if (ino == BTRFS_FIRST_FREE_OBJECTID)1974 return 1;1975 1976 ret = get_cur_inode_state(sctx, ino, gen, send_gen, parent_gen);1977 if (ret < 0)1978 goto out;1979 1980 if (ret == inode_state_no_change ||1981 ret == inode_state_did_create ||1982 ret == inode_state_will_delete)1983 ret = 1;1984 else1985 ret = 0;1986 1987out:1988 return ret;1989}1990 1991/*1992 * Helper function to lookup a dir item in a dir.1993 */1994static int lookup_dir_item_inode(struct btrfs_root *root,1995 u64 dir, const char *name, int name_len,1996 u64 *found_inode)1997{1998 int ret = 0;1999 struct btrfs_dir_item *di;2000 struct btrfs_key key;2001 struct btrfs_path *path;2002 struct fscrypt_str name_str = FSTR_INIT((char *)name, name_len);2003 2004 path = alloc_path_for_send();2005 if (!path)2006 return -ENOMEM;2007 2008 di = btrfs_lookup_dir_item(NULL, root, path, dir, &name_str, 0);2009 if (IS_ERR_OR_NULL(di)) {2010 ret = di ? PTR_ERR(di) : -ENOENT;2011 goto out;2012 }2013 btrfs_dir_item_key_to_cpu(path->nodes[0], di, &key);2014 if (key.type == BTRFS_ROOT_ITEM_KEY) {2015 ret = -ENOENT;2016 goto out;2017 }2018 *found_inode = key.objectid;2019 2020out:2021 btrfs_free_path(path);2022 return ret;2023}2024 2025/*2026 * Looks up the first btrfs_inode_ref of a given ino. It returns the parent dir,2027 * generation of the parent dir and the name of the dir entry.2028 */2029static int get_first_ref(struct btrfs_root *root, u64 ino,2030 u64 *dir, u64 *dir_gen, struct fs_path *name)2031{2032 int ret;2033 struct btrfs_key key;2034 struct btrfs_key found_key;2035 struct btrfs_path *path;2036 int len;2037 u64 parent_dir;2038 2039 path = alloc_path_for_send();2040 if (!path)2041 return -ENOMEM;2042 2043 key.objectid = ino;2044 key.type = BTRFS_INODE_REF_KEY;2045 key.offset = 0;2046 2047 ret = btrfs_search_slot_for_read(root, &key, path, 1, 0);2048 if (ret < 0)2049 goto out;2050 if (!ret)2051 btrfs_item_key_to_cpu(path->nodes[0], &found_key,2052 path->slots[0]);2053 if (ret || found_key.objectid != ino ||2054 (found_key.type != BTRFS_INODE_REF_KEY &&2055 found_key.type != BTRFS_INODE_EXTREF_KEY)) {2056 ret = -ENOENT;2057 goto out;2058 }2059 2060 if (found_key.type == BTRFS_INODE_REF_KEY) {2061 struct btrfs_inode_ref *iref;2062 iref = btrfs_item_ptr(path->nodes[0], path->slots[0],2063 struct btrfs_inode_ref);2064 len = btrfs_inode_ref_name_len(path->nodes[0], iref);2065 ret = fs_path_add_from_extent_buffer(name, path->nodes[0],2066 (unsigned long)(iref + 1),2067 len);2068 parent_dir = found_key.offset;2069 } else {2070 struct btrfs_inode_extref *extref;2071 extref = btrfs_item_ptr(path->nodes[0], path->slots[0],2072 struct btrfs_inode_extref);2073 len = btrfs_inode_extref_name_len(path->nodes[0], extref);2074 ret = fs_path_add_from_extent_buffer(name, path->nodes[0],2075 (unsigned long)&extref->name, len);2076 parent_dir = btrfs_inode_extref_parent(path->nodes[0], extref);2077 }2078 if (ret < 0)2079 goto out;2080 btrfs_release_path(path);2081 2082 if (dir_gen) {2083 ret = get_inode_gen(root, parent_dir, dir_gen);2084 if (ret < 0)2085 goto out;2086 }2087 2088 *dir = parent_dir;2089 2090out:2091 btrfs_free_path(path);2092 return ret;2093}2094 2095static int is_first_ref(struct btrfs_root *root,2096 u64 ino, u64 dir,2097 const char *name, int name_len)2098{2099 int ret;2100 struct fs_path *tmp_name;2101 u64 tmp_dir;2102 2103 tmp_name = fs_path_alloc();2104 if (!tmp_name)2105 return -ENOMEM;2106 2107 ret = get_first_ref(root, ino, &tmp_dir, NULL, tmp_name);2108 if (ret < 0)2109 goto out;2110 2111 if (dir != tmp_dir || name_len != fs_path_len(tmp_name)) {2112 ret = 0;2113 goto out;2114 }2115 2116 ret = !memcmp(tmp_name->start, name, name_len);2117 2118out:2119 fs_path_free(tmp_name);2120 return ret;2121}2122 2123/*2124 * Used by process_recorded_refs to determine if a new ref would overwrite an2125 * already existing ref. In case it detects an overwrite, it returns the2126 * inode/gen in who_ino/who_gen.2127 * When an overwrite is detected, process_recorded_refs does proper orphanizing2128 * to make sure later references to the overwritten inode are possible.2129 * Orphanizing is however only required for the first ref of an inode.2130 * process_recorded_refs does an additional is_first_ref check to see if2131 * orphanizing is really required.2132 */2133static int will_overwrite_ref(struct send_ctx *sctx, u64 dir, u64 dir_gen,2134 const char *name, int name_len,2135 u64 *who_ino, u64 *who_gen, u64 *who_mode)2136{2137 int ret;2138 u64 parent_root_dir_gen;2139 u64 other_inode = 0;2140 struct btrfs_inode_info info;2141 2142 if (!sctx->parent_root)2143 return 0;2144 2145 ret = is_inode_existent(sctx, dir, dir_gen, NULL, &parent_root_dir_gen);2146 if (ret <= 0)2147 return 0;2148 2149 /*2150 * If we have a parent root we need to verify that the parent dir was2151 * not deleted and then re-created, if it was then we have no overwrite2152 * and we can just unlink this entry.2153 *2154 * @parent_root_dir_gen was set to 0 if the inode does not exist in the2155 * parent root.2156 */2157 if (sctx->parent_root && dir != BTRFS_FIRST_FREE_OBJECTID &&2158 parent_root_dir_gen != dir_gen)2159 return 0;2160 2161 ret = lookup_dir_item_inode(sctx->parent_root, dir, name, name_len,2162 &other_inode);2163 if (ret == -ENOENT)2164 return 0;2165 else if (ret < 0)2166 return ret;2167 2168 /*2169 * Check if the overwritten ref was already processed. If yes, the ref2170 * was already unlinked/moved, so we can safely assume that we will not2171 * overwrite anything at this point in time.2172 */2173 if (other_inode > sctx->send_progress ||2174 is_waiting_for_move(sctx, other_inode)) {2175 ret = get_inode_info(sctx->parent_root, other_inode, &info);2176 if (ret < 0)2177 return ret;2178 2179 *who_ino = other_inode;2180 *who_gen = info.gen;2181 *who_mode = info.mode;2182 return 1;2183 }2184 2185 return 0;2186}2187 2188/*2189 * Checks if the ref was overwritten by an already processed inode. This is2190 * used by __get_cur_name_and_parent to find out if the ref was orphanized and2191 * thus the orphan name needs be used.2192 * process_recorded_refs also uses it to avoid unlinking of refs that were2193 * overwritten.2194 */2195static int did_overwrite_ref(struct send_ctx *sctx,2196 u64 dir, u64 dir_gen,2197 u64 ino, u64 ino_gen,2198 const char *name, int name_len)2199{2200 int ret;2201 u64 ow_inode;2202 u64 ow_gen = 0;2203 u64 send_root_dir_gen;2204 2205 if (!sctx->parent_root)2206 return 0;2207 2208 ret = is_inode_existent(sctx, dir, dir_gen, &send_root_dir_gen, NULL);2209 if (ret <= 0)2210 return ret;2211 2212 /*2213 * @send_root_dir_gen was set to 0 if the inode does not exist in the2214 * send root.2215 */2216 if (dir != BTRFS_FIRST_FREE_OBJECTID && send_root_dir_gen != dir_gen)2217 return 0;2218 2219 /* check if the ref was overwritten by another ref */2220 ret = lookup_dir_item_inode(sctx->send_root, dir, name, name_len,2221 &ow_inode);2222 if (ret == -ENOENT) {2223 /* was never and will never be overwritten */2224 return 0;2225 } else if (ret < 0) {2226 return ret;2227 }2228 2229 if (ow_inode == ino) {2230 ret = get_inode_gen(sctx->send_root, ow_inode, &ow_gen);2231 if (ret < 0)2232 return ret;2233 2234 /* It's the same inode, so no overwrite happened. */2235 if (ow_gen == ino_gen)2236 return 0;2237 }2238 2239 /*2240 * We know that it is or will be overwritten. Check this now.2241 * The current inode being processed might have been the one that caused2242 * inode 'ino' to be orphanized, therefore check if ow_inode matches2243 * the current inode being processed.2244 */2245 if (ow_inode < sctx->send_progress)2246 return 1;2247 2248 if (ino != sctx->cur_ino && ow_inode == sctx->cur_ino) {2249 if (ow_gen == 0) {2250 ret = get_inode_gen(sctx->send_root, ow_inode, &ow_gen);2251 if (ret < 0)2252 return ret;2253 }2254 if (ow_gen == sctx->cur_inode_gen)2255 return 1;2256 }2257 2258 return 0;2259}2260 2261/*2262 * Same as did_overwrite_ref, but also checks if it is the first ref of an inode2263 * that got overwritten. This is used by process_recorded_refs to determine2264 * if it has to use the path as returned by get_cur_path or the orphan name.2265 */2266static int did_overwrite_first_ref(struct send_ctx *sctx, u64 ino, u64 gen)2267{2268 int ret = 0;2269 struct fs_path *name = NULL;2270 u64 dir;2271 u64 dir_gen;2272 2273 if (!sctx->parent_root)2274 goto out;2275 2276 name = fs_path_alloc();2277 if (!name)2278 return -ENOMEM;2279 2280 ret = get_first_ref(sctx->parent_root, ino, &dir, &dir_gen, name);2281 if (ret < 0)2282 goto out;2283 2284 ret = did_overwrite_ref(sctx, dir, dir_gen, ino, gen,2285 name->start, fs_path_len(name));2286 2287out:2288 fs_path_free(name);2289 return ret;2290}2291 2292static inline struct name_cache_entry *name_cache_search(struct send_ctx *sctx,2293 u64 ino, u64 gen)2294{2295 struct btrfs_lru_cache_entry *entry;2296 2297 entry = btrfs_lru_cache_lookup(&sctx->name_cache, ino, gen);2298 if (!entry)2299 return NULL;2300 2301 return container_of(entry, struct name_cache_entry, entry);2302}2303 2304/*2305 * Used by get_cur_path for each ref up to the root.2306 * Returns 0 if it succeeded.2307 * Returns 1 if the inode is not existent or got overwritten. In that case, the2308 * name is an orphan name. This instructs get_cur_path to stop iterating. If 12309 * is returned, parent_ino/parent_gen are not guaranteed to be valid.2310 * Returns <0 in case of error.2311 */2312static int __get_cur_name_and_parent(struct send_ctx *sctx,2313 u64 ino, u64 gen,2314 u64 *parent_ino,2315 u64 *parent_gen,2316 struct fs_path *dest)2317{2318 int ret;2319 int nce_ret;2320 struct name_cache_entry *nce;2321 2322 /*2323 * First check if we already did a call to this function with the same2324 * ino/gen. If yes, check if the cache entry is still up-to-date. If yes2325 * return the cached result.2326 */2327 nce = name_cache_search(sctx, ino, gen);2328 if (nce) {2329 if (ino < sctx->send_progress && nce->need_later_update) {2330 btrfs_lru_cache_remove(&sctx->name_cache, &nce->entry);2331 nce = NULL;2332 } else {2333 *parent_ino = nce->parent_ino;2334 *parent_gen = nce->parent_gen;2335 ret = fs_path_add(dest, nce->name, nce->name_len);2336 if (ret < 0)2337 goto out;2338 ret = nce->ret;2339 goto out;2340 }2341 }2342 2343 /*2344 * If the inode is not existent yet, add the orphan name and return 1.2345 * This should only happen for the parent dir that we determine in2346 * record_new_ref_if_needed().2347 */2348 ret = is_inode_existent(sctx, ino, gen, NULL, NULL);2349 if (ret < 0)2350 goto out;2351 2352 if (!ret) {2353 ret = gen_unique_name(sctx, ino, gen, dest);2354 if (ret < 0)2355 goto out;2356 ret = 1;2357 goto out_cache;2358 }2359 2360 /*2361 * Depending on whether the inode was already processed or not, use2362 * send_root or parent_root for ref lookup.2363 */2364 if (ino < sctx->send_progress)2365 ret = get_first_ref(sctx->send_root, ino,2366 parent_ino, parent_gen, dest);2367 else2368 ret = get_first_ref(sctx->parent_root, ino,2369 parent_ino, parent_gen, dest);2370 if (ret < 0)2371 goto out;2372 2373 /*2374 * Check if the ref was overwritten by an inode's ref that was processed2375 * earlier. If yes, treat as orphan and return 1.2376 */2377 ret = did_overwrite_ref(sctx, *parent_ino, *parent_gen, ino, gen,2378 dest->start, dest->end - dest->start);2379 if (ret < 0)2380 goto out;2381 if (ret) {2382 fs_path_reset(dest);2383 ret = gen_unique_name(sctx, ino, gen, dest);2384 if (ret < 0)2385 goto out;2386 ret = 1;2387 }2388 2389out_cache:2390 /*2391 * Store the result of the lookup in the name cache.2392 */2393 nce = kmalloc(sizeof(*nce) + fs_path_len(dest), GFP_KERNEL);2394 if (!nce) {2395 ret = -ENOMEM;2396 goto out;2397 }2398 2399 nce->entry.key = ino;2400 nce->entry.gen = gen;2401 nce->parent_ino = *parent_ino;2402 nce->parent_gen = *parent_gen;2403 nce->name_len = fs_path_len(dest);2404 nce->ret = ret;2405 memcpy(nce->name, dest->start, nce->name_len);2406 2407 if (ino < sctx->send_progress)2408 nce->need_later_update = 0;2409 else2410 nce->need_later_update = 1;2411 2412 nce_ret = btrfs_lru_cache_store(&sctx->name_cache, &nce->entry, GFP_KERNEL);2413 if (nce_ret < 0) {2414 kfree(nce);2415 ret = nce_ret;2416 }2417 2418out:2419 return ret;2420}2421 2422/*2423 * Magic happens here. This function returns the first ref to an inode as it2424 * would look like while receiving the stream at this point in time.2425 * We walk the path up to the root. For every inode in between, we check if it2426 * was already processed/sent. If yes, we continue with the parent as found2427 * in send_root. If not, we continue with the parent as found in parent_root.2428 * If we encounter an inode that was deleted at this point in time, we use the2429 * inodes "orphan" name instead of the real name and stop. Same with new inodes2430 * that were not created yet and overwritten inodes/refs.2431 *2432 * When do we have orphan inodes:2433 * 1. When an inode is freshly created and thus no valid refs are available yet2434 * 2. When a directory lost all it's refs (deleted) but still has dir items2435 * inside which were not processed yet (pending for move/delete). If anyone2436 * tried to get the path to the dir items, it would get a path inside that2437 * orphan directory.2438 * 3. When an inode is moved around or gets new links, it may overwrite the ref2439 * of an unprocessed inode. If in that case the first ref would be2440 * overwritten, the overwritten inode gets "orphanized". Later when we2441 * process this overwritten inode, it is restored at a new place by moving2442 * the orphan inode.2443 *2444 * sctx->send_progress tells this function at which point in time receiving2445 * would be.2446 */2447static int get_cur_path(struct send_ctx *sctx, u64 ino, u64 gen,2448 struct fs_path *dest)2449{2450 int ret = 0;2451 struct fs_path *name = NULL;2452 u64 parent_inode = 0;2453 u64 parent_gen = 0;2454 int stop = 0;2455 2456 name = fs_path_alloc();2457 if (!name) {2458 ret = -ENOMEM;2459 goto out;2460 }2461 2462 dest->reversed = 1;2463 fs_path_reset(dest);2464 2465 while (!stop && ino != BTRFS_FIRST_FREE_OBJECTID) {2466 struct waiting_dir_move *wdm;2467 2468 fs_path_reset(name);2469 2470 if (is_waiting_for_rm(sctx, ino, gen)) {2471 ret = gen_unique_name(sctx, ino, gen, name);2472 if (ret < 0)2473 goto out;2474 ret = fs_path_add_path(dest, name);2475 break;2476 }2477 2478 wdm = get_waiting_dir_move(sctx, ino);2479 if (wdm && wdm->orphanized) {2480 ret = gen_unique_name(sctx, ino, gen, name);2481 stop = 1;2482 } else if (wdm) {2483 ret = get_first_ref(sctx->parent_root, ino,2484 &parent_inode, &parent_gen, name);2485 } else {2486 ret = __get_cur_name_and_parent(sctx, ino, gen,2487 &parent_inode,2488 &parent_gen, name);2489 if (ret)2490 stop = 1;2491 }2492 2493 if (ret < 0)2494 goto out;2495 2496 ret = fs_path_add_path(dest, name);2497 if (ret < 0)2498 goto out;2499 2500 ino = parent_inode;2501 gen = parent_gen;2502 }2503 2504out:2505 fs_path_free(name);2506 if (!ret)2507 fs_path_unreverse(dest);2508 return ret;2509}2510 2511/*2512 * Sends a BTRFS_SEND_C_SUBVOL command/item to userspace2513 */2514static int send_subvol_begin(struct send_ctx *sctx)2515{2516 int ret;2517 struct btrfs_root *send_root = sctx->send_root;2518 struct btrfs_root *parent_root = sctx->parent_root;2519 struct btrfs_path *path;2520 struct btrfs_key key;2521 struct btrfs_root_ref *ref;2522 struct extent_buffer *leaf;2523 char *name = NULL;2524 int namelen;2525 2526 path = btrfs_alloc_path();2527 if (!path)2528 return -ENOMEM;2529 2530 name = kmalloc(BTRFS_PATH_NAME_MAX, GFP_KERNEL);2531 if (!name) {2532 btrfs_free_path(path);2533 return -ENOMEM;2534 }2535 2536 key.objectid = btrfs_root_id(send_root);2537 key.type = BTRFS_ROOT_BACKREF_KEY;2538 key.offset = 0;2539 2540 ret = btrfs_search_slot_for_read(send_root->fs_info->tree_root,2541 &key, path, 1, 0);2542 if (ret < 0)2543 goto out;2544 if (ret) {2545 ret = -ENOENT;2546 goto out;2547 }2548 2549 leaf = path->nodes[0];2550 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);2551 if (key.type != BTRFS_ROOT_BACKREF_KEY ||2552 key.objectid != btrfs_root_id(send_root)) {2553 ret = -ENOENT;2554 goto out;2555 }2556 ref = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_root_ref);2557 namelen = btrfs_root_ref_name_len(leaf, ref);2558 read_extent_buffer(leaf, name, (unsigned long)(ref + 1), namelen);2559 btrfs_release_path(path);2560 2561 if (parent_root) {2562 ret = begin_cmd(sctx, BTRFS_SEND_C_SNAPSHOT);2563 if (ret < 0)2564 goto out;2565 } else {2566 ret = begin_cmd(sctx, BTRFS_SEND_C_SUBVOL);2567 if (ret < 0)2568 goto out;2569 }2570 2571 TLV_PUT_STRING(sctx, BTRFS_SEND_A_PATH, name, namelen);2572 2573 if (!btrfs_is_empty_uuid(sctx->send_root->root_item.received_uuid))2574 TLV_PUT_UUID(sctx, BTRFS_SEND_A_UUID,2575 sctx->send_root->root_item.received_uuid);2576 else2577 TLV_PUT_UUID(sctx, BTRFS_SEND_A_UUID,2578 sctx->send_root->root_item.uuid);2579 2580 TLV_PUT_U64(sctx, BTRFS_SEND_A_CTRANSID,2581 btrfs_root_ctransid(&sctx->send_root->root_item));2582 if (parent_root) {2583 if (!btrfs_is_empty_uuid(parent_root->root_item.received_uuid))2584 TLV_PUT_UUID(sctx, BTRFS_SEND_A_CLONE_UUID,2585 parent_root->root_item.received_uuid);2586 else2587 TLV_PUT_UUID(sctx, BTRFS_SEND_A_CLONE_UUID,2588 parent_root->root_item.uuid);2589 TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_CTRANSID,2590 btrfs_root_ctransid(&sctx->parent_root->root_item));2591 }2592 2593 ret = send_cmd(sctx);2594 2595tlv_put_failure:2596out:2597 btrfs_free_path(path);2598 kfree(name);2599 return ret;2600}2601 2602static int send_truncate(struct send_ctx *sctx, u64 ino, u64 gen, u64 size)2603{2604 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;2605 int ret = 0;2606 struct fs_path *p;2607 2608 btrfs_debug(fs_info, "send_truncate %llu size=%llu", ino, size);2609 2610 p = fs_path_alloc();2611 if (!p)2612 return -ENOMEM;2613 2614 ret = begin_cmd(sctx, BTRFS_SEND_C_TRUNCATE);2615 if (ret < 0)2616 goto out;2617 2618 ret = get_cur_path(sctx, ino, gen, p);2619 if (ret < 0)2620 goto out;2621 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);2622 TLV_PUT_U64(sctx, BTRFS_SEND_A_SIZE, size);2623 2624 ret = send_cmd(sctx);2625 2626tlv_put_failure:2627out:2628 fs_path_free(p);2629 return ret;2630}2631 2632static int send_chmod(struct send_ctx *sctx, u64 ino, u64 gen, u64 mode)2633{2634 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;2635 int ret = 0;2636 struct fs_path *p;2637 2638 btrfs_debug(fs_info, "send_chmod %llu mode=%llu", ino, mode);2639 2640 p = fs_path_alloc();2641 if (!p)2642 return -ENOMEM;2643 2644 ret = begin_cmd(sctx, BTRFS_SEND_C_CHMOD);2645 if (ret < 0)2646 goto out;2647 2648 ret = get_cur_path(sctx, ino, gen, p);2649 if (ret < 0)2650 goto out;2651 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);2652 TLV_PUT_U64(sctx, BTRFS_SEND_A_MODE, mode & 07777);2653 2654 ret = send_cmd(sctx);2655 2656tlv_put_failure:2657out:2658 fs_path_free(p);2659 return ret;2660}2661 2662static int send_fileattr(struct send_ctx *sctx, u64 ino, u64 gen, u64 fileattr)2663{2664 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;2665 int ret = 0;2666 struct fs_path *p;2667 2668 if (sctx->proto < 2)2669 return 0;2670 2671 btrfs_debug(fs_info, "send_fileattr %llu fileattr=%llu", ino, fileattr);2672 2673 p = fs_path_alloc();2674 if (!p)2675 return -ENOMEM;2676 2677 ret = begin_cmd(sctx, BTRFS_SEND_C_FILEATTR);2678 if (ret < 0)2679 goto out;2680 2681 ret = get_cur_path(sctx, ino, gen, p);2682 if (ret < 0)2683 goto out;2684 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);2685 TLV_PUT_U64(sctx, BTRFS_SEND_A_FILEATTR, fileattr);2686 2687 ret = send_cmd(sctx);2688 2689tlv_put_failure:2690out:2691 fs_path_free(p);2692 return ret;2693}2694 2695static int send_chown(struct send_ctx *sctx, u64 ino, u64 gen, u64 uid, u64 gid)2696{2697 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;2698 int ret = 0;2699 struct fs_path *p;2700 2701 btrfs_debug(fs_info, "send_chown %llu uid=%llu, gid=%llu",2702 ino, uid, gid);2703 2704 p = fs_path_alloc();2705 if (!p)2706 return -ENOMEM;2707 2708 ret = begin_cmd(sctx, BTRFS_SEND_C_CHOWN);2709 if (ret < 0)2710 goto out;2711 2712 ret = get_cur_path(sctx, ino, gen, p);2713 if (ret < 0)2714 goto out;2715 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);2716 TLV_PUT_U64(sctx, BTRFS_SEND_A_UID, uid);2717 TLV_PUT_U64(sctx, BTRFS_SEND_A_GID, gid);2718 2719 ret = send_cmd(sctx);2720 2721tlv_put_failure:2722out:2723 fs_path_free(p);2724 return ret;2725}2726 2727static int send_utimes(struct send_ctx *sctx, u64 ino, u64 gen)2728{2729 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;2730 int ret = 0;2731 struct fs_path *p = NULL;2732 struct btrfs_inode_item *ii;2733 struct btrfs_path *path = NULL;2734 struct extent_buffer *eb;2735 struct btrfs_key key;2736 int slot;2737 2738 btrfs_debug(fs_info, "send_utimes %llu", ino);2739 2740 p = fs_path_alloc();2741 if (!p)2742 return -ENOMEM;2743 2744 path = alloc_path_for_send();2745 if (!path) {2746 ret = -ENOMEM;2747 goto out;2748 }2749 2750 key.objectid = ino;2751 key.type = BTRFS_INODE_ITEM_KEY;2752 key.offset = 0;2753 ret = btrfs_search_slot(NULL, sctx->send_root, &key, path, 0, 0);2754 if (ret > 0)2755 ret = -ENOENT;2756 if (ret < 0)2757 goto out;2758 2759 eb = path->nodes[0];2760 slot = path->slots[0];2761 ii = btrfs_item_ptr(eb, slot, struct btrfs_inode_item);2762 2763 ret = begin_cmd(sctx, BTRFS_SEND_C_UTIMES);2764 if (ret < 0)2765 goto out;2766 2767 ret = get_cur_path(sctx, ino, gen, p);2768 if (ret < 0)2769 goto out;2770 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);2771 TLV_PUT_BTRFS_TIMESPEC(sctx, BTRFS_SEND_A_ATIME, eb, &ii->atime);2772 TLV_PUT_BTRFS_TIMESPEC(sctx, BTRFS_SEND_A_MTIME, eb, &ii->mtime);2773 TLV_PUT_BTRFS_TIMESPEC(sctx, BTRFS_SEND_A_CTIME, eb, &ii->ctime);2774 if (sctx->proto >= 2)2775 TLV_PUT_BTRFS_TIMESPEC(sctx, BTRFS_SEND_A_OTIME, eb, &ii->otime);2776 2777 ret = send_cmd(sctx);2778 2779tlv_put_failure:2780out:2781 fs_path_free(p);2782 btrfs_free_path(path);2783 return ret;2784}2785 2786/*2787 * If the cache is full, we can't remove entries from it and do a call to2788 * send_utimes() for each respective inode, because we might be finishing2789 * processing an inode that is a directory and it just got renamed, and existing2790 * entries in the cache may refer to inodes that have the directory in their2791 * full path - in which case we would generate outdated paths (pre-rename)2792 * for the inodes that the cache entries point to. Instead of prunning the2793 * cache when inserting, do it after we finish processing each inode at2794 * finish_inode_if_needed().2795 */2796static int cache_dir_utimes(struct send_ctx *sctx, u64 dir, u64 gen)2797{2798 struct btrfs_lru_cache_entry *entry;2799 int ret;2800 2801 entry = btrfs_lru_cache_lookup(&sctx->dir_utimes_cache, dir, gen);2802 if (entry != NULL)2803 return 0;2804 2805 /* Caching is optional, don't fail if we can't allocate memory. */2806 entry = kmalloc(sizeof(*entry), GFP_KERNEL);2807 if (!entry)2808 return send_utimes(sctx, dir, gen);2809 2810 entry->key = dir;2811 entry->gen = gen;2812 2813 ret = btrfs_lru_cache_store(&sctx->dir_utimes_cache, entry, GFP_KERNEL);2814 ASSERT(ret != -EEXIST);2815 if (ret) {2816 kfree(entry);2817 return send_utimes(sctx, dir, gen);2818 }2819 2820 return 0;2821}2822 2823static int trim_dir_utimes_cache(struct send_ctx *sctx)2824{2825 while (sctx->dir_utimes_cache.size > SEND_MAX_DIR_UTIMES_CACHE_SIZE) {2826 struct btrfs_lru_cache_entry *lru;2827 int ret;2828 2829 lru = btrfs_lru_cache_lru_entry(&sctx->dir_utimes_cache);2830 ASSERT(lru != NULL);2831 2832 ret = send_utimes(sctx, lru->key, lru->gen);2833 if (ret)2834 return ret;2835 2836 btrfs_lru_cache_remove(&sctx->dir_utimes_cache, lru);2837 }2838 2839 return 0;2840}2841 2842/*2843 * Sends a BTRFS_SEND_C_MKXXX or SYMLINK command to user space. We don't have2844 * a valid path yet because we did not process the refs yet. So, the inode2845 * is created as orphan.2846 */2847static int send_create_inode(struct send_ctx *sctx, u64 ino)2848{2849 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;2850 int ret = 0;2851 struct fs_path *p;2852 int cmd;2853 struct btrfs_inode_info info;2854 u64 gen;2855 u64 mode;2856 u64 rdev;2857 2858 btrfs_debug(fs_info, "send_create_inode %llu", ino);2859 2860 p = fs_path_alloc();2861 if (!p)2862 return -ENOMEM;2863 2864 if (ino != sctx->cur_ino) {2865 ret = get_inode_info(sctx->send_root, ino, &info);2866 if (ret < 0)2867 goto out;2868 gen = info.gen;2869 mode = info.mode;2870 rdev = info.rdev;2871 } else {2872 gen = sctx->cur_inode_gen;2873 mode = sctx->cur_inode_mode;2874 rdev = sctx->cur_inode_rdev;2875 }2876 2877 if (S_ISREG(mode)) {2878 cmd = BTRFS_SEND_C_MKFILE;2879 } else if (S_ISDIR(mode)) {2880 cmd = BTRFS_SEND_C_MKDIR;2881 } else if (S_ISLNK(mode)) {2882 cmd = BTRFS_SEND_C_SYMLINK;2883 } else if (S_ISCHR(mode) || S_ISBLK(mode)) {2884 cmd = BTRFS_SEND_C_MKNOD;2885 } else if (S_ISFIFO(mode)) {2886 cmd = BTRFS_SEND_C_MKFIFO;2887 } else if (S_ISSOCK(mode)) {2888 cmd = BTRFS_SEND_C_MKSOCK;2889 } else {2890 btrfs_warn(sctx->send_root->fs_info, "unexpected inode type %o",2891 (int)(mode & S_IFMT));2892 ret = -EOPNOTSUPP;2893 goto out;2894 }2895 2896 ret = begin_cmd(sctx, cmd);2897 if (ret < 0)2898 goto out;2899 2900 ret = gen_unique_name(sctx, ino, gen, p);2901 if (ret < 0)2902 goto out;2903 2904 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);2905 TLV_PUT_U64(sctx, BTRFS_SEND_A_INO, ino);2906 2907 if (S_ISLNK(mode)) {2908 fs_path_reset(p);2909 ret = read_symlink(sctx->send_root, ino, p);2910 if (ret < 0)2911 goto out;2912 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH_LINK, p);2913 } else if (S_ISCHR(mode) || S_ISBLK(mode) ||2914 S_ISFIFO(mode) || S_ISSOCK(mode)) {2915 TLV_PUT_U64(sctx, BTRFS_SEND_A_RDEV, new_encode_dev(rdev));2916 TLV_PUT_U64(sctx, BTRFS_SEND_A_MODE, mode);2917 }2918 2919 ret = send_cmd(sctx);2920 if (ret < 0)2921 goto out;2922 2923 2924tlv_put_failure:2925out:2926 fs_path_free(p);2927 return ret;2928}2929 2930static void cache_dir_created(struct send_ctx *sctx, u64 dir)2931{2932 struct btrfs_lru_cache_entry *entry;2933 int ret;2934 2935 /* Caching is optional, ignore any failures. */2936 entry = kmalloc(sizeof(*entry), GFP_KERNEL);2937 if (!entry)2938 return;2939 2940 entry->key = dir;2941 entry->gen = 0;2942 ret = btrfs_lru_cache_store(&sctx->dir_created_cache, entry, GFP_KERNEL);2943 if (ret < 0)2944 kfree(entry);2945}2946 2947/*2948 * We need some special handling for inodes that get processed before the parent2949 * directory got created. See process_recorded_refs for details.2950 * This function does the check if we already created the dir out of order.2951 */2952static int did_create_dir(struct send_ctx *sctx, u64 dir)2953{2954 int ret = 0;2955 int iter_ret = 0;2956 struct btrfs_path *path = NULL;2957 struct btrfs_key key;2958 struct btrfs_key found_key;2959 struct btrfs_key di_key;2960 struct btrfs_dir_item *di;2961 2962 if (btrfs_lru_cache_lookup(&sctx->dir_created_cache, dir, 0))2963 return 1;2964 2965 path = alloc_path_for_send();2966 if (!path)2967 return -ENOMEM;2968 2969 key.objectid = dir;2970 key.type = BTRFS_DIR_INDEX_KEY;2971 key.offset = 0;2972 2973 btrfs_for_each_slot(sctx->send_root, &key, &found_key, path, iter_ret) {2974 struct extent_buffer *eb = path->nodes[0];2975 2976 if (found_key.objectid != key.objectid ||2977 found_key.type != key.type) {2978 ret = 0;2979 break;2980 }2981 2982 di = btrfs_item_ptr(eb, path->slots[0], struct btrfs_dir_item);2983 btrfs_dir_item_key_to_cpu(eb, di, &di_key);2984 2985 if (di_key.type != BTRFS_ROOT_ITEM_KEY &&2986 di_key.objectid < sctx->send_progress) {2987 ret = 1;2988 cache_dir_created(sctx, dir);2989 break;2990 }2991 }2992 /* Catch error found during iteration */2993 if (iter_ret < 0)2994 ret = iter_ret;2995 2996 btrfs_free_path(path);2997 return ret;2998}2999 3000/*3001 * Only creates the inode if it is:3002 * 1. Not a directory3003 * 2. Or a directory which was not created already due to out of order3004 * directories. See did_create_dir and process_recorded_refs for details.3005 */3006static int send_create_inode_if_needed(struct send_ctx *sctx)3007{3008 int ret;3009 3010 if (S_ISDIR(sctx->cur_inode_mode)) {3011 ret = did_create_dir(sctx, sctx->cur_ino);3012 if (ret < 0)3013 return ret;3014 else if (ret > 0)3015 return 0;3016 }3017 3018 ret = send_create_inode(sctx, sctx->cur_ino);3019 3020 if (ret == 0 && S_ISDIR(sctx->cur_inode_mode))3021 cache_dir_created(sctx, sctx->cur_ino);3022 3023 return ret;3024}3025 3026struct recorded_ref {3027 struct list_head list;3028 char *name;3029 struct fs_path *full_path;3030 u64 dir;3031 u64 dir_gen;3032 int name_len;3033 struct rb_node node;3034 struct rb_root *root;3035};3036 3037static struct recorded_ref *recorded_ref_alloc(void)3038{3039 struct recorded_ref *ref;3040 3041 ref = kzalloc(sizeof(*ref), GFP_KERNEL);3042 if (!ref)3043 return NULL;3044 RB_CLEAR_NODE(&ref->node);3045 INIT_LIST_HEAD(&ref->list);3046 return ref;3047}3048 3049static void recorded_ref_free(struct recorded_ref *ref)3050{3051 if (!ref)3052 return;3053 if (!RB_EMPTY_NODE(&ref->node))3054 rb_erase(&ref->node, ref->root);3055 list_del(&ref->list);3056 fs_path_free(ref->full_path);3057 kfree(ref);3058}3059 3060static void set_ref_path(struct recorded_ref *ref, struct fs_path *path)3061{3062 ref->full_path = path;3063 ref->name = (char *)kbasename(ref->full_path->start);3064 ref->name_len = ref->full_path->end - ref->name;3065}3066 3067static int dup_ref(struct recorded_ref *ref, struct list_head *list)3068{3069 struct recorded_ref *new;3070 3071 new = recorded_ref_alloc();3072 if (!new)3073 return -ENOMEM;3074 3075 new->dir = ref->dir;3076 new->dir_gen = ref->dir_gen;3077 list_add_tail(&new->list, list);3078 return 0;3079}3080 3081static void __free_recorded_refs(struct list_head *head)3082{3083 struct recorded_ref *cur;3084 3085 while (!list_empty(head)) {3086 cur = list_entry(head->next, struct recorded_ref, list);3087 recorded_ref_free(cur);3088 }3089}3090 3091static void free_recorded_refs(struct send_ctx *sctx)3092{3093 __free_recorded_refs(&sctx->new_refs);3094 __free_recorded_refs(&sctx->deleted_refs);3095}3096 3097/*3098 * Renames/moves a file/dir to its orphan name. Used when the first3099 * ref of an unprocessed inode gets overwritten and for all non empty3100 * directories.3101 */3102static int orphanize_inode(struct send_ctx *sctx, u64 ino, u64 gen,3103 struct fs_path *path)3104{3105 int ret;3106 struct fs_path *orphan;3107 3108 orphan = fs_path_alloc();3109 if (!orphan)3110 return -ENOMEM;3111 3112 ret = gen_unique_name(sctx, ino, gen, orphan);3113 if (ret < 0)3114 goto out;3115 3116 ret = send_rename(sctx, path, orphan);3117 3118out:3119 fs_path_free(orphan);3120 return ret;3121}3122 3123static struct orphan_dir_info *add_orphan_dir_info(struct send_ctx *sctx,3124 u64 dir_ino, u64 dir_gen)3125{3126 struct rb_node **p = &sctx->orphan_dirs.rb_node;3127 struct rb_node *parent = NULL;3128 struct orphan_dir_info *entry, *odi;3129 3130 while (*p) {3131 parent = *p;3132 entry = rb_entry(parent, struct orphan_dir_info, node);3133 if (dir_ino < entry->ino)3134 p = &(*p)->rb_left;3135 else if (dir_ino > entry->ino)3136 p = &(*p)->rb_right;3137 else if (dir_gen < entry->gen)3138 p = &(*p)->rb_left;3139 else if (dir_gen > entry->gen)3140 p = &(*p)->rb_right;3141 else3142 return entry;3143 }3144 3145 odi = kmalloc(sizeof(*odi), GFP_KERNEL);3146 if (!odi)3147 return ERR_PTR(-ENOMEM);3148 odi->ino = dir_ino;3149 odi->gen = dir_gen;3150 odi->last_dir_index_offset = 0;3151 odi->dir_high_seq_ino = 0;3152 3153 rb_link_node(&odi->node, parent, p);3154 rb_insert_color(&odi->node, &sctx->orphan_dirs);3155 return odi;3156}3157 3158static struct orphan_dir_info *get_orphan_dir_info(struct send_ctx *sctx,3159 u64 dir_ino, u64 gen)3160{3161 struct rb_node *n = sctx->orphan_dirs.rb_node;3162 struct orphan_dir_info *entry;3163 3164 while (n) {3165 entry = rb_entry(n, struct orphan_dir_info, node);3166 if (dir_ino < entry->ino)3167 n = n->rb_left;3168 else if (dir_ino > entry->ino)3169 n = n->rb_right;3170 else if (gen < entry->gen)3171 n = n->rb_left;3172 else if (gen > entry->gen)3173 n = n->rb_right;3174 else3175 return entry;3176 }3177 return NULL;3178}3179 3180static int is_waiting_for_rm(struct send_ctx *sctx, u64 dir_ino, u64 gen)3181{3182 struct orphan_dir_info *odi = get_orphan_dir_info(sctx, dir_ino, gen);3183 3184 return odi != NULL;3185}3186 3187static void free_orphan_dir_info(struct send_ctx *sctx,3188 struct orphan_dir_info *odi)3189{3190 if (!odi)3191 return;3192 rb_erase(&odi->node, &sctx->orphan_dirs);3193 kfree(odi);3194}3195 3196/*3197 * Returns 1 if a directory can be removed at this point in time.3198 * We check this by iterating all dir items and checking if the inode behind3199 * the dir item was already processed.3200 */3201static int can_rmdir(struct send_ctx *sctx, u64 dir, u64 dir_gen)3202{3203 int ret = 0;3204 int iter_ret = 0;3205 struct btrfs_root *root = sctx->parent_root;3206 struct btrfs_path *path;3207 struct btrfs_key key;3208 struct btrfs_key found_key;3209 struct btrfs_key loc;3210 struct btrfs_dir_item *di;3211 struct orphan_dir_info *odi = NULL;3212 u64 dir_high_seq_ino = 0;3213 u64 last_dir_index_offset = 0;3214 3215 /*3216 * Don't try to rmdir the top/root subvolume dir.3217 */3218 if (dir == BTRFS_FIRST_FREE_OBJECTID)3219 return 0;3220 3221 odi = get_orphan_dir_info(sctx, dir, dir_gen);3222 if (odi && sctx->cur_ino < odi->dir_high_seq_ino)3223 return 0;3224 3225 path = alloc_path_for_send();3226 if (!path)3227 return -ENOMEM;3228 3229 if (!odi) {3230 /*3231 * Find the inode number associated with the last dir index3232 * entry. This is very likely the inode with the highest number3233 * of all inodes that have an entry in the directory. We can3234 * then use it to avoid future calls to can_rmdir(), when3235 * processing inodes with a lower number, from having to search3236 * the parent root b+tree for dir index keys.3237 */3238 key.objectid = dir;3239 key.type = BTRFS_DIR_INDEX_KEY;3240 key.offset = (u64)-1;3241 3242 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);3243 if (ret < 0) {3244 goto out;3245 } else if (ret > 0) {3246 /* Can't happen, the root is never empty. */3247 ASSERT(path->slots[0] > 0);3248 if (WARN_ON(path->slots[0] == 0)) {3249 ret = -EUCLEAN;3250 goto out;3251 }3252 path->slots[0]--;3253 }3254 3255 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);3256 if (key.objectid != dir || key.type != BTRFS_DIR_INDEX_KEY) {3257 /* No index keys, dir can be removed. */3258 ret = 1;3259 goto out;3260 }3261 3262 di = btrfs_item_ptr(path->nodes[0], path->slots[0],3263 struct btrfs_dir_item);3264 btrfs_dir_item_key_to_cpu(path->nodes[0], di, &loc);3265 dir_high_seq_ino = loc.objectid;3266 if (sctx->cur_ino < dir_high_seq_ino) {3267 ret = 0;3268 goto out;3269 }3270 3271 btrfs_release_path(path);3272 }3273 3274 key.objectid = dir;3275 key.type = BTRFS_DIR_INDEX_KEY;3276 key.offset = (odi ? odi->last_dir_index_offset : 0);3277 3278 btrfs_for_each_slot(root, &key, &found_key, path, iter_ret) {3279 struct waiting_dir_move *dm;3280 3281 if (found_key.objectid != key.objectid ||3282 found_key.type != key.type)3283 break;3284 3285 di = btrfs_item_ptr(path->nodes[0], path->slots[0],3286 struct btrfs_dir_item);3287 btrfs_dir_item_key_to_cpu(path->nodes[0], di, &loc);3288 3289 dir_high_seq_ino = max(dir_high_seq_ino, loc.objectid);3290 last_dir_index_offset = found_key.offset;3291 3292 dm = get_waiting_dir_move(sctx, loc.objectid);3293 if (dm) {3294 dm->rmdir_ino = dir;3295 dm->rmdir_gen = dir_gen;3296 ret = 0;3297 goto out;3298 }3299 3300 if (loc.objectid > sctx->cur_ino) {3301 ret = 0;3302 goto out;3303 }3304 }3305 if (iter_ret < 0) {3306 ret = iter_ret;3307 goto out;3308 }3309 free_orphan_dir_info(sctx, odi);3310 3311 ret = 1;3312 3313out:3314 btrfs_free_path(path);3315 3316 if (ret)3317 return ret;3318 3319 if (!odi) {3320 odi = add_orphan_dir_info(sctx, dir, dir_gen);3321 if (IS_ERR(odi))3322 return PTR_ERR(odi);3323 3324 odi->gen = dir_gen;3325 }3326 3327 odi->last_dir_index_offset = last_dir_index_offset;3328 odi->dir_high_seq_ino = max(odi->dir_high_seq_ino, dir_high_seq_ino);3329 3330 return 0;3331}3332 3333static int is_waiting_for_move(struct send_ctx *sctx, u64 ino)3334{3335 struct waiting_dir_move *entry = get_waiting_dir_move(sctx, ino);3336 3337 return entry != NULL;3338}3339 3340static int add_waiting_dir_move(struct send_ctx *sctx, u64 ino, bool orphanized)3341{3342 struct rb_node **p = &sctx->waiting_dir_moves.rb_node;3343 struct rb_node *parent = NULL;3344 struct waiting_dir_move *entry, *dm;3345 3346 dm = kmalloc(sizeof(*dm), GFP_KERNEL);3347 if (!dm)3348 return -ENOMEM;3349 dm->ino = ino;3350 dm->rmdir_ino = 0;3351 dm->rmdir_gen = 0;3352 dm->orphanized = orphanized;3353 3354 while (*p) {3355 parent = *p;3356 entry = rb_entry(parent, struct waiting_dir_move, node);3357 if (ino < entry->ino) {3358 p = &(*p)->rb_left;3359 } else if (ino > entry->ino) {3360 p = &(*p)->rb_right;3361 } else {3362 kfree(dm);3363 return -EEXIST;3364 }3365 }3366 3367 rb_link_node(&dm->node, parent, p);3368 rb_insert_color(&dm->node, &sctx->waiting_dir_moves);3369 return 0;3370}3371 3372static struct waiting_dir_move *3373get_waiting_dir_move(struct send_ctx *sctx, u64 ino)3374{3375 struct rb_node *n = sctx->waiting_dir_moves.rb_node;3376 struct waiting_dir_move *entry;3377 3378 while (n) {3379 entry = rb_entry(n, struct waiting_dir_move, node);3380 if (ino < entry->ino)3381 n = n->rb_left;3382 else if (ino > entry->ino)3383 n = n->rb_right;3384 else3385 return entry;3386 }3387 return NULL;3388}3389 3390static void free_waiting_dir_move(struct send_ctx *sctx,3391 struct waiting_dir_move *dm)3392{3393 if (!dm)3394 return;3395 rb_erase(&dm->node, &sctx->waiting_dir_moves);3396 kfree(dm);3397}3398 3399static int add_pending_dir_move(struct send_ctx *sctx,3400 u64 ino,3401 u64 ino_gen,3402 u64 parent_ino,3403 struct list_head *new_refs,3404 struct list_head *deleted_refs,3405 const bool is_orphan)3406{3407 struct rb_node **p = &sctx->pending_dir_moves.rb_node;3408 struct rb_node *parent = NULL;3409 struct pending_dir_move *entry = NULL, *pm;3410 struct recorded_ref *cur;3411 int exists = 0;3412 int ret;3413 3414 pm = kmalloc(sizeof(*pm), GFP_KERNEL);3415 if (!pm)3416 return -ENOMEM;3417 pm->parent_ino = parent_ino;3418 pm->ino = ino;3419 pm->gen = ino_gen;3420 INIT_LIST_HEAD(&pm->list);3421 INIT_LIST_HEAD(&pm->update_refs);3422 RB_CLEAR_NODE(&pm->node);3423 3424 while (*p) {3425 parent = *p;3426 entry = rb_entry(parent, struct pending_dir_move, node);3427 if (parent_ino < entry->parent_ino) {3428 p = &(*p)->rb_left;3429 } else if (parent_ino > entry->parent_ino) {3430 p = &(*p)->rb_right;3431 } else {3432 exists = 1;3433 break;3434 }3435 }3436 3437 list_for_each_entry(cur, deleted_refs, list) {3438 ret = dup_ref(cur, &pm->update_refs);3439 if (ret < 0)3440 goto out;3441 }3442 list_for_each_entry(cur, new_refs, list) {3443 ret = dup_ref(cur, &pm->update_refs);3444 if (ret < 0)3445 goto out;3446 }3447 3448 ret = add_waiting_dir_move(sctx, pm->ino, is_orphan);3449 if (ret)3450 goto out;3451 3452 if (exists) {3453 list_add_tail(&pm->list, &entry->list);3454 } else {3455 rb_link_node(&pm->node, parent, p);3456 rb_insert_color(&pm->node, &sctx->pending_dir_moves);3457 }3458 ret = 0;3459out:3460 if (ret) {3461 __free_recorded_refs(&pm->update_refs);3462 kfree(pm);3463 }3464 return ret;3465}3466 3467static struct pending_dir_move *get_pending_dir_moves(struct send_ctx *sctx,3468 u64 parent_ino)3469{3470 struct rb_node *n = sctx->pending_dir_moves.rb_node;3471 struct pending_dir_move *entry;3472 3473 while (n) {3474 entry = rb_entry(n, struct pending_dir_move, node);3475 if (parent_ino < entry->parent_ino)3476 n = n->rb_left;3477 else if (parent_ino > entry->parent_ino)3478 n = n->rb_right;3479 else3480 return entry;3481 }3482 return NULL;3483}3484 3485static int path_loop(struct send_ctx *sctx, struct fs_path *name,3486 u64 ino, u64 gen, u64 *ancestor_ino)3487{3488 int ret = 0;3489 u64 parent_inode = 0;3490 u64 parent_gen = 0;3491 u64 start_ino = ino;3492 3493 *ancestor_ino = 0;3494 while (ino != BTRFS_FIRST_FREE_OBJECTID) {3495 fs_path_reset(name);3496 3497 if (is_waiting_for_rm(sctx, ino, gen))3498 break;3499 if (is_waiting_for_move(sctx, ino)) {3500 if (*ancestor_ino == 0)3501 *ancestor_ino = ino;3502 ret = get_first_ref(sctx->parent_root, ino,3503 &parent_inode, &parent_gen, name);3504 } else {3505 ret = __get_cur_name_and_parent(sctx, ino, gen,3506 &parent_inode,3507 &parent_gen, name);3508 if (ret > 0) {3509 ret = 0;3510 break;3511 }3512 }3513 if (ret < 0)3514 break;3515 if (parent_inode == start_ino) {3516 ret = 1;3517 if (*ancestor_ino == 0)3518 *ancestor_ino = ino;3519 break;3520 }3521 ino = parent_inode;3522 gen = parent_gen;3523 }3524 return ret;3525}3526 3527static int apply_dir_move(struct send_ctx *sctx, struct pending_dir_move *pm)3528{3529 struct fs_path *from_path = NULL;3530 struct fs_path *to_path = NULL;3531 struct fs_path *name = NULL;3532 u64 orig_progress = sctx->send_progress;3533 struct recorded_ref *cur;3534 u64 parent_ino, parent_gen;3535 struct waiting_dir_move *dm = NULL;3536 u64 rmdir_ino = 0;3537 u64 rmdir_gen;3538 u64 ancestor;3539 bool is_orphan;3540 int ret;3541 3542 name = fs_path_alloc();3543 from_path = fs_path_alloc();3544 if (!name || !from_path) {3545 ret = -ENOMEM;3546 goto out;3547 }3548 3549 dm = get_waiting_dir_move(sctx, pm->ino);3550 ASSERT(dm);3551 rmdir_ino = dm->rmdir_ino;3552 rmdir_gen = dm->rmdir_gen;3553 is_orphan = dm->orphanized;3554 free_waiting_dir_move(sctx, dm);3555 3556 if (is_orphan) {3557 ret = gen_unique_name(sctx, pm->ino,3558 pm->gen, from_path);3559 } else {3560 ret = get_first_ref(sctx->parent_root, pm->ino,3561 &parent_ino, &parent_gen, name);3562 if (ret < 0)3563 goto out;3564 ret = get_cur_path(sctx, parent_ino, parent_gen,3565 from_path);3566 if (ret < 0)3567 goto out;3568 ret = fs_path_add_path(from_path, name);3569 }3570 if (ret < 0)3571 goto out;3572 3573 sctx->send_progress = sctx->cur_ino + 1;3574 ret = path_loop(sctx, name, pm->ino, pm->gen, &ancestor);3575 if (ret < 0)3576 goto out;3577 if (ret) {3578 LIST_HEAD(deleted_refs);3579 ASSERT(ancestor > BTRFS_FIRST_FREE_OBJECTID);3580 ret = add_pending_dir_move(sctx, pm->ino, pm->gen, ancestor,3581 &pm->update_refs, &deleted_refs,3582 is_orphan);3583 if (ret < 0)3584 goto out;3585 if (rmdir_ino) {3586 dm = get_waiting_dir_move(sctx, pm->ino);3587 ASSERT(dm);3588 dm->rmdir_ino = rmdir_ino;3589 dm->rmdir_gen = rmdir_gen;3590 }3591 goto out;3592 }3593 fs_path_reset(name);3594 to_path = name;3595 name = NULL;3596 ret = get_cur_path(sctx, pm->ino, pm->gen, to_path);3597 if (ret < 0)3598 goto out;3599 3600 ret = send_rename(sctx, from_path, to_path);3601 if (ret < 0)3602 goto out;3603 3604 if (rmdir_ino) {3605 struct orphan_dir_info *odi;3606 u64 gen;3607 3608 odi = get_orphan_dir_info(sctx, rmdir_ino, rmdir_gen);3609 if (!odi) {3610 /* already deleted */3611 goto finish;3612 }3613 gen = odi->gen;3614 3615 ret = can_rmdir(sctx, rmdir_ino, gen);3616 if (ret < 0)3617 goto out;3618 if (!ret)3619 goto finish;3620 3621 name = fs_path_alloc();3622 if (!name) {3623 ret = -ENOMEM;3624 goto out;3625 }3626 ret = get_cur_path(sctx, rmdir_ino, gen, name);3627 if (ret < 0)3628 goto out;3629 ret = send_rmdir(sctx, name);3630 if (ret < 0)3631 goto out;3632 }3633 3634finish:3635 ret = cache_dir_utimes(sctx, pm->ino, pm->gen);3636 if (ret < 0)3637 goto out;3638 3639 /*3640 * After rename/move, need to update the utimes of both new parent(s)3641 * and old parent(s).3642 */3643 list_for_each_entry(cur, &pm->update_refs, list) {3644 /*3645 * The parent inode might have been deleted in the send snapshot3646 */3647 ret = get_inode_info(sctx->send_root, cur->dir, NULL);3648 if (ret == -ENOENT) {3649 ret = 0;3650 continue;3651 }3652 if (ret < 0)3653 goto out;3654 3655 ret = cache_dir_utimes(sctx, cur->dir, cur->dir_gen);3656 if (ret < 0)3657 goto out;3658 }3659 3660out:3661 fs_path_free(name);3662 fs_path_free(from_path);3663 fs_path_free(to_path);3664 sctx->send_progress = orig_progress;3665 3666 return ret;3667}3668 3669static void free_pending_move(struct send_ctx *sctx, struct pending_dir_move *m)3670{3671 if (!list_empty(&m->list))3672 list_del(&m->list);3673 if (!RB_EMPTY_NODE(&m->node))3674 rb_erase(&m->node, &sctx->pending_dir_moves);3675 __free_recorded_refs(&m->update_refs);3676 kfree(m);3677}3678 3679static void tail_append_pending_moves(struct send_ctx *sctx,3680 struct pending_dir_move *moves,3681 struct list_head *stack)3682{3683 if (list_empty(&moves->list)) {3684 list_add_tail(&moves->list, stack);3685 } else {3686 LIST_HEAD(list);3687 list_splice_init(&moves->list, &list);3688 list_add_tail(&moves->list, stack);3689 list_splice_tail(&list, stack);3690 }3691 if (!RB_EMPTY_NODE(&moves->node)) {3692 rb_erase(&moves->node, &sctx->pending_dir_moves);3693 RB_CLEAR_NODE(&moves->node);3694 }3695}3696 3697static int apply_children_dir_moves(struct send_ctx *sctx)3698{3699 struct pending_dir_move *pm;3700 LIST_HEAD(stack);3701 u64 parent_ino = sctx->cur_ino;3702 int ret = 0;3703 3704 pm = get_pending_dir_moves(sctx, parent_ino);3705 if (!pm)3706 return 0;3707 3708 tail_append_pending_moves(sctx, pm, &stack);3709 3710 while (!list_empty(&stack)) {3711 pm = list_first_entry(&stack, struct pending_dir_move, list);3712 parent_ino = pm->ino;3713 ret = apply_dir_move(sctx, pm);3714 free_pending_move(sctx, pm);3715 if (ret)3716 goto out;3717 pm = get_pending_dir_moves(sctx, parent_ino);3718 if (pm)3719 tail_append_pending_moves(sctx, pm, &stack);3720 }3721 return 0;3722 3723out:3724 while (!list_empty(&stack)) {3725 pm = list_first_entry(&stack, struct pending_dir_move, list);3726 free_pending_move(sctx, pm);3727 }3728 return ret;3729}3730 3731/*3732 * We might need to delay a directory rename even when no ancestor directory3733 * (in the send root) with a higher inode number than ours (sctx->cur_ino) was3734 * renamed. This happens when we rename a directory to the old name (the name3735 * in the parent root) of some other unrelated directory that got its rename3736 * delayed due to some ancestor with higher number that got renamed.3737 *3738 * Example:3739 *3740 * Parent snapshot:3741 * . (ino 256)3742 * |---- a/ (ino 257)3743 * | |---- file (ino 260)3744 * |3745 * |---- b/ (ino 258)3746 * |---- c/ (ino 259)3747 *3748 * Send snapshot:3749 * . (ino 256)3750 * |---- a/ (ino 258)3751 * |---- x/ (ino 259)3752 * |---- y/ (ino 257)3753 * |----- file (ino 260)3754 *3755 * Here we can not rename 258 from 'b' to 'a' without the rename of inode 2573756 * from 'a' to 'x/y' happening first, which in turn depends on the rename of3757 * inode 259 from 'c' to 'x'. So the order of rename commands the send stream3758 * must issue is:3759 *3760 * 1 - rename 259 from 'c' to 'x'3761 * 2 - rename 257 from 'a' to 'x/y'3762 * 3 - rename 258 from 'b' to 'a'3763 *3764 * Returns 1 if the rename of sctx->cur_ino needs to be delayed, 0 if it can3765 * be done right away and < 0 on error.3766 */3767static int wait_for_dest_dir_move(struct send_ctx *sctx,3768 struct recorded_ref *parent_ref,3769 const bool is_orphan)3770{3771 struct btrfs_fs_info *fs_info = sctx->parent_root->fs_info;3772 struct btrfs_path *path;3773 struct btrfs_key key;3774 struct btrfs_key di_key;3775 struct btrfs_dir_item *di;3776 u64 left_gen;3777 u64 right_gen;3778 int ret = 0;3779 struct waiting_dir_move *wdm;3780 3781 if (RB_EMPTY_ROOT(&sctx->waiting_dir_moves))3782 return 0;3783 3784 path = alloc_path_for_send();3785 if (!path)3786 return -ENOMEM;3787 3788 key.objectid = parent_ref->dir;3789 key.type = BTRFS_DIR_ITEM_KEY;3790 key.offset = btrfs_name_hash(parent_ref->name, parent_ref->name_len);3791 3792 ret = btrfs_search_slot(NULL, sctx->parent_root, &key, path, 0, 0);3793 if (ret < 0) {3794 goto out;3795 } else if (ret > 0) {3796 ret = 0;3797 goto out;3798 }3799 3800 di = btrfs_match_dir_item_name(fs_info, path, parent_ref->name,3801 parent_ref->name_len);3802 if (!di) {3803 ret = 0;3804 goto out;3805 }3806 /*3807 * di_key.objectid has the number of the inode that has a dentry in the3808 * parent directory with the same name that sctx->cur_ino is being3809 * renamed to. We need to check if that inode is in the send root as3810 * well and if it is currently marked as an inode with a pending rename,3811 * if it is, we need to delay the rename of sctx->cur_ino as well, so3812 * that it happens after that other inode is renamed.3813 */3814 btrfs_dir_item_key_to_cpu(path->nodes[0], di, &di_key);3815 if (di_key.type != BTRFS_INODE_ITEM_KEY) {3816 ret = 0;3817 goto out;3818 }3819 3820 ret = get_inode_gen(sctx->parent_root, di_key.objectid, &left_gen);3821 if (ret < 0)3822 goto out;3823 ret = get_inode_gen(sctx->send_root, di_key.objectid, &right_gen);3824 if (ret < 0) {3825 if (ret == -ENOENT)3826 ret = 0;3827 goto out;3828 }3829 3830 /* Different inode, no need to delay the rename of sctx->cur_ino */3831 if (right_gen != left_gen) {3832 ret = 0;3833 goto out;3834 }3835 3836 wdm = get_waiting_dir_move(sctx, di_key.objectid);3837 if (wdm && !wdm->orphanized) {3838 ret = add_pending_dir_move(sctx,3839 sctx->cur_ino,3840 sctx->cur_inode_gen,3841 di_key.objectid,3842 &sctx->new_refs,3843 &sctx->deleted_refs,3844 is_orphan);3845 if (!ret)3846 ret = 1;3847 }3848out:3849 btrfs_free_path(path);3850 return ret;3851}3852 3853/*3854 * Check if inode ino2, or any of its ancestors, is inode ino1.3855 * Return 1 if true, 0 if false and < 0 on error.3856 */3857static int check_ino_in_path(struct btrfs_root *root,3858 const u64 ino1,3859 const u64 ino1_gen,3860 const u64 ino2,3861 const u64 ino2_gen,3862 struct fs_path *fs_path)3863{3864 u64 ino = ino2;3865 3866 if (ino1 == ino2)3867 return ino1_gen == ino2_gen;3868 3869 while (ino > BTRFS_FIRST_FREE_OBJECTID) {3870 u64 parent;3871 u64 parent_gen;3872 int ret;3873 3874 fs_path_reset(fs_path);3875 ret = get_first_ref(root, ino, &parent, &parent_gen, fs_path);3876 if (ret < 0)3877 return ret;3878 if (parent == ino1)3879 return parent_gen == ino1_gen;3880 ino = parent;3881 }3882 return 0;3883}3884 3885/*3886 * Check if inode ino1 is an ancestor of inode ino2 in the given root for any3887 * possible path (in case ino2 is not a directory and has multiple hard links).3888 * Return 1 if true, 0 if false and < 0 on error.3889 */3890static int is_ancestor(struct btrfs_root *root,3891 const u64 ino1,3892 const u64 ino1_gen,3893 const u64 ino2,3894 struct fs_path *fs_path)3895{3896 bool free_fs_path = false;3897 int ret = 0;3898 int iter_ret = 0;3899 struct btrfs_path *path = NULL;3900 struct btrfs_key key;3901 3902 if (!fs_path) {3903 fs_path = fs_path_alloc();3904 if (!fs_path)3905 return -ENOMEM;3906 free_fs_path = true;3907 }3908 3909 path = alloc_path_for_send();3910 if (!path) {3911 ret = -ENOMEM;3912 goto out;3913 }3914 3915 key.objectid = ino2;3916 key.type = BTRFS_INODE_REF_KEY;3917 key.offset = 0;3918 3919 btrfs_for_each_slot(root, &key, &key, path, iter_ret) {3920 struct extent_buffer *leaf = path->nodes[0];3921 int slot = path->slots[0];3922 u32 cur_offset = 0;3923 u32 item_size;3924 3925 if (key.objectid != ino2)3926 break;3927 if (key.type != BTRFS_INODE_REF_KEY &&3928 key.type != BTRFS_INODE_EXTREF_KEY)3929 break;3930 3931 item_size = btrfs_item_size(leaf, slot);3932 while (cur_offset < item_size) {3933 u64 parent;3934 u64 parent_gen;3935 3936 if (key.type == BTRFS_INODE_EXTREF_KEY) {3937 unsigned long ptr;3938 struct btrfs_inode_extref *extref;3939 3940 ptr = btrfs_item_ptr_offset(leaf, slot);3941 extref = (struct btrfs_inode_extref *)3942 (ptr + cur_offset);3943 parent = btrfs_inode_extref_parent(leaf,3944 extref);3945 cur_offset += sizeof(*extref);3946 cur_offset += btrfs_inode_extref_name_len(leaf,3947 extref);3948 } else {3949 parent = key.offset;3950 cur_offset = item_size;3951 }3952 3953 ret = get_inode_gen(root, parent, &parent_gen);3954 if (ret < 0)3955 goto out;3956 ret = check_ino_in_path(root, ino1, ino1_gen,3957 parent, parent_gen, fs_path);3958 if (ret)3959 goto out;3960 }3961 }3962 ret = 0;3963 if (iter_ret < 0)3964 ret = iter_ret;3965 3966out:3967 btrfs_free_path(path);3968 if (free_fs_path)3969 fs_path_free(fs_path);3970 return ret;3971}3972 3973static int wait_for_parent_move(struct send_ctx *sctx,3974 struct recorded_ref *parent_ref,3975 const bool is_orphan)3976{3977 int ret = 0;3978 u64 ino = parent_ref->dir;3979 u64 ino_gen = parent_ref->dir_gen;3980 u64 parent_ino_before, parent_ino_after;3981 struct fs_path *path_before = NULL;3982 struct fs_path *path_after = NULL;3983 int len1, len2;3984 3985 path_after = fs_path_alloc();3986 path_before = fs_path_alloc();3987 if (!path_after || !path_before) {3988 ret = -ENOMEM;3989 goto out;3990 }3991 3992 /*3993 * Our current directory inode may not yet be renamed/moved because some3994 * ancestor (immediate or not) has to be renamed/moved first. So find if3995 * such ancestor exists and make sure our own rename/move happens after3996 * that ancestor is processed to avoid path build infinite loops (done3997 * at get_cur_path()).3998 */3999 while (ino > BTRFS_FIRST_FREE_OBJECTID) {4000 u64 parent_ino_after_gen;4001 4002 if (is_waiting_for_move(sctx, ino)) {4003 /*4004 * If the current inode is an ancestor of ino in the4005 * parent root, we need to delay the rename of the4006 * current inode, otherwise don't delayed the rename4007 * because we can end up with a circular dependency4008 * of renames, resulting in some directories never4009 * getting the respective rename operations issued in4010 * the send stream or getting into infinite path build4011 * loops.4012 */4013 ret = is_ancestor(sctx->parent_root,4014 sctx->cur_ino, sctx->cur_inode_gen,4015 ino, path_before);4016 if (ret)4017 break;4018 }4019 4020 fs_path_reset(path_before);4021 fs_path_reset(path_after);4022 4023 ret = get_first_ref(sctx->send_root, ino, &parent_ino_after,4024 &parent_ino_after_gen, path_after);4025 if (ret < 0)4026 goto out;4027 ret = get_first_ref(sctx->parent_root, ino, &parent_ino_before,4028 NULL, path_before);4029 if (ret < 0 && ret != -ENOENT) {4030 goto out;4031 } else if (ret == -ENOENT) {4032 ret = 0;4033 break;4034 }4035 4036 len1 = fs_path_len(path_before);4037 len2 = fs_path_len(path_after);4038 if (ino > sctx->cur_ino &&4039 (parent_ino_before != parent_ino_after || len1 != len2 ||4040 memcmp(path_before->start, path_after->start, len1))) {4041 u64 parent_ino_gen;4042 4043 ret = get_inode_gen(sctx->parent_root, ino, &parent_ino_gen);4044 if (ret < 0)4045 goto out;4046 if (ino_gen == parent_ino_gen) {4047 ret = 1;4048 break;4049 }4050 }4051 ino = parent_ino_after;4052 ino_gen = parent_ino_after_gen;4053 }4054 4055out:4056 fs_path_free(path_before);4057 fs_path_free(path_after);4058 4059 if (ret == 1) {4060 ret = add_pending_dir_move(sctx,4061 sctx->cur_ino,4062 sctx->cur_inode_gen,4063 ino,4064 &sctx->new_refs,4065 &sctx->deleted_refs,4066 is_orphan);4067 if (!ret)4068 ret = 1;4069 }4070 4071 return ret;4072}4073 4074static int update_ref_path(struct send_ctx *sctx, struct recorded_ref *ref)4075{4076 int ret;4077 struct fs_path *new_path;4078 4079 /*4080 * Our reference's name member points to its full_path member string, so4081 * we use here a new path.4082 */4083 new_path = fs_path_alloc();4084 if (!new_path)4085 return -ENOMEM;4086 4087 ret = get_cur_path(sctx, ref->dir, ref->dir_gen, new_path);4088 if (ret < 0) {4089 fs_path_free(new_path);4090 return ret;4091 }4092 ret = fs_path_add(new_path, ref->name, ref->name_len);4093 if (ret < 0) {4094 fs_path_free(new_path);4095 return ret;4096 }4097 4098 fs_path_free(ref->full_path);4099 set_ref_path(ref, new_path);4100 4101 return 0;4102}4103 4104/*4105 * When processing the new references for an inode we may orphanize an existing4106 * directory inode because its old name conflicts with one of the new references4107 * of the current inode. Later, when processing another new reference of our4108 * inode, we might need to orphanize another inode, but the path we have in the4109 * reference reflects the pre-orphanization name of the directory we previously4110 * orphanized. For example:4111 *4112 * parent snapshot looks like:4113 *4114 * . (ino 256)4115 * |----- f1 (ino 257)4116 * |----- f2 (ino 258)4117 * |----- d1/ (ino 259)4118 * |----- d2/ (ino 260)4119 *4120 * send snapshot looks like:4121 *4122 * . (ino 256)4123 * |----- d1 (ino 258)4124 * |----- f2/ (ino 259)4125 * |----- f2_link/ (ino 260)4126 * | |----- f1 (ino 257)4127 * |4128 * |----- d2 (ino 258)4129 *4130 * When processing inode 257 we compute the name for inode 259 as "d1", and we4131 * cache it in the name cache. Later when we start processing inode 258, when4132 * collecting all its new references we set a full path of "d1/d2" for its new4133 * reference with name "d2". When we start processing the new references we4134 * start by processing the new reference with name "d1", and this results in4135 * orphanizing inode 259, since its old reference causes a conflict. Then we4136 * move on the next new reference, with name "d2", and we find out we must4137 * orphanize inode 260, as its old reference conflicts with ours - but for the4138 * orphanization we use a source path corresponding to the path we stored in the4139 * new reference, which is "d1/d2" and not "o259-6-0/d2" - this makes the4140 * receiver fail since the path component "d1/" no longer exists, it was renamed4141 * to "o259-6-0/" when processing the previous new reference. So in this case we4142 * must recompute the path in the new reference and use it for the new4143 * orphanization operation.4144 */4145static int refresh_ref_path(struct send_ctx *sctx, struct recorded_ref *ref)4146{4147 char *name;4148 int ret;4149 4150 name = kmemdup(ref->name, ref->name_len, GFP_KERNEL);4151 if (!name)4152 return -ENOMEM;4153 4154 fs_path_reset(ref->full_path);4155 ret = get_cur_path(sctx, ref->dir, ref->dir_gen, ref->full_path);4156 if (ret < 0)4157 goto out;4158 4159 ret = fs_path_add(ref->full_path, name, ref->name_len);4160 if (ret < 0)4161 goto out;4162 4163 /* Update the reference's base name pointer. */4164 set_ref_path(ref, ref->full_path);4165out:4166 kfree(name);4167 return ret;4168}4169 4170/*4171 * This does all the move/link/unlink/rmdir magic.4172 */4173static int process_recorded_refs(struct send_ctx *sctx, int *pending_move)4174{4175 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;4176 int ret = 0;4177 struct recorded_ref *cur;4178 struct recorded_ref *cur2;4179 LIST_HEAD(check_dirs);4180 struct fs_path *valid_path = NULL;4181 u64 ow_inode = 0;4182 u64 ow_gen;4183 u64 ow_mode;4184 int did_overwrite = 0;4185 int is_orphan = 0;4186 u64 last_dir_ino_rm = 0;4187 bool can_rename = true;4188 bool orphanized_dir = false;4189 bool orphanized_ancestor = false;4190 4191 btrfs_debug(fs_info, "process_recorded_refs %llu", sctx->cur_ino);4192 4193 /*4194 * This should never happen as the root dir always has the same ref4195 * which is always '..'4196 */4197 if (unlikely(sctx->cur_ino <= BTRFS_FIRST_FREE_OBJECTID)) {4198 btrfs_err(fs_info,4199 "send: unexpected inode %llu in process_recorded_refs()",4200 sctx->cur_ino);4201 ret = -EINVAL;4202 goto out;4203 }4204 4205 valid_path = fs_path_alloc();4206 if (!valid_path) {4207 ret = -ENOMEM;4208 goto out;4209 }4210 4211 /*4212 * First, check if the first ref of the current inode was overwritten4213 * before. If yes, we know that the current inode was already orphanized4214 * and thus use the orphan name. If not, we can use get_cur_path to4215 * get the path of the first ref as it would like while receiving at4216 * this point in time.4217 * New inodes are always orphan at the beginning, so force to use the4218 * orphan name in this case.4219 * The first ref is stored in valid_path and will be updated if it4220 * gets moved around.4221 */4222 if (!sctx->cur_inode_new) {4223 ret = did_overwrite_first_ref(sctx, sctx->cur_ino,4224 sctx->cur_inode_gen);4225 if (ret < 0)4226 goto out;4227 if (ret)4228 did_overwrite = 1;4229 }4230 if (sctx->cur_inode_new || did_overwrite) {4231 ret = gen_unique_name(sctx, sctx->cur_ino,4232 sctx->cur_inode_gen, valid_path);4233 if (ret < 0)4234 goto out;4235 is_orphan = 1;4236 } else {4237 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen,4238 valid_path);4239 if (ret < 0)4240 goto out;4241 }4242 4243 /*4244 * Before doing any rename and link operations, do a first pass on the4245 * new references to orphanize any unprocessed inodes that may have a4246 * reference that conflicts with one of the new references of the current4247 * inode. This needs to happen first because a new reference may conflict4248 * with the old reference of a parent directory, so we must make sure4249 * that the path used for link and rename commands don't use an4250 * orphanized name when an ancestor was not yet orphanized.4251 *4252 * Example:4253 *4254 * Parent snapshot:4255 *4256 * . (ino 256)4257 * |----- testdir/ (ino 259)4258 * | |----- a (ino 257)4259 * |4260 * |----- b (ino 258)4261 *4262 * Send snapshot:4263 *4264 * . (ino 256)4265 * |----- testdir_2/ (ino 259)4266 * | |----- a (ino 260)4267 * |4268 * |----- testdir (ino 257)4269 * |----- b (ino 257)4270 * |----- b2 (ino 258)4271 *4272 * Processing the new reference for inode 257 with name "b" may happen4273 * before processing the new reference with name "testdir". If so, we4274 * must make sure that by the time we send a link command to create the4275 * hard link "b", inode 259 was already orphanized, since the generated4276 * path in "valid_path" already contains the orphanized name for 259.4277 * We are processing inode 257, so only later when processing 259 we do4278 * the rename operation to change its temporary (orphanized) name to4279 * "testdir_2".4280 */4281 list_for_each_entry(cur, &sctx->new_refs, list) {4282 ret = get_cur_inode_state(sctx, cur->dir, cur->dir_gen, NULL, NULL);4283 if (ret < 0)4284 goto out;4285 if (ret == inode_state_will_create)4286 continue;4287 4288 /*4289 * Check if this new ref would overwrite the first ref of another4290 * unprocessed inode. If yes, orphanize the overwritten inode.4291 * If we find an overwritten ref that is not the first ref,4292 * simply unlink it.4293 */4294 ret = will_overwrite_ref(sctx, cur->dir, cur->dir_gen,4295 cur->name, cur->name_len,4296 &ow_inode, &ow_gen, &ow_mode);4297 if (ret < 0)4298 goto out;4299 if (ret) {4300 ret = is_first_ref(sctx->parent_root,4301 ow_inode, cur->dir, cur->name,4302 cur->name_len);4303 if (ret < 0)4304 goto out;4305 if (ret) {4306 struct name_cache_entry *nce;4307 struct waiting_dir_move *wdm;4308 4309 if (orphanized_dir) {4310 ret = refresh_ref_path(sctx, cur);4311 if (ret < 0)4312 goto out;4313 }4314 4315 ret = orphanize_inode(sctx, ow_inode, ow_gen,4316 cur->full_path);4317 if (ret < 0)4318 goto out;4319 if (S_ISDIR(ow_mode))4320 orphanized_dir = true;4321 4322 /*4323 * If ow_inode has its rename operation delayed4324 * make sure that its orphanized name is used in4325 * the source path when performing its rename4326 * operation.4327 */4328 wdm = get_waiting_dir_move(sctx, ow_inode);4329 if (wdm)4330 wdm->orphanized = true;4331 4332 /*4333 * Make sure we clear our orphanized inode's4334 * name from the name cache. This is because the4335 * inode ow_inode might be an ancestor of some4336 * other inode that will be orphanized as well4337 * later and has an inode number greater than4338 * sctx->send_progress. We need to prevent4339 * future name lookups from using the old name4340 * and get instead the orphan name.4341 */4342 nce = name_cache_search(sctx, ow_inode, ow_gen);4343 if (nce)4344 btrfs_lru_cache_remove(&sctx->name_cache,4345 &nce->entry);4346 4347 /*4348 * ow_inode might currently be an ancestor of4349 * cur_ino, therefore compute valid_path (the4350 * current path of cur_ino) again because it4351 * might contain the pre-orphanization name of4352 * ow_inode, which is no longer valid.4353 */4354 ret = is_ancestor(sctx->parent_root,4355 ow_inode, ow_gen,4356 sctx->cur_ino, NULL);4357 if (ret > 0) {4358 orphanized_ancestor = true;4359 fs_path_reset(valid_path);4360 ret = get_cur_path(sctx, sctx->cur_ino,4361 sctx->cur_inode_gen,4362 valid_path);4363 }4364 if (ret < 0)4365 goto out;4366 } else {4367 /*4368 * If we previously orphanized a directory that4369 * collided with a new reference that we already4370 * processed, recompute the current path because4371 * that directory may be part of the path.4372 */4373 if (orphanized_dir) {4374 ret = refresh_ref_path(sctx, cur);4375 if (ret < 0)4376 goto out;4377 }4378 ret = send_unlink(sctx, cur->full_path);4379 if (ret < 0)4380 goto out;4381 }4382 }4383 4384 }4385 4386 list_for_each_entry(cur, &sctx->new_refs, list) {4387 /*4388 * We may have refs where the parent directory does not exist4389 * yet. This happens if the parent directories inum is higher4390 * than the current inum. To handle this case, we create the4391 * parent directory out of order. But we need to check if this4392 * did already happen before due to other refs in the same dir.4393 */4394 ret = get_cur_inode_state(sctx, cur->dir, cur->dir_gen, NULL, NULL);4395 if (ret < 0)4396 goto out;4397 if (ret == inode_state_will_create) {4398 ret = 0;4399 /*4400 * First check if any of the current inodes refs did4401 * already create the dir.4402 */4403 list_for_each_entry(cur2, &sctx->new_refs, list) {4404 if (cur == cur2)4405 break;4406 if (cur2->dir == cur->dir) {4407 ret = 1;4408 break;4409 }4410 }4411 4412 /*4413 * If that did not happen, check if a previous inode4414 * did already create the dir.4415 */4416 if (!ret)4417 ret = did_create_dir(sctx, cur->dir);4418 if (ret < 0)4419 goto out;4420 if (!ret) {4421 ret = send_create_inode(sctx, cur->dir);4422 if (ret < 0)4423 goto out;4424 cache_dir_created(sctx, cur->dir);4425 }4426 }4427 4428 if (S_ISDIR(sctx->cur_inode_mode) && sctx->parent_root) {4429 ret = wait_for_dest_dir_move(sctx, cur, is_orphan);4430 if (ret < 0)4431 goto out;4432 if (ret == 1) {4433 can_rename = false;4434 *pending_move = 1;4435 }4436 }4437 4438 if (S_ISDIR(sctx->cur_inode_mode) && sctx->parent_root &&4439 can_rename) {4440 ret = wait_for_parent_move(sctx, cur, is_orphan);4441 if (ret < 0)4442 goto out;4443 if (ret == 1) {4444 can_rename = false;4445 *pending_move = 1;4446 }4447 }4448 4449 /*4450 * link/move the ref to the new place. If we have an orphan4451 * inode, move it and update valid_path. If not, link or move4452 * it depending on the inode mode.4453 */4454 if (is_orphan && can_rename) {4455 ret = send_rename(sctx, valid_path, cur->full_path);4456 if (ret < 0)4457 goto out;4458 is_orphan = 0;4459 ret = fs_path_copy(valid_path, cur->full_path);4460 if (ret < 0)4461 goto out;4462 } else if (can_rename) {4463 if (S_ISDIR(sctx->cur_inode_mode)) {4464 /*4465 * Dirs can't be linked, so move it. For moved4466 * dirs, we always have one new and one deleted4467 * ref. The deleted ref is ignored later.4468 */4469 ret = send_rename(sctx, valid_path,4470 cur->full_path);4471 if (!ret)4472 ret = fs_path_copy(valid_path,4473 cur->full_path);4474 if (ret < 0)4475 goto out;4476 } else {4477 /*4478 * We might have previously orphanized an inode4479 * which is an ancestor of our current inode,4480 * so our reference's full path, which was4481 * computed before any such orphanizations, must4482 * be updated.4483 */4484 if (orphanized_dir) {4485 ret = update_ref_path(sctx, cur);4486 if (ret < 0)4487 goto out;4488 }4489 ret = send_link(sctx, cur->full_path,4490 valid_path);4491 if (ret < 0)4492 goto out;4493 }4494 }4495 ret = dup_ref(cur, &check_dirs);4496 if (ret < 0)4497 goto out;4498 }4499 4500 if (S_ISDIR(sctx->cur_inode_mode) && sctx->cur_inode_deleted) {4501 /*4502 * Check if we can already rmdir the directory. If not,4503 * orphanize it. For every dir item inside that gets deleted4504 * later, we do this check again and rmdir it then if possible.4505 * See the use of check_dirs for more details.4506 */4507 ret = can_rmdir(sctx, sctx->cur_ino, sctx->cur_inode_gen);4508 if (ret < 0)4509 goto out;4510 if (ret) {4511 ret = send_rmdir(sctx, valid_path);4512 if (ret < 0)4513 goto out;4514 } else if (!is_orphan) {4515 ret = orphanize_inode(sctx, sctx->cur_ino,4516 sctx->cur_inode_gen, valid_path);4517 if (ret < 0)4518 goto out;4519 is_orphan = 1;4520 }4521 4522 list_for_each_entry(cur, &sctx->deleted_refs, list) {4523 ret = dup_ref(cur, &check_dirs);4524 if (ret < 0)4525 goto out;4526 }4527 } else if (S_ISDIR(sctx->cur_inode_mode) &&4528 !list_empty(&sctx->deleted_refs)) {4529 /*4530 * We have a moved dir. Add the old parent to check_dirs4531 */4532 cur = list_entry(sctx->deleted_refs.next, struct recorded_ref,4533 list);4534 ret = dup_ref(cur, &check_dirs);4535 if (ret < 0)4536 goto out;4537 } else if (!S_ISDIR(sctx->cur_inode_mode)) {4538 /*4539 * We have a non dir inode. Go through all deleted refs and4540 * unlink them if they were not already overwritten by other4541 * inodes.4542 */4543 list_for_each_entry(cur, &sctx->deleted_refs, list) {4544 ret = did_overwrite_ref(sctx, cur->dir, cur->dir_gen,4545 sctx->cur_ino, sctx->cur_inode_gen,4546 cur->name, cur->name_len);4547 if (ret < 0)4548 goto out;4549 if (!ret) {4550 /*4551 * If we orphanized any ancestor before, we need4552 * to recompute the full path for deleted names,4553 * since any such path was computed before we4554 * processed any references and orphanized any4555 * ancestor inode.4556 */4557 if (orphanized_ancestor) {4558 ret = update_ref_path(sctx, cur);4559 if (ret < 0)4560 goto out;4561 }4562 ret = send_unlink(sctx, cur->full_path);4563 if (ret < 0)4564 goto out;4565 }4566 ret = dup_ref(cur, &check_dirs);4567 if (ret < 0)4568 goto out;4569 }4570 /*4571 * If the inode is still orphan, unlink the orphan. This may4572 * happen when a previous inode did overwrite the first ref4573 * of this inode and no new refs were added for the current4574 * inode. Unlinking does not mean that the inode is deleted in4575 * all cases. There may still be links to this inode in other4576 * places.4577 */4578 if (is_orphan) {4579 ret = send_unlink(sctx, valid_path);4580 if (ret < 0)4581 goto out;4582 }4583 }4584 4585 /*4586 * We did collect all parent dirs where cur_inode was once located. We4587 * now go through all these dirs and check if they are pending for4588 * deletion and if it's finally possible to perform the rmdir now.4589 * We also update the inode stats of the parent dirs here.4590 */4591 list_for_each_entry(cur, &check_dirs, list) {4592 /*4593 * In case we had refs into dirs that were not processed yet,4594 * we don't need to do the utime and rmdir logic for these dirs.4595 * The dir will be processed later.4596 */4597 if (cur->dir > sctx->cur_ino)4598 continue;4599 4600 ret = get_cur_inode_state(sctx, cur->dir, cur->dir_gen, NULL, NULL);4601 if (ret < 0)4602 goto out;4603 4604 if (ret == inode_state_did_create ||4605 ret == inode_state_no_change) {4606 ret = cache_dir_utimes(sctx, cur->dir, cur->dir_gen);4607 if (ret < 0)4608 goto out;4609 } else if (ret == inode_state_did_delete &&4610 cur->dir != last_dir_ino_rm) {4611 ret = can_rmdir(sctx, cur->dir, cur->dir_gen);4612 if (ret < 0)4613 goto out;4614 if (ret) {4615 ret = get_cur_path(sctx, cur->dir,4616 cur->dir_gen, valid_path);4617 if (ret < 0)4618 goto out;4619 ret = send_rmdir(sctx, valid_path);4620 if (ret < 0)4621 goto out;4622 last_dir_ino_rm = cur->dir;4623 }4624 }4625 }4626 4627 ret = 0;4628 4629out:4630 __free_recorded_refs(&check_dirs);4631 free_recorded_refs(sctx);4632 fs_path_free(valid_path);4633 return ret;4634}4635 4636static int rbtree_ref_comp(const void *k, const struct rb_node *node)4637{4638 const struct recorded_ref *data = k;4639 const struct recorded_ref *ref = rb_entry(node, struct recorded_ref, node);4640 int result;4641 4642 if (data->dir > ref->dir)4643 return 1;4644 if (data->dir < ref->dir)4645 return -1;4646 if (data->dir_gen > ref->dir_gen)4647 return 1;4648 if (data->dir_gen < ref->dir_gen)4649 return -1;4650 if (data->name_len > ref->name_len)4651 return 1;4652 if (data->name_len < ref->name_len)4653 return -1;4654 result = strcmp(data->name, ref->name);4655 if (result > 0)4656 return 1;4657 if (result < 0)4658 return -1;4659 return 0;4660}4661 4662static bool rbtree_ref_less(struct rb_node *node, const struct rb_node *parent)4663{4664 const struct recorded_ref *entry = rb_entry(node, struct recorded_ref, node);4665 4666 return rbtree_ref_comp(entry, parent) < 0;4667}4668 4669static int record_ref_in_tree(struct rb_root *root, struct list_head *refs,4670 struct fs_path *name, u64 dir, u64 dir_gen,4671 struct send_ctx *sctx)4672{4673 int ret = 0;4674 struct fs_path *path = NULL;4675 struct recorded_ref *ref = NULL;4676 4677 path = fs_path_alloc();4678 if (!path) {4679 ret = -ENOMEM;4680 goto out;4681 }4682 4683 ref = recorded_ref_alloc();4684 if (!ref) {4685 ret = -ENOMEM;4686 goto out;4687 }4688 4689 ret = get_cur_path(sctx, dir, dir_gen, path);4690 if (ret < 0)4691 goto out;4692 ret = fs_path_add_path(path, name);4693 if (ret < 0)4694 goto out;4695 4696 ref->dir = dir;4697 ref->dir_gen = dir_gen;4698 set_ref_path(ref, path);4699 list_add_tail(&ref->list, refs);4700 rb_add(&ref->node, root, rbtree_ref_less);4701 ref->root = root;4702out:4703 if (ret) {4704 if (path && (!ref || !ref->full_path))4705 fs_path_free(path);4706 recorded_ref_free(ref);4707 }4708 return ret;4709}4710 4711static int record_new_ref_if_needed(int num, u64 dir, int index,4712 struct fs_path *name, void *ctx)4713{4714 int ret = 0;4715 struct send_ctx *sctx = ctx;4716 struct rb_node *node = NULL;4717 struct recorded_ref data;4718 struct recorded_ref *ref;4719 u64 dir_gen;4720 4721 ret = get_inode_gen(sctx->send_root, dir, &dir_gen);4722 if (ret < 0)4723 goto out;4724 4725 data.dir = dir;4726 data.dir_gen = dir_gen;4727 set_ref_path(&data, name);4728 node = rb_find(&data, &sctx->rbtree_deleted_refs, rbtree_ref_comp);4729 if (node) {4730 ref = rb_entry(node, struct recorded_ref, node);4731 recorded_ref_free(ref);4732 } else {4733 ret = record_ref_in_tree(&sctx->rbtree_new_refs,4734 &sctx->new_refs, name, dir, dir_gen,4735 sctx);4736 }4737out:4738 return ret;4739}4740 4741static int record_deleted_ref_if_needed(int num, u64 dir, int index,4742 struct fs_path *name, void *ctx)4743{4744 int ret = 0;4745 struct send_ctx *sctx = ctx;4746 struct rb_node *node = NULL;4747 struct recorded_ref data;4748 struct recorded_ref *ref;4749 u64 dir_gen;4750 4751 ret = get_inode_gen(sctx->parent_root, dir, &dir_gen);4752 if (ret < 0)4753 goto out;4754 4755 data.dir = dir;4756 data.dir_gen = dir_gen;4757 set_ref_path(&data, name);4758 node = rb_find(&data, &sctx->rbtree_new_refs, rbtree_ref_comp);4759 if (node) {4760 ref = rb_entry(node, struct recorded_ref, node);4761 recorded_ref_free(ref);4762 } else {4763 ret = record_ref_in_tree(&sctx->rbtree_deleted_refs,4764 &sctx->deleted_refs, name, dir,4765 dir_gen, sctx);4766 }4767out:4768 return ret;4769}4770 4771static int record_new_ref(struct send_ctx *sctx)4772{4773 int ret;4774 4775 ret = iterate_inode_ref(sctx->send_root, sctx->left_path,4776 sctx->cmp_key, 0, record_new_ref_if_needed, sctx);4777 if (ret < 0)4778 goto out;4779 ret = 0;4780 4781out:4782 return ret;4783}4784 4785static int record_deleted_ref(struct send_ctx *sctx)4786{4787 int ret;4788 4789 ret = iterate_inode_ref(sctx->parent_root, sctx->right_path,4790 sctx->cmp_key, 0, record_deleted_ref_if_needed,4791 sctx);4792 if (ret < 0)4793 goto out;4794 ret = 0;4795 4796out:4797 return ret;4798}4799 4800static int record_changed_ref(struct send_ctx *sctx)4801{4802 int ret = 0;4803 4804 ret = iterate_inode_ref(sctx->send_root, sctx->left_path,4805 sctx->cmp_key, 0, record_new_ref_if_needed, sctx);4806 if (ret < 0)4807 goto out;4808 ret = iterate_inode_ref(sctx->parent_root, sctx->right_path,4809 sctx->cmp_key, 0, record_deleted_ref_if_needed, sctx);4810 if (ret < 0)4811 goto out;4812 ret = 0;4813 4814out:4815 return ret;4816}4817 4818/*4819 * Record and process all refs at once. Needed when an inode changes the4820 * generation number, which means that it was deleted and recreated.4821 */4822static int process_all_refs(struct send_ctx *sctx,4823 enum btrfs_compare_tree_result cmd)4824{4825 int ret = 0;4826 int iter_ret = 0;4827 struct btrfs_root *root;4828 struct btrfs_path *path;4829 struct btrfs_key key;4830 struct btrfs_key found_key;4831 iterate_inode_ref_t cb;4832 int pending_move = 0;4833 4834 path = alloc_path_for_send();4835 if (!path)4836 return -ENOMEM;4837 4838 if (cmd == BTRFS_COMPARE_TREE_NEW) {4839 root = sctx->send_root;4840 cb = record_new_ref_if_needed;4841 } else if (cmd == BTRFS_COMPARE_TREE_DELETED) {4842 root = sctx->parent_root;4843 cb = record_deleted_ref_if_needed;4844 } else {4845 btrfs_err(sctx->send_root->fs_info,4846 "Wrong command %d in process_all_refs", cmd);4847 ret = -EINVAL;4848 goto out;4849 }4850 4851 key.objectid = sctx->cmp_key->objectid;4852 key.type = BTRFS_INODE_REF_KEY;4853 key.offset = 0;4854 btrfs_for_each_slot(root, &key, &found_key, path, iter_ret) {4855 if (found_key.objectid != key.objectid ||4856 (found_key.type != BTRFS_INODE_REF_KEY &&4857 found_key.type != BTRFS_INODE_EXTREF_KEY))4858 break;4859 4860 ret = iterate_inode_ref(root, path, &found_key, 0, cb, sctx);4861 if (ret < 0)4862 goto out;4863 }4864 /* Catch error found during iteration */4865 if (iter_ret < 0) {4866 ret = iter_ret;4867 goto out;4868 }4869 btrfs_release_path(path);4870 4871 /*4872 * We don't actually care about pending_move as we are simply4873 * re-creating this inode and will be rename'ing it into place once we4874 * rename the parent directory.4875 */4876 ret = process_recorded_refs(sctx, &pending_move);4877out:4878 btrfs_free_path(path);4879 return ret;4880}4881 4882static int send_set_xattr(struct send_ctx *sctx,4883 struct fs_path *path,4884 const char *name, int name_len,4885 const char *data, int data_len)4886{4887 int ret = 0;4888 4889 ret = begin_cmd(sctx, BTRFS_SEND_C_SET_XATTR);4890 if (ret < 0)4891 goto out;4892 4893 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);4894 TLV_PUT_STRING(sctx, BTRFS_SEND_A_XATTR_NAME, name, name_len);4895 TLV_PUT(sctx, BTRFS_SEND_A_XATTR_DATA, data, data_len);4896 4897 ret = send_cmd(sctx);4898 4899tlv_put_failure:4900out:4901 return ret;4902}4903 4904static int send_remove_xattr(struct send_ctx *sctx,4905 struct fs_path *path,4906 const char *name, int name_len)4907{4908 int ret = 0;4909 4910 ret = begin_cmd(sctx, BTRFS_SEND_C_REMOVE_XATTR);4911 if (ret < 0)4912 goto out;4913 4914 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);4915 TLV_PUT_STRING(sctx, BTRFS_SEND_A_XATTR_NAME, name, name_len);4916 4917 ret = send_cmd(sctx);4918 4919tlv_put_failure:4920out:4921 return ret;4922}4923 4924static int __process_new_xattr(int num, struct btrfs_key *di_key,4925 const char *name, int name_len, const char *data,4926 int data_len, void *ctx)4927{4928 int ret;4929 struct send_ctx *sctx = ctx;4930 struct fs_path *p;4931 struct posix_acl_xattr_header dummy_acl;4932 4933 /* Capabilities are emitted by finish_inode_if_needed */4934 if (!strncmp(name, XATTR_NAME_CAPS, name_len))4935 return 0;4936 4937 p = fs_path_alloc();4938 if (!p)4939 return -ENOMEM;4940 4941 /*4942 * This hack is needed because empty acls are stored as zero byte4943 * data in xattrs. Problem with that is, that receiving these zero byte4944 * acls will fail later. To fix this, we send a dummy acl list that4945 * only contains the version number and no entries.4946 */4947 if (!strncmp(name, XATTR_NAME_POSIX_ACL_ACCESS, name_len) ||4948 !strncmp(name, XATTR_NAME_POSIX_ACL_DEFAULT, name_len)) {4949 if (data_len == 0) {4950 dummy_acl.a_version =4951 cpu_to_le32(POSIX_ACL_XATTR_VERSION);4952 data = (char *)&dummy_acl;4953 data_len = sizeof(dummy_acl);4954 }4955 }4956 4957 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);4958 if (ret < 0)4959 goto out;4960 4961 ret = send_set_xattr(sctx, p, name, name_len, data, data_len);4962 4963out:4964 fs_path_free(p);4965 return ret;4966}4967 4968static int __process_deleted_xattr(int num, struct btrfs_key *di_key,4969 const char *name, int name_len,4970 const char *data, int data_len, void *ctx)4971{4972 int ret;4973 struct send_ctx *sctx = ctx;4974 struct fs_path *p;4975 4976 p = fs_path_alloc();4977 if (!p)4978 return -ENOMEM;4979 4980 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);4981 if (ret < 0)4982 goto out;4983 4984 ret = send_remove_xattr(sctx, p, name, name_len);4985 4986out:4987 fs_path_free(p);4988 return ret;4989}4990 4991static int process_new_xattr(struct send_ctx *sctx)4992{4993 int ret = 0;4994 4995 ret = iterate_dir_item(sctx->send_root, sctx->left_path,4996 __process_new_xattr, sctx);4997 4998 return ret;4999}5000 5001static int process_deleted_xattr(struct send_ctx *sctx)5002{5003 return iterate_dir_item(sctx->parent_root, sctx->right_path,5004 __process_deleted_xattr, sctx);5005}5006 5007struct find_xattr_ctx {5008 const char *name;5009 int name_len;5010 int found_idx;5011 char *found_data;5012 int found_data_len;5013};5014 5015static int __find_xattr(int num, struct btrfs_key *di_key, const char *name,5016 int name_len, const char *data, int data_len, void *vctx)5017{5018 struct find_xattr_ctx *ctx = vctx;5019 5020 if (name_len == ctx->name_len &&5021 strncmp(name, ctx->name, name_len) == 0) {5022 ctx->found_idx = num;5023 ctx->found_data_len = data_len;5024 ctx->found_data = kmemdup(data, data_len, GFP_KERNEL);5025 if (!ctx->found_data)5026 return -ENOMEM;5027 return 1;5028 }5029 return 0;5030}5031 5032static int find_xattr(struct btrfs_root *root,5033 struct btrfs_path *path,5034 struct btrfs_key *key,5035 const char *name, int name_len,5036 char **data, int *data_len)5037{5038 int ret;5039 struct find_xattr_ctx ctx;5040 5041 ctx.name = name;5042 ctx.name_len = name_len;5043 ctx.found_idx = -1;5044 ctx.found_data = NULL;5045 ctx.found_data_len = 0;5046 5047 ret = iterate_dir_item(root, path, __find_xattr, &ctx);5048 if (ret < 0)5049 return ret;5050 5051 if (ctx.found_idx == -1)5052 return -ENOENT;5053 if (data) {5054 *data = ctx.found_data;5055 *data_len = ctx.found_data_len;5056 } else {5057 kfree(ctx.found_data);5058 }5059 return ctx.found_idx;5060}5061 5062 5063static int __process_changed_new_xattr(int num, struct btrfs_key *di_key,5064 const char *name, int name_len,5065 const char *data, int data_len,5066 void *ctx)5067{5068 int ret;5069 struct send_ctx *sctx = ctx;5070 char *found_data = NULL;5071 int found_data_len = 0;5072 5073 ret = find_xattr(sctx->parent_root, sctx->right_path,5074 sctx->cmp_key, name, name_len, &found_data,5075 &found_data_len);5076 if (ret == -ENOENT) {5077 ret = __process_new_xattr(num, di_key, name, name_len, data,5078 data_len, ctx);5079 } else if (ret >= 0) {5080 if (data_len != found_data_len ||5081 memcmp(data, found_data, data_len)) {5082 ret = __process_new_xattr(num, di_key, name, name_len,5083 data, data_len, ctx);5084 } else {5085 ret = 0;5086 }5087 }5088 5089 kfree(found_data);5090 return ret;5091}5092 5093static int __process_changed_deleted_xattr(int num, struct btrfs_key *di_key,5094 const char *name, int name_len,5095 const char *data, int data_len,5096 void *ctx)5097{5098 int ret;5099 struct send_ctx *sctx = ctx;5100 5101 ret = find_xattr(sctx->send_root, sctx->left_path, sctx->cmp_key,5102 name, name_len, NULL, NULL);5103 if (ret == -ENOENT)5104 ret = __process_deleted_xattr(num, di_key, name, name_len, data,5105 data_len, ctx);5106 else if (ret >= 0)5107 ret = 0;5108 5109 return ret;5110}5111 5112static int process_changed_xattr(struct send_ctx *sctx)5113{5114 int ret = 0;5115 5116 ret = iterate_dir_item(sctx->send_root, sctx->left_path,5117 __process_changed_new_xattr, sctx);5118 if (ret < 0)5119 goto out;5120 ret = iterate_dir_item(sctx->parent_root, sctx->right_path,5121 __process_changed_deleted_xattr, sctx);5122 5123out:5124 return ret;5125}5126 5127static int process_all_new_xattrs(struct send_ctx *sctx)5128{5129 int ret = 0;5130 int iter_ret = 0;5131 struct btrfs_root *root;5132 struct btrfs_path *path;5133 struct btrfs_key key;5134 struct btrfs_key found_key;5135 5136 path = alloc_path_for_send();5137 if (!path)5138 return -ENOMEM;5139 5140 root = sctx->send_root;5141 5142 key.objectid = sctx->cmp_key->objectid;5143 key.type = BTRFS_XATTR_ITEM_KEY;5144 key.offset = 0;5145 btrfs_for_each_slot(root, &key, &found_key, path, iter_ret) {5146 if (found_key.objectid != key.objectid ||5147 found_key.type != key.type) {5148 ret = 0;5149 break;5150 }5151 5152 ret = iterate_dir_item(root, path, __process_new_xattr, sctx);5153 if (ret < 0)5154 break;5155 }5156 /* Catch error found during iteration */5157 if (iter_ret < 0)5158 ret = iter_ret;5159 5160 btrfs_free_path(path);5161 return ret;5162}5163 5164static int send_verity(struct send_ctx *sctx, struct fs_path *path,5165 struct fsverity_descriptor *desc)5166{5167 int ret;5168 5169 ret = begin_cmd(sctx, BTRFS_SEND_C_ENABLE_VERITY);5170 if (ret < 0)5171 goto out;5172 5173 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path);5174 TLV_PUT_U8(sctx, BTRFS_SEND_A_VERITY_ALGORITHM,5175 le8_to_cpu(desc->hash_algorithm));5176 TLV_PUT_U32(sctx, BTRFS_SEND_A_VERITY_BLOCK_SIZE,5177 1U << le8_to_cpu(desc->log_blocksize));5178 TLV_PUT(sctx, BTRFS_SEND_A_VERITY_SALT_DATA, desc->salt,5179 le8_to_cpu(desc->salt_size));5180 TLV_PUT(sctx, BTRFS_SEND_A_VERITY_SIG_DATA, desc->signature,5181 le32_to_cpu(desc->sig_size));5182 5183 ret = send_cmd(sctx);5184 5185tlv_put_failure:5186out:5187 return ret;5188}5189 5190static int process_verity(struct send_ctx *sctx)5191{5192 int ret = 0;5193 struct inode *inode;5194 struct fs_path *p;5195 5196 inode = btrfs_iget(sctx->cur_ino, sctx->send_root);5197 if (IS_ERR(inode))5198 return PTR_ERR(inode);5199 5200 ret = btrfs_get_verity_descriptor(inode, NULL, 0);5201 if (ret < 0)5202 goto iput;5203 5204 if (ret > FS_VERITY_MAX_DESCRIPTOR_SIZE) {5205 ret = -EMSGSIZE;5206 goto iput;5207 }5208 if (!sctx->verity_descriptor) {5209 sctx->verity_descriptor = kvmalloc(FS_VERITY_MAX_DESCRIPTOR_SIZE,5210 GFP_KERNEL);5211 if (!sctx->verity_descriptor) {5212 ret = -ENOMEM;5213 goto iput;5214 }5215 }5216 5217 ret = btrfs_get_verity_descriptor(inode, sctx->verity_descriptor, ret);5218 if (ret < 0)5219 goto iput;5220 5221 p = fs_path_alloc();5222 if (!p) {5223 ret = -ENOMEM;5224 goto iput;5225 }5226 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);5227 if (ret < 0)5228 goto free_path;5229 5230 ret = send_verity(sctx, p, sctx->verity_descriptor);5231 if (ret < 0)5232 goto free_path;5233 5234free_path:5235 fs_path_free(p);5236iput:5237 iput(inode);5238 return ret;5239}5240 5241static inline u64 max_send_read_size(const struct send_ctx *sctx)5242{5243 return sctx->send_max_size - SZ_16K;5244}5245 5246static int put_data_header(struct send_ctx *sctx, u32 len)5247{5248 if (WARN_ON_ONCE(sctx->put_data))5249 return -EINVAL;5250 sctx->put_data = true;5251 if (sctx->proto >= 2) {5252 /*5253 * Since v2, the data attribute header doesn't include a length,5254 * it is implicitly to the end of the command.5255 */5256 if (sctx->send_max_size - sctx->send_size < sizeof(__le16) + len)5257 return -EOVERFLOW;5258 put_unaligned_le16(BTRFS_SEND_A_DATA, sctx->send_buf + sctx->send_size);5259 sctx->send_size += sizeof(__le16);5260 } else {5261 struct btrfs_tlv_header *hdr;5262 5263 if (sctx->send_max_size - sctx->send_size < sizeof(*hdr) + len)5264 return -EOVERFLOW;5265 hdr = (struct btrfs_tlv_header *)(sctx->send_buf + sctx->send_size);5266 put_unaligned_le16(BTRFS_SEND_A_DATA, &hdr->tlv_type);5267 put_unaligned_le16(len, &hdr->tlv_len);5268 sctx->send_size += sizeof(*hdr);5269 }5270 return 0;5271}5272 5273static int put_file_data(struct send_ctx *sctx, u64 offset, u32 len)5274{5275 struct btrfs_root *root = sctx->send_root;5276 struct btrfs_fs_info *fs_info = root->fs_info;5277 struct folio *folio;5278 pgoff_t index = offset >> PAGE_SHIFT;5279 pgoff_t last_index;5280 unsigned pg_offset = offset_in_page(offset);5281 struct address_space *mapping = sctx->cur_inode->i_mapping;5282 int ret;5283 5284 ret = put_data_header(sctx, len);5285 if (ret)5286 return ret;5287 5288 last_index = (offset + len - 1) >> PAGE_SHIFT;5289 5290 while (index <= last_index) {5291 unsigned cur_len = min_t(unsigned, len,5292 PAGE_SIZE - pg_offset);5293 5294 folio = filemap_lock_folio(mapping, index);5295 if (IS_ERR(folio)) {5296 page_cache_sync_readahead(mapping,5297 &sctx->ra, NULL, index,5298 last_index + 1 - index);5299 5300 folio = filemap_grab_folio(mapping, index);5301 if (IS_ERR(folio)) {5302 ret = PTR_ERR(folio);5303 break;5304 }5305 }5306 5307 WARN_ON(folio_order(folio));5308 5309 if (folio_test_readahead(folio))5310 page_cache_async_readahead(mapping, &sctx->ra, NULL, folio,5311 last_index + 1 - index);5312 5313 if (!folio_test_uptodate(folio)) {5314 btrfs_read_folio(NULL, folio);5315 folio_lock(folio);5316 if (!folio_test_uptodate(folio)) {5317 folio_unlock(folio);5318 btrfs_err(fs_info,5319 "send: IO error at offset %llu for inode %llu root %llu",5320 folio_pos(folio), sctx->cur_ino,5321 btrfs_root_id(sctx->send_root));5322 folio_put(folio);5323 ret = -EIO;5324 break;5325 }5326 }5327 5328 memcpy_from_folio(sctx->send_buf + sctx->send_size, folio,5329 pg_offset, cur_len);5330 folio_unlock(folio);5331 folio_put(folio);5332 index++;5333 pg_offset = 0;5334 len -= cur_len;5335 sctx->send_size += cur_len;5336 }5337 5338 return ret;5339}5340 5341/*5342 * Read some bytes from the current inode/file and send a write command to5343 * user space.5344 */5345static int send_write(struct send_ctx *sctx, u64 offset, u32 len)5346{5347 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info;5348 int ret = 0;5349 struct fs_path *p;5350 5351 p = fs_path_alloc();5352 if (!p)5353 return -ENOMEM;5354 5355 btrfs_debug(fs_info, "send_write offset=%llu, len=%d", offset, len);5356 5357 ret = begin_cmd(sctx, BTRFS_SEND_C_WRITE);5358 if (ret < 0)5359 goto out;5360 5361 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);5362 if (ret < 0)5363 goto out;5364 5365 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);5366 TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset);5367 ret = put_file_data(sctx, offset, len);5368 if (ret < 0)5369 goto out;5370 5371 ret = send_cmd(sctx);5372 5373tlv_put_failure:5374out:5375 fs_path_free(p);5376 return ret;5377}5378 5379/*5380 * Send a clone command to user space.5381 */5382static int send_clone(struct send_ctx *sctx,5383 u64 offset, u32 len,5384 struct clone_root *clone_root)5385{5386 int ret = 0;5387 struct fs_path *p;5388 u64 gen;5389 5390 btrfs_debug(sctx->send_root->fs_info,5391 "send_clone offset=%llu, len=%d, clone_root=%llu, clone_inode=%llu, clone_offset=%llu",5392 offset, len, btrfs_root_id(clone_root->root),5393 clone_root->ino, clone_root->offset);5394 5395 p = fs_path_alloc();5396 if (!p)5397 return -ENOMEM;5398 5399 ret = begin_cmd(sctx, BTRFS_SEND_C_CLONE);5400 if (ret < 0)5401 goto out;5402 5403 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);5404 if (ret < 0)5405 goto out;5406 5407 TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset);5408 TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_LEN, len);5409 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);5410 5411 if (clone_root->root == sctx->send_root) {5412 ret = get_inode_gen(sctx->send_root, clone_root->ino, &gen);5413 if (ret < 0)5414 goto out;5415 ret = get_cur_path(sctx, clone_root->ino, gen, p);5416 } else {5417 ret = get_inode_path(clone_root->root, clone_root->ino, p);5418 }5419 if (ret < 0)5420 goto out;5421 5422 /*5423 * If the parent we're using has a received_uuid set then use that as5424 * our clone source as that is what we will look for when doing a5425 * receive.5426 *5427 * This covers the case that we create a snapshot off of a received5428 * subvolume and then use that as the parent and try to receive on a5429 * different host.5430 */5431 if (!btrfs_is_empty_uuid(clone_root->root->root_item.received_uuid))5432 TLV_PUT_UUID(sctx, BTRFS_SEND_A_CLONE_UUID,5433 clone_root->root->root_item.received_uuid);5434 else5435 TLV_PUT_UUID(sctx, BTRFS_SEND_A_CLONE_UUID,5436 clone_root->root->root_item.uuid);5437 TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_CTRANSID,5438 btrfs_root_ctransid(&clone_root->root->root_item));5439 TLV_PUT_PATH(sctx, BTRFS_SEND_A_CLONE_PATH, p);5440 TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_OFFSET,5441 clone_root->offset);5442 5443 ret = send_cmd(sctx);5444 5445tlv_put_failure:5446out:5447 fs_path_free(p);5448 return ret;5449}5450 5451/*5452 * Send an update extent command to user space.5453 */5454static int send_update_extent(struct send_ctx *sctx,5455 u64 offset, u32 len)5456{5457 int ret = 0;5458 struct fs_path *p;5459 5460 p = fs_path_alloc();5461 if (!p)5462 return -ENOMEM;5463 5464 ret = begin_cmd(sctx, BTRFS_SEND_C_UPDATE_EXTENT);5465 if (ret < 0)5466 goto out;5467 5468 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);5469 if (ret < 0)5470 goto out;5471 5472 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);5473 TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset);5474 TLV_PUT_U64(sctx, BTRFS_SEND_A_SIZE, len);5475 5476 ret = send_cmd(sctx);5477 5478tlv_put_failure:5479out:5480 fs_path_free(p);5481 return ret;5482}5483 5484static int send_hole(struct send_ctx *sctx, u64 end)5485{5486 struct fs_path *p = NULL;5487 u64 read_size = max_send_read_size(sctx);5488 u64 offset = sctx->cur_inode_last_extent;5489 int ret = 0;5490 5491 /*5492 * A hole that starts at EOF or beyond it. Since we do not yet support5493 * fallocate (for extent preallocation and hole punching), sending a5494 * write of zeroes starting at EOF or beyond would later require issuing5495 * a truncate operation which would undo the write and achieve nothing.5496 */5497 if (offset >= sctx->cur_inode_size)5498 return 0;5499 5500 /*5501 * Don't go beyond the inode's i_size due to prealloc extents that start5502 * after the i_size.5503 */5504 end = min_t(u64, end, sctx->cur_inode_size);5505 5506 if (sctx->flags & BTRFS_SEND_FLAG_NO_FILE_DATA)5507 return send_update_extent(sctx, offset, end - offset);5508 5509 p = fs_path_alloc();5510 if (!p)5511 return -ENOMEM;5512 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p);5513 if (ret < 0)5514 goto tlv_put_failure;5515 while (offset < end) {5516 u64 len = min(end - offset, read_size);5517 5518 ret = begin_cmd(sctx, BTRFS_SEND_C_WRITE);5519 if (ret < 0)5520 break;5521 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p);5522 TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset);5523 ret = put_data_header(sctx, len);5524 if (ret < 0)5525 break;5526 memset(sctx->send_buf + sctx->send_size, 0, len);5527 sctx->send_size += len;5528 ret = send_cmd(sctx);5529 if (ret < 0)5530 break;5531 offset += len;5532 }5533 sctx->cur_inode_next_write_offset = offset;5534tlv_put_failure:5535 fs_path_free(p);5536 return ret;5537}5538 5539static int send_encoded_inline_extent(struct send_ctx *sctx,5540 struct btrfs_path *path, u64 offset,5541 u64 len)5542{5543 struct btrfs_root *root = sctx->send_root;5544 struct btrfs_fs_info *fs_info = root->fs_info;5545 struct inode *inode;5546 struct fs_path *fspath;5547 struct extent_buffer *leaf = path->nodes[0];5548 struct btrfs_key key;5549 struct btrfs_file_extent_item *ei;5550 u64 ram_bytes;5551 size_t inline_size;5552 int ret;5553 5554 inode = btrfs_iget(sctx->cur_ino, root);5555 if (IS_ERR(inode))5556 return PTR_ERR(inode);5557 5558 fspath = fs_path_alloc();5559 if (!fspath) {5560 ret = -ENOMEM;5561 goto out;5562 }5563 5564 ret = begin_cmd(sctx, BTRFS_SEND_C_ENCODED_WRITE);5565 if (ret < 0)5566 goto out;5567 5568 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, fspath);5569 if (ret < 0)5570 goto out;5571 5572 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);5573 ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_file_extent_item);5574 ram_bytes = btrfs_file_extent_ram_bytes(leaf, ei);5575 inline_size = btrfs_file_extent_inline_item_len(leaf, path->slots[0]);5576 5577 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, fspath);5578 TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset);5579 TLV_PUT_U64(sctx, BTRFS_SEND_A_UNENCODED_FILE_LEN,5580 min(key.offset + ram_bytes - offset, len));5581 TLV_PUT_U64(sctx, BTRFS_SEND_A_UNENCODED_LEN, ram_bytes);5582 TLV_PUT_U64(sctx, BTRFS_SEND_A_UNENCODED_OFFSET, offset - key.offset);5583 ret = btrfs_encoded_io_compression_from_extent(fs_info,5584 btrfs_file_extent_compression(leaf, ei));5585 if (ret < 0)5586 goto out;5587 TLV_PUT_U32(sctx, BTRFS_SEND_A_COMPRESSION, ret);5588 5589 ret = put_data_header(sctx, inline_size);5590 if (ret < 0)5591 goto out;5592 read_extent_buffer(leaf, sctx->send_buf + sctx->send_size,5593 btrfs_file_extent_inline_start(ei), inline_size);5594 sctx->send_size += inline_size;5595 5596 ret = send_cmd(sctx);5597 5598tlv_put_failure:5599out:5600 fs_path_free(fspath);5601 iput(inode);5602 return ret;5603}5604 5605static int send_encoded_extent(struct send_ctx *sctx, struct btrfs_path *path,5606 u64 offset, u64 len)5607{5608 struct btrfs_root *root = sctx->send_root;5609 struct btrfs_fs_info *fs_info = root->fs_info;5610 struct inode *inode;5611 struct fs_path *fspath;5612 struct extent_buffer *leaf = path->nodes[0];5613 struct btrfs_key key;5614 struct btrfs_file_extent_item *ei;5615 u64 disk_bytenr, disk_num_bytes;5616 u32 data_offset;5617 struct btrfs_cmd_header *hdr;5618 u32 crc;5619 int ret;5620 5621 inode = btrfs_iget(sctx->cur_ino, root);5622 if (IS_ERR(inode))5623 return PTR_ERR(inode);5624 5625 fspath = fs_path_alloc();5626 if (!fspath) {5627 ret = -ENOMEM;5628 goto out;5629 }5630 5631 ret = begin_cmd(sctx, BTRFS_SEND_C_ENCODED_WRITE);5632 if (ret < 0)5633 goto out;5634 5635 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, fspath);5636 if (ret < 0)5637 goto out;5638 5639 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);5640 ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_file_extent_item);5641 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, ei);5642 disk_num_bytes = btrfs_file_extent_disk_num_bytes(leaf, ei);5643 5644 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, fspath);5645 TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset);5646 TLV_PUT_U64(sctx, BTRFS_SEND_A_UNENCODED_FILE_LEN,5647 min(key.offset + btrfs_file_extent_num_bytes(leaf, ei) - offset,5648 len));5649 TLV_PUT_U64(sctx, BTRFS_SEND_A_UNENCODED_LEN,5650 btrfs_file_extent_ram_bytes(leaf, ei));5651 TLV_PUT_U64(sctx, BTRFS_SEND_A_UNENCODED_OFFSET,5652 offset - key.offset + btrfs_file_extent_offset(leaf, ei));5653 ret = btrfs_encoded_io_compression_from_extent(fs_info,5654 btrfs_file_extent_compression(leaf, ei));5655 if (ret < 0)5656 goto out;5657 TLV_PUT_U32(sctx, BTRFS_SEND_A_COMPRESSION, ret);5658 TLV_PUT_U32(sctx, BTRFS_SEND_A_ENCRYPTION, 0);5659 5660 ret = put_data_header(sctx, disk_num_bytes);5661 if (ret < 0)5662 goto out;5663 5664 /*5665 * We want to do I/O directly into the send buffer, so get the next page5666 * boundary in the send buffer. This means that there may be a gap5667 * between the beginning of the command and the file data.5668 */5669 data_offset = PAGE_ALIGN(sctx->send_size);5670 if (data_offset > sctx->send_max_size ||5671 sctx->send_max_size - data_offset < disk_num_bytes) {5672 ret = -EOVERFLOW;5673 goto out;5674 }5675 5676 /*5677 * Note that send_buf is a mapping of send_buf_pages, so this is really5678 * reading into send_buf.5679 */5680 ret = btrfs_encoded_read_regular_fill_pages(BTRFS_I(inode), offset,5681 disk_bytenr, disk_num_bytes,5682 sctx->send_buf_pages +5683 (data_offset >> PAGE_SHIFT));5684 if (ret)5685 goto out;5686 5687 hdr = (struct btrfs_cmd_header *)sctx->send_buf;5688 hdr->len = cpu_to_le32(sctx->send_size + disk_num_bytes - sizeof(*hdr));5689 hdr->crc = 0;5690 crc = crc32c(0, sctx->send_buf, sctx->send_size);5691 crc = crc32c(crc, sctx->send_buf + data_offset, disk_num_bytes);5692 hdr->crc = cpu_to_le32(crc);5693 5694 ret = write_buf(sctx->send_filp, sctx->send_buf, sctx->send_size,5695 &sctx->send_off);5696 if (!ret) {5697 ret = write_buf(sctx->send_filp, sctx->send_buf + data_offset,5698 disk_num_bytes, &sctx->send_off);5699 }5700 sctx->send_size = 0;5701 sctx->put_data = false;5702 5703tlv_put_failure:5704out:5705 fs_path_free(fspath);5706 iput(inode);5707 return ret;5708}5709 5710static int send_extent_data(struct send_ctx *sctx, struct btrfs_path *path,5711 const u64 offset, const u64 len)5712{5713 const u64 end = offset + len;5714 struct extent_buffer *leaf = path->nodes[0];5715 struct btrfs_file_extent_item *ei;5716 u64 read_size = max_send_read_size(sctx);5717 u64 sent = 0;5718 5719 if (sctx->flags & BTRFS_SEND_FLAG_NO_FILE_DATA)5720 return send_update_extent(sctx, offset, len);5721 5722 ei = btrfs_item_ptr(leaf, path->slots[0],5723 struct btrfs_file_extent_item);5724 if ((sctx->flags & BTRFS_SEND_FLAG_COMPRESSED) &&5725 btrfs_file_extent_compression(leaf, ei) != BTRFS_COMPRESS_NONE) {5726 bool is_inline = (btrfs_file_extent_type(leaf, ei) ==5727 BTRFS_FILE_EXTENT_INLINE);5728 5729 /*5730 * Send the compressed extent unless the compressed data is5731 * larger than the decompressed data. This can happen if we're5732 * not sending the entire extent, either because it has been5733 * partially overwritten/truncated or because this is a part of5734 * the extent that we couldn't clone in clone_range().5735 */5736 if (is_inline &&5737 btrfs_file_extent_inline_item_len(leaf,5738 path->slots[0]) <= len) {5739 return send_encoded_inline_extent(sctx, path, offset,5740 len);5741 } else if (!is_inline &&5742 btrfs_file_extent_disk_num_bytes(leaf, ei) <= len) {5743 return send_encoded_extent(sctx, path, offset, len);5744 }5745 }5746 5747 if (sctx->cur_inode == NULL) {5748 struct btrfs_root *root = sctx->send_root;5749 5750 sctx->cur_inode = btrfs_iget(sctx->cur_ino, root);5751 if (IS_ERR(sctx->cur_inode)) {5752 int err = PTR_ERR(sctx->cur_inode);5753 5754 sctx->cur_inode = NULL;5755 return err;5756 }5757 memset(&sctx->ra, 0, sizeof(struct file_ra_state));5758 file_ra_state_init(&sctx->ra, sctx->cur_inode->i_mapping);5759 5760 /*5761 * It's very likely there are no pages from this inode in the page5762 * cache, so after reading extents and sending their data, we clean5763 * the page cache to avoid trashing the page cache (adding pressure5764 * to the page cache and forcing eviction of other data more useful5765 * for applications).5766 *5767 * We decide if we should clean the page cache simply by checking5768 * if the inode's mapping nrpages is 0 when we first open it, and5769 * not by using something like filemap_range_has_page() before5770 * reading an extent because when we ask the readahead code to5771 * read a given file range, it may (and almost always does) read5772 * pages from beyond that range (see the documentation for5773 * page_cache_sync_readahead()), so it would not be reliable,5774 * because after reading the first extent future calls to5775 * filemap_range_has_page() would return true because the readahead5776 * on the previous extent resulted in reading pages of the current5777 * extent as well.5778 */5779 sctx->clean_page_cache = (sctx->cur_inode->i_mapping->nrpages == 0);5780 sctx->page_cache_clear_start = round_down(offset, PAGE_SIZE);5781 }5782 5783 while (sent < len) {5784 u64 size = min(len - sent, read_size);5785 int ret;5786 5787 ret = send_write(sctx, offset + sent, size);5788 if (ret < 0)5789 return ret;5790 sent += size;5791 }5792 5793 if (sctx->clean_page_cache && PAGE_ALIGNED(end)) {5794 /*5795 * Always operate only on ranges that are a multiple of the page5796 * size. This is not only to prevent zeroing parts of a page in5797 * the case of subpage sector size, but also to guarantee we evict5798 * pages, as passing a range that is smaller than page size does5799 * not evict the respective page (only zeroes part of its content).5800 *5801 * Always start from the end offset of the last range cleared.5802 * This is because the readahead code may (and very often does)5803 * reads pages beyond the range we request for readahead. So if5804 * we have an extent layout like this:5805 *5806 * [ extent A ] [ extent B ] [ extent C ]5807 *5808 * When we ask page_cache_sync_readahead() to read extent A, it5809 * may also trigger reads for pages of extent B. If we are doing5810 * an incremental send and extent B has not changed between the5811 * parent and send snapshots, some or all of its pages may end5812 * up being read and placed in the page cache. So when truncating5813 * the page cache we always start from the end offset of the5814 * previously processed extent up to the end of the current5815 * extent.5816 */5817 truncate_inode_pages_range(&sctx->cur_inode->i_data,5818 sctx->page_cache_clear_start,5819 end - 1);5820 sctx->page_cache_clear_start = end;5821 }5822 5823 return 0;5824}5825 5826/*5827 * Search for a capability xattr related to sctx->cur_ino. If the capability is5828 * found, call send_set_xattr function to emit it.5829 *5830 * Return 0 if there isn't a capability, or when the capability was emitted5831 * successfully, or < 0 if an error occurred.5832 */5833static int send_capabilities(struct send_ctx *sctx)5834{5835 struct fs_path *fspath = NULL;5836 struct btrfs_path *path;5837 struct btrfs_dir_item *di;5838 struct extent_buffer *leaf;5839 unsigned long data_ptr;5840 char *buf = NULL;5841 int buf_len;5842 int ret = 0;5843 5844 path = alloc_path_for_send();5845 if (!path)5846 return -ENOMEM;5847 5848 di = btrfs_lookup_xattr(NULL, sctx->send_root, path, sctx->cur_ino,5849 XATTR_NAME_CAPS, strlen(XATTR_NAME_CAPS), 0);5850 if (!di) {5851 /* There is no xattr for this inode */5852 goto out;5853 } else if (IS_ERR(di)) {5854 ret = PTR_ERR(di);5855 goto out;5856 }5857 5858 leaf = path->nodes[0];5859 buf_len = btrfs_dir_data_len(leaf, di);5860 5861 fspath = fs_path_alloc();5862 buf = kmalloc(buf_len, GFP_KERNEL);5863 if (!fspath || !buf) {5864 ret = -ENOMEM;5865 goto out;5866 }5867 5868 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, fspath);5869 if (ret < 0)5870 goto out;5871 5872 data_ptr = (unsigned long)(di + 1) + btrfs_dir_name_len(leaf, di);5873 read_extent_buffer(leaf, buf, data_ptr, buf_len);5874 5875 ret = send_set_xattr(sctx, fspath, XATTR_NAME_CAPS,5876 strlen(XATTR_NAME_CAPS), buf, buf_len);5877out:5878 kfree(buf);5879 fs_path_free(fspath);5880 btrfs_free_path(path);5881 return ret;5882}5883 5884static int clone_range(struct send_ctx *sctx, struct btrfs_path *dst_path,5885 struct clone_root *clone_root, const u64 disk_byte,5886 u64 data_offset, u64 offset, u64 len)5887{5888 struct btrfs_path *path;5889 struct btrfs_key key;5890 int ret;5891 struct btrfs_inode_info info;5892 u64 clone_src_i_size = 0;5893 5894 /*5895 * Prevent cloning from a zero offset with a length matching the sector5896 * size because in some scenarios this will make the receiver fail.5897 *5898 * For example, if in the source filesystem the extent at offset 05899 * has a length of sectorsize and it was written using direct IO, then5900 * it can never be an inline extent (even if compression is enabled).5901 * Then this extent can be cloned in the original filesystem to a non5902 * zero file offset, but it may not be possible to clone in the5903 * destination filesystem because it can be inlined due to compression5904 * on the destination filesystem (as the receiver's write operations are5905 * always done using buffered IO). The same happens when the original5906 * filesystem does not have compression enabled but the destination5907 * filesystem has.5908 */5909 if (clone_root->offset == 0 &&5910 len == sctx->send_root->fs_info->sectorsize)5911 return send_extent_data(sctx, dst_path, offset, len);5912 5913 path = alloc_path_for_send();5914 if (!path)5915 return -ENOMEM;5916 5917 /*5918 * There are inodes that have extents that lie behind its i_size. Don't5919 * accept clones from these extents.5920 */5921 ret = get_inode_info(clone_root->root, clone_root->ino, &info);5922 btrfs_release_path(path);5923 if (ret < 0)5924 goto out;5925 clone_src_i_size = info.size;5926 5927 /*5928 * We can't send a clone operation for the entire range if we find5929 * extent items in the respective range in the source file that5930 * refer to different extents or if we find holes.5931 * So check for that and do a mix of clone and regular write/copy5932 * operations if needed.5933 *5934 * Example:5935 *5936 * mkfs.btrfs -f /dev/sda5937 * mount /dev/sda /mnt5938 * xfs_io -f -c "pwrite -S 0xaa 0K 100K" /mnt/foo5939 * cp --reflink=always /mnt/foo /mnt/bar5940 * xfs_io -c "pwrite -S 0xbb 50K 50K" /mnt/foo5941 * btrfs subvolume snapshot -r /mnt /mnt/snap5942 *5943 * If when we send the snapshot and we are processing file bar (which5944 * has a higher inode number than foo) we blindly send a clone operation5945 * for the [0, 100K[ range from foo to bar, the receiver ends up getting5946 * a file bar that matches the content of file foo - iow, doesn't match5947 * the content from bar in the original filesystem.5948 */5949 key.objectid = clone_root->ino;5950 key.type = BTRFS_EXTENT_DATA_KEY;5951 key.offset = clone_root->offset;5952 ret = btrfs_search_slot(NULL, clone_root->root, &key, path, 0, 0);5953 if (ret < 0)5954 goto out;5955 if (ret > 0 && path->slots[0] > 0) {5956 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0] - 1);5957 if (key.objectid == clone_root->ino &&5958 key.type == BTRFS_EXTENT_DATA_KEY)5959 path->slots[0]--;5960 }5961 5962 while (true) {5963 struct extent_buffer *leaf = path->nodes[0];5964 int slot = path->slots[0];5965 struct btrfs_file_extent_item *ei;5966 u8 type;5967 u64 ext_len;5968 u64 clone_len;5969 u64 clone_data_offset;5970 bool crossed_src_i_size = false;5971 5972 if (slot >= btrfs_header_nritems(leaf)) {5973 ret = btrfs_next_leaf(clone_root->root, path);5974 if (ret < 0)5975 goto out;5976 else if (ret > 0)5977 break;5978 continue;5979 }5980 5981 btrfs_item_key_to_cpu(leaf, &key, slot);5982 5983 /*5984 * We might have an implicit trailing hole (NO_HOLES feature5985 * enabled). We deal with it after leaving this loop.5986 */5987 if (key.objectid != clone_root->ino ||5988 key.type != BTRFS_EXTENT_DATA_KEY)5989 break;5990 5991 ei = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);5992 type = btrfs_file_extent_type(leaf, ei);5993 if (type == BTRFS_FILE_EXTENT_INLINE) {5994 ext_len = btrfs_file_extent_ram_bytes(leaf, ei);5995 ext_len = PAGE_ALIGN(ext_len);5996 } else {5997 ext_len = btrfs_file_extent_num_bytes(leaf, ei);5998 }5999 6000 if (key.offset + ext_len <= clone_root->offset)6001 goto next;6002 6003 if (key.offset > clone_root->offset) {6004 /* Implicit hole, NO_HOLES feature enabled. */6005 u64 hole_len = key.offset - clone_root->offset;6006 6007 if (hole_len > len)6008 hole_len = len;6009 ret = send_extent_data(sctx, dst_path, offset,6010 hole_len);6011 if (ret < 0)6012 goto out;6013 6014 len -= hole_len;6015 if (len == 0)6016 break;6017 offset += hole_len;6018 clone_root->offset += hole_len;6019 data_offset += hole_len;6020 }6021 6022 if (key.offset >= clone_root->offset + len)6023 break;6024 6025 if (key.offset >= clone_src_i_size)6026 break;6027 6028 if (key.offset + ext_len > clone_src_i_size) {6029 ext_len = clone_src_i_size - key.offset;6030 crossed_src_i_size = true;6031 }6032 6033 clone_data_offset = btrfs_file_extent_offset(leaf, ei);6034 if (btrfs_file_extent_disk_bytenr(leaf, ei) == disk_byte) {6035 clone_root->offset = key.offset;6036 if (clone_data_offset < data_offset &&6037 clone_data_offset + ext_len > data_offset) {6038 u64 extent_offset;6039 6040 extent_offset = data_offset - clone_data_offset;6041 ext_len -= extent_offset;6042 clone_data_offset += extent_offset;6043 clone_root->offset += extent_offset;6044 }6045 }6046 6047 clone_len = min_t(u64, ext_len, len);6048 6049 if (btrfs_file_extent_disk_bytenr(leaf, ei) == disk_byte &&6050 clone_data_offset == data_offset) {6051 const u64 src_end = clone_root->offset + clone_len;6052 const u64 sectorsize = SZ_64K;6053 6054 /*6055 * We can't clone the last block, when its size is not6056 * sector size aligned, into the middle of a file. If we6057 * do so, the receiver will get a failure (-EINVAL) when6058 * trying to clone or will silently corrupt the data in6059 * the destination file if it's on a kernel without the6060 * fix introduced by commit ac765f83f13976466061 * ("Btrfs: fix data corruption due to cloning of eof6062 * block).6063 *6064 * So issue a clone of the aligned down range plus a6065 * regular write for the eof block, if we hit that case.6066 *6067 * Also, we use the maximum possible sector size, 64K,6068 * because we don't know what's the sector size of the6069 * filesystem that receives the stream, so we have to6070 * assume the largest possible sector size.6071 */6072 if (src_end == clone_src_i_size &&6073 !IS_ALIGNED(src_end, sectorsize) &&6074 offset + clone_len < sctx->cur_inode_size) {6075 u64 slen;6076 6077 slen = ALIGN_DOWN(src_end - clone_root->offset,6078 sectorsize);6079 if (slen > 0) {6080 ret = send_clone(sctx, offset, slen,6081 clone_root);6082 if (ret < 0)6083 goto out;6084 }6085 ret = send_extent_data(sctx, dst_path,6086 offset + slen,6087 clone_len - slen);6088 } else {6089 ret = send_clone(sctx, offset, clone_len,6090 clone_root);6091 }6092 } else if (crossed_src_i_size && clone_len < len) {6093 /*6094 * If we are at i_size of the clone source inode and we6095 * can not clone from it, terminate the loop. This is6096 * to avoid sending two write operations, one with a6097 * length matching clone_len and the final one after6098 * this loop with a length of len - clone_len.6099 *6100 * When using encoded writes (BTRFS_SEND_FLAG_COMPRESSED6101 * was passed to the send ioctl), this helps avoid6102 * sending an encoded write for an offset that is not6103 * sector size aligned, in case the i_size of the source6104 * inode is not sector size aligned. That will make the6105 * receiver fallback to decompression of the data and6106 * writing it using regular buffered IO, therefore while6107 * not incorrect, it's not optimal due decompression and6108 * possible re-compression at the receiver.6109 */6110 break;6111 } else {6112 ret = send_extent_data(sctx, dst_path, offset,6113 clone_len);6114 }6115 6116 if (ret < 0)6117 goto out;6118 6119 len -= clone_len;6120 if (len == 0)6121 break;6122 offset += clone_len;6123 clone_root->offset += clone_len;6124 6125 /*6126 * If we are cloning from the file we are currently processing,6127 * and using the send root as the clone root, we must stop once6128 * the current clone offset reaches the current eof of the file6129 * at the receiver, otherwise we would issue an invalid clone6130 * operation (source range going beyond eof) and cause the6131 * receiver to fail. So if we reach the current eof, bail out6132 * and fallback to a regular write.6133 */6134 if (clone_root->root == sctx->send_root &&6135 clone_root->ino == sctx->cur_ino &&6136 clone_root->offset >= sctx->cur_inode_next_write_offset)6137 break;6138 6139 data_offset += clone_len;6140next:6141 path->slots[0]++;6142 }6143 6144 if (len > 0)6145 ret = send_extent_data(sctx, dst_path, offset, len);6146 else6147 ret = 0;6148out:6149 btrfs_free_path(path);6150 return ret;6151}6152 6153static int send_write_or_clone(struct send_ctx *sctx,6154 struct btrfs_path *path,6155 struct btrfs_key *key,6156 struct clone_root *clone_root)6157{6158 int ret = 0;6159 u64 offset = key->offset;6160 u64 end;6161 u64 bs = sctx->send_root->fs_info->sectorsize;6162 struct btrfs_file_extent_item *ei;6163 u64 disk_byte;6164 u64 data_offset;6165 u64 num_bytes;6166 struct btrfs_inode_info info = { 0 };6167 6168 end = min_t(u64, btrfs_file_extent_end(path), sctx->cur_inode_size);6169 if (offset >= end)6170 return 0;6171 6172 num_bytes = end - offset;6173 6174 if (!clone_root)6175 goto write_data;6176 6177 if (IS_ALIGNED(end, bs))6178 goto clone_data;6179 6180 /*6181 * If the extent end is not aligned, we can clone if the extent ends at6182 * the i_size of the inode and the clone range ends at the i_size of the6183 * source inode, otherwise the clone operation fails with -EINVAL.6184 */6185 if (end != sctx->cur_inode_size)6186 goto write_data;6187 6188 ret = get_inode_info(clone_root->root, clone_root->ino, &info);6189 if (ret < 0)6190 return ret;6191 6192 if (clone_root->offset + num_bytes == info.size) {6193 /*6194 * The final size of our file matches the end offset, but it may6195 * be that its current size is larger, so we have to truncate it6196 * to any value between the start offset of the range and the6197 * final i_size, otherwise the clone operation is invalid6198 * because it's unaligned and it ends before the current EOF.6199 * We do this truncate to the final i_size when we finish6200 * processing the inode, but it's too late by then. And here we6201 * truncate to the start offset of the range because it's always6202 * sector size aligned while if it were the final i_size it6203 * would result in dirtying part of a page, filling part of a6204 * page with zeroes and then having the clone operation at the6205 * receiver trigger IO and wait for it due to the dirty page.6206 */6207 if (sctx->parent_root != NULL) {6208 ret = send_truncate(sctx, sctx->cur_ino,6209 sctx->cur_inode_gen, offset);6210 if (ret < 0)6211 return ret;6212 }6213 goto clone_data;6214 }6215 6216write_data:6217 ret = send_extent_data(sctx, path, offset, num_bytes);6218 sctx->cur_inode_next_write_offset = end;6219 return ret;6220 6221clone_data:6222 ei = btrfs_item_ptr(path->nodes[0], path->slots[0],6223 struct btrfs_file_extent_item);6224 disk_byte = btrfs_file_extent_disk_bytenr(path->nodes[0], ei);6225 data_offset = btrfs_file_extent_offset(path->nodes[0], ei);6226 ret = clone_range(sctx, path, clone_root, disk_byte, data_offset, offset,6227 num_bytes);6228 sctx->cur_inode_next_write_offset = end;6229 return ret;6230}6231 6232static int is_extent_unchanged(struct send_ctx *sctx,6233 struct btrfs_path *left_path,6234 struct btrfs_key *ekey)6235{6236 int ret = 0;6237 struct btrfs_key key;6238 struct btrfs_path *path = NULL;6239 struct extent_buffer *eb;6240 int slot;6241 struct btrfs_key found_key;6242 struct btrfs_file_extent_item *ei;6243 u64 left_disknr;6244 u64 right_disknr;6245 u64 left_offset;6246 u64 right_offset;6247 u64 left_offset_fixed;6248 u64 left_len;6249 u64 right_len;6250 u64 left_gen;6251 u64 right_gen;6252 u8 left_type;6253 u8 right_type;6254 6255 path = alloc_path_for_send();6256 if (!path)6257 return -ENOMEM;6258 6259 eb = left_path->nodes[0];6260 slot = left_path->slots[0];6261 ei = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);6262 left_type = btrfs_file_extent_type(eb, ei);6263 6264 if (left_type != BTRFS_FILE_EXTENT_REG) {6265 ret = 0;6266 goto out;6267 }6268 left_disknr = btrfs_file_extent_disk_bytenr(eb, ei);6269 left_len = btrfs_file_extent_num_bytes(eb, ei);6270 left_offset = btrfs_file_extent_offset(eb, ei);6271 left_gen = btrfs_file_extent_generation(eb, ei);6272 6273 /*6274 * Following comments will refer to these graphics. L is the left6275 * extents which we are checking at the moment. 1-8 are the right6276 * extents that we iterate.6277 *6278 * |-----L-----|6279 * |-1-|-2a-|-3-|-4-|-5-|-6-|6280 *6281 * |-----L-----|6282 * |--1--|-2b-|...(same as above)6283 *6284 * Alternative situation. Happens on files where extents got split.6285 * |-----L-----|6286 * |-----------7-----------|-6-|6287 *6288 * Alternative situation. Happens on files which got larger.6289 * |-----L-----|6290 * |-8-|6291 * Nothing follows after 8.6292 */6293 6294 key.objectid = ekey->objectid;6295 key.type = BTRFS_EXTENT_DATA_KEY;6296 key.offset = ekey->offset;6297 ret = btrfs_search_slot_for_read(sctx->parent_root, &key, path, 0, 0);6298 if (ret < 0)6299 goto out;6300 if (ret) {6301 ret = 0;6302 goto out;6303 }6304 6305 /*6306 * Handle special case where the right side has no extents at all.6307 */6308 eb = path->nodes[0];6309 slot = path->slots[0];6310 btrfs_item_key_to_cpu(eb, &found_key, slot);6311 if (found_key.objectid != key.objectid ||6312 found_key.type != key.type) {6313 /* If we're a hole then just pretend nothing changed */6314 ret = (left_disknr) ? 0 : 1;6315 goto out;6316 }6317 6318 /*6319 * We're now on 2a, 2b or 7.6320 */6321 key = found_key;6322 while (key.offset < ekey->offset + left_len) {6323 ei = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);6324 right_type = btrfs_file_extent_type(eb, ei);6325 if (right_type != BTRFS_FILE_EXTENT_REG &&6326 right_type != BTRFS_FILE_EXTENT_INLINE) {6327 ret = 0;6328 goto out;6329 }6330 6331 if (right_type == BTRFS_FILE_EXTENT_INLINE) {6332 right_len = btrfs_file_extent_ram_bytes(eb, ei);6333 right_len = PAGE_ALIGN(right_len);6334 } else {6335 right_len = btrfs_file_extent_num_bytes(eb, ei);6336 }6337 6338 /*6339 * Are we at extent 8? If yes, we know the extent is changed.6340 * This may only happen on the first iteration.6341 */6342 if (found_key.offset + right_len <= ekey->offset) {6343 /* If we're a hole just pretend nothing changed */6344 ret = (left_disknr) ? 0 : 1;6345 goto out;6346 }6347 6348 /*6349 * We just wanted to see if when we have an inline extent, what6350 * follows it is a regular extent (wanted to check the above6351 * condition for inline extents too). This should normally not6352 * happen but it's possible for example when we have an inline6353 * compressed extent representing data with a size matching6354 * the page size (currently the same as sector size).6355 */6356 if (right_type == BTRFS_FILE_EXTENT_INLINE) {6357 ret = 0;6358 goto out;6359 }6360 6361 right_disknr = btrfs_file_extent_disk_bytenr(eb, ei);6362 right_offset = btrfs_file_extent_offset(eb, ei);6363 right_gen = btrfs_file_extent_generation(eb, ei);6364 6365 left_offset_fixed = left_offset;6366 if (key.offset < ekey->offset) {6367 /* Fix the right offset for 2a and 7. */6368 right_offset += ekey->offset - key.offset;6369 } else {6370 /* Fix the left offset for all behind 2a and 2b */6371 left_offset_fixed += key.offset - ekey->offset;6372 }6373 6374 /*6375 * Check if we have the same extent.6376 */6377 if (left_disknr != right_disknr ||6378 left_offset_fixed != right_offset ||6379 left_gen != right_gen) {6380 ret = 0;6381 goto out;6382 }6383 6384 /*6385 * Go to the next extent.6386 */6387 ret = btrfs_next_item(sctx->parent_root, path);6388 if (ret < 0)6389 goto out;6390 if (!ret) {6391 eb = path->nodes[0];6392 slot = path->slots[0];6393 btrfs_item_key_to_cpu(eb, &found_key, slot);6394 }6395 if (ret || found_key.objectid != key.objectid ||6396 found_key.type != key.type) {6397 key.offset += right_len;6398 break;6399 }6400 if (found_key.offset != key.offset + right_len) {6401 ret = 0;6402 goto out;6403 }6404 key = found_key;6405 }6406 6407 /*6408 * We're now behind the left extent (treat as unchanged) or at the end6409 * of the right side (treat as changed).6410 */6411 if (key.offset >= ekey->offset + left_len)6412 ret = 1;6413 else6414 ret = 0;6415 6416 6417out:6418 btrfs_free_path(path);6419 return ret;6420}6421 6422static int get_last_extent(struct send_ctx *sctx, u64 offset)6423{6424 struct btrfs_path *path;6425 struct btrfs_root *root = sctx->send_root;6426 struct btrfs_key key;6427 int ret;6428 6429 path = alloc_path_for_send();6430 if (!path)6431 return -ENOMEM;6432 6433 sctx->cur_inode_last_extent = 0;6434 6435 key.objectid = sctx->cur_ino;6436 key.type = BTRFS_EXTENT_DATA_KEY;6437 key.offset = offset;6438 ret = btrfs_search_slot_for_read(root, &key, path, 0, 1);6439 if (ret < 0)6440 goto out;6441 ret = 0;6442 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);6443 if (key.objectid != sctx->cur_ino || key.type != BTRFS_EXTENT_DATA_KEY)6444 goto out;6445 6446 sctx->cur_inode_last_extent = btrfs_file_extent_end(path);6447out:6448 btrfs_free_path(path);6449 return ret;6450}6451 6452static int range_is_hole_in_parent(struct send_ctx *sctx,6453 const u64 start,6454 const u64 end)6455{6456 struct btrfs_path *path;6457 struct btrfs_key key;6458 struct btrfs_root *root = sctx->parent_root;6459 u64 search_start = start;6460 int ret;6461 6462 path = alloc_path_for_send();6463 if (!path)6464 return -ENOMEM;6465 6466 key.objectid = sctx->cur_ino;6467 key.type = BTRFS_EXTENT_DATA_KEY;6468 key.offset = search_start;6469 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);6470 if (ret < 0)6471 goto out;6472 if (ret > 0 && path->slots[0] > 0)6473 path->slots[0]--;6474 6475 while (search_start < end) {6476 struct extent_buffer *leaf = path->nodes[0];6477 int slot = path->slots[0];6478 struct btrfs_file_extent_item *fi;6479 u64 extent_end;6480 6481 if (slot >= btrfs_header_nritems(leaf)) {6482 ret = btrfs_next_leaf(root, path);6483 if (ret < 0)6484 goto out;6485 else if (ret > 0)6486 break;6487 continue;6488 }6489 6490 btrfs_item_key_to_cpu(leaf, &key, slot);6491 if (key.objectid < sctx->cur_ino ||6492 key.type < BTRFS_EXTENT_DATA_KEY)6493 goto next;6494 if (key.objectid > sctx->cur_ino ||6495 key.type > BTRFS_EXTENT_DATA_KEY ||6496 key.offset >= end)6497 break;6498 6499 fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);6500 extent_end = btrfs_file_extent_end(path);6501 if (extent_end <= start)6502 goto next;6503 if (btrfs_file_extent_disk_bytenr(leaf, fi) == 0) {6504 search_start = extent_end;6505 goto next;6506 }6507 ret = 0;6508 goto out;6509next:6510 path->slots[0]++;6511 }6512 ret = 1;6513out:6514 btrfs_free_path(path);6515 return ret;6516}6517 6518static int maybe_send_hole(struct send_ctx *sctx, struct btrfs_path *path,6519 struct btrfs_key *key)6520{6521 int ret = 0;6522 6523 if (sctx->cur_ino != key->objectid || !need_send_hole(sctx))6524 return 0;6525 6526 /*6527 * Get last extent's end offset (exclusive) if we haven't determined it6528 * yet (we're processing the first file extent item that is new), or if6529 * we're at the first slot of a leaf and the last extent's end is less6530 * than the current extent's offset, because we might have skipped6531 * entire leaves that contained only file extent items for our current6532 * inode. These leaves have a generation number smaller (older) than the6533 * one in the current leaf and the leaf our last extent came from, and6534 * are located between these 2 leaves.6535 */6536 if ((sctx->cur_inode_last_extent == (u64)-1) ||6537 (path->slots[0] == 0 && sctx->cur_inode_last_extent < key->offset)) {6538 ret = get_last_extent(sctx, key->offset - 1);6539 if (ret)6540 return ret;6541 }6542 6543 if (sctx->cur_inode_last_extent < key->offset) {6544 ret = range_is_hole_in_parent(sctx,6545 sctx->cur_inode_last_extent,6546 key->offset);6547 if (ret < 0)6548 return ret;6549 else if (ret == 0)6550 ret = send_hole(sctx, key->offset);6551 else6552 ret = 0;6553 }6554 sctx->cur_inode_last_extent = btrfs_file_extent_end(path);6555 return ret;6556}6557 6558static int process_extent(struct send_ctx *sctx,6559 struct btrfs_path *path,6560 struct btrfs_key *key)6561{6562 struct clone_root *found_clone = NULL;6563 int ret = 0;6564 6565 if (S_ISLNK(sctx->cur_inode_mode))6566 return 0;6567 6568 if (sctx->parent_root && !sctx->cur_inode_new) {6569 ret = is_extent_unchanged(sctx, path, key);6570 if (ret < 0)6571 goto out;6572 if (ret) {6573 ret = 0;6574 goto out_hole;6575 }6576 } else {6577 struct btrfs_file_extent_item *ei;6578 u8 type;6579 6580 ei = btrfs_item_ptr(path->nodes[0], path->slots[0],6581 struct btrfs_file_extent_item);6582 type = btrfs_file_extent_type(path->nodes[0], ei);6583 if (type == BTRFS_FILE_EXTENT_PREALLOC ||6584 type == BTRFS_FILE_EXTENT_REG) {6585 /*6586 * The send spec does not have a prealloc command yet,6587 * so just leave a hole for prealloc'ed extents until6588 * we have enough commands queued up to justify rev'ing6589 * the send spec.6590 */6591 if (type == BTRFS_FILE_EXTENT_PREALLOC) {6592 ret = 0;6593 goto out;6594 }6595 6596 /* Have a hole, just skip it. */6597 if (btrfs_file_extent_disk_bytenr(path->nodes[0], ei) == 0) {6598 ret = 0;6599 goto out;6600 }6601 }6602 }6603 6604 ret = find_extent_clone(sctx, path, key->objectid, key->offset,6605 sctx->cur_inode_size, &found_clone);6606 if (ret != -ENOENT && ret < 0)6607 goto out;6608 6609 ret = send_write_or_clone(sctx, path, key, found_clone);6610 if (ret)6611 goto out;6612out_hole:6613 ret = maybe_send_hole(sctx, path, key);6614out:6615 return ret;6616}6617 6618static int process_all_extents(struct send_ctx *sctx)6619{6620 int ret = 0;6621 int iter_ret = 0;6622 struct btrfs_root *root;6623 struct btrfs_path *path;6624 struct btrfs_key key;6625 struct btrfs_key found_key;6626 6627 root = sctx->send_root;6628 path = alloc_path_for_send();6629 if (!path)6630 return -ENOMEM;6631 6632 key.objectid = sctx->cmp_key->objectid;6633 key.type = BTRFS_EXTENT_DATA_KEY;6634 key.offset = 0;6635 btrfs_for_each_slot(root, &key, &found_key, path, iter_ret) {6636 if (found_key.objectid != key.objectid ||6637 found_key.type != key.type) {6638 ret = 0;6639 break;6640 }6641 6642 ret = process_extent(sctx, path, &found_key);6643 if (ret < 0)6644 break;6645 }6646 /* Catch error found during iteration */6647 if (iter_ret < 0)6648 ret = iter_ret;6649 6650 btrfs_free_path(path);6651 return ret;6652}6653 6654static int process_recorded_refs_if_needed(struct send_ctx *sctx, int at_end,6655 int *pending_move,6656 int *refs_processed)6657{6658 int ret = 0;6659 6660 if (sctx->cur_ino == 0)6661 goto out;6662 if (!at_end && sctx->cur_ino == sctx->cmp_key->objectid &&6663 sctx->cmp_key->type <= BTRFS_INODE_EXTREF_KEY)6664 goto out;6665 if (list_empty(&sctx->new_refs) && list_empty(&sctx->deleted_refs))6666 goto out;6667 6668 ret = process_recorded_refs(sctx, pending_move);6669 if (ret < 0)6670 goto out;6671 6672 *refs_processed = 1;6673out:6674 return ret;6675}6676 6677static int finish_inode_if_needed(struct send_ctx *sctx, int at_end)6678{6679 int ret = 0;6680 struct btrfs_inode_info info;6681 u64 left_mode;6682 u64 left_uid;6683 u64 left_gid;6684 u64 left_fileattr;6685 u64 right_mode;6686 u64 right_uid;6687 u64 right_gid;6688 u64 right_fileattr;6689 int need_chmod = 0;6690 int need_chown = 0;6691 bool need_fileattr = false;6692 int need_truncate = 1;6693 int pending_move = 0;6694 int refs_processed = 0;6695 6696 if (sctx->ignore_cur_inode)6697 return 0;6698 6699 ret = process_recorded_refs_if_needed(sctx, at_end, &pending_move,6700 &refs_processed);6701 if (ret < 0)6702 goto out;6703 6704 /*6705 * We have processed the refs and thus need to advance send_progress.6706 * Now, calls to get_cur_xxx will take the updated refs of the current6707 * inode into account.6708 *6709 * On the other hand, if our current inode is a directory and couldn't6710 * be moved/renamed because its parent was renamed/moved too and it has6711 * a higher inode number, we can only move/rename our current inode6712 * after we moved/renamed its parent. Therefore in this case operate on6713 * the old path (pre move/rename) of our current inode, and the6714 * move/rename will be performed later.6715 */6716 if (refs_processed && !pending_move)6717 sctx->send_progress = sctx->cur_ino + 1;6718 6719 if (sctx->cur_ino == 0 || sctx->cur_inode_deleted)6720 goto out;6721 if (!at_end && sctx->cmp_key->objectid == sctx->cur_ino)6722 goto out;6723 ret = get_inode_info(sctx->send_root, sctx->cur_ino, &info);6724 if (ret < 0)6725 goto out;6726 left_mode = info.mode;6727 left_uid = info.uid;6728 left_gid = info.gid;6729 left_fileattr = info.fileattr;6730 6731 if (!sctx->parent_root || sctx->cur_inode_new) {6732 need_chown = 1;6733 if (!S_ISLNK(sctx->cur_inode_mode))6734 need_chmod = 1;6735 if (sctx->cur_inode_next_write_offset == sctx->cur_inode_size)6736 need_truncate = 0;6737 } else {6738 u64 old_size;6739 6740 ret = get_inode_info(sctx->parent_root, sctx->cur_ino, &info);6741 if (ret < 0)6742 goto out;6743 old_size = info.size;6744 right_mode = info.mode;6745 right_uid = info.uid;6746 right_gid = info.gid;6747 right_fileattr = info.fileattr;6748 6749 if (left_uid != right_uid || left_gid != right_gid)6750 need_chown = 1;6751 if (!S_ISLNK(sctx->cur_inode_mode) && left_mode != right_mode)6752 need_chmod = 1;6753 if (!S_ISLNK(sctx->cur_inode_mode) && left_fileattr != right_fileattr)6754 need_fileattr = true;6755 if ((old_size == sctx->cur_inode_size) ||6756 (sctx->cur_inode_size > old_size &&6757 sctx->cur_inode_next_write_offset == sctx->cur_inode_size))6758 need_truncate = 0;6759 }6760 6761 if (S_ISREG(sctx->cur_inode_mode)) {6762 if (need_send_hole(sctx)) {6763 if (sctx->cur_inode_last_extent == (u64)-1 ||6764 sctx->cur_inode_last_extent <6765 sctx->cur_inode_size) {6766 ret = get_last_extent(sctx, (u64)-1);6767 if (ret)6768 goto out;6769 }6770 if (sctx->cur_inode_last_extent < sctx->cur_inode_size) {6771 ret = range_is_hole_in_parent(sctx,6772 sctx->cur_inode_last_extent,6773 sctx->cur_inode_size);6774 if (ret < 0) {6775 goto out;6776 } else if (ret == 0) {6777 ret = send_hole(sctx, sctx->cur_inode_size);6778 if (ret < 0)6779 goto out;6780 } else {6781 /* Range is already a hole, skip. */6782 ret = 0;6783 }6784 }6785 }6786 if (need_truncate) {6787 ret = send_truncate(sctx, sctx->cur_ino,6788 sctx->cur_inode_gen,6789 sctx->cur_inode_size);6790 if (ret < 0)6791 goto out;6792 }6793 }6794 6795 if (need_chown) {6796 ret = send_chown(sctx, sctx->cur_ino, sctx->cur_inode_gen,6797 left_uid, left_gid);6798 if (ret < 0)6799 goto out;6800 }6801 if (need_chmod) {6802 ret = send_chmod(sctx, sctx->cur_ino, sctx->cur_inode_gen,6803 left_mode);6804 if (ret < 0)6805 goto out;6806 }6807 if (need_fileattr) {6808 ret = send_fileattr(sctx, sctx->cur_ino, sctx->cur_inode_gen,6809 left_fileattr);6810 if (ret < 0)6811 goto out;6812 }6813 6814 if (proto_cmd_ok(sctx, BTRFS_SEND_C_ENABLE_VERITY)6815 && sctx->cur_inode_needs_verity) {6816 ret = process_verity(sctx);6817 if (ret < 0)6818 goto out;6819 }6820 6821 ret = send_capabilities(sctx);6822 if (ret < 0)6823 goto out;6824 6825 /*6826 * If other directory inodes depended on our current directory6827 * inode's move/rename, now do their move/rename operations.6828 */6829 if (!is_waiting_for_move(sctx, sctx->cur_ino)) {6830 ret = apply_children_dir_moves(sctx);6831 if (ret)6832 goto out;6833 /*6834 * Need to send that every time, no matter if it actually6835 * changed between the two trees as we have done changes to6836 * the inode before. If our inode is a directory and it's6837 * waiting to be moved/renamed, we will send its utimes when6838 * it's moved/renamed, therefore we don't need to do it here.6839 */6840 sctx->send_progress = sctx->cur_ino + 1;6841 6842 /*6843 * If the current inode is a non-empty directory, delay issuing6844 * the utimes command for it, as it's very likely we have inodes6845 * with an higher number inside it. We want to issue the utimes6846 * command only after adding all dentries to it.6847 */6848 if (S_ISDIR(sctx->cur_inode_mode) && sctx->cur_inode_size > 0)6849 ret = cache_dir_utimes(sctx, sctx->cur_ino, sctx->cur_inode_gen);6850 else6851 ret = send_utimes(sctx, sctx->cur_ino, sctx->cur_inode_gen);6852 6853 if (ret < 0)6854 goto out;6855 }6856 6857out:6858 if (!ret)6859 ret = trim_dir_utimes_cache(sctx);6860 6861 return ret;6862}6863 6864static void close_current_inode(struct send_ctx *sctx)6865{6866 u64 i_size;6867 6868 if (sctx->cur_inode == NULL)6869 return;6870 6871 i_size = i_size_read(sctx->cur_inode);6872 6873 /*6874 * If we are doing an incremental send, we may have extents between the6875 * last processed extent and the i_size that have not been processed6876 * because they haven't changed but we may have read some of their pages6877 * through readahead, see the comments at send_extent_data().6878 */6879 if (sctx->clean_page_cache && sctx->page_cache_clear_start < i_size)6880 truncate_inode_pages_range(&sctx->cur_inode->i_data,6881 sctx->page_cache_clear_start,6882 round_up(i_size, PAGE_SIZE) - 1);6883 6884 iput(sctx->cur_inode);6885 sctx->cur_inode = NULL;6886}6887 6888static int changed_inode(struct send_ctx *sctx,6889 enum btrfs_compare_tree_result result)6890{6891 int ret = 0;6892 struct btrfs_key *key = sctx->cmp_key;6893 struct btrfs_inode_item *left_ii = NULL;6894 struct btrfs_inode_item *right_ii = NULL;6895 u64 left_gen = 0;6896 u64 right_gen = 0;6897 6898 close_current_inode(sctx);6899 6900 sctx->cur_ino = key->objectid;6901 sctx->cur_inode_new_gen = false;6902 sctx->cur_inode_last_extent = (u64)-1;6903 sctx->cur_inode_next_write_offset = 0;6904 sctx->ignore_cur_inode = false;6905 6906 /*6907 * Set send_progress to current inode. This will tell all get_cur_xxx6908 * functions that the current inode's refs are not updated yet. Later,6909 * when process_recorded_refs is finished, it is set to cur_ino + 1.6910 */6911 sctx->send_progress = sctx->cur_ino;6912 6913 if (result == BTRFS_COMPARE_TREE_NEW ||6914 result == BTRFS_COMPARE_TREE_CHANGED) {6915 left_ii = btrfs_item_ptr(sctx->left_path->nodes[0],6916 sctx->left_path->slots[0],6917 struct btrfs_inode_item);6918 left_gen = btrfs_inode_generation(sctx->left_path->nodes[0],6919 left_ii);6920 } else {6921 right_ii = btrfs_item_ptr(sctx->right_path->nodes[0],6922 sctx->right_path->slots[0],6923 struct btrfs_inode_item);6924 right_gen = btrfs_inode_generation(sctx->right_path->nodes[0],6925 right_ii);6926 }6927 if (result == BTRFS_COMPARE_TREE_CHANGED) {6928 right_ii = btrfs_item_ptr(sctx->right_path->nodes[0],6929 sctx->right_path->slots[0],6930 struct btrfs_inode_item);6931 6932 right_gen = btrfs_inode_generation(sctx->right_path->nodes[0],6933 right_ii);6934 6935 /*6936 * The cur_ino = root dir case is special here. We can't treat6937 * the inode as deleted+reused because it would generate a6938 * stream that tries to delete/mkdir the root dir.6939 */6940 if (left_gen != right_gen &&6941 sctx->cur_ino != BTRFS_FIRST_FREE_OBJECTID)6942 sctx->cur_inode_new_gen = true;6943 }6944 6945 /*6946 * Normally we do not find inodes with a link count of zero (orphans)6947 * because the most common case is to create a snapshot and use it6948 * for a send operation. However other less common use cases involve6949 * using a subvolume and send it after turning it to RO mode just6950 * after deleting all hard links of a file while holding an open6951 * file descriptor against it or turning a RO snapshot into RW mode,6952 * keep an open file descriptor against a file, delete it and then6953 * turn the snapshot back to RO mode before using it for a send6954 * operation. The former is what the receiver operation does.6955 * Therefore, if we want to send these snapshots soon after they're6956 * received, we need to handle orphan inodes as well. Moreover, orphans6957 * can appear not only in the send snapshot but also in the parent6958 * snapshot. Here are several cases:6959 *6960 * Case 1: BTRFS_COMPARE_TREE_NEW6961 * | send snapshot | action6962 * --------------------------------6963 * nlink | 0 | ignore6964 *6965 * Case 2: BTRFS_COMPARE_TREE_DELETED6966 * | parent snapshot | action6967 * ----------------------------------6968 * nlink | 0 | as usual6969 * Note: No unlinks will be sent because there're no paths for it.6970 *6971 * Case 3: BTRFS_COMPARE_TREE_CHANGED6972 * | | parent snapshot | send snapshot | action6973 * -----------------------------------------------------------------------6974 * subcase 1 | nlink | 0 | 0 | ignore6975 * subcase 2 | nlink | >0 | 0 | new_gen(deletion)6976 * subcase 3 | nlink | 0 | >0 | new_gen(creation)6977 *6978 */6979 if (result == BTRFS_COMPARE_TREE_NEW) {6980 if (btrfs_inode_nlink(sctx->left_path->nodes[0], left_ii) == 0) {6981 sctx->ignore_cur_inode = true;6982 goto out;6983 }6984 sctx->cur_inode_gen = left_gen;6985 sctx->cur_inode_new = true;6986 sctx->cur_inode_deleted = false;6987 sctx->cur_inode_size = btrfs_inode_size(6988 sctx->left_path->nodes[0], left_ii);6989 sctx->cur_inode_mode = btrfs_inode_mode(6990 sctx->left_path->nodes[0], left_ii);6991 sctx->cur_inode_rdev = btrfs_inode_rdev(6992 sctx->left_path->nodes[0], left_ii);6993 if (sctx->cur_ino != BTRFS_FIRST_FREE_OBJECTID)6994 ret = send_create_inode_if_needed(sctx);6995 } else if (result == BTRFS_COMPARE_TREE_DELETED) {6996 sctx->cur_inode_gen = right_gen;6997 sctx->cur_inode_new = false;6998 sctx->cur_inode_deleted = true;6999 sctx->cur_inode_size = btrfs_inode_size(7000 sctx->right_path->nodes[0], right_ii);7001 sctx->cur_inode_mode = btrfs_inode_mode(7002 sctx->right_path->nodes[0], right_ii);7003 } else if (result == BTRFS_COMPARE_TREE_CHANGED) {7004 u32 new_nlinks, old_nlinks;7005 7006 new_nlinks = btrfs_inode_nlink(sctx->left_path->nodes[0], left_ii);7007 old_nlinks = btrfs_inode_nlink(sctx->right_path->nodes[0], right_ii);7008 if (new_nlinks == 0 && old_nlinks == 0) {7009 sctx->ignore_cur_inode = true;7010 goto out;7011 } else if (new_nlinks == 0 || old_nlinks == 0) {7012 sctx->cur_inode_new_gen = 1;7013 }7014 /*7015 * We need to do some special handling in case the inode was7016 * reported as changed with a changed generation number. This7017 * means that the original inode was deleted and new inode7018 * reused the same inum. So we have to treat the old inode as7019 * deleted and the new one as new.7020 */7021 if (sctx->cur_inode_new_gen) {7022 /*7023 * First, process the inode as if it was deleted.7024 */7025 if (old_nlinks > 0) {7026 sctx->cur_inode_gen = right_gen;7027 sctx->cur_inode_new = false;7028 sctx->cur_inode_deleted = true;7029 sctx->cur_inode_size = btrfs_inode_size(7030 sctx->right_path->nodes[0], right_ii);7031 sctx->cur_inode_mode = btrfs_inode_mode(7032 sctx->right_path->nodes[0], right_ii);7033 ret = process_all_refs(sctx,7034 BTRFS_COMPARE_TREE_DELETED);7035 if (ret < 0)7036 goto out;7037 }7038 7039 /*7040 * Now process the inode as if it was new.7041 */7042 if (new_nlinks > 0) {7043 sctx->cur_inode_gen = left_gen;7044 sctx->cur_inode_new = true;7045 sctx->cur_inode_deleted = false;7046 sctx->cur_inode_size = btrfs_inode_size(7047 sctx->left_path->nodes[0],7048 left_ii);7049 sctx->cur_inode_mode = btrfs_inode_mode(7050 sctx->left_path->nodes[0],7051 left_ii);7052 sctx->cur_inode_rdev = btrfs_inode_rdev(7053 sctx->left_path->nodes[0],7054 left_ii);7055 ret = send_create_inode_if_needed(sctx);7056 if (ret < 0)7057 goto out;7058 7059 ret = process_all_refs(sctx, BTRFS_COMPARE_TREE_NEW);7060 if (ret < 0)7061 goto out;7062 /*7063 * Advance send_progress now as we did not get7064 * into process_recorded_refs_if_needed in the7065 * new_gen case.7066 */7067 sctx->send_progress = sctx->cur_ino + 1;7068 7069 /*7070 * Now process all extents and xattrs of the7071 * inode as if they were all new.7072 */7073 ret = process_all_extents(sctx);7074 if (ret < 0)7075 goto out;7076 ret = process_all_new_xattrs(sctx);7077 if (ret < 0)7078 goto out;7079 }7080 } else {7081 sctx->cur_inode_gen = left_gen;7082 sctx->cur_inode_new = false;7083 sctx->cur_inode_new_gen = false;7084 sctx->cur_inode_deleted = false;7085 sctx->cur_inode_size = btrfs_inode_size(7086 sctx->left_path->nodes[0], left_ii);7087 sctx->cur_inode_mode = btrfs_inode_mode(7088 sctx->left_path->nodes[0], left_ii);7089 }7090 }7091 7092out:7093 return ret;7094}7095 7096/*7097 * We have to process new refs before deleted refs, but compare_trees gives us7098 * the new and deleted refs mixed. To fix this, we record the new/deleted refs7099 * first and later process them in process_recorded_refs.7100 * For the cur_inode_new_gen case, we skip recording completely because7101 * changed_inode did already initiate processing of refs. The reason for this is7102 * that in this case, compare_tree actually compares the refs of 2 different7103 * inodes. To fix this, process_all_refs is used in changed_inode to handle all7104 * refs of the right tree as deleted and all refs of the left tree as new.7105 */7106static int changed_ref(struct send_ctx *sctx,7107 enum btrfs_compare_tree_result result)7108{7109 int ret = 0;7110 7111 if (sctx->cur_ino != sctx->cmp_key->objectid) {7112 inconsistent_snapshot_error(sctx, result, "reference");7113 return -EIO;7114 }7115 7116 if (!sctx->cur_inode_new_gen &&7117 sctx->cur_ino != BTRFS_FIRST_FREE_OBJECTID) {7118 if (result == BTRFS_COMPARE_TREE_NEW)7119 ret = record_new_ref(sctx);7120 else if (result == BTRFS_COMPARE_TREE_DELETED)7121 ret = record_deleted_ref(sctx);7122 else if (result == BTRFS_COMPARE_TREE_CHANGED)7123 ret = record_changed_ref(sctx);7124 }7125 7126 return ret;7127}7128 7129/*7130 * Process new/deleted/changed xattrs. We skip processing in the7131 * cur_inode_new_gen case because changed_inode did already initiate processing7132 * of xattrs. The reason is the same as in changed_ref7133 */7134static int changed_xattr(struct send_ctx *sctx,7135 enum btrfs_compare_tree_result result)7136{7137 int ret = 0;7138 7139 if (sctx->cur_ino != sctx->cmp_key->objectid) {7140 inconsistent_snapshot_error(sctx, result, "xattr");7141 return -EIO;7142 }7143 7144 if (!sctx->cur_inode_new_gen && !sctx->cur_inode_deleted) {7145 if (result == BTRFS_COMPARE_TREE_NEW)7146 ret = process_new_xattr(sctx);7147 else if (result == BTRFS_COMPARE_TREE_DELETED)7148 ret = process_deleted_xattr(sctx);7149 else if (result == BTRFS_COMPARE_TREE_CHANGED)7150 ret = process_changed_xattr(sctx);7151 }7152 7153 return ret;7154}7155 7156/*7157 * Process new/deleted/changed extents. We skip processing in the7158 * cur_inode_new_gen case because changed_inode did already initiate processing7159 * of extents. The reason is the same as in changed_ref7160 */7161static int changed_extent(struct send_ctx *sctx,7162 enum btrfs_compare_tree_result result)7163{7164 int ret = 0;7165 7166 /*7167 * We have found an extent item that changed without the inode item7168 * having changed. This can happen either after relocation (where the7169 * disk_bytenr of an extent item is replaced at7170 * relocation.c:replace_file_extents()) or after deduplication into a7171 * file in both the parent and send snapshots (where an extent item can7172 * get modified or replaced with a new one). Note that deduplication7173 * updates the inode item, but it only changes the iversion (sequence7174 * field in the inode item) of the inode, so if a file is deduplicated7175 * the same amount of times in both the parent and send snapshots, its7176 * iversion becomes the same in both snapshots, whence the inode item is7177 * the same on both snapshots.7178 */7179 if (sctx->cur_ino != sctx->cmp_key->objectid)7180 return 0;7181 7182 if (!sctx->cur_inode_new_gen && !sctx->cur_inode_deleted) {7183 if (result != BTRFS_COMPARE_TREE_DELETED)7184 ret = process_extent(sctx, sctx->left_path,7185 sctx->cmp_key);7186 }7187 7188 return ret;7189}7190 7191static int changed_verity(struct send_ctx *sctx, enum btrfs_compare_tree_result result)7192{7193 if (!sctx->cur_inode_new_gen && !sctx->cur_inode_deleted) {7194 if (result == BTRFS_COMPARE_TREE_NEW)7195 sctx->cur_inode_needs_verity = true;7196 }7197 return 0;7198}7199 7200static int dir_changed(struct send_ctx *sctx, u64 dir)7201{7202 u64 orig_gen, new_gen;7203 int ret;7204 7205 ret = get_inode_gen(sctx->send_root, dir, &new_gen);7206 if (ret)7207 return ret;7208 7209 ret = get_inode_gen(sctx->parent_root, dir, &orig_gen);7210 if (ret)7211 return ret;7212 7213 return (orig_gen != new_gen) ? 1 : 0;7214}7215 7216static int compare_refs(struct send_ctx *sctx, struct btrfs_path *path,7217 struct btrfs_key *key)7218{7219 struct btrfs_inode_extref *extref;7220 struct extent_buffer *leaf;7221 u64 dirid = 0, last_dirid = 0;7222 unsigned long ptr;7223 u32 item_size;7224 u32 cur_offset = 0;7225 int ref_name_len;7226 int ret = 0;7227 7228 /* Easy case, just check this one dirid */7229 if (key->type == BTRFS_INODE_REF_KEY) {7230 dirid = key->offset;7231 7232 ret = dir_changed(sctx, dirid);7233 goto out;7234 }7235 7236 leaf = path->nodes[0];7237 item_size = btrfs_item_size(leaf, path->slots[0]);7238 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);7239 while (cur_offset < item_size) {7240 extref = (struct btrfs_inode_extref *)(ptr +7241 cur_offset);7242 dirid = btrfs_inode_extref_parent(leaf, extref);7243 ref_name_len = btrfs_inode_extref_name_len(leaf, extref);7244 cur_offset += ref_name_len + sizeof(*extref);7245 if (dirid == last_dirid)7246 continue;7247 ret = dir_changed(sctx, dirid);7248 if (ret)7249 break;7250 last_dirid = dirid;7251 }7252out:7253 return ret;7254}7255 7256/*7257 * Updates compare related fields in sctx and simply forwards to the actual7258 * changed_xxx functions.7259 */7260static int changed_cb(struct btrfs_path *left_path,7261 struct btrfs_path *right_path,7262 struct btrfs_key *key,7263 enum btrfs_compare_tree_result result,7264 struct send_ctx *sctx)7265{7266 int ret = 0;7267 7268 /*7269 * We can not hold the commit root semaphore here. This is because in7270 * the case of sending and receiving to the same filesystem, using a7271 * pipe, could result in a deadlock:7272 *7273 * 1) The task running send blocks on the pipe because it's full;7274 *7275 * 2) The task running receive, which is the only consumer of the pipe,7276 * is waiting for a transaction commit (for example due to a space7277 * reservation when doing a write or triggering a transaction commit7278 * when creating a subvolume);7279 *7280 * 3) The transaction is waiting to write lock the commit root semaphore,7281 * but can not acquire it since it's being held at 1).7282 *7283 * Down this call chain we write to the pipe through kernel_write().7284 * The same type of problem can also happen when sending to a file that7285 * is stored in the same filesystem - when reserving space for a write7286 * into the file, we can trigger a transaction commit.7287 *7288 * Our caller has supplied us with clones of leaves from the send and7289 * parent roots, so we're safe here from a concurrent relocation and7290 * further reallocation of metadata extents while we are here. Below we7291 * also assert that the leaves are clones.7292 */7293 lockdep_assert_not_held(&sctx->send_root->fs_info->commit_root_sem);7294 7295 /*7296 * We always have a send root, so left_path is never NULL. We will not7297 * have a leaf when we have reached the end of the send root but have7298 * not yet reached the end of the parent root.7299 */7300 if (left_path->nodes[0])7301 ASSERT(test_bit(EXTENT_BUFFER_UNMAPPED,7302 &left_path->nodes[0]->bflags));7303 /*7304 * When doing a full send we don't have a parent root, so right_path is7305 * NULL. When doing an incremental send, we may have reached the end of7306 * the parent root already, so we don't have a leaf at right_path.7307 */7308 if (right_path && right_path->nodes[0])7309 ASSERT(test_bit(EXTENT_BUFFER_UNMAPPED,7310 &right_path->nodes[0]->bflags));7311 7312 if (result == BTRFS_COMPARE_TREE_SAME) {7313 if (key->type == BTRFS_INODE_REF_KEY ||7314 key->type == BTRFS_INODE_EXTREF_KEY) {7315 ret = compare_refs(sctx, left_path, key);7316 if (!ret)7317 return 0;7318 if (ret < 0)7319 return ret;7320 } else if (key->type == BTRFS_EXTENT_DATA_KEY) {7321 return maybe_send_hole(sctx, left_path, key);7322 } else {7323 return 0;7324 }7325 result = BTRFS_COMPARE_TREE_CHANGED;7326 ret = 0;7327 }7328 7329 sctx->left_path = left_path;7330 sctx->right_path = right_path;7331 sctx->cmp_key = key;7332 7333 ret = finish_inode_if_needed(sctx, 0);7334 if (ret < 0)7335 goto out;7336 7337 /* Ignore non-FS objects */7338 if (key->objectid == BTRFS_FREE_INO_OBJECTID ||7339 key->objectid == BTRFS_FREE_SPACE_OBJECTID)7340 goto out;7341 7342 if (key->type == BTRFS_INODE_ITEM_KEY) {7343 ret = changed_inode(sctx, result);7344 } else if (!sctx->ignore_cur_inode) {7345 if (key->type == BTRFS_INODE_REF_KEY ||7346 key->type == BTRFS_INODE_EXTREF_KEY)7347 ret = changed_ref(sctx, result);7348 else if (key->type == BTRFS_XATTR_ITEM_KEY)7349 ret = changed_xattr(sctx, result);7350 else if (key->type == BTRFS_EXTENT_DATA_KEY)7351 ret = changed_extent(sctx, result);7352 else if (key->type == BTRFS_VERITY_DESC_ITEM_KEY &&7353 key->offset == 0)7354 ret = changed_verity(sctx, result);7355 }7356 7357out:7358 return ret;7359}7360 7361static int search_key_again(const struct send_ctx *sctx,7362 struct btrfs_root *root,7363 struct btrfs_path *path,7364 const struct btrfs_key *key)7365{7366 int ret;7367 7368 if (!path->need_commit_sem)7369 lockdep_assert_held_read(&root->fs_info->commit_root_sem);7370 7371 /*7372 * Roots used for send operations are readonly and no one can add,7373 * update or remove keys from them, so we should be able to find our7374 * key again. The only exception is deduplication, which can operate on7375 * readonly roots and add, update or remove keys to/from them - but at7376 * the moment we don't allow it to run in parallel with send.7377 */7378 ret = btrfs_search_slot(NULL, root, key, path, 0, 0);7379 ASSERT(ret <= 0);7380 if (ret > 0) {7381 btrfs_print_tree(path->nodes[path->lowest_level], false);7382 btrfs_err(root->fs_info,7383"send: key (%llu %u %llu) not found in %s root %llu, lowest_level %d, slot %d",7384 key->objectid, key->type, key->offset,7385 (root == sctx->parent_root ? "parent" : "send"),7386 btrfs_root_id(root), path->lowest_level,7387 path->slots[path->lowest_level]);7388 return -EUCLEAN;7389 }7390 7391 return ret;7392}7393 7394static int full_send_tree(struct send_ctx *sctx)7395{7396 int ret;7397 struct btrfs_root *send_root = sctx->send_root;7398 struct btrfs_key key;7399 struct btrfs_fs_info *fs_info = send_root->fs_info;7400 struct btrfs_path *path;7401 7402 path = alloc_path_for_send();7403 if (!path)7404 return -ENOMEM;7405 path->reada = READA_FORWARD_ALWAYS;7406 7407 key.objectid = BTRFS_FIRST_FREE_OBJECTID;7408 key.type = BTRFS_INODE_ITEM_KEY;7409 key.offset = 0;7410 7411 down_read(&fs_info->commit_root_sem);7412 sctx->last_reloc_trans = fs_info->last_reloc_trans;7413 up_read(&fs_info->commit_root_sem);7414 7415 ret = btrfs_search_slot_for_read(send_root, &key, path, 1, 0);7416 if (ret < 0)7417 goto out;7418 if (ret)7419 goto out_finish;7420 7421 while (1) {7422 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);7423 7424 ret = changed_cb(path, NULL, &key,7425 BTRFS_COMPARE_TREE_NEW, sctx);7426 if (ret < 0)7427 goto out;7428 7429 down_read(&fs_info->commit_root_sem);7430 if (fs_info->last_reloc_trans > sctx->last_reloc_trans) {7431 sctx->last_reloc_trans = fs_info->last_reloc_trans;7432 up_read(&fs_info->commit_root_sem);7433 /*7434 * A transaction used for relocating a block group was7435 * committed or is about to finish its commit. Release7436 * our path (leaf) and restart the search, so that we7437 * avoid operating on any file extent items that are7438 * stale, with a disk_bytenr that reflects a pre7439 * relocation value. This way we avoid as much as7440 * possible to fallback to regular writes when checking7441 * if we can clone file ranges.7442 */7443 btrfs_release_path(path);7444 ret = search_key_again(sctx, send_root, path, &key);7445 if (ret < 0)7446 goto out;7447 } else {7448 up_read(&fs_info->commit_root_sem);7449 }7450 7451 ret = btrfs_next_item(send_root, path);7452 if (ret < 0)7453 goto out;7454 if (ret) {7455 ret = 0;7456 break;7457 }7458 }7459 7460out_finish:7461 ret = finish_inode_if_needed(sctx, 1);7462 7463out:7464 btrfs_free_path(path);7465 return ret;7466}7467 7468static int replace_node_with_clone(struct btrfs_path *path, int level)7469{7470 struct extent_buffer *clone;7471 7472 clone = btrfs_clone_extent_buffer(path->nodes[level]);7473 if (!clone)7474 return -ENOMEM;7475 7476 free_extent_buffer(path->nodes[level]);7477 path->nodes[level] = clone;7478 7479 return 0;7480}7481 7482static int tree_move_down(struct btrfs_path *path, int *level, u64 reada_min_gen)7483{7484 struct extent_buffer *eb;7485 struct extent_buffer *parent = path->nodes[*level];7486 int slot = path->slots[*level];7487 const int nritems = btrfs_header_nritems(parent);7488 u64 reada_max;7489 u64 reada_done = 0;7490 7491 lockdep_assert_held_read(&parent->fs_info->commit_root_sem);7492 ASSERT(*level != 0);7493 7494 eb = btrfs_read_node_slot(parent, slot);7495 if (IS_ERR(eb))7496 return PTR_ERR(eb);7497 7498 /*7499 * Trigger readahead for the next leaves we will process, so that it is7500 * very likely that when we need them they are already in memory and we7501 * will not block on disk IO. For nodes we only do readahead for one,7502 * since the time window between processing nodes is typically larger.7503 */7504 reada_max = (*level == 1 ? SZ_128K : eb->fs_info->nodesize);7505 7506 for (slot++; slot < nritems && reada_done < reada_max; slot++) {7507 if (btrfs_node_ptr_generation(parent, slot) > reada_min_gen) {7508 btrfs_readahead_node_child(parent, slot);7509 reada_done += eb->fs_info->nodesize;7510 }7511 }7512 7513 path->nodes[*level - 1] = eb;7514 path->slots[*level - 1] = 0;7515 (*level)--;7516 7517 if (*level == 0)7518 return replace_node_with_clone(path, 0);7519 7520 return 0;7521}7522 7523static int tree_move_next_or_upnext(struct btrfs_path *path,7524 int *level, int root_level)7525{7526 int ret = 0;7527 int nritems;7528 nritems = btrfs_header_nritems(path->nodes[*level]);7529 7530 path->slots[*level]++;7531 7532 while (path->slots[*level] >= nritems) {7533 if (*level == root_level) {7534 path->slots[*level] = nritems - 1;7535 return -1;7536 }7537 7538 /* move upnext */7539 path->slots[*level] = 0;7540 free_extent_buffer(path->nodes[*level]);7541 path->nodes[*level] = NULL;7542 (*level)++;7543 path->slots[*level]++;7544 7545 nritems = btrfs_header_nritems(path->nodes[*level]);7546 ret = 1;7547 }7548 return ret;7549}7550 7551/*7552 * Returns 1 if it had to move up and next. 0 is returned if it moved only next7553 * or down.7554 */7555static int tree_advance(struct btrfs_path *path,7556 int *level, int root_level,7557 int allow_down,7558 struct btrfs_key *key,7559 u64 reada_min_gen)7560{7561 int ret;7562 7563 if (*level == 0 || !allow_down) {7564 ret = tree_move_next_or_upnext(path, level, root_level);7565 } else {7566 ret = tree_move_down(path, level, reada_min_gen);7567 }7568 7569 /*7570 * Even if we have reached the end of a tree, ret is -1, update the key7571 * anyway, so that in case we need to restart due to a block group7572 * relocation, we can assert that the last key of the root node still7573 * exists in the tree.7574 */7575 if (*level == 0)7576 btrfs_item_key_to_cpu(path->nodes[*level], key,7577 path->slots[*level]);7578 else7579 btrfs_node_key_to_cpu(path->nodes[*level], key,7580 path->slots[*level]);7581 7582 return ret;7583}7584 7585static int tree_compare_item(struct btrfs_path *left_path,7586 struct btrfs_path *right_path,7587 char *tmp_buf)7588{7589 int cmp;7590 int len1, len2;7591 unsigned long off1, off2;7592 7593 len1 = btrfs_item_size(left_path->nodes[0], left_path->slots[0]);7594 len2 = btrfs_item_size(right_path->nodes[0], right_path->slots[0]);7595 if (len1 != len2)7596 return 1;7597 7598 off1 = btrfs_item_ptr_offset(left_path->nodes[0], left_path->slots[0]);7599 off2 = btrfs_item_ptr_offset(right_path->nodes[0],7600 right_path->slots[0]);7601 7602 read_extent_buffer(left_path->nodes[0], tmp_buf, off1, len1);7603 7604 cmp = memcmp_extent_buffer(right_path->nodes[0], tmp_buf, off2, len1);7605 if (cmp)7606 return 1;7607 return 0;7608}7609 7610/*7611 * A transaction used for relocating a block group was committed or is about to7612 * finish its commit. Release our paths and restart the search, so that we are7613 * not using stale extent buffers:7614 *7615 * 1) For levels > 0, we are only holding references of extent buffers, without7616 * any locks on them, which does not prevent them from having been relocated7617 * and reallocated after the last time we released the commit root semaphore.7618 * The exception are the root nodes, for which we always have a clone, see7619 * the comment at btrfs_compare_trees();7620 *7621 * 2) For leaves, level 0, we are holding copies (clones) of extent buffers, so7622 * we are safe from the concurrent relocation and reallocation. However they7623 * can have file extent items with a pre relocation disk_bytenr value, so we7624 * restart the start from the current commit roots and clone the new leaves so7625 * that we get the post relocation disk_bytenr values. Not doing so, could7626 * make us clone the wrong data in case there are new extents using the old7627 * disk_bytenr that happen to be shared.7628 */7629static int restart_after_relocation(struct btrfs_path *left_path,7630 struct btrfs_path *right_path,7631 const struct btrfs_key *left_key,7632 const struct btrfs_key *right_key,7633 int left_level,7634 int right_level,7635 const struct send_ctx *sctx)7636{7637 int root_level;7638 int ret;7639 7640 lockdep_assert_held_read(&sctx->send_root->fs_info->commit_root_sem);7641 7642 btrfs_release_path(left_path);7643 btrfs_release_path(right_path);7644 7645 /*7646 * Since keys can not be added or removed to/from our roots because they7647 * are readonly and we do not allow deduplication to run in parallel7648 * (which can add, remove or change keys), the layout of the trees should7649 * not change.7650 */7651 left_path->lowest_level = left_level;7652 ret = search_key_again(sctx, sctx->send_root, left_path, left_key);7653 if (ret < 0)7654 return ret;7655 7656 right_path->lowest_level = right_level;7657 ret = search_key_again(sctx, sctx->parent_root, right_path, right_key);7658 if (ret < 0)7659 return ret;7660 7661 /*7662 * If the lowest level nodes are leaves, clone them so that they can be7663 * safely used by changed_cb() while not under the protection of the7664 * commit root semaphore, even if relocation and reallocation happens in7665 * parallel.7666 */7667 if (left_level == 0) {7668 ret = replace_node_with_clone(left_path, 0);7669 if (ret < 0)7670 return ret;7671 }7672 7673 if (right_level == 0) {7674 ret = replace_node_with_clone(right_path, 0);7675 if (ret < 0)7676 return ret;7677 }7678 7679 /*7680 * Now clone the root nodes (unless they happen to be the leaves we have7681 * already cloned). This is to protect against concurrent snapshotting of7682 * the send and parent roots (see the comment at btrfs_compare_trees()).7683 */7684 root_level = btrfs_header_level(sctx->send_root->commit_root);7685 if (root_level > 0) {7686 ret = replace_node_with_clone(left_path, root_level);7687 if (ret < 0)7688 return ret;7689 }7690 7691 root_level = btrfs_header_level(sctx->parent_root->commit_root);7692 if (root_level > 0) {7693 ret = replace_node_with_clone(right_path, root_level);7694 if (ret < 0)7695 return ret;7696 }7697 7698 return 0;7699}7700 7701/*7702 * This function compares two trees and calls the provided callback for7703 * every changed/new/deleted item it finds.7704 * If shared tree blocks are encountered, whole subtrees are skipped, making7705 * the compare pretty fast on snapshotted subvolumes.7706 *7707 * This currently works on commit roots only. As commit roots are read only,7708 * we don't do any locking. The commit roots are protected with transactions.7709 * Transactions are ended and rejoined when a commit is tried in between.7710 *7711 * This function checks for modifications done to the trees while comparing.7712 * If it detects a change, it aborts immediately.7713 */7714static int btrfs_compare_trees(struct btrfs_root *left_root,7715 struct btrfs_root *right_root, struct send_ctx *sctx)7716{7717 struct btrfs_fs_info *fs_info = left_root->fs_info;7718 int ret;7719 int cmp;7720 struct btrfs_path *left_path = NULL;7721 struct btrfs_path *right_path = NULL;7722 struct btrfs_key left_key;7723 struct btrfs_key right_key;7724 char *tmp_buf = NULL;7725 int left_root_level;7726 int right_root_level;7727 int left_level;7728 int right_level;7729 int left_end_reached = 0;7730 int right_end_reached = 0;7731 int advance_left = 0;7732 int advance_right = 0;7733 u64 left_blockptr;7734 u64 right_blockptr;7735 u64 left_gen;7736 u64 right_gen;7737 u64 reada_min_gen;7738 7739 left_path = btrfs_alloc_path();7740 if (!left_path) {7741 ret = -ENOMEM;7742 goto out;7743 }7744 right_path = btrfs_alloc_path();7745 if (!right_path) {7746 ret = -ENOMEM;7747 goto out;7748 }7749 7750 tmp_buf = kvmalloc(fs_info->nodesize, GFP_KERNEL);7751 if (!tmp_buf) {7752 ret = -ENOMEM;7753 goto out;7754 }7755 7756 left_path->search_commit_root = 1;7757 left_path->skip_locking = 1;7758 right_path->search_commit_root = 1;7759 right_path->skip_locking = 1;7760 7761 /*7762 * Strategy: Go to the first items of both trees. Then do7763 *7764 * If both trees are at level 07765 * Compare keys of current items7766 * If left < right treat left item as new, advance left tree7767 * and repeat7768 * If left > right treat right item as deleted, advance right tree7769 * and repeat7770 * If left == right do deep compare of items, treat as changed if7771 * needed, advance both trees and repeat7772 * If both trees are at the same level but not at level 07773 * Compare keys of current nodes/leafs7774 * If left < right advance left tree and repeat7775 * If left > right advance right tree and repeat7776 * If left == right compare blockptrs of the next nodes/leafs7777 * If they match advance both trees but stay at the same level7778 * and repeat7779 * If they don't match advance both trees while allowing to go7780 * deeper and repeat7781 * If tree levels are different7782 * Advance the tree that needs it and repeat7783 *7784 * Advancing a tree means:7785 * If we are at level 0, try to go to the next slot. If that's not7786 * possible, go one level up and repeat. Stop when we found a level7787 * where we could go to the next slot. We may at this point be on a7788 * node or a leaf.7789 *7790 * If we are not at level 0 and not on shared tree blocks, go one7791 * level deeper.7792 *7793 * If we are not at level 0 and on shared tree blocks, go one slot to7794 * the right if possible or go up and right.7795 */7796 7797 down_read(&fs_info->commit_root_sem);7798 left_level = btrfs_header_level(left_root->commit_root);7799 left_root_level = left_level;7800 /*7801 * We clone the root node of the send and parent roots to prevent races7802 * with snapshot creation of these roots. Snapshot creation COWs the7803 * root node of a tree, so after the transaction is committed the old7804 * extent can be reallocated while this send operation is still ongoing.7805 * So we clone them, under the commit root semaphore, to be race free.7806 */7807 left_path->nodes[left_level] =7808 btrfs_clone_extent_buffer(left_root->commit_root);7809 if (!left_path->nodes[left_level]) {7810 ret = -ENOMEM;7811 goto out_unlock;7812 }7813 7814 right_level = btrfs_header_level(right_root->commit_root);7815 right_root_level = right_level;7816 right_path->nodes[right_level] =7817 btrfs_clone_extent_buffer(right_root->commit_root);7818 if (!right_path->nodes[right_level]) {7819 ret = -ENOMEM;7820 goto out_unlock;7821 }7822 /*7823 * Our right root is the parent root, while the left root is the "send"7824 * root. We know that all new nodes/leaves in the left root must have7825 * a generation greater than the right root's generation, so we trigger7826 * readahead for those nodes and leaves of the left root, as we know we7827 * will need to read them at some point.7828 */7829 reada_min_gen = btrfs_header_generation(right_root->commit_root);7830 7831 if (left_level == 0)7832 btrfs_item_key_to_cpu(left_path->nodes[left_level],7833 &left_key, left_path->slots[left_level]);7834 else7835 btrfs_node_key_to_cpu(left_path->nodes[left_level],7836 &left_key, left_path->slots[left_level]);7837 if (right_level == 0)7838 btrfs_item_key_to_cpu(right_path->nodes[right_level],7839 &right_key, right_path->slots[right_level]);7840 else7841 btrfs_node_key_to_cpu(right_path->nodes[right_level],7842 &right_key, right_path->slots[right_level]);7843 7844 sctx->last_reloc_trans = fs_info->last_reloc_trans;7845 7846 while (1) {7847 if (need_resched() ||7848 rwsem_is_contended(&fs_info->commit_root_sem)) {7849 up_read(&fs_info->commit_root_sem);7850 cond_resched();7851 down_read(&fs_info->commit_root_sem);7852 }7853 7854 if (fs_info->last_reloc_trans > sctx->last_reloc_trans) {7855 ret = restart_after_relocation(left_path, right_path,7856 &left_key, &right_key,7857 left_level, right_level,7858 sctx);7859 if (ret < 0)7860 goto out_unlock;7861 sctx->last_reloc_trans = fs_info->last_reloc_trans;7862 }7863 7864 if (advance_left && !left_end_reached) {7865 ret = tree_advance(left_path, &left_level,7866 left_root_level,7867 advance_left != ADVANCE_ONLY_NEXT,7868 &left_key, reada_min_gen);7869 if (ret == -1)7870 left_end_reached = ADVANCE;7871 else if (ret < 0)7872 goto out_unlock;7873 advance_left = 0;7874 }7875 if (advance_right && !right_end_reached) {7876 ret = tree_advance(right_path, &right_level,7877 right_root_level,7878 advance_right != ADVANCE_ONLY_NEXT,7879 &right_key, reada_min_gen);7880 if (ret == -1)7881 right_end_reached = ADVANCE;7882 else if (ret < 0)7883 goto out_unlock;7884 advance_right = 0;7885 }7886 7887 if (left_end_reached && right_end_reached) {7888 ret = 0;7889 goto out_unlock;7890 } else if (left_end_reached) {7891 if (right_level == 0) {7892 up_read(&fs_info->commit_root_sem);7893 ret = changed_cb(left_path, right_path,7894 &right_key,7895 BTRFS_COMPARE_TREE_DELETED,7896 sctx);7897 if (ret < 0)7898 goto out;7899 down_read(&fs_info->commit_root_sem);7900 }7901 advance_right = ADVANCE;7902 continue;7903 } else if (right_end_reached) {7904 if (left_level == 0) {7905 up_read(&fs_info->commit_root_sem);7906 ret = changed_cb(left_path, right_path,7907 &left_key,7908 BTRFS_COMPARE_TREE_NEW,7909 sctx);7910 if (ret < 0)7911 goto out;7912 down_read(&fs_info->commit_root_sem);7913 }7914 advance_left = ADVANCE;7915 continue;7916 }7917 7918 if (left_level == 0 && right_level == 0) {7919 up_read(&fs_info->commit_root_sem);7920 cmp = btrfs_comp_cpu_keys(&left_key, &right_key);7921 if (cmp < 0) {7922 ret = changed_cb(left_path, right_path,7923 &left_key,7924 BTRFS_COMPARE_TREE_NEW,7925 sctx);7926 advance_left = ADVANCE;7927 } else if (cmp > 0) {7928 ret = changed_cb(left_path, right_path,7929 &right_key,7930 BTRFS_COMPARE_TREE_DELETED,7931 sctx);7932 advance_right = ADVANCE;7933 } else {7934 enum btrfs_compare_tree_result result;7935 7936 WARN_ON(!extent_buffer_uptodate(left_path->nodes[0]));7937 ret = tree_compare_item(left_path, right_path,7938 tmp_buf);7939 if (ret)7940 result = BTRFS_COMPARE_TREE_CHANGED;7941 else7942 result = BTRFS_COMPARE_TREE_SAME;7943 ret = changed_cb(left_path, right_path,7944 &left_key, result, sctx);7945 advance_left = ADVANCE;7946 advance_right = ADVANCE;7947 }7948 7949 if (ret < 0)7950 goto out;7951 down_read(&fs_info->commit_root_sem);7952 } else if (left_level == right_level) {7953 cmp = btrfs_comp_cpu_keys(&left_key, &right_key);7954 if (cmp < 0) {7955 advance_left = ADVANCE;7956 } else if (cmp > 0) {7957 advance_right = ADVANCE;7958 } else {7959 left_blockptr = btrfs_node_blockptr(7960 left_path->nodes[left_level],7961 left_path->slots[left_level]);7962 right_blockptr = btrfs_node_blockptr(7963 right_path->nodes[right_level],7964 right_path->slots[right_level]);7965 left_gen = btrfs_node_ptr_generation(7966 left_path->nodes[left_level],7967 left_path->slots[left_level]);7968 right_gen = btrfs_node_ptr_generation(7969 right_path->nodes[right_level],7970 right_path->slots[right_level]);7971 if (left_blockptr == right_blockptr &&7972 left_gen == right_gen) {7973 /*7974 * As we're on a shared block, don't7975 * allow to go deeper.7976 */7977 advance_left = ADVANCE_ONLY_NEXT;7978 advance_right = ADVANCE_ONLY_NEXT;7979 } else {7980 advance_left = ADVANCE;7981 advance_right = ADVANCE;7982 }7983 }7984 } else if (left_level < right_level) {7985 advance_right = ADVANCE;7986 } else {7987 advance_left = ADVANCE;7988 }7989 }7990 7991out_unlock:7992 up_read(&fs_info->commit_root_sem);7993out:7994 btrfs_free_path(left_path);7995 btrfs_free_path(right_path);7996 kvfree(tmp_buf);7997 return ret;7998}7999 8000static int send_subvol(struct send_ctx *sctx)8001{8002 int ret;8003 8004 if (!(sctx->flags & BTRFS_SEND_FLAG_OMIT_STREAM_HEADER)) {8005 ret = send_header(sctx);8006 if (ret < 0)8007 goto out;8008 }8009 8010 ret = send_subvol_begin(sctx);8011 if (ret < 0)8012 goto out;8013 8014 if (sctx->parent_root) {8015 ret = btrfs_compare_trees(sctx->send_root, sctx->parent_root, sctx);8016 if (ret < 0)8017 goto out;8018 ret = finish_inode_if_needed(sctx, 1);8019 if (ret < 0)8020 goto out;8021 } else {8022 ret = full_send_tree(sctx);8023 if (ret < 0)8024 goto out;8025 }8026 8027out:8028 free_recorded_refs(sctx);8029 return ret;8030}8031 8032/*8033 * If orphan cleanup did remove any orphans from a root, it means the tree8034 * was modified and therefore the commit root is not the same as the current8035 * root anymore. This is a problem, because send uses the commit root and8036 * therefore can see inode items that don't exist in the current root anymore,8037 * and for example make calls to btrfs_iget, which will do tree lookups based8038 * on the current root and not on the commit root. Those lookups will fail,8039 * returning a -ESTALE error, and making send fail with that error. So make8040 * sure a send does not see any orphans we have just removed, and that it will8041 * see the same inodes regardless of whether a transaction commit happened8042 * before it started (meaning that the commit root will be the same as the8043 * current root) or not.8044 */8045static int ensure_commit_roots_uptodate(struct send_ctx *sctx)8046{8047 struct btrfs_root *root = sctx->parent_root;8048 8049 if (root && root->node != root->commit_root)8050 return btrfs_commit_current_transaction(root);8051 8052 for (int i = 0; i < sctx->clone_roots_cnt; i++) {8053 root = sctx->clone_roots[i].root;8054 if (root->node != root->commit_root)8055 return btrfs_commit_current_transaction(root);8056 }8057 8058 return 0;8059}8060 8061/*8062 * Make sure any existing dellaloc is flushed for any root used by a send8063 * operation so that we do not miss any data and we do not race with writeback8064 * finishing and changing a tree while send is using the tree. This could8065 * happen if a subvolume is in RW mode, has delalloc, is turned to RO mode and8066 * a send operation then uses the subvolume.8067 * After flushing delalloc ensure_commit_roots_uptodate() must be called.8068 */8069static int flush_delalloc_roots(struct send_ctx *sctx)8070{8071 struct btrfs_root *root = sctx->parent_root;8072 int ret;8073 int i;8074 8075 if (root) {8076 ret = btrfs_start_delalloc_snapshot(root, false);8077 if (ret)8078 return ret;8079 btrfs_wait_ordered_extents(root, U64_MAX, NULL);8080 }8081 8082 for (i = 0; i < sctx->clone_roots_cnt; i++) {8083 root = sctx->clone_roots[i].root;8084 ret = btrfs_start_delalloc_snapshot(root, false);8085 if (ret)8086 return ret;8087 btrfs_wait_ordered_extents(root, U64_MAX, NULL);8088 }8089 8090 return 0;8091}8092 8093static void btrfs_root_dec_send_in_progress(struct btrfs_root* root)8094{8095 spin_lock(&root->root_item_lock);8096 root->send_in_progress--;8097 /*8098 * Not much left to do, we don't know why it's unbalanced and8099 * can't blindly reset it to 0.8100 */8101 if (root->send_in_progress < 0)8102 btrfs_err(root->fs_info,8103 "send_in_progress unbalanced %d root %llu",8104 root->send_in_progress, btrfs_root_id(root));8105 spin_unlock(&root->root_item_lock);8106}8107 8108static void dedupe_in_progress_warn(const struct btrfs_root *root)8109{8110 btrfs_warn_rl(root->fs_info,8111"cannot use root %llu for send while deduplications on it are in progress (%d in progress)",8112 btrfs_root_id(root), root->dedupe_in_progress);8113}8114 8115long btrfs_ioctl_send(struct btrfs_inode *inode, const struct btrfs_ioctl_send_args *arg)8116{8117 int ret = 0;8118 struct btrfs_root *send_root = inode->root;8119 struct btrfs_fs_info *fs_info = send_root->fs_info;8120 struct btrfs_root *clone_root;8121 struct send_ctx *sctx = NULL;8122 u32 i;8123 u64 *clone_sources_tmp = NULL;8124 int clone_sources_to_rollback = 0;8125 size_t alloc_size;8126 int sort_clone_roots = 0;8127 struct btrfs_lru_cache_entry *entry;8128 struct btrfs_lru_cache_entry *tmp;8129 8130 if (!capable(CAP_SYS_ADMIN))8131 return -EPERM;8132 8133 /*8134 * The subvolume must remain read-only during send, protect against8135 * making it RW. This also protects against deletion.8136 */8137 spin_lock(&send_root->root_item_lock);8138 if (btrfs_root_readonly(send_root) && send_root->dedupe_in_progress) {8139 dedupe_in_progress_warn(send_root);8140 spin_unlock(&send_root->root_item_lock);8141 return -EAGAIN;8142 }8143 send_root->send_in_progress++;8144 spin_unlock(&send_root->root_item_lock);8145 8146 /*8147 * Userspace tools do the checks and warn the user if it's8148 * not RO.8149 */8150 if (!btrfs_root_readonly(send_root)) {8151 ret = -EPERM;8152 goto out;8153 }8154 8155 /*8156 * Check that we don't overflow at later allocations, we request8157 * clone_sources_count + 1 items, and compare to unsigned long inside8158 * access_ok. Also set an upper limit for allocation size so this can't8159 * easily exhaust memory. Max number of clone sources is about 200K.8160 */8161 if (arg->clone_sources_count > SZ_8M / sizeof(struct clone_root)) {8162 ret = -EINVAL;8163 goto out;8164 }8165 8166 if (arg->flags & ~BTRFS_SEND_FLAG_MASK) {8167 ret = -EOPNOTSUPP;8168 goto out;8169 }8170 8171 sctx = kzalloc(sizeof(struct send_ctx), GFP_KERNEL);8172 if (!sctx) {8173 ret = -ENOMEM;8174 goto out;8175 }8176 8177 INIT_LIST_HEAD(&sctx->new_refs);8178 INIT_LIST_HEAD(&sctx->deleted_refs);8179 8180 btrfs_lru_cache_init(&sctx->name_cache, SEND_MAX_NAME_CACHE_SIZE);8181 btrfs_lru_cache_init(&sctx->backref_cache, SEND_MAX_BACKREF_CACHE_SIZE);8182 btrfs_lru_cache_init(&sctx->dir_created_cache,8183 SEND_MAX_DIR_CREATED_CACHE_SIZE);8184 /*8185 * This cache is periodically trimmed to a fixed size elsewhere, see8186 * cache_dir_utimes() and trim_dir_utimes_cache().8187 */8188 btrfs_lru_cache_init(&sctx->dir_utimes_cache, 0);8189 8190 sctx->pending_dir_moves = RB_ROOT;8191 sctx->waiting_dir_moves = RB_ROOT;8192 sctx->orphan_dirs = RB_ROOT;8193 sctx->rbtree_new_refs = RB_ROOT;8194 sctx->rbtree_deleted_refs = RB_ROOT;8195 8196 sctx->flags = arg->flags;8197 8198 if (arg->flags & BTRFS_SEND_FLAG_VERSION) {8199 if (arg->version > BTRFS_SEND_STREAM_VERSION) {8200 ret = -EPROTO;8201 goto out;8202 }8203 /* Zero means "use the highest version" */8204 sctx->proto = arg->version ?: BTRFS_SEND_STREAM_VERSION;8205 } else {8206 sctx->proto = 1;8207 }8208 if ((arg->flags & BTRFS_SEND_FLAG_COMPRESSED) && sctx->proto < 2) {8209 ret = -EINVAL;8210 goto out;8211 }8212 8213 sctx->send_filp = fget(arg->send_fd);8214 if (!sctx->send_filp || !(sctx->send_filp->f_mode & FMODE_WRITE)) {8215 ret = -EBADF;8216 goto out;8217 }8218 8219 sctx->send_root = send_root;8220 /*8221 * Unlikely but possible, if the subvolume is marked for deletion but8222 * is slow to remove the directory entry, send can still be started8223 */8224 if (btrfs_root_dead(sctx->send_root)) {8225 ret = -EPERM;8226 goto out;8227 }8228 8229 sctx->clone_roots_cnt = arg->clone_sources_count;8230 8231 if (sctx->proto >= 2) {8232 u32 send_buf_num_pages;8233 8234 sctx->send_max_size = BTRFS_SEND_BUF_SIZE_V2;8235 sctx->send_buf = vmalloc(sctx->send_max_size);8236 if (!sctx->send_buf) {8237 ret = -ENOMEM;8238 goto out;8239 }8240 send_buf_num_pages = sctx->send_max_size >> PAGE_SHIFT;8241 sctx->send_buf_pages = kcalloc(send_buf_num_pages,8242 sizeof(*sctx->send_buf_pages),8243 GFP_KERNEL);8244 if (!sctx->send_buf_pages) {8245 ret = -ENOMEM;8246 goto out;8247 }8248 for (i = 0; i < send_buf_num_pages; i++) {8249 sctx->send_buf_pages[i] =8250 vmalloc_to_page(sctx->send_buf + (i << PAGE_SHIFT));8251 }8252 } else {8253 sctx->send_max_size = BTRFS_SEND_BUF_SIZE_V1;8254 sctx->send_buf = kvmalloc(sctx->send_max_size, GFP_KERNEL);8255 }8256 if (!sctx->send_buf) {8257 ret = -ENOMEM;8258 goto out;8259 }8260 8261 sctx->clone_roots = kvcalloc(arg->clone_sources_count + 1,8262 sizeof(*sctx->clone_roots),8263 GFP_KERNEL);8264 if (!sctx->clone_roots) {8265 ret = -ENOMEM;8266 goto out;8267 }8268 8269 alloc_size = array_size(sizeof(*arg->clone_sources),8270 arg->clone_sources_count);8271 8272 if (arg->clone_sources_count) {8273 clone_sources_tmp = kvmalloc(alloc_size, GFP_KERNEL);8274 if (!clone_sources_tmp) {8275 ret = -ENOMEM;8276 goto out;8277 }8278 8279 ret = copy_from_user(clone_sources_tmp, arg->clone_sources,8280 alloc_size);8281 if (ret) {8282 ret = -EFAULT;8283 goto out;8284 }8285 8286 for (i = 0; i < arg->clone_sources_count; i++) {8287 clone_root = btrfs_get_fs_root(fs_info,8288 clone_sources_tmp[i], true);8289 if (IS_ERR(clone_root)) {8290 ret = PTR_ERR(clone_root);8291 goto out;8292 }8293 spin_lock(&clone_root->root_item_lock);8294 if (!btrfs_root_readonly(clone_root) ||8295 btrfs_root_dead(clone_root)) {8296 spin_unlock(&clone_root->root_item_lock);8297 btrfs_put_root(clone_root);8298 ret = -EPERM;8299 goto out;8300 }8301 if (clone_root->dedupe_in_progress) {8302 dedupe_in_progress_warn(clone_root);8303 spin_unlock(&clone_root->root_item_lock);8304 btrfs_put_root(clone_root);8305 ret = -EAGAIN;8306 goto out;8307 }8308 clone_root->send_in_progress++;8309 spin_unlock(&clone_root->root_item_lock);8310 8311 sctx->clone_roots[i].root = clone_root;8312 clone_sources_to_rollback = i + 1;8313 }8314 kvfree(clone_sources_tmp);8315 clone_sources_tmp = NULL;8316 }8317 8318 if (arg->parent_root) {8319 sctx->parent_root = btrfs_get_fs_root(fs_info, arg->parent_root,8320 true);8321 if (IS_ERR(sctx->parent_root)) {8322 ret = PTR_ERR(sctx->parent_root);8323 goto out;8324 }8325 8326 spin_lock(&sctx->parent_root->root_item_lock);8327 sctx->parent_root->send_in_progress++;8328 if (!btrfs_root_readonly(sctx->parent_root) ||8329 btrfs_root_dead(sctx->parent_root)) {8330 spin_unlock(&sctx->parent_root->root_item_lock);8331 ret = -EPERM;8332 goto out;8333 }8334 if (sctx->parent_root->dedupe_in_progress) {8335 dedupe_in_progress_warn(sctx->parent_root);8336 spin_unlock(&sctx->parent_root->root_item_lock);8337 ret = -EAGAIN;8338 goto out;8339 }8340 spin_unlock(&sctx->parent_root->root_item_lock);8341 }8342 8343 /*8344 * Clones from send_root are allowed, but only if the clone source8345 * is behind the current send position. This is checked while searching8346 * for possible clone sources.8347 */8348 sctx->clone_roots[sctx->clone_roots_cnt++].root =8349 btrfs_grab_root(sctx->send_root);8350 8351 /* We do a bsearch later */8352 sort(sctx->clone_roots, sctx->clone_roots_cnt,8353 sizeof(*sctx->clone_roots), __clone_root_cmp_sort,8354 NULL);8355 sort_clone_roots = 1;8356 8357 ret = flush_delalloc_roots(sctx);8358 if (ret)8359 goto out;8360 8361 ret = ensure_commit_roots_uptodate(sctx);8362 if (ret)8363 goto out;8364 8365 ret = send_subvol(sctx);8366 if (ret < 0)8367 goto out;8368 8369 btrfs_lru_cache_for_each_entry_safe(&sctx->dir_utimes_cache, entry, tmp) {8370 ret = send_utimes(sctx, entry->key, entry->gen);8371 if (ret < 0)8372 goto out;8373 btrfs_lru_cache_remove(&sctx->dir_utimes_cache, entry);8374 }8375 8376 if (!(sctx->flags & BTRFS_SEND_FLAG_OMIT_END_CMD)) {8377 ret = begin_cmd(sctx, BTRFS_SEND_C_END);8378 if (ret < 0)8379 goto out;8380 ret = send_cmd(sctx);8381 if (ret < 0)8382 goto out;8383 }8384 8385out:8386 WARN_ON(sctx && !ret && !RB_EMPTY_ROOT(&sctx->pending_dir_moves));8387 while (sctx && !RB_EMPTY_ROOT(&sctx->pending_dir_moves)) {8388 struct rb_node *n;8389 struct pending_dir_move *pm;8390 8391 n = rb_first(&sctx->pending_dir_moves);8392 pm = rb_entry(n, struct pending_dir_move, node);8393 while (!list_empty(&pm->list)) {8394 struct pending_dir_move *pm2;8395 8396 pm2 = list_first_entry(&pm->list,8397 struct pending_dir_move, list);8398 free_pending_move(sctx, pm2);8399 }8400 free_pending_move(sctx, pm);8401 }8402 8403 WARN_ON(sctx && !ret && !RB_EMPTY_ROOT(&sctx->waiting_dir_moves));8404 while (sctx && !RB_EMPTY_ROOT(&sctx->waiting_dir_moves)) {8405 struct rb_node *n;8406 struct waiting_dir_move *dm;8407 8408 n = rb_first(&sctx->waiting_dir_moves);8409 dm = rb_entry(n, struct waiting_dir_move, node);8410 rb_erase(&dm->node, &sctx->waiting_dir_moves);8411 kfree(dm);8412 }8413 8414 WARN_ON(sctx && !ret && !RB_EMPTY_ROOT(&sctx->orphan_dirs));8415 while (sctx && !RB_EMPTY_ROOT(&sctx->orphan_dirs)) {8416 struct rb_node *n;8417 struct orphan_dir_info *odi;8418 8419 n = rb_first(&sctx->orphan_dirs);8420 odi = rb_entry(n, struct orphan_dir_info, node);8421 free_orphan_dir_info(sctx, odi);8422 }8423 8424 if (sort_clone_roots) {8425 for (i = 0; i < sctx->clone_roots_cnt; i++) {8426 btrfs_root_dec_send_in_progress(8427 sctx->clone_roots[i].root);8428 btrfs_put_root(sctx->clone_roots[i].root);8429 }8430 } else {8431 for (i = 0; sctx && i < clone_sources_to_rollback; i++) {8432 btrfs_root_dec_send_in_progress(8433 sctx->clone_roots[i].root);8434 btrfs_put_root(sctx->clone_roots[i].root);8435 }8436 8437 btrfs_root_dec_send_in_progress(send_root);8438 }8439 if (sctx && !IS_ERR_OR_NULL(sctx->parent_root)) {8440 btrfs_root_dec_send_in_progress(sctx->parent_root);8441 btrfs_put_root(sctx->parent_root);8442 }8443 8444 kvfree(clone_sources_tmp);8445 8446 if (sctx) {8447 if (sctx->send_filp)8448 fput(sctx->send_filp);8449 8450 kvfree(sctx->clone_roots);8451 kfree(sctx->send_buf_pages);8452 kvfree(sctx->send_buf);8453 kvfree(sctx->verity_descriptor);8454 8455 close_current_inode(sctx);8456 8457 btrfs_lru_cache_clear(&sctx->name_cache);8458 btrfs_lru_cache_clear(&sctx->backref_cache);8459 btrfs_lru_cache_clear(&sctx->dir_created_cache);8460 btrfs_lru_cache_clear(&sctx->dir_utimes_cache);8461 8462 kfree(sctx);8463 }8464 8465 return ret;8466}8467