1 // SPDX-License-Identifier: GPL-2.0 2 /* 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 19 #include "send.h" 20 #include "backref.h" 21 #include "locking.h" 22 #include "disk-io.h" 23 #include "btrfs_inode.h" 24 #include "transaction.h" 25 #include "compression.h" 26 #include "xattr.h" 27 #include "print-tree.h" 28 29 /* 30 * Maximum number of references an extent can have in order for us to attempt to 31 * issue clone operations instead of write operations. This currently exists to 32 * avoid hitting limitations of the backreference walking code (taking a lot of 33 * time and using too much memory for extents with large number of references). 34 */ 35 #define SEND_MAX_EXTENT_REFS 64 36 37 /* 38 * A fs_path is a helper to dynamically build path names with unknown size. 39 * It reallocates the internal buffer on demand. 40 * It allows fast adding of path elements on the right side (normal path) and 41 * fast adding to the left side (reversed path). A reversed path can also be 42 * unreversed if needed. 43 */ 44 struct fs_path { 45 union { 46 struct { 47 char *start; 48 char *end; 49 50 char *buf; 51 unsigned short buf_len:15; 52 unsigned short reversed:1; 53 char inline_buf[]; 54 }; 55 /* 56 * Average path length does not exceed 200 bytes, we'll have 57 * better packing in the slab and higher chance to satisfy 58 * a allocation later during send. 59 */ 60 char pad[256]; 61 }; 62 }; 63 #define FS_PATH_INLINE_SIZE \ 64 (sizeof(struct fs_path) - offsetof(struct fs_path, inline_buf)) 65 66 67 /* reused for each extent */ 68 struct clone_root { 69 struct btrfs_root *root; 70 u64 ino; 71 u64 offset; 72 73 u64 found_refs; 74 }; 75 76 #define SEND_CTX_MAX_NAME_CACHE_SIZE 128 77 #define SEND_CTX_NAME_CACHE_CLEAN_SIZE (SEND_CTX_MAX_NAME_CACHE_SIZE * 2) 78 79 struct send_ctx { 80 struct file *send_filp; 81 loff_t send_off; 82 char *send_buf; 83 u32 send_size; 84 u32 send_max_size; 85 u64 total_send_size; 86 u64 cmd_send_size[BTRFS_SEND_C_MAX + 1]; 87 u64 flags; /* 'flags' member of btrfs_ioctl_send_args is u64 */ 88 /* Protocol version compatibility requested */ 89 u32 proto; 90 91 struct btrfs_root *send_root; 92 struct btrfs_root *parent_root; 93 struct clone_root *clone_roots; 94 int clone_roots_cnt; 95 96 /* current state of the compare_tree call */ 97 struct btrfs_path *left_path; 98 struct btrfs_path *right_path; 99 struct btrfs_key *cmp_key; 100 101 /* 102 * Keep track of the generation of the last transaction that was used 103 * for relocating a block group. This is periodically checked in order 104 * to detect if a relocation happened since the last check, so that we 105 * don't operate on stale extent buffers for nodes (level >= 1) or on 106 * stale disk_bytenr values of file extent items. 107 */ 108 u64 last_reloc_trans; 109 110 /* 111 * infos of the currently processed inode. In case of deleted inodes, 112 * these are the values from the deleted inode. 113 */ 114 u64 cur_ino; 115 u64 cur_inode_gen; 116 int cur_inode_new; 117 int cur_inode_new_gen; 118 int cur_inode_deleted; 119 u64 cur_inode_size; 120 u64 cur_inode_mode; 121 u64 cur_inode_rdev; 122 u64 cur_inode_last_extent; 123 u64 cur_inode_next_write_offset; 124 bool ignore_cur_inode; 125 126 u64 send_progress; 127 128 struct list_head new_refs; 129 struct list_head deleted_refs; 130 131 struct radix_tree_root name_cache; 132 struct list_head name_cache_list; 133 int name_cache_size; 134 135 /* 136 * The inode we are currently processing. It's not NULL only when we 137 * need to issue write commands for data extents from this inode. 138 */ 139 struct inode *cur_inode; 140 struct file_ra_state ra; 141 u64 page_cache_clear_start; 142 bool clean_page_cache; 143 144 /* 145 * We process inodes by their increasing order, so if before an 146 * incremental send we reverse the parent/child relationship of 147 * directories such that a directory with a lower inode number was 148 * the parent of a directory with a higher inode number, and the one 149 * becoming the new parent got renamed too, we can't rename/move the 150 * directory with lower inode number when we finish processing it - we 151 * must process the directory with higher inode number first, then 152 * rename/move it and then rename/move the directory with lower inode 153 * number. Example follows. 154 * 155 * Tree state when the first send was performed: 156 * 157 * . 158 * |-- a (ino 257) 159 * |-- b (ino 258) 160 * | 161 * | 162 * |-- c (ino 259) 163 * | |-- d (ino 260) 164 * | 165 * |-- c2 (ino 261) 166 * 167 * Tree state when the second (incremental) send is performed: 168 * 169 * . 170 * |-- a (ino 257) 171 * |-- b (ino 258) 172 * |-- c2 (ino 261) 173 * |-- d2 (ino 260) 174 * |-- cc (ino 259) 175 * 176 * The sequence of steps that lead to the second state was: 177 * 178 * mv /a/b/c/d /a/b/c2/d2 179 * mv /a/b/c /a/b/c2/d2/cc 180 * 181 * "c" has lower inode number, but we can't move it (2nd mv operation) 182 * before we move "d", which has higher inode number. 183 * 184 * So we just memorize which move/rename operations must be performed 185 * later when their respective parent is processed and moved/renamed. 186 */ 187 188 /* Indexed by parent directory inode number. */ 189 struct rb_root pending_dir_moves; 190 191 /* 192 * Reverse index, indexed by the inode number of a directory that 193 * is waiting for the move/rename of its immediate parent before its 194 * own move/rename can be performed. 195 */ 196 struct rb_root waiting_dir_moves; 197 198 /* 199 * A directory that is going to be rm'ed might have a child directory 200 * which is in the pending directory moves index above. In this case, 201 * the directory can only be removed after the move/rename of its child 202 * is performed. Example: 203 * 204 * Parent snapshot: 205 * 206 * . (ino 256) 207 * |-- a/ (ino 257) 208 * |-- b/ (ino 258) 209 * |-- c/ (ino 259) 210 * | |-- x/ (ino 260) 211 * | 212 * |-- y/ (ino 261) 213 * 214 * Send snapshot: 215 * 216 * . (ino 256) 217 * |-- a/ (ino 257) 218 * |-- b/ (ino 258) 219 * |-- YY/ (ino 261) 220 * |-- x/ (ino 260) 221 * 222 * Sequence of steps that lead to the send snapshot: 223 * rm -f /a/b/c/foo.txt 224 * mv /a/b/y /a/b/YY 225 * mv /a/b/c/x /a/b/YY 226 * rmdir /a/b/c 227 * 228 * When the child is processed, its move/rename is delayed until its 229 * parent is processed (as explained above), but all other operations 230 * like update utimes, chown, chgrp, etc, are performed and the paths 231 * that it uses for those operations must use the orphanized name of 232 * its parent (the directory we're going to rm later), so we need to 233 * memorize that name. 234 * 235 * Indexed by the inode number of the directory to be deleted. 236 */ 237 struct rb_root orphan_dirs; 238 }; 239 240 struct pending_dir_move { 241 struct rb_node node; 242 struct list_head list; 243 u64 parent_ino; 244 u64 ino; 245 u64 gen; 246 struct list_head update_refs; 247 }; 248 249 struct waiting_dir_move { 250 struct rb_node node; 251 u64 ino; 252 /* 253 * There might be some directory that could not be removed because it 254 * was waiting for this directory inode to be moved first. Therefore 255 * after this directory is moved, we can try to rmdir the ino rmdir_ino. 256 */ 257 u64 rmdir_ino; 258 u64 rmdir_gen; 259 bool orphanized; 260 }; 261 262 struct orphan_dir_info { 263 struct rb_node node; 264 u64 ino; 265 u64 gen; 266 u64 last_dir_index_offset; 267 }; 268 269 struct name_cache_entry { 270 struct list_head list; 271 /* 272 * radix_tree has only 32bit entries but we need to handle 64bit inums. 273 * We use the lower 32bit of the 64bit inum to store it in the tree. If 274 * more then one inum would fall into the same entry, we use radix_list 275 * to store the additional entries. radix_list is also used to store 276 * entries where two entries have the same inum but different 277 * generations. 278 */ 279 struct list_head radix_list; 280 u64 ino; 281 u64 gen; 282 u64 parent_ino; 283 u64 parent_gen; 284 int ret; 285 int need_later_update; 286 int name_len; 287 char name[]; 288 }; 289 290 #define ADVANCE 1 291 #define ADVANCE_ONLY_NEXT -1 292 293 enum btrfs_compare_tree_result { 294 BTRFS_COMPARE_TREE_NEW, 295 BTRFS_COMPARE_TREE_DELETED, 296 BTRFS_COMPARE_TREE_CHANGED, 297 BTRFS_COMPARE_TREE_SAME, 298 }; 299 300 __cold 301 static void inconsistent_snapshot_error(struct send_ctx *sctx, 302 enum btrfs_compare_tree_result result, 303 const char *what) 304 { 305 const char *result_string; 306 307 switch (result) { 308 case BTRFS_COMPARE_TREE_NEW: 309 result_string = "new"; 310 break; 311 case BTRFS_COMPARE_TREE_DELETED: 312 result_string = "deleted"; 313 break; 314 case BTRFS_COMPARE_TREE_CHANGED: 315 result_string = "updated"; 316 break; 317 case BTRFS_COMPARE_TREE_SAME: 318 ASSERT(0); 319 result_string = "unchanged"; 320 break; 321 default: 322 ASSERT(0); 323 result_string = "unexpected"; 324 } 325 326 btrfs_err(sctx->send_root->fs_info, 327 "Send: inconsistent snapshot, found %s %s for inode %llu without updated inode item, send root is %llu, parent root is %llu", 328 result_string, what, sctx->cmp_key->objectid, 329 sctx->send_root->root_key.objectid, 330 (sctx->parent_root ? 331 sctx->parent_root->root_key.objectid : 0)); 332 } 333 334 __maybe_unused 335 static bool proto_cmd_ok(const struct send_ctx *sctx, int cmd) 336 { 337 switch (sctx->proto) { 338 case 1: return cmd < __BTRFS_SEND_C_MAX_V1; 339 case 2: return cmd < __BTRFS_SEND_C_MAX_V2; 340 default: return false; 341 } 342 } 343 344 static int is_waiting_for_move(struct send_ctx *sctx, u64 ino); 345 346 static struct waiting_dir_move * 347 get_waiting_dir_move(struct send_ctx *sctx, u64 ino); 348 349 static int is_waiting_for_rm(struct send_ctx *sctx, u64 dir_ino, u64 gen); 350 351 static int need_send_hole(struct send_ctx *sctx) 352 { 353 return (sctx->parent_root && !sctx->cur_inode_new && 354 !sctx->cur_inode_new_gen && !sctx->cur_inode_deleted && 355 S_ISREG(sctx->cur_inode_mode)); 356 } 357 358 static void fs_path_reset(struct fs_path *p) 359 { 360 if (p->reversed) { 361 p->start = p->buf + p->buf_len - 1; 362 p->end = p->start; 363 *p->start = 0; 364 } else { 365 p->start = p->buf; 366 p->end = p->start; 367 *p->start = 0; 368 } 369 } 370 371 static struct fs_path *fs_path_alloc(void) 372 { 373 struct fs_path *p; 374 375 p = kmalloc(sizeof(*p), GFP_KERNEL); 376 if (!p) 377 return NULL; 378 p->reversed = 0; 379 p->buf = p->inline_buf; 380 p->buf_len = FS_PATH_INLINE_SIZE; 381 fs_path_reset(p); 382 return p; 383 } 384 385 static struct fs_path *fs_path_alloc_reversed(void) 386 { 387 struct fs_path *p; 388 389 p = fs_path_alloc(); 390 if (!p) 391 return NULL; 392 p->reversed = 1; 393 fs_path_reset(p); 394 return p; 395 } 396 397 static void fs_path_free(struct fs_path *p) 398 { 399 if (!p) 400 return; 401 if (p->buf != p->inline_buf) 402 kfree(p->buf); 403 kfree(p); 404 } 405 406 static int fs_path_len(struct fs_path *p) 407 { 408 return p->end - p->start; 409 } 410 411 static int fs_path_ensure_buf(struct fs_path *p, int len) 412 { 413 char *tmp_buf; 414 int path_len; 415 int old_buf_len; 416 417 len++; 418 419 if (p->buf_len >= len) 420 return 0; 421 422 if (len > PATH_MAX) { 423 WARN_ON(1); 424 return -ENOMEM; 425 } 426 427 path_len = p->end - p->start; 428 old_buf_len = p->buf_len; 429 430 /* 431 * First time the inline_buf does not suffice 432 */ 433 if (p->buf == p->inline_buf) { 434 tmp_buf = kmalloc(len, GFP_KERNEL); 435 if (tmp_buf) 436 memcpy(tmp_buf, p->buf, old_buf_len); 437 } else { 438 tmp_buf = krealloc(p->buf, len, GFP_KERNEL); 439 } 440 if (!tmp_buf) 441 return -ENOMEM; 442 p->buf = tmp_buf; 443 /* 444 * The real size of the buffer is bigger, this will let the fast path 445 * happen most of the time 446 */ 447 p->buf_len = ksize(p->buf); 448 449 if (p->reversed) { 450 tmp_buf = p->buf + old_buf_len - path_len - 1; 451 p->end = p->buf + p->buf_len - 1; 452 p->start = p->end - path_len; 453 memmove(p->start, tmp_buf, path_len + 1); 454 } else { 455 p->start = p->buf; 456 p->end = p->start + path_len; 457 } 458 return 0; 459 } 460 461 static int fs_path_prepare_for_add(struct fs_path *p, int name_len, 462 char **prepared) 463 { 464 int ret; 465 int new_len; 466 467 new_len = p->end - p->start + name_len; 468 if (p->start != p->end) 469 new_len++; 470 ret = fs_path_ensure_buf(p, new_len); 471 if (ret < 0) 472 goto out; 473 474 if (p->reversed) { 475 if (p->start != p->end) 476 *--p->start = '/'; 477 p->start -= name_len; 478 *prepared = p->start; 479 } else { 480 if (p->start != p->end) 481 *p->end++ = '/'; 482 *prepared = p->end; 483 p->end += name_len; 484 *p->end = 0; 485 } 486 487 out: 488 return ret; 489 } 490 491 static int fs_path_add(struct fs_path *p, const char *name, int name_len) 492 { 493 int ret; 494 char *prepared; 495 496 ret = fs_path_prepare_for_add(p, name_len, &prepared); 497 if (ret < 0) 498 goto out; 499 memcpy(prepared, name, name_len); 500 501 out: 502 return ret; 503 } 504 505 static int fs_path_add_path(struct fs_path *p, struct fs_path *p2) 506 { 507 int ret; 508 char *prepared; 509 510 ret = fs_path_prepare_for_add(p, p2->end - p2->start, &prepared); 511 if (ret < 0) 512 goto out; 513 memcpy(prepared, p2->start, p2->end - p2->start); 514 515 out: 516 return ret; 517 } 518 519 static int fs_path_add_from_extent_buffer(struct fs_path *p, 520 struct extent_buffer *eb, 521 unsigned long off, int len) 522 { 523 int ret; 524 char *prepared; 525 526 ret = fs_path_prepare_for_add(p, len, &prepared); 527 if (ret < 0) 528 goto out; 529 530 read_extent_buffer(eb, prepared, off, len); 531 532 out: 533 return ret; 534 } 535 536 static int fs_path_copy(struct fs_path *p, struct fs_path *from) 537 { 538 p->reversed = from->reversed; 539 fs_path_reset(p); 540 541 return fs_path_add_path(p, from); 542 } 543 544 static void fs_path_unreverse(struct fs_path *p) 545 { 546 char *tmp; 547 int len; 548 549 if (!p->reversed) 550 return; 551 552 tmp = p->start; 553 len = p->end - p->start; 554 p->start = p->buf; 555 p->end = p->start + len; 556 memmove(p->start, tmp, len + 1); 557 p->reversed = 0; 558 } 559 560 static struct btrfs_path *alloc_path_for_send(void) 561 { 562 struct btrfs_path *path; 563 564 path = btrfs_alloc_path(); 565 if (!path) 566 return NULL; 567 path->search_commit_root = 1; 568 path->skip_locking = 1; 569 path->need_commit_sem = 1; 570 return path; 571 } 572 573 static int write_buf(struct file *filp, const void *buf, u32 len, loff_t *off) 574 { 575 int ret; 576 u32 pos = 0; 577 578 while (pos < len) { 579 ret = kernel_write(filp, buf + pos, len - pos, off); 580 /* TODO handle that correctly */ 581 /*if (ret == -ERESTARTSYS) { 582 continue; 583 }*/ 584 if (ret < 0) 585 return ret; 586 if (ret == 0) { 587 return -EIO; 588 } 589 pos += ret; 590 } 591 592 return 0; 593 } 594 595 static int tlv_put(struct send_ctx *sctx, u16 attr, const void *data, int len) 596 { 597 struct btrfs_tlv_header *hdr; 598 int total_len = sizeof(*hdr) + len; 599 int left = sctx->send_max_size - sctx->send_size; 600 601 if (unlikely(left < total_len)) 602 return -EOVERFLOW; 603 604 hdr = (struct btrfs_tlv_header *) (sctx->send_buf + sctx->send_size); 605 put_unaligned_le16(attr, &hdr->tlv_type); 606 put_unaligned_le16(len, &hdr->tlv_len); 607 memcpy(hdr + 1, data, len); 608 sctx->send_size += total_len; 609 610 return 0; 611 } 612 613 #define TLV_PUT_DEFINE_INT(bits) \ 614 static int tlv_put_u##bits(struct send_ctx *sctx, \ 615 u##bits attr, u##bits value) \ 616 { \ 617 __le##bits __tmp = cpu_to_le##bits(value); \ 618 return tlv_put(sctx, attr, &__tmp, sizeof(__tmp)); \ 619 } 620 621 TLV_PUT_DEFINE_INT(64) 622 623 static int tlv_put_string(struct send_ctx *sctx, u16 attr, 624 const char *str, int len) 625 { 626 if (len == -1) 627 len = strlen(str); 628 return tlv_put(sctx, attr, str, len); 629 } 630 631 static int tlv_put_uuid(struct send_ctx *sctx, u16 attr, 632 const u8 *uuid) 633 { 634 return tlv_put(sctx, attr, uuid, BTRFS_UUID_SIZE); 635 } 636 637 static int tlv_put_btrfs_timespec(struct send_ctx *sctx, u16 attr, 638 struct extent_buffer *eb, 639 struct btrfs_timespec *ts) 640 { 641 struct btrfs_timespec bts; 642 read_extent_buffer(eb, &bts, (unsigned long)ts, sizeof(bts)); 643 return tlv_put(sctx, attr, &bts, sizeof(bts)); 644 } 645 646 647 #define TLV_PUT(sctx, attrtype, data, attrlen) \ 648 do { \ 649 ret = tlv_put(sctx, attrtype, data, attrlen); \ 650 if (ret < 0) \ 651 goto tlv_put_failure; \ 652 } while (0) 653 654 #define TLV_PUT_INT(sctx, attrtype, bits, value) \ 655 do { \ 656 ret = tlv_put_u##bits(sctx, attrtype, value); \ 657 if (ret < 0) \ 658 goto tlv_put_failure; \ 659 } while (0) 660 661 #define TLV_PUT_U8(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 8, data) 662 #define TLV_PUT_U16(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 16, data) 663 #define TLV_PUT_U32(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 32, data) 664 #define TLV_PUT_U64(sctx, attrtype, data) TLV_PUT_INT(sctx, attrtype, 64, data) 665 #define TLV_PUT_STRING(sctx, attrtype, str, len) \ 666 do { \ 667 ret = tlv_put_string(sctx, attrtype, str, len); \ 668 if (ret < 0) \ 669 goto tlv_put_failure; \ 670 } while (0) 671 #define TLV_PUT_PATH(sctx, attrtype, p) \ 672 do { \ 673 ret = tlv_put_string(sctx, attrtype, p->start, \ 674 p->end - p->start); \ 675 if (ret < 0) \ 676 goto tlv_put_failure; \ 677 } while(0) 678 #define TLV_PUT_UUID(sctx, attrtype, uuid) \ 679 do { \ 680 ret = tlv_put_uuid(sctx, attrtype, uuid); \ 681 if (ret < 0) \ 682 goto tlv_put_failure; \ 683 } while (0) 684 #define TLV_PUT_BTRFS_TIMESPEC(sctx, attrtype, eb, ts) \ 685 do { \ 686 ret = tlv_put_btrfs_timespec(sctx, attrtype, eb, ts); \ 687 if (ret < 0) \ 688 goto tlv_put_failure; \ 689 } while (0) 690 691 static int send_header(struct send_ctx *sctx) 692 { 693 struct btrfs_stream_header hdr; 694 695 strcpy(hdr.magic, BTRFS_SEND_STREAM_MAGIC); 696 hdr.version = cpu_to_le32(BTRFS_SEND_STREAM_VERSION); 697 698 return write_buf(sctx->send_filp, &hdr, sizeof(hdr), 699 &sctx->send_off); 700 } 701 702 /* 703 * For each command/item we want to send to userspace, we call this function. 704 */ 705 static int begin_cmd(struct send_ctx *sctx, int cmd) 706 { 707 struct btrfs_cmd_header *hdr; 708 709 if (WARN_ON(!sctx->send_buf)) 710 return -EINVAL; 711 712 BUG_ON(sctx->send_size); 713 714 sctx->send_size += sizeof(*hdr); 715 hdr = (struct btrfs_cmd_header *)sctx->send_buf; 716 put_unaligned_le16(cmd, &hdr->cmd); 717 718 return 0; 719 } 720 721 static int send_cmd(struct send_ctx *sctx) 722 { 723 int ret; 724 struct btrfs_cmd_header *hdr; 725 u32 crc; 726 727 hdr = (struct btrfs_cmd_header *)sctx->send_buf; 728 put_unaligned_le32(sctx->send_size - sizeof(*hdr), &hdr->len); 729 put_unaligned_le32(0, &hdr->crc); 730 731 crc = btrfs_crc32c(0, (unsigned char *)sctx->send_buf, sctx->send_size); 732 put_unaligned_le32(crc, &hdr->crc); 733 734 ret = write_buf(sctx->send_filp, sctx->send_buf, sctx->send_size, 735 &sctx->send_off); 736 737 sctx->total_send_size += sctx->send_size; 738 sctx->cmd_send_size[get_unaligned_le16(&hdr->cmd)] += sctx->send_size; 739 sctx->send_size = 0; 740 741 return ret; 742 } 743 744 /* 745 * Sends a move instruction to user space 746 */ 747 static int send_rename(struct send_ctx *sctx, 748 struct fs_path *from, struct fs_path *to) 749 { 750 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info; 751 int ret; 752 753 btrfs_debug(fs_info, "send_rename %s -> %s", from->start, to->start); 754 755 ret = begin_cmd(sctx, BTRFS_SEND_C_RENAME); 756 if (ret < 0) 757 goto out; 758 759 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, from); 760 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH_TO, to); 761 762 ret = send_cmd(sctx); 763 764 tlv_put_failure: 765 out: 766 return ret; 767 } 768 769 /* 770 * Sends a link instruction to user space 771 */ 772 static int send_link(struct send_ctx *sctx, 773 struct fs_path *path, struct fs_path *lnk) 774 { 775 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info; 776 int ret; 777 778 btrfs_debug(fs_info, "send_link %s -> %s", path->start, lnk->start); 779 780 ret = begin_cmd(sctx, BTRFS_SEND_C_LINK); 781 if (ret < 0) 782 goto out; 783 784 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path); 785 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH_LINK, lnk); 786 787 ret = send_cmd(sctx); 788 789 tlv_put_failure: 790 out: 791 return ret; 792 } 793 794 /* 795 * Sends an unlink instruction to user space 796 */ 797 static int send_unlink(struct send_ctx *sctx, struct fs_path *path) 798 { 799 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info; 800 int ret; 801 802 btrfs_debug(fs_info, "send_unlink %s", path->start); 803 804 ret = begin_cmd(sctx, BTRFS_SEND_C_UNLINK); 805 if (ret < 0) 806 goto out; 807 808 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path); 809 810 ret = send_cmd(sctx); 811 812 tlv_put_failure: 813 out: 814 return ret; 815 } 816 817 /* 818 * Sends a rmdir instruction to user space 819 */ 820 static int send_rmdir(struct send_ctx *sctx, struct fs_path *path) 821 { 822 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info; 823 int ret; 824 825 btrfs_debug(fs_info, "send_rmdir %s", path->start); 826 827 ret = begin_cmd(sctx, BTRFS_SEND_C_RMDIR); 828 if (ret < 0) 829 goto out; 830 831 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path); 832 833 ret = send_cmd(sctx); 834 835 tlv_put_failure: 836 out: 837 return ret; 838 } 839 840 /* 841 * Helper function to retrieve some fields from an inode item. 842 */ 843 static int __get_inode_info(struct btrfs_root *root, struct btrfs_path *path, 844 u64 ino, u64 *size, u64 *gen, u64 *mode, u64 *uid, 845 u64 *gid, u64 *rdev) 846 { 847 int ret; 848 struct btrfs_inode_item *ii; 849 struct btrfs_key key; 850 851 key.objectid = ino; 852 key.type = BTRFS_INODE_ITEM_KEY; 853 key.offset = 0; 854 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 855 if (ret) { 856 if (ret > 0) 857 ret = -ENOENT; 858 return ret; 859 } 860 861 ii = btrfs_item_ptr(path->nodes[0], path->slots[0], 862 struct btrfs_inode_item); 863 if (size) 864 *size = btrfs_inode_size(path->nodes[0], ii); 865 if (gen) 866 *gen = btrfs_inode_generation(path->nodes[0], ii); 867 if (mode) 868 *mode = btrfs_inode_mode(path->nodes[0], ii); 869 if (uid) 870 *uid = btrfs_inode_uid(path->nodes[0], ii); 871 if (gid) 872 *gid = btrfs_inode_gid(path->nodes[0], ii); 873 if (rdev) 874 *rdev = btrfs_inode_rdev(path->nodes[0], ii); 875 876 return ret; 877 } 878 879 static int get_inode_info(struct btrfs_root *root, 880 u64 ino, u64 *size, u64 *gen, 881 u64 *mode, u64 *uid, u64 *gid, 882 u64 *rdev) 883 { 884 struct btrfs_path *path; 885 int ret; 886 887 path = alloc_path_for_send(); 888 if (!path) 889 return -ENOMEM; 890 ret = __get_inode_info(root, path, ino, size, gen, mode, uid, gid, 891 rdev); 892 btrfs_free_path(path); 893 return ret; 894 } 895 896 typedef int (*iterate_inode_ref_t)(int num, u64 dir, int index, 897 struct fs_path *p, 898 void *ctx); 899 900 /* 901 * Helper function to iterate the entries in ONE btrfs_inode_ref or 902 * btrfs_inode_extref. 903 * The iterate callback may return a non zero value to stop iteration. This can 904 * be a negative value for error codes or 1 to simply stop it. 905 * 906 * path must point to the INODE_REF or INODE_EXTREF when called. 907 */ 908 static int iterate_inode_ref(struct btrfs_root *root, struct btrfs_path *path, 909 struct btrfs_key *found_key, int resolve, 910 iterate_inode_ref_t iterate, void *ctx) 911 { 912 struct extent_buffer *eb = path->nodes[0]; 913 struct btrfs_inode_ref *iref; 914 struct btrfs_inode_extref *extref; 915 struct btrfs_path *tmp_path; 916 struct fs_path *p; 917 u32 cur = 0; 918 u32 total; 919 int slot = path->slots[0]; 920 u32 name_len; 921 char *start; 922 int ret = 0; 923 int num = 0; 924 int index; 925 u64 dir; 926 unsigned long name_off; 927 unsigned long elem_size; 928 unsigned long ptr; 929 930 p = fs_path_alloc_reversed(); 931 if (!p) 932 return -ENOMEM; 933 934 tmp_path = alloc_path_for_send(); 935 if (!tmp_path) { 936 fs_path_free(p); 937 return -ENOMEM; 938 } 939 940 941 if (found_key->type == BTRFS_INODE_REF_KEY) { 942 ptr = (unsigned long)btrfs_item_ptr(eb, slot, 943 struct btrfs_inode_ref); 944 total = btrfs_item_size(eb, slot); 945 elem_size = sizeof(*iref); 946 } else { 947 ptr = btrfs_item_ptr_offset(eb, slot); 948 total = btrfs_item_size(eb, slot); 949 elem_size = sizeof(*extref); 950 } 951 952 while (cur < total) { 953 fs_path_reset(p); 954 955 if (found_key->type == BTRFS_INODE_REF_KEY) { 956 iref = (struct btrfs_inode_ref *)(ptr + cur); 957 name_len = btrfs_inode_ref_name_len(eb, iref); 958 name_off = (unsigned long)(iref + 1); 959 index = btrfs_inode_ref_index(eb, iref); 960 dir = found_key->offset; 961 } else { 962 extref = (struct btrfs_inode_extref *)(ptr + cur); 963 name_len = btrfs_inode_extref_name_len(eb, extref); 964 name_off = (unsigned long)&extref->name; 965 index = btrfs_inode_extref_index(eb, extref); 966 dir = btrfs_inode_extref_parent(eb, extref); 967 } 968 969 if (resolve) { 970 start = btrfs_ref_to_path(root, tmp_path, name_len, 971 name_off, eb, dir, 972 p->buf, p->buf_len); 973 if (IS_ERR(start)) { 974 ret = PTR_ERR(start); 975 goto out; 976 } 977 if (start < p->buf) { 978 /* overflow , try again with larger buffer */ 979 ret = fs_path_ensure_buf(p, 980 p->buf_len + p->buf - start); 981 if (ret < 0) 982 goto out; 983 start = btrfs_ref_to_path(root, tmp_path, 984 name_len, name_off, 985 eb, dir, 986 p->buf, p->buf_len); 987 if (IS_ERR(start)) { 988 ret = PTR_ERR(start); 989 goto out; 990 } 991 BUG_ON(start < p->buf); 992 } 993 p->start = start; 994 } else { 995 ret = fs_path_add_from_extent_buffer(p, eb, name_off, 996 name_len); 997 if (ret < 0) 998 goto out; 999 } 1000 1001 cur += elem_size + name_len; 1002 ret = iterate(num, dir, index, p, ctx); 1003 if (ret) 1004 goto out; 1005 num++; 1006 } 1007 1008 out: 1009 btrfs_free_path(tmp_path); 1010 fs_path_free(p); 1011 return ret; 1012 } 1013 1014 typedef int (*iterate_dir_item_t)(int num, struct btrfs_key *di_key, 1015 const char *name, int name_len, 1016 const char *data, int data_len, 1017 void *ctx); 1018 1019 /* 1020 * Helper function to iterate the entries in ONE btrfs_dir_item. 1021 * The iterate callback may return a non zero value to stop iteration. This can 1022 * be a negative value for error codes or 1 to simply stop it. 1023 * 1024 * path must point to the dir item when called. 1025 */ 1026 static int iterate_dir_item(struct btrfs_root *root, struct btrfs_path *path, 1027 iterate_dir_item_t iterate, void *ctx) 1028 { 1029 int ret = 0; 1030 struct extent_buffer *eb; 1031 struct btrfs_dir_item *di; 1032 struct btrfs_key di_key; 1033 char *buf = NULL; 1034 int buf_len; 1035 u32 name_len; 1036 u32 data_len; 1037 u32 cur; 1038 u32 len; 1039 u32 total; 1040 int slot; 1041 int num; 1042 1043 /* 1044 * Start with a small buffer (1 page). If later we end up needing more 1045 * space, which can happen for xattrs on a fs with a leaf size greater 1046 * then the page size, attempt to increase the buffer. Typically xattr 1047 * values are small. 1048 */ 1049 buf_len = PATH_MAX; 1050 buf = kmalloc(buf_len, GFP_KERNEL); 1051 if (!buf) { 1052 ret = -ENOMEM; 1053 goto out; 1054 } 1055 1056 eb = path->nodes[0]; 1057 slot = path->slots[0]; 1058 di = btrfs_item_ptr(eb, slot, struct btrfs_dir_item); 1059 cur = 0; 1060 len = 0; 1061 total = btrfs_item_size(eb, slot); 1062 1063 num = 0; 1064 while (cur < total) { 1065 name_len = btrfs_dir_name_len(eb, di); 1066 data_len = btrfs_dir_data_len(eb, di); 1067 btrfs_dir_item_key_to_cpu(eb, di, &di_key); 1068 1069 if (btrfs_dir_type(eb, di) == BTRFS_FT_XATTR) { 1070 if (name_len > XATTR_NAME_MAX) { 1071 ret = -ENAMETOOLONG; 1072 goto out; 1073 } 1074 if (name_len + data_len > 1075 BTRFS_MAX_XATTR_SIZE(root->fs_info)) { 1076 ret = -E2BIG; 1077 goto out; 1078 } 1079 } else { 1080 /* 1081 * Path too long 1082 */ 1083 if (name_len + data_len > PATH_MAX) { 1084 ret = -ENAMETOOLONG; 1085 goto out; 1086 } 1087 } 1088 1089 if (name_len + data_len > buf_len) { 1090 buf_len = name_len + data_len; 1091 if (is_vmalloc_addr(buf)) { 1092 vfree(buf); 1093 buf = NULL; 1094 } else { 1095 char *tmp = krealloc(buf, buf_len, 1096 GFP_KERNEL | __GFP_NOWARN); 1097 1098 if (!tmp) 1099 kfree(buf); 1100 buf = tmp; 1101 } 1102 if (!buf) { 1103 buf = kvmalloc(buf_len, GFP_KERNEL); 1104 if (!buf) { 1105 ret = -ENOMEM; 1106 goto out; 1107 } 1108 } 1109 } 1110 1111 read_extent_buffer(eb, buf, (unsigned long)(di + 1), 1112 name_len + data_len); 1113 1114 len = sizeof(*di) + name_len + data_len; 1115 di = (struct btrfs_dir_item *)((char *)di + len); 1116 cur += len; 1117 1118 ret = iterate(num, &di_key, buf, name_len, buf + name_len, 1119 data_len, ctx); 1120 if (ret < 0) 1121 goto out; 1122 if (ret) { 1123 ret = 0; 1124 goto out; 1125 } 1126 1127 num++; 1128 } 1129 1130 out: 1131 kvfree(buf); 1132 return ret; 1133 } 1134 1135 static int __copy_first_ref(int num, u64 dir, int index, 1136 struct fs_path *p, void *ctx) 1137 { 1138 int ret; 1139 struct fs_path *pt = ctx; 1140 1141 ret = fs_path_copy(pt, p); 1142 if (ret < 0) 1143 return ret; 1144 1145 /* we want the first only */ 1146 return 1; 1147 } 1148 1149 /* 1150 * Retrieve the first path of an inode. If an inode has more then one 1151 * ref/hardlink, this is ignored. 1152 */ 1153 static int get_inode_path(struct btrfs_root *root, 1154 u64 ino, struct fs_path *path) 1155 { 1156 int ret; 1157 struct btrfs_key key, found_key; 1158 struct btrfs_path *p; 1159 1160 p = alloc_path_for_send(); 1161 if (!p) 1162 return -ENOMEM; 1163 1164 fs_path_reset(path); 1165 1166 key.objectid = ino; 1167 key.type = BTRFS_INODE_REF_KEY; 1168 key.offset = 0; 1169 1170 ret = btrfs_search_slot_for_read(root, &key, p, 1, 0); 1171 if (ret < 0) 1172 goto out; 1173 if (ret) { 1174 ret = 1; 1175 goto out; 1176 } 1177 btrfs_item_key_to_cpu(p->nodes[0], &found_key, p->slots[0]); 1178 if (found_key.objectid != ino || 1179 (found_key.type != BTRFS_INODE_REF_KEY && 1180 found_key.type != BTRFS_INODE_EXTREF_KEY)) { 1181 ret = -ENOENT; 1182 goto out; 1183 } 1184 1185 ret = iterate_inode_ref(root, p, &found_key, 1, 1186 __copy_first_ref, path); 1187 if (ret < 0) 1188 goto out; 1189 ret = 0; 1190 1191 out: 1192 btrfs_free_path(p); 1193 return ret; 1194 } 1195 1196 struct backref_ctx { 1197 struct send_ctx *sctx; 1198 1199 /* number of total found references */ 1200 u64 found; 1201 1202 /* 1203 * used for clones found in send_root. clones found behind cur_objectid 1204 * and cur_offset are not considered as allowed clones. 1205 */ 1206 u64 cur_objectid; 1207 u64 cur_offset; 1208 1209 /* may be truncated in case it's the last extent in a file */ 1210 u64 extent_len; 1211 1212 /* Just to check for bugs in backref resolving */ 1213 int found_itself; 1214 }; 1215 1216 static int __clone_root_cmp_bsearch(const void *key, const void *elt) 1217 { 1218 u64 root = (u64)(uintptr_t)key; 1219 const struct clone_root *cr = elt; 1220 1221 if (root < cr->root->root_key.objectid) 1222 return -1; 1223 if (root > cr->root->root_key.objectid) 1224 return 1; 1225 return 0; 1226 } 1227 1228 static int __clone_root_cmp_sort(const void *e1, const void *e2) 1229 { 1230 const struct clone_root *cr1 = e1; 1231 const struct clone_root *cr2 = e2; 1232 1233 if (cr1->root->root_key.objectid < cr2->root->root_key.objectid) 1234 return -1; 1235 if (cr1->root->root_key.objectid > cr2->root->root_key.objectid) 1236 return 1; 1237 return 0; 1238 } 1239 1240 /* 1241 * Called for every backref that is found for the current extent. 1242 * Results are collected in sctx->clone_roots->ino/offset/found_refs 1243 */ 1244 static int __iterate_backrefs(u64 ino, u64 offset, u64 root, void *ctx_) 1245 { 1246 struct backref_ctx *bctx = ctx_; 1247 struct clone_root *found; 1248 1249 /* First check if the root is in the list of accepted clone sources */ 1250 found = bsearch((void *)(uintptr_t)root, bctx->sctx->clone_roots, 1251 bctx->sctx->clone_roots_cnt, 1252 sizeof(struct clone_root), 1253 __clone_root_cmp_bsearch); 1254 if (!found) 1255 return 0; 1256 1257 if (found->root == bctx->sctx->send_root && 1258 ino == bctx->cur_objectid && 1259 offset == bctx->cur_offset) { 1260 bctx->found_itself = 1; 1261 } 1262 1263 /* 1264 * Make sure we don't consider clones from send_root that are 1265 * behind the current inode/offset. 1266 */ 1267 if (found->root == bctx->sctx->send_root) { 1268 /* 1269 * If the source inode was not yet processed we can't issue a 1270 * clone operation, as the source extent does not exist yet at 1271 * the destination of the stream. 1272 */ 1273 if (ino > bctx->cur_objectid) 1274 return 0; 1275 /* 1276 * We clone from the inode currently being sent as long as the 1277 * source extent is already processed, otherwise we could try 1278 * to clone from an extent that does not exist yet at the 1279 * destination of the stream. 1280 */ 1281 if (ino == bctx->cur_objectid && 1282 offset + bctx->extent_len > 1283 bctx->sctx->cur_inode_next_write_offset) 1284 return 0; 1285 } 1286 1287 bctx->found++; 1288 found->found_refs++; 1289 if (ino < found->ino) { 1290 found->ino = ino; 1291 found->offset = offset; 1292 } else if (found->ino == ino) { 1293 /* 1294 * same extent found more then once in the same file. 1295 */ 1296 if (found->offset > offset + bctx->extent_len) 1297 found->offset = offset; 1298 } 1299 1300 return 0; 1301 } 1302 1303 /* 1304 * Given an inode, offset and extent item, it finds a good clone for a clone 1305 * instruction. Returns -ENOENT when none could be found. The function makes 1306 * sure that the returned clone is usable at the point where sending is at the 1307 * moment. This means, that no clones are accepted which lie behind the current 1308 * inode+offset. 1309 * 1310 * path must point to the extent item when called. 1311 */ 1312 static int find_extent_clone(struct send_ctx *sctx, 1313 struct btrfs_path *path, 1314 u64 ino, u64 data_offset, 1315 u64 ino_size, 1316 struct clone_root **found) 1317 { 1318 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info; 1319 int ret; 1320 int extent_type; 1321 u64 logical; 1322 u64 disk_byte; 1323 u64 num_bytes; 1324 u64 extent_item_pos; 1325 u64 flags = 0; 1326 struct btrfs_file_extent_item *fi; 1327 struct extent_buffer *eb = path->nodes[0]; 1328 struct backref_ctx backref_ctx = {0}; 1329 struct clone_root *cur_clone_root; 1330 struct btrfs_key found_key; 1331 struct btrfs_path *tmp_path; 1332 struct btrfs_extent_item *ei; 1333 int compressed; 1334 u32 i; 1335 1336 tmp_path = alloc_path_for_send(); 1337 if (!tmp_path) 1338 return -ENOMEM; 1339 1340 /* We only use this path under the commit sem */ 1341 tmp_path->need_commit_sem = 0; 1342 1343 if (data_offset >= ino_size) { 1344 /* 1345 * There may be extents that lie behind the file's size. 1346 * I at least had this in combination with snapshotting while 1347 * writing large files. 1348 */ 1349 ret = 0; 1350 goto out; 1351 } 1352 1353 fi = btrfs_item_ptr(eb, path->slots[0], 1354 struct btrfs_file_extent_item); 1355 extent_type = btrfs_file_extent_type(eb, fi); 1356 if (extent_type == BTRFS_FILE_EXTENT_INLINE) { 1357 ret = -ENOENT; 1358 goto out; 1359 } 1360 compressed = btrfs_file_extent_compression(eb, fi); 1361 1362 num_bytes = btrfs_file_extent_num_bytes(eb, fi); 1363 disk_byte = btrfs_file_extent_disk_bytenr(eb, fi); 1364 if (disk_byte == 0) { 1365 ret = -ENOENT; 1366 goto out; 1367 } 1368 logical = disk_byte + btrfs_file_extent_offset(eb, fi); 1369 1370 down_read(&fs_info->commit_root_sem); 1371 ret = extent_from_logical(fs_info, disk_byte, tmp_path, 1372 &found_key, &flags); 1373 up_read(&fs_info->commit_root_sem); 1374 1375 if (ret < 0) 1376 goto out; 1377 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) { 1378 ret = -EIO; 1379 goto out; 1380 } 1381 1382 ei = btrfs_item_ptr(tmp_path->nodes[0], tmp_path->slots[0], 1383 struct btrfs_extent_item); 1384 /* 1385 * Backreference walking (iterate_extent_inodes() below) is currently 1386 * too expensive when an extent has a large number of references, both 1387 * in time spent and used memory. So for now just fallback to write 1388 * operations instead of clone operations when an extent has more than 1389 * a certain amount of references. 1390 */ 1391 if (btrfs_extent_refs(tmp_path->nodes[0], ei) > SEND_MAX_EXTENT_REFS) { 1392 ret = -ENOENT; 1393 goto out; 1394 } 1395 btrfs_release_path(tmp_path); 1396 1397 /* 1398 * Setup the clone roots. 1399 */ 1400 for (i = 0; i < sctx->clone_roots_cnt; i++) { 1401 cur_clone_root = sctx->clone_roots + i; 1402 cur_clone_root->ino = (u64)-1; 1403 cur_clone_root->offset = 0; 1404 cur_clone_root->found_refs = 0; 1405 } 1406 1407 backref_ctx.sctx = sctx; 1408 backref_ctx.found = 0; 1409 backref_ctx.cur_objectid = ino; 1410 backref_ctx.cur_offset = data_offset; 1411 backref_ctx.found_itself = 0; 1412 backref_ctx.extent_len = num_bytes; 1413 1414 /* 1415 * The last extent of a file may be too large due to page alignment. 1416 * We need to adjust extent_len in this case so that the checks in 1417 * __iterate_backrefs work. 1418 */ 1419 if (data_offset + num_bytes >= ino_size) 1420 backref_ctx.extent_len = ino_size - data_offset; 1421 1422 /* 1423 * Now collect all backrefs. 1424 */ 1425 if (compressed == BTRFS_COMPRESS_NONE) 1426 extent_item_pos = logical - found_key.objectid; 1427 else 1428 extent_item_pos = 0; 1429 ret = iterate_extent_inodes(fs_info, found_key.objectid, 1430 extent_item_pos, 1, __iterate_backrefs, 1431 &backref_ctx, false); 1432 1433 if (ret < 0) 1434 goto out; 1435 1436 down_read(&fs_info->commit_root_sem); 1437 if (fs_info->last_reloc_trans > sctx->last_reloc_trans) { 1438 /* 1439 * A transaction commit for a transaction in which block group 1440 * relocation was done just happened. 1441 * The disk_bytenr of the file extent item we processed is 1442 * possibly stale, referring to the extent's location before 1443 * relocation. So act as if we haven't found any clone sources 1444 * and fallback to write commands, which will read the correct 1445 * data from the new extent location. Otherwise we will fail 1446 * below because we haven't found our own back reference or we 1447 * could be getting incorrect sources in case the old extent 1448 * was already reallocated after the relocation. 1449 */ 1450 up_read(&fs_info->commit_root_sem); 1451 ret = -ENOENT; 1452 goto out; 1453 } 1454 up_read(&fs_info->commit_root_sem); 1455 1456 if (!backref_ctx.found_itself) { 1457 /* found a bug in backref code? */ 1458 ret = -EIO; 1459 btrfs_err(fs_info, 1460 "did not find backref in send_root. inode=%llu, offset=%llu, disk_byte=%llu found extent=%llu", 1461 ino, data_offset, disk_byte, found_key.objectid); 1462 goto out; 1463 } 1464 1465 btrfs_debug(fs_info, 1466 "find_extent_clone: data_offset=%llu, ino=%llu, num_bytes=%llu, logical=%llu", 1467 data_offset, ino, num_bytes, logical); 1468 1469 if (!backref_ctx.found) 1470 btrfs_debug(fs_info, "no clones found"); 1471 1472 cur_clone_root = NULL; 1473 for (i = 0; i < sctx->clone_roots_cnt; i++) { 1474 if (sctx->clone_roots[i].found_refs) { 1475 if (!cur_clone_root) 1476 cur_clone_root = sctx->clone_roots + i; 1477 else if (sctx->clone_roots[i].root == sctx->send_root) 1478 /* prefer clones from send_root over others */ 1479 cur_clone_root = sctx->clone_roots + i; 1480 } 1481 1482 } 1483 1484 if (cur_clone_root) { 1485 *found = cur_clone_root; 1486 ret = 0; 1487 } else { 1488 ret = -ENOENT; 1489 } 1490 1491 out: 1492 btrfs_free_path(tmp_path); 1493 return ret; 1494 } 1495 1496 static int read_symlink(struct btrfs_root *root, 1497 u64 ino, 1498 struct fs_path *dest) 1499 { 1500 int ret; 1501 struct btrfs_path *path; 1502 struct btrfs_key key; 1503 struct btrfs_file_extent_item *ei; 1504 u8 type; 1505 u8 compression; 1506 unsigned long off; 1507 int len; 1508 1509 path = alloc_path_for_send(); 1510 if (!path) 1511 return -ENOMEM; 1512 1513 key.objectid = ino; 1514 key.type = BTRFS_EXTENT_DATA_KEY; 1515 key.offset = 0; 1516 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 1517 if (ret < 0) 1518 goto out; 1519 if (ret) { 1520 /* 1521 * An empty symlink inode. Can happen in rare error paths when 1522 * creating a symlink (transaction committed before the inode 1523 * eviction handler removed the symlink inode items and a crash 1524 * happened in between or the subvol was snapshoted in between). 1525 * Print an informative message to dmesg/syslog so that the user 1526 * can delete the symlink. 1527 */ 1528 btrfs_err(root->fs_info, 1529 "Found empty symlink inode %llu at root %llu", 1530 ino, root->root_key.objectid); 1531 ret = -EIO; 1532 goto out; 1533 } 1534 1535 ei = btrfs_item_ptr(path->nodes[0], path->slots[0], 1536 struct btrfs_file_extent_item); 1537 type = btrfs_file_extent_type(path->nodes[0], ei); 1538 compression = btrfs_file_extent_compression(path->nodes[0], ei); 1539 BUG_ON(type != BTRFS_FILE_EXTENT_INLINE); 1540 BUG_ON(compression); 1541 1542 off = btrfs_file_extent_inline_start(ei); 1543 len = btrfs_file_extent_ram_bytes(path->nodes[0], ei); 1544 1545 ret = fs_path_add_from_extent_buffer(dest, path->nodes[0], off, len); 1546 1547 out: 1548 btrfs_free_path(path); 1549 return ret; 1550 } 1551 1552 /* 1553 * Helper function to generate a file name that is unique in the root of 1554 * send_root and parent_root. This is used to generate names for orphan inodes. 1555 */ 1556 static int gen_unique_name(struct send_ctx *sctx, 1557 u64 ino, u64 gen, 1558 struct fs_path *dest) 1559 { 1560 int ret = 0; 1561 struct btrfs_path *path; 1562 struct btrfs_dir_item *di; 1563 char tmp[64]; 1564 int len; 1565 u64 idx = 0; 1566 1567 path = alloc_path_for_send(); 1568 if (!path) 1569 return -ENOMEM; 1570 1571 while (1) { 1572 len = snprintf(tmp, sizeof(tmp), "o%llu-%llu-%llu", 1573 ino, gen, idx); 1574 ASSERT(len < sizeof(tmp)); 1575 1576 di = btrfs_lookup_dir_item(NULL, sctx->send_root, 1577 path, BTRFS_FIRST_FREE_OBJECTID, 1578 tmp, strlen(tmp), 0); 1579 btrfs_release_path(path); 1580 if (IS_ERR(di)) { 1581 ret = PTR_ERR(di); 1582 goto out; 1583 } 1584 if (di) { 1585 /* not unique, try again */ 1586 idx++; 1587 continue; 1588 } 1589 1590 if (!sctx->parent_root) { 1591 /* unique */ 1592 ret = 0; 1593 break; 1594 } 1595 1596 di = btrfs_lookup_dir_item(NULL, sctx->parent_root, 1597 path, BTRFS_FIRST_FREE_OBJECTID, 1598 tmp, strlen(tmp), 0); 1599 btrfs_release_path(path); 1600 if (IS_ERR(di)) { 1601 ret = PTR_ERR(di); 1602 goto out; 1603 } 1604 if (di) { 1605 /* not unique, try again */ 1606 idx++; 1607 continue; 1608 } 1609 /* unique */ 1610 break; 1611 } 1612 1613 ret = fs_path_add(dest, tmp, strlen(tmp)); 1614 1615 out: 1616 btrfs_free_path(path); 1617 return ret; 1618 } 1619 1620 enum inode_state { 1621 inode_state_no_change, 1622 inode_state_will_create, 1623 inode_state_did_create, 1624 inode_state_will_delete, 1625 inode_state_did_delete, 1626 }; 1627 1628 static int get_cur_inode_state(struct send_ctx *sctx, u64 ino, u64 gen) 1629 { 1630 int ret; 1631 int left_ret; 1632 int right_ret; 1633 u64 left_gen; 1634 u64 right_gen; 1635 1636 ret = get_inode_info(sctx->send_root, ino, NULL, &left_gen, NULL, NULL, 1637 NULL, NULL); 1638 if (ret < 0 && ret != -ENOENT) 1639 goto out; 1640 left_ret = ret; 1641 1642 if (!sctx->parent_root) { 1643 right_ret = -ENOENT; 1644 } else { 1645 ret = get_inode_info(sctx->parent_root, ino, NULL, &right_gen, 1646 NULL, NULL, NULL, NULL); 1647 if (ret < 0 && ret != -ENOENT) 1648 goto out; 1649 right_ret = ret; 1650 } 1651 1652 if (!left_ret && !right_ret) { 1653 if (left_gen == gen && right_gen == gen) { 1654 ret = inode_state_no_change; 1655 } else if (left_gen == gen) { 1656 if (ino < sctx->send_progress) 1657 ret = inode_state_did_create; 1658 else 1659 ret = inode_state_will_create; 1660 } else if (right_gen == gen) { 1661 if (ino < sctx->send_progress) 1662 ret = inode_state_did_delete; 1663 else 1664 ret = inode_state_will_delete; 1665 } else { 1666 ret = -ENOENT; 1667 } 1668 } else if (!left_ret) { 1669 if (left_gen == gen) { 1670 if (ino < sctx->send_progress) 1671 ret = inode_state_did_create; 1672 else 1673 ret = inode_state_will_create; 1674 } else { 1675 ret = -ENOENT; 1676 } 1677 } else if (!right_ret) { 1678 if (right_gen == gen) { 1679 if (ino < sctx->send_progress) 1680 ret = inode_state_did_delete; 1681 else 1682 ret = inode_state_will_delete; 1683 } else { 1684 ret = -ENOENT; 1685 } 1686 } else { 1687 ret = -ENOENT; 1688 } 1689 1690 out: 1691 return ret; 1692 } 1693 1694 static int is_inode_existent(struct send_ctx *sctx, u64 ino, u64 gen) 1695 { 1696 int ret; 1697 1698 if (ino == BTRFS_FIRST_FREE_OBJECTID) 1699 return 1; 1700 1701 ret = get_cur_inode_state(sctx, ino, gen); 1702 if (ret < 0) 1703 goto out; 1704 1705 if (ret == inode_state_no_change || 1706 ret == inode_state_did_create || 1707 ret == inode_state_will_delete) 1708 ret = 1; 1709 else 1710 ret = 0; 1711 1712 out: 1713 return ret; 1714 } 1715 1716 /* 1717 * Helper function to lookup a dir item in a dir. 1718 */ 1719 static int lookup_dir_item_inode(struct btrfs_root *root, 1720 u64 dir, const char *name, int name_len, 1721 u64 *found_inode) 1722 { 1723 int ret = 0; 1724 struct btrfs_dir_item *di; 1725 struct btrfs_key key; 1726 struct btrfs_path *path; 1727 1728 path = alloc_path_for_send(); 1729 if (!path) 1730 return -ENOMEM; 1731 1732 di = btrfs_lookup_dir_item(NULL, root, path, 1733 dir, name, name_len, 0); 1734 if (IS_ERR_OR_NULL(di)) { 1735 ret = di ? PTR_ERR(di) : -ENOENT; 1736 goto out; 1737 } 1738 btrfs_dir_item_key_to_cpu(path->nodes[0], di, &key); 1739 if (key.type == BTRFS_ROOT_ITEM_KEY) { 1740 ret = -ENOENT; 1741 goto out; 1742 } 1743 *found_inode = key.objectid; 1744 1745 out: 1746 btrfs_free_path(path); 1747 return ret; 1748 } 1749 1750 /* 1751 * Looks up the first btrfs_inode_ref of a given ino. It returns the parent dir, 1752 * generation of the parent dir and the name of the dir entry. 1753 */ 1754 static int get_first_ref(struct btrfs_root *root, u64 ino, 1755 u64 *dir, u64 *dir_gen, struct fs_path *name) 1756 { 1757 int ret; 1758 struct btrfs_key key; 1759 struct btrfs_key found_key; 1760 struct btrfs_path *path; 1761 int len; 1762 u64 parent_dir; 1763 1764 path = alloc_path_for_send(); 1765 if (!path) 1766 return -ENOMEM; 1767 1768 key.objectid = ino; 1769 key.type = BTRFS_INODE_REF_KEY; 1770 key.offset = 0; 1771 1772 ret = btrfs_search_slot_for_read(root, &key, path, 1, 0); 1773 if (ret < 0) 1774 goto out; 1775 if (!ret) 1776 btrfs_item_key_to_cpu(path->nodes[0], &found_key, 1777 path->slots[0]); 1778 if (ret || found_key.objectid != ino || 1779 (found_key.type != BTRFS_INODE_REF_KEY && 1780 found_key.type != BTRFS_INODE_EXTREF_KEY)) { 1781 ret = -ENOENT; 1782 goto out; 1783 } 1784 1785 if (found_key.type == BTRFS_INODE_REF_KEY) { 1786 struct btrfs_inode_ref *iref; 1787 iref = btrfs_item_ptr(path->nodes[0], path->slots[0], 1788 struct btrfs_inode_ref); 1789 len = btrfs_inode_ref_name_len(path->nodes[0], iref); 1790 ret = fs_path_add_from_extent_buffer(name, path->nodes[0], 1791 (unsigned long)(iref + 1), 1792 len); 1793 parent_dir = found_key.offset; 1794 } else { 1795 struct btrfs_inode_extref *extref; 1796 extref = btrfs_item_ptr(path->nodes[0], path->slots[0], 1797 struct btrfs_inode_extref); 1798 len = btrfs_inode_extref_name_len(path->nodes[0], extref); 1799 ret = fs_path_add_from_extent_buffer(name, path->nodes[0], 1800 (unsigned long)&extref->name, len); 1801 parent_dir = btrfs_inode_extref_parent(path->nodes[0], extref); 1802 } 1803 if (ret < 0) 1804 goto out; 1805 btrfs_release_path(path); 1806 1807 if (dir_gen) { 1808 ret = get_inode_info(root, parent_dir, NULL, dir_gen, NULL, 1809 NULL, NULL, NULL); 1810 if (ret < 0) 1811 goto out; 1812 } 1813 1814 *dir = parent_dir; 1815 1816 out: 1817 btrfs_free_path(path); 1818 return ret; 1819 } 1820 1821 static int is_first_ref(struct btrfs_root *root, 1822 u64 ino, u64 dir, 1823 const char *name, int name_len) 1824 { 1825 int ret; 1826 struct fs_path *tmp_name; 1827 u64 tmp_dir; 1828 1829 tmp_name = fs_path_alloc(); 1830 if (!tmp_name) 1831 return -ENOMEM; 1832 1833 ret = get_first_ref(root, ino, &tmp_dir, NULL, tmp_name); 1834 if (ret < 0) 1835 goto out; 1836 1837 if (dir != tmp_dir || name_len != fs_path_len(tmp_name)) { 1838 ret = 0; 1839 goto out; 1840 } 1841 1842 ret = !memcmp(tmp_name->start, name, name_len); 1843 1844 out: 1845 fs_path_free(tmp_name); 1846 return ret; 1847 } 1848 1849 /* 1850 * Used by process_recorded_refs to determine if a new ref would overwrite an 1851 * already existing ref. In case it detects an overwrite, it returns the 1852 * inode/gen in who_ino/who_gen. 1853 * When an overwrite is detected, process_recorded_refs does proper orphanizing 1854 * to make sure later references to the overwritten inode are possible. 1855 * Orphanizing is however only required for the first ref of an inode. 1856 * process_recorded_refs does an additional is_first_ref check to see if 1857 * orphanizing is really required. 1858 */ 1859 static int will_overwrite_ref(struct send_ctx *sctx, u64 dir, u64 dir_gen, 1860 const char *name, int name_len, 1861 u64 *who_ino, u64 *who_gen, u64 *who_mode) 1862 { 1863 int ret = 0; 1864 u64 gen; 1865 u64 other_inode = 0; 1866 1867 if (!sctx->parent_root) 1868 goto out; 1869 1870 ret = is_inode_existent(sctx, dir, dir_gen); 1871 if (ret <= 0) 1872 goto out; 1873 1874 /* 1875 * If we have a parent root we need to verify that the parent dir was 1876 * not deleted and then re-created, if it was then we have no overwrite 1877 * and we can just unlink this entry. 1878 */ 1879 if (sctx->parent_root && dir != BTRFS_FIRST_FREE_OBJECTID) { 1880 ret = get_inode_info(sctx->parent_root, dir, NULL, &gen, NULL, 1881 NULL, NULL, NULL); 1882 if (ret < 0 && ret != -ENOENT) 1883 goto out; 1884 if (ret) { 1885 ret = 0; 1886 goto out; 1887 } 1888 if (gen != dir_gen) 1889 goto out; 1890 } 1891 1892 ret = lookup_dir_item_inode(sctx->parent_root, dir, name, name_len, 1893 &other_inode); 1894 if (ret < 0 && ret != -ENOENT) 1895 goto out; 1896 if (ret) { 1897 ret = 0; 1898 goto out; 1899 } 1900 1901 /* 1902 * Check if the overwritten ref was already processed. If yes, the ref 1903 * was already unlinked/moved, so we can safely assume that we will not 1904 * overwrite anything at this point in time. 1905 */ 1906 if (other_inode > sctx->send_progress || 1907 is_waiting_for_move(sctx, other_inode)) { 1908 ret = get_inode_info(sctx->parent_root, other_inode, NULL, 1909 who_gen, who_mode, NULL, NULL, NULL); 1910 if (ret < 0) 1911 goto out; 1912 1913 ret = 1; 1914 *who_ino = other_inode; 1915 } else { 1916 ret = 0; 1917 } 1918 1919 out: 1920 return ret; 1921 } 1922 1923 /* 1924 * Checks if the ref was overwritten by an already processed inode. This is 1925 * used by __get_cur_name_and_parent to find out if the ref was orphanized and 1926 * thus the orphan name needs be used. 1927 * process_recorded_refs also uses it to avoid unlinking of refs that were 1928 * overwritten. 1929 */ 1930 static int did_overwrite_ref(struct send_ctx *sctx, 1931 u64 dir, u64 dir_gen, 1932 u64 ino, u64 ino_gen, 1933 const char *name, int name_len) 1934 { 1935 int ret = 0; 1936 u64 gen; 1937 u64 ow_inode; 1938 1939 if (!sctx->parent_root) 1940 goto out; 1941 1942 ret = is_inode_existent(sctx, dir, dir_gen); 1943 if (ret <= 0) 1944 goto out; 1945 1946 if (dir != BTRFS_FIRST_FREE_OBJECTID) { 1947 ret = get_inode_info(sctx->send_root, dir, NULL, &gen, NULL, 1948 NULL, NULL, NULL); 1949 if (ret < 0 && ret != -ENOENT) 1950 goto out; 1951 if (ret) { 1952 ret = 0; 1953 goto out; 1954 } 1955 if (gen != dir_gen) 1956 goto out; 1957 } 1958 1959 /* check if the ref was overwritten by another ref */ 1960 ret = lookup_dir_item_inode(sctx->send_root, dir, name, name_len, 1961 &ow_inode); 1962 if (ret < 0 && ret != -ENOENT) 1963 goto out; 1964 if (ret) { 1965 /* was never and will never be overwritten */ 1966 ret = 0; 1967 goto out; 1968 } 1969 1970 ret = get_inode_info(sctx->send_root, ow_inode, NULL, &gen, NULL, NULL, 1971 NULL, NULL); 1972 if (ret < 0) 1973 goto out; 1974 1975 if (ow_inode == ino && gen == ino_gen) { 1976 ret = 0; 1977 goto out; 1978 } 1979 1980 /* 1981 * We know that it is or will be overwritten. Check this now. 1982 * The current inode being processed might have been the one that caused 1983 * inode 'ino' to be orphanized, therefore check if ow_inode matches 1984 * the current inode being processed. 1985 */ 1986 if ((ow_inode < sctx->send_progress) || 1987 (ino != sctx->cur_ino && ow_inode == sctx->cur_ino && 1988 gen == sctx->cur_inode_gen)) 1989 ret = 1; 1990 else 1991 ret = 0; 1992 1993 out: 1994 return ret; 1995 } 1996 1997 /* 1998 * Same as did_overwrite_ref, but also checks if it is the first ref of an inode 1999 * that got overwritten. This is used by process_recorded_refs to determine 2000 * if it has to use the path as returned by get_cur_path or the orphan name. 2001 */ 2002 static int did_overwrite_first_ref(struct send_ctx *sctx, u64 ino, u64 gen) 2003 { 2004 int ret = 0; 2005 struct fs_path *name = NULL; 2006 u64 dir; 2007 u64 dir_gen; 2008 2009 if (!sctx->parent_root) 2010 goto out; 2011 2012 name = fs_path_alloc(); 2013 if (!name) 2014 return -ENOMEM; 2015 2016 ret = get_first_ref(sctx->parent_root, ino, &dir, &dir_gen, name); 2017 if (ret < 0) 2018 goto out; 2019 2020 ret = did_overwrite_ref(sctx, dir, dir_gen, ino, gen, 2021 name->start, fs_path_len(name)); 2022 2023 out: 2024 fs_path_free(name); 2025 return ret; 2026 } 2027 2028 /* 2029 * Insert a name cache entry. On 32bit kernels the radix tree index is 32bit, 2030 * so we need to do some special handling in case we have clashes. This function 2031 * takes care of this with the help of name_cache_entry::radix_list. 2032 * In case of error, nce is kfreed. 2033 */ 2034 static int name_cache_insert(struct send_ctx *sctx, 2035 struct name_cache_entry *nce) 2036 { 2037 int ret = 0; 2038 struct list_head *nce_head; 2039 2040 nce_head = radix_tree_lookup(&sctx->name_cache, 2041 (unsigned long)nce->ino); 2042 if (!nce_head) { 2043 nce_head = kmalloc(sizeof(*nce_head), GFP_KERNEL); 2044 if (!nce_head) { 2045 kfree(nce); 2046 return -ENOMEM; 2047 } 2048 INIT_LIST_HEAD(nce_head); 2049 2050 ret = radix_tree_insert(&sctx->name_cache, nce->ino, nce_head); 2051 if (ret < 0) { 2052 kfree(nce_head); 2053 kfree(nce); 2054 return ret; 2055 } 2056 } 2057 list_add_tail(&nce->radix_list, nce_head); 2058 list_add_tail(&nce->list, &sctx->name_cache_list); 2059 sctx->name_cache_size++; 2060 2061 return ret; 2062 } 2063 2064 static void name_cache_delete(struct send_ctx *sctx, 2065 struct name_cache_entry *nce) 2066 { 2067 struct list_head *nce_head; 2068 2069 nce_head = radix_tree_lookup(&sctx->name_cache, 2070 (unsigned long)nce->ino); 2071 if (!nce_head) { 2072 btrfs_err(sctx->send_root->fs_info, 2073 "name_cache_delete lookup failed ino %llu cache size %d, leaking memory", 2074 nce->ino, sctx->name_cache_size); 2075 } 2076 2077 list_del(&nce->radix_list); 2078 list_del(&nce->list); 2079 sctx->name_cache_size--; 2080 2081 /* 2082 * We may not get to the final release of nce_head if the lookup fails 2083 */ 2084 if (nce_head && list_empty(nce_head)) { 2085 radix_tree_delete(&sctx->name_cache, (unsigned long)nce->ino); 2086 kfree(nce_head); 2087 } 2088 } 2089 2090 static struct name_cache_entry *name_cache_search(struct send_ctx *sctx, 2091 u64 ino, u64 gen) 2092 { 2093 struct list_head *nce_head; 2094 struct name_cache_entry *cur; 2095 2096 nce_head = radix_tree_lookup(&sctx->name_cache, (unsigned long)ino); 2097 if (!nce_head) 2098 return NULL; 2099 2100 list_for_each_entry(cur, nce_head, radix_list) { 2101 if (cur->ino == ino && cur->gen == gen) 2102 return cur; 2103 } 2104 return NULL; 2105 } 2106 2107 /* 2108 * Remove some entries from the beginning of name_cache_list. 2109 */ 2110 static void name_cache_clean_unused(struct send_ctx *sctx) 2111 { 2112 struct name_cache_entry *nce; 2113 2114 if (sctx->name_cache_size < SEND_CTX_NAME_CACHE_CLEAN_SIZE) 2115 return; 2116 2117 while (sctx->name_cache_size > SEND_CTX_MAX_NAME_CACHE_SIZE) { 2118 nce = list_entry(sctx->name_cache_list.next, 2119 struct name_cache_entry, list); 2120 name_cache_delete(sctx, nce); 2121 kfree(nce); 2122 } 2123 } 2124 2125 static void name_cache_free(struct send_ctx *sctx) 2126 { 2127 struct name_cache_entry *nce; 2128 2129 while (!list_empty(&sctx->name_cache_list)) { 2130 nce = list_entry(sctx->name_cache_list.next, 2131 struct name_cache_entry, list); 2132 name_cache_delete(sctx, nce); 2133 kfree(nce); 2134 } 2135 } 2136 2137 /* 2138 * Used by get_cur_path for each ref up to the root. 2139 * Returns 0 if it succeeded. 2140 * Returns 1 if the inode is not existent or got overwritten. In that case, the 2141 * name is an orphan name. This instructs get_cur_path to stop iterating. If 1 2142 * is returned, parent_ino/parent_gen are not guaranteed to be valid. 2143 * Returns <0 in case of error. 2144 */ 2145 static int __get_cur_name_and_parent(struct send_ctx *sctx, 2146 u64 ino, u64 gen, 2147 u64 *parent_ino, 2148 u64 *parent_gen, 2149 struct fs_path *dest) 2150 { 2151 int ret; 2152 int nce_ret; 2153 struct name_cache_entry *nce = NULL; 2154 2155 /* 2156 * First check if we already did a call to this function with the same 2157 * ino/gen. If yes, check if the cache entry is still up-to-date. If yes 2158 * return the cached result. 2159 */ 2160 nce = name_cache_search(sctx, ino, gen); 2161 if (nce) { 2162 if (ino < sctx->send_progress && nce->need_later_update) { 2163 name_cache_delete(sctx, nce); 2164 kfree(nce); 2165 nce = NULL; 2166 } else { 2167 /* 2168 * Removes the entry from the list and adds it back to 2169 * the end. This marks the entry as recently used so 2170 * that name_cache_clean_unused does not remove it. 2171 */ 2172 list_move_tail(&nce->list, &sctx->name_cache_list); 2173 2174 *parent_ino = nce->parent_ino; 2175 *parent_gen = nce->parent_gen; 2176 ret = fs_path_add(dest, nce->name, nce->name_len); 2177 if (ret < 0) 2178 goto out; 2179 ret = nce->ret; 2180 goto out; 2181 } 2182 } 2183 2184 /* 2185 * If the inode is not existent yet, add the orphan name and return 1. 2186 * This should only happen for the parent dir that we determine in 2187 * __record_new_ref 2188 */ 2189 ret = is_inode_existent(sctx, ino, gen); 2190 if (ret < 0) 2191 goto out; 2192 2193 if (!ret) { 2194 ret = gen_unique_name(sctx, ino, gen, dest); 2195 if (ret < 0) 2196 goto out; 2197 ret = 1; 2198 goto out_cache; 2199 } 2200 2201 /* 2202 * Depending on whether the inode was already processed or not, use 2203 * send_root or parent_root for ref lookup. 2204 */ 2205 if (ino < sctx->send_progress) 2206 ret = get_first_ref(sctx->send_root, ino, 2207 parent_ino, parent_gen, dest); 2208 else 2209 ret = get_first_ref(sctx->parent_root, ino, 2210 parent_ino, parent_gen, dest); 2211 if (ret < 0) 2212 goto out; 2213 2214 /* 2215 * Check if the ref was overwritten by an inode's ref that was processed 2216 * earlier. If yes, treat as orphan and return 1. 2217 */ 2218 ret = did_overwrite_ref(sctx, *parent_ino, *parent_gen, ino, gen, 2219 dest->start, dest->end - dest->start); 2220 if (ret < 0) 2221 goto out; 2222 if (ret) { 2223 fs_path_reset(dest); 2224 ret = gen_unique_name(sctx, ino, gen, dest); 2225 if (ret < 0) 2226 goto out; 2227 ret = 1; 2228 } 2229 2230 out_cache: 2231 /* 2232 * Store the result of the lookup in the name cache. 2233 */ 2234 nce = kmalloc(sizeof(*nce) + fs_path_len(dest) + 1, GFP_KERNEL); 2235 if (!nce) { 2236 ret = -ENOMEM; 2237 goto out; 2238 } 2239 2240 nce->ino = ino; 2241 nce->gen = gen; 2242 nce->parent_ino = *parent_ino; 2243 nce->parent_gen = *parent_gen; 2244 nce->name_len = fs_path_len(dest); 2245 nce->ret = ret; 2246 strcpy(nce->name, dest->start); 2247 2248 if (ino < sctx->send_progress) 2249 nce->need_later_update = 0; 2250 else 2251 nce->need_later_update = 1; 2252 2253 nce_ret = name_cache_insert(sctx, nce); 2254 if (nce_ret < 0) 2255 ret = nce_ret; 2256 name_cache_clean_unused(sctx); 2257 2258 out: 2259 return ret; 2260 } 2261 2262 /* 2263 * Magic happens here. This function returns the first ref to an inode as it 2264 * would look like while receiving the stream at this point in time. 2265 * We walk the path up to the root. For every inode in between, we check if it 2266 * was already processed/sent. If yes, we continue with the parent as found 2267 * in send_root. If not, we continue with the parent as found in parent_root. 2268 * If we encounter an inode that was deleted at this point in time, we use the 2269 * inodes "orphan" name instead of the real name and stop. Same with new inodes 2270 * that were not created yet and overwritten inodes/refs. 2271 * 2272 * When do we have orphan inodes: 2273 * 1. When an inode is freshly created and thus no valid refs are available yet 2274 * 2. When a directory lost all it's refs (deleted) but still has dir items 2275 * inside which were not processed yet (pending for move/delete). If anyone 2276 * tried to get the path to the dir items, it would get a path inside that 2277 * orphan directory. 2278 * 3. When an inode is moved around or gets new links, it may overwrite the ref 2279 * of an unprocessed inode. If in that case the first ref would be 2280 * overwritten, the overwritten inode gets "orphanized". Later when we 2281 * process this overwritten inode, it is restored at a new place by moving 2282 * the orphan inode. 2283 * 2284 * sctx->send_progress tells this function at which point in time receiving 2285 * would be. 2286 */ 2287 static int get_cur_path(struct send_ctx *sctx, u64 ino, u64 gen, 2288 struct fs_path *dest) 2289 { 2290 int ret = 0; 2291 struct fs_path *name = NULL; 2292 u64 parent_inode = 0; 2293 u64 parent_gen = 0; 2294 int stop = 0; 2295 2296 name = fs_path_alloc(); 2297 if (!name) { 2298 ret = -ENOMEM; 2299 goto out; 2300 } 2301 2302 dest->reversed = 1; 2303 fs_path_reset(dest); 2304 2305 while (!stop && ino != BTRFS_FIRST_FREE_OBJECTID) { 2306 struct waiting_dir_move *wdm; 2307 2308 fs_path_reset(name); 2309 2310 if (is_waiting_for_rm(sctx, ino, gen)) { 2311 ret = gen_unique_name(sctx, ino, gen, name); 2312 if (ret < 0) 2313 goto out; 2314 ret = fs_path_add_path(dest, name); 2315 break; 2316 } 2317 2318 wdm = get_waiting_dir_move(sctx, ino); 2319 if (wdm && wdm->orphanized) { 2320 ret = gen_unique_name(sctx, ino, gen, name); 2321 stop = 1; 2322 } else if (wdm) { 2323 ret = get_first_ref(sctx->parent_root, ino, 2324 &parent_inode, &parent_gen, name); 2325 } else { 2326 ret = __get_cur_name_and_parent(sctx, ino, gen, 2327 &parent_inode, 2328 &parent_gen, name); 2329 if (ret) 2330 stop = 1; 2331 } 2332 2333 if (ret < 0) 2334 goto out; 2335 2336 ret = fs_path_add_path(dest, name); 2337 if (ret < 0) 2338 goto out; 2339 2340 ino = parent_inode; 2341 gen = parent_gen; 2342 } 2343 2344 out: 2345 fs_path_free(name); 2346 if (!ret) 2347 fs_path_unreverse(dest); 2348 return ret; 2349 } 2350 2351 /* 2352 * Sends a BTRFS_SEND_C_SUBVOL command/item to userspace 2353 */ 2354 static int send_subvol_begin(struct send_ctx *sctx) 2355 { 2356 int ret; 2357 struct btrfs_root *send_root = sctx->send_root; 2358 struct btrfs_root *parent_root = sctx->parent_root; 2359 struct btrfs_path *path; 2360 struct btrfs_key key; 2361 struct btrfs_root_ref *ref; 2362 struct extent_buffer *leaf; 2363 char *name = NULL; 2364 int namelen; 2365 2366 path = btrfs_alloc_path(); 2367 if (!path) 2368 return -ENOMEM; 2369 2370 name = kmalloc(BTRFS_PATH_NAME_MAX, GFP_KERNEL); 2371 if (!name) { 2372 btrfs_free_path(path); 2373 return -ENOMEM; 2374 } 2375 2376 key.objectid = send_root->root_key.objectid; 2377 key.type = BTRFS_ROOT_BACKREF_KEY; 2378 key.offset = 0; 2379 2380 ret = btrfs_search_slot_for_read(send_root->fs_info->tree_root, 2381 &key, path, 1, 0); 2382 if (ret < 0) 2383 goto out; 2384 if (ret) { 2385 ret = -ENOENT; 2386 goto out; 2387 } 2388 2389 leaf = path->nodes[0]; 2390 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); 2391 if (key.type != BTRFS_ROOT_BACKREF_KEY || 2392 key.objectid != send_root->root_key.objectid) { 2393 ret = -ENOENT; 2394 goto out; 2395 } 2396 ref = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_root_ref); 2397 namelen = btrfs_root_ref_name_len(leaf, ref); 2398 read_extent_buffer(leaf, name, (unsigned long)(ref + 1), namelen); 2399 btrfs_release_path(path); 2400 2401 if (parent_root) { 2402 ret = begin_cmd(sctx, BTRFS_SEND_C_SNAPSHOT); 2403 if (ret < 0) 2404 goto out; 2405 } else { 2406 ret = begin_cmd(sctx, BTRFS_SEND_C_SUBVOL); 2407 if (ret < 0) 2408 goto out; 2409 } 2410 2411 TLV_PUT_STRING(sctx, BTRFS_SEND_A_PATH, name, namelen); 2412 2413 if (!btrfs_is_empty_uuid(sctx->send_root->root_item.received_uuid)) 2414 TLV_PUT_UUID(sctx, BTRFS_SEND_A_UUID, 2415 sctx->send_root->root_item.received_uuid); 2416 else 2417 TLV_PUT_UUID(sctx, BTRFS_SEND_A_UUID, 2418 sctx->send_root->root_item.uuid); 2419 2420 TLV_PUT_U64(sctx, BTRFS_SEND_A_CTRANSID, 2421 btrfs_root_ctransid(&sctx->send_root->root_item)); 2422 if (parent_root) { 2423 if (!btrfs_is_empty_uuid(parent_root->root_item.received_uuid)) 2424 TLV_PUT_UUID(sctx, BTRFS_SEND_A_CLONE_UUID, 2425 parent_root->root_item.received_uuid); 2426 else 2427 TLV_PUT_UUID(sctx, BTRFS_SEND_A_CLONE_UUID, 2428 parent_root->root_item.uuid); 2429 TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_CTRANSID, 2430 btrfs_root_ctransid(&sctx->parent_root->root_item)); 2431 } 2432 2433 ret = send_cmd(sctx); 2434 2435 tlv_put_failure: 2436 out: 2437 btrfs_free_path(path); 2438 kfree(name); 2439 return ret; 2440 } 2441 2442 static int send_truncate(struct send_ctx *sctx, u64 ino, u64 gen, u64 size) 2443 { 2444 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info; 2445 int ret = 0; 2446 struct fs_path *p; 2447 2448 btrfs_debug(fs_info, "send_truncate %llu size=%llu", ino, size); 2449 2450 p = fs_path_alloc(); 2451 if (!p) 2452 return -ENOMEM; 2453 2454 ret = begin_cmd(sctx, BTRFS_SEND_C_TRUNCATE); 2455 if (ret < 0) 2456 goto out; 2457 2458 ret = get_cur_path(sctx, ino, gen, p); 2459 if (ret < 0) 2460 goto out; 2461 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p); 2462 TLV_PUT_U64(sctx, BTRFS_SEND_A_SIZE, size); 2463 2464 ret = send_cmd(sctx); 2465 2466 tlv_put_failure: 2467 out: 2468 fs_path_free(p); 2469 return ret; 2470 } 2471 2472 static int send_chmod(struct send_ctx *sctx, u64 ino, u64 gen, u64 mode) 2473 { 2474 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info; 2475 int ret = 0; 2476 struct fs_path *p; 2477 2478 btrfs_debug(fs_info, "send_chmod %llu mode=%llu", ino, mode); 2479 2480 p = fs_path_alloc(); 2481 if (!p) 2482 return -ENOMEM; 2483 2484 ret = begin_cmd(sctx, BTRFS_SEND_C_CHMOD); 2485 if (ret < 0) 2486 goto out; 2487 2488 ret = get_cur_path(sctx, ino, gen, p); 2489 if (ret < 0) 2490 goto out; 2491 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p); 2492 TLV_PUT_U64(sctx, BTRFS_SEND_A_MODE, mode & 07777); 2493 2494 ret = send_cmd(sctx); 2495 2496 tlv_put_failure: 2497 out: 2498 fs_path_free(p); 2499 return ret; 2500 } 2501 2502 static int send_chown(struct send_ctx *sctx, u64 ino, u64 gen, u64 uid, u64 gid) 2503 { 2504 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info; 2505 int ret = 0; 2506 struct fs_path *p; 2507 2508 btrfs_debug(fs_info, "send_chown %llu uid=%llu, gid=%llu", 2509 ino, uid, gid); 2510 2511 p = fs_path_alloc(); 2512 if (!p) 2513 return -ENOMEM; 2514 2515 ret = begin_cmd(sctx, BTRFS_SEND_C_CHOWN); 2516 if (ret < 0) 2517 goto out; 2518 2519 ret = get_cur_path(sctx, ino, gen, p); 2520 if (ret < 0) 2521 goto out; 2522 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p); 2523 TLV_PUT_U64(sctx, BTRFS_SEND_A_UID, uid); 2524 TLV_PUT_U64(sctx, BTRFS_SEND_A_GID, gid); 2525 2526 ret = send_cmd(sctx); 2527 2528 tlv_put_failure: 2529 out: 2530 fs_path_free(p); 2531 return ret; 2532 } 2533 2534 static int send_utimes(struct send_ctx *sctx, u64 ino, u64 gen) 2535 { 2536 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info; 2537 int ret = 0; 2538 struct fs_path *p = NULL; 2539 struct btrfs_inode_item *ii; 2540 struct btrfs_path *path = NULL; 2541 struct extent_buffer *eb; 2542 struct btrfs_key key; 2543 int slot; 2544 2545 btrfs_debug(fs_info, "send_utimes %llu", ino); 2546 2547 p = fs_path_alloc(); 2548 if (!p) 2549 return -ENOMEM; 2550 2551 path = alloc_path_for_send(); 2552 if (!path) { 2553 ret = -ENOMEM; 2554 goto out; 2555 } 2556 2557 key.objectid = ino; 2558 key.type = BTRFS_INODE_ITEM_KEY; 2559 key.offset = 0; 2560 ret = btrfs_search_slot(NULL, sctx->send_root, &key, path, 0, 0); 2561 if (ret > 0) 2562 ret = -ENOENT; 2563 if (ret < 0) 2564 goto out; 2565 2566 eb = path->nodes[0]; 2567 slot = path->slots[0]; 2568 ii = btrfs_item_ptr(eb, slot, struct btrfs_inode_item); 2569 2570 ret = begin_cmd(sctx, BTRFS_SEND_C_UTIMES); 2571 if (ret < 0) 2572 goto out; 2573 2574 ret = get_cur_path(sctx, ino, gen, p); 2575 if (ret < 0) 2576 goto out; 2577 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p); 2578 TLV_PUT_BTRFS_TIMESPEC(sctx, BTRFS_SEND_A_ATIME, eb, &ii->atime); 2579 TLV_PUT_BTRFS_TIMESPEC(sctx, BTRFS_SEND_A_MTIME, eb, &ii->mtime); 2580 TLV_PUT_BTRFS_TIMESPEC(sctx, BTRFS_SEND_A_CTIME, eb, &ii->ctime); 2581 /* TODO Add otime support when the otime patches get into upstream */ 2582 2583 ret = send_cmd(sctx); 2584 2585 tlv_put_failure: 2586 out: 2587 fs_path_free(p); 2588 btrfs_free_path(path); 2589 return ret; 2590 } 2591 2592 /* 2593 * Sends a BTRFS_SEND_C_MKXXX or SYMLINK command to user space. We don't have 2594 * a valid path yet because we did not process the refs yet. So, the inode 2595 * is created as orphan. 2596 */ 2597 static int send_create_inode(struct send_ctx *sctx, u64 ino) 2598 { 2599 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info; 2600 int ret = 0; 2601 struct fs_path *p; 2602 int cmd; 2603 u64 gen; 2604 u64 mode; 2605 u64 rdev; 2606 2607 btrfs_debug(fs_info, "send_create_inode %llu", ino); 2608 2609 p = fs_path_alloc(); 2610 if (!p) 2611 return -ENOMEM; 2612 2613 if (ino != sctx->cur_ino) { 2614 ret = get_inode_info(sctx->send_root, ino, NULL, &gen, &mode, 2615 NULL, NULL, &rdev); 2616 if (ret < 0) 2617 goto out; 2618 } else { 2619 gen = sctx->cur_inode_gen; 2620 mode = sctx->cur_inode_mode; 2621 rdev = sctx->cur_inode_rdev; 2622 } 2623 2624 if (S_ISREG(mode)) { 2625 cmd = BTRFS_SEND_C_MKFILE; 2626 } else if (S_ISDIR(mode)) { 2627 cmd = BTRFS_SEND_C_MKDIR; 2628 } else if (S_ISLNK(mode)) { 2629 cmd = BTRFS_SEND_C_SYMLINK; 2630 } else if (S_ISCHR(mode) || S_ISBLK(mode)) { 2631 cmd = BTRFS_SEND_C_MKNOD; 2632 } else if (S_ISFIFO(mode)) { 2633 cmd = BTRFS_SEND_C_MKFIFO; 2634 } else if (S_ISSOCK(mode)) { 2635 cmd = BTRFS_SEND_C_MKSOCK; 2636 } else { 2637 btrfs_warn(sctx->send_root->fs_info, "unexpected inode type %o", 2638 (int)(mode & S_IFMT)); 2639 ret = -EOPNOTSUPP; 2640 goto out; 2641 } 2642 2643 ret = begin_cmd(sctx, cmd); 2644 if (ret < 0) 2645 goto out; 2646 2647 ret = gen_unique_name(sctx, ino, gen, p); 2648 if (ret < 0) 2649 goto out; 2650 2651 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p); 2652 TLV_PUT_U64(sctx, BTRFS_SEND_A_INO, ino); 2653 2654 if (S_ISLNK(mode)) { 2655 fs_path_reset(p); 2656 ret = read_symlink(sctx->send_root, ino, p); 2657 if (ret < 0) 2658 goto out; 2659 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH_LINK, p); 2660 } else if (S_ISCHR(mode) || S_ISBLK(mode) || 2661 S_ISFIFO(mode) || S_ISSOCK(mode)) { 2662 TLV_PUT_U64(sctx, BTRFS_SEND_A_RDEV, new_encode_dev(rdev)); 2663 TLV_PUT_U64(sctx, BTRFS_SEND_A_MODE, mode); 2664 } 2665 2666 ret = send_cmd(sctx); 2667 if (ret < 0) 2668 goto out; 2669 2670 2671 tlv_put_failure: 2672 out: 2673 fs_path_free(p); 2674 return ret; 2675 } 2676 2677 /* 2678 * We need some special handling for inodes that get processed before the parent 2679 * directory got created. See process_recorded_refs for details. 2680 * This function does the check if we already created the dir out of order. 2681 */ 2682 static int did_create_dir(struct send_ctx *sctx, u64 dir) 2683 { 2684 int ret = 0; 2685 int iter_ret = 0; 2686 struct btrfs_path *path = NULL; 2687 struct btrfs_key key; 2688 struct btrfs_key found_key; 2689 struct btrfs_key di_key; 2690 struct btrfs_dir_item *di; 2691 2692 path = alloc_path_for_send(); 2693 if (!path) 2694 return -ENOMEM; 2695 2696 key.objectid = dir; 2697 key.type = BTRFS_DIR_INDEX_KEY; 2698 key.offset = 0; 2699 2700 btrfs_for_each_slot(sctx->send_root, &key, &found_key, path, iter_ret) { 2701 struct extent_buffer *eb = path->nodes[0]; 2702 2703 if (found_key.objectid != key.objectid || 2704 found_key.type != key.type) { 2705 ret = 0; 2706 break; 2707 } 2708 2709 di = btrfs_item_ptr(eb, path->slots[0], struct btrfs_dir_item); 2710 btrfs_dir_item_key_to_cpu(eb, di, &di_key); 2711 2712 if (di_key.type != BTRFS_ROOT_ITEM_KEY && 2713 di_key.objectid < sctx->send_progress) { 2714 ret = 1; 2715 break; 2716 } 2717 } 2718 /* Catch error found during iteration */ 2719 if (iter_ret < 0) 2720 ret = iter_ret; 2721 2722 btrfs_free_path(path); 2723 return ret; 2724 } 2725 2726 /* 2727 * Only creates the inode if it is: 2728 * 1. Not a directory 2729 * 2. Or a directory which was not created already due to out of order 2730 * directories. See did_create_dir and process_recorded_refs for details. 2731 */ 2732 static int send_create_inode_if_needed(struct send_ctx *sctx) 2733 { 2734 int ret; 2735 2736 if (S_ISDIR(sctx->cur_inode_mode)) { 2737 ret = did_create_dir(sctx, sctx->cur_ino); 2738 if (ret < 0) 2739 return ret; 2740 else if (ret > 0) 2741 return 0; 2742 } 2743 2744 return send_create_inode(sctx, sctx->cur_ino); 2745 } 2746 2747 struct recorded_ref { 2748 struct list_head list; 2749 char *name; 2750 struct fs_path *full_path; 2751 u64 dir; 2752 u64 dir_gen; 2753 int name_len; 2754 }; 2755 2756 static void set_ref_path(struct recorded_ref *ref, struct fs_path *path) 2757 { 2758 ref->full_path = path; 2759 ref->name = (char *)kbasename(ref->full_path->start); 2760 ref->name_len = ref->full_path->end - ref->name; 2761 } 2762 2763 /* 2764 * We need to process new refs before deleted refs, but compare_tree gives us 2765 * everything mixed. So we first record all refs and later process them. 2766 * This function is a helper to record one ref. 2767 */ 2768 static int __record_ref(struct list_head *head, u64 dir, 2769 u64 dir_gen, struct fs_path *path) 2770 { 2771 struct recorded_ref *ref; 2772 2773 ref = kmalloc(sizeof(*ref), GFP_KERNEL); 2774 if (!ref) 2775 return -ENOMEM; 2776 2777 ref->dir = dir; 2778 ref->dir_gen = dir_gen; 2779 set_ref_path(ref, path); 2780 list_add_tail(&ref->list, head); 2781 return 0; 2782 } 2783 2784 static int dup_ref(struct recorded_ref *ref, struct list_head *list) 2785 { 2786 struct recorded_ref *new; 2787 2788 new = kmalloc(sizeof(*ref), GFP_KERNEL); 2789 if (!new) 2790 return -ENOMEM; 2791 2792 new->dir = ref->dir; 2793 new->dir_gen = ref->dir_gen; 2794 new->full_path = NULL; 2795 INIT_LIST_HEAD(&new->list); 2796 list_add_tail(&new->list, list); 2797 return 0; 2798 } 2799 2800 static void __free_recorded_refs(struct list_head *head) 2801 { 2802 struct recorded_ref *cur; 2803 2804 while (!list_empty(head)) { 2805 cur = list_entry(head->next, struct recorded_ref, list); 2806 fs_path_free(cur->full_path); 2807 list_del(&cur->list); 2808 kfree(cur); 2809 } 2810 } 2811 2812 static void free_recorded_refs(struct send_ctx *sctx) 2813 { 2814 __free_recorded_refs(&sctx->new_refs); 2815 __free_recorded_refs(&sctx->deleted_refs); 2816 } 2817 2818 /* 2819 * Renames/moves a file/dir to its orphan name. Used when the first 2820 * ref of an unprocessed inode gets overwritten and for all non empty 2821 * directories. 2822 */ 2823 static int orphanize_inode(struct send_ctx *sctx, u64 ino, u64 gen, 2824 struct fs_path *path) 2825 { 2826 int ret; 2827 struct fs_path *orphan; 2828 2829 orphan = fs_path_alloc(); 2830 if (!orphan) 2831 return -ENOMEM; 2832 2833 ret = gen_unique_name(sctx, ino, gen, orphan); 2834 if (ret < 0) 2835 goto out; 2836 2837 ret = send_rename(sctx, path, orphan); 2838 2839 out: 2840 fs_path_free(orphan); 2841 return ret; 2842 } 2843 2844 static struct orphan_dir_info *add_orphan_dir_info(struct send_ctx *sctx, 2845 u64 dir_ino, u64 dir_gen) 2846 { 2847 struct rb_node **p = &sctx->orphan_dirs.rb_node; 2848 struct rb_node *parent = NULL; 2849 struct orphan_dir_info *entry, *odi; 2850 2851 while (*p) { 2852 parent = *p; 2853 entry = rb_entry(parent, struct orphan_dir_info, node); 2854 if (dir_ino < entry->ino) 2855 p = &(*p)->rb_left; 2856 else if (dir_ino > entry->ino) 2857 p = &(*p)->rb_right; 2858 else if (dir_gen < entry->gen) 2859 p = &(*p)->rb_left; 2860 else if (dir_gen > entry->gen) 2861 p = &(*p)->rb_right; 2862 else 2863 return entry; 2864 } 2865 2866 odi = kmalloc(sizeof(*odi), GFP_KERNEL); 2867 if (!odi) 2868 return ERR_PTR(-ENOMEM); 2869 odi->ino = dir_ino; 2870 odi->gen = dir_gen; 2871 odi->last_dir_index_offset = 0; 2872 2873 rb_link_node(&odi->node, parent, p); 2874 rb_insert_color(&odi->node, &sctx->orphan_dirs); 2875 return odi; 2876 } 2877 2878 static struct orphan_dir_info *get_orphan_dir_info(struct send_ctx *sctx, 2879 u64 dir_ino, u64 gen) 2880 { 2881 struct rb_node *n = sctx->orphan_dirs.rb_node; 2882 struct orphan_dir_info *entry; 2883 2884 while (n) { 2885 entry = rb_entry(n, struct orphan_dir_info, node); 2886 if (dir_ino < entry->ino) 2887 n = n->rb_left; 2888 else if (dir_ino > entry->ino) 2889 n = n->rb_right; 2890 else if (gen < entry->gen) 2891 n = n->rb_left; 2892 else if (gen > entry->gen) 2893 n = n->rb_right; 2894 else 2895 return entry; 2896 } 2897 return NULL; 2898 } 2899 2900 static int is_waiting_for_rm(struct send_ctx *sctx, u64 dir_ino, u64 gen) 2901 { 2902 struct orphan_dir_info *odi = get_orphan_dir_info(sctx, dir_ino, gen); 2903 2904 return odi != NULL; 2905 } 2906 2907 static void free_orphan_dir_info(struct send_ctx *sctx, 2908 struct orphan_dir_info *odi) 2909 { 2910 if (!odi) 2911 return; 2912 rb_erase(&odi->node, &sctx->orphan_dirs); 2913 kfree(odi); 2914 } 2915 2916 /* 2917 * Returns 1 if a directory can be removed at this point in time. 2918 * We check this by iterating all dir items and checking if the inode behind 2919 * the dir item was already processed. 2920 */ 2921 static int can_rmdir(struct send_ctx *sctx, u64 dir, u64 dir_gen, 2922 u64 send_progress) 2923 { 2924 int ret = 0; 2925 int iter_ret = 0; 2926 struct btrfs_root *root = sctx->parent_root; 2927 struct btrfs_path *path; 2928 struct btrfs_key key; 2929 struct btrfs_key found_key; 2930 struct btrfs_key loc; 2931 struct btrfs_dir_item *di; 2932 struct orphan_dir_info *odi = NULL; 2933 2934 /* 2935 * Don't try to rmdir the top/root subvolume dir. 2936 */ 2937 if (dir == BTRFS_FIRST_FREE_OBJECTID) 2938 return 0; 2939 2940 path = alloc_path_for_send(); 2941 if (!path) 2942 return -ENOMEM; 2943 2944 key.objectid = dir; 2945 key.type = BTRFS_DIR_INDEX_KEY; 2946 key.offset = 0; 2947 2948 odi = get_orphan_dir_info(sctx, dir, dir_gen); 2949 if (odi) 2950 key.offset = odi->last_dir_index_offset; 2951 2952 btrfs_for_each_slot(root, &key, &found_key, path, iter_ret) { 2953 struct waiting_dir_move *dm; 2954 2955 if (found_key.objectid != key.objectid || 2956 found_key.type != key.type) 2957 break; 2958 2959 di = btrfs_item_ptr(path->nodes[0], path->slots[0], 2960 struct btrfs_dir_item); 2961 btrfs_dir_item_key_to_cpu(path->nodes[0], di, &loc); 2962 2963 dm = get_waiting_dir_move(sctx, loc.objectid); 2964 if (dm) { 2965 odi = add_orphan_dir_info(sctx, dir, dir_gen); 2966 if (IS_ERR(odi)) { 2967 ret = PTR_ERR(odi); 2968 goto out; 2969 } 2970 odi->gen = dir_gen; 2971 odi->last_dir_index_offset = found_key.offset; 2972 dm->rmdir_ino = dir; 2973 dm->rmdir_gen = dir_gen; 2974 ret = 0; 2975 goto out; 2976 } 2977 2978 if (loc.objectid > send_progress) { 2979 odi = add_orphan_dir_info(sctx, dir, dir_gen); 2980 if (IS_ERR(odi)) { 2981 ret = PTR_ERR(odi); 2982 goto out; 2983 } 2984 odi->gen = dir_gen; 2985 odi->last_dir_index_offset = found_key.offset; 2986 ret = 0; 2987 goto out; 2988 } 2989 } 2990 if (iter_ret < 0) { 2991 ret = iter_ret; 2992 goto out; 2993 } 2994 free_orphan_dir_info(sctx, odi); 2995 2996 ret = 1; 2997 2998 out: 2999 btrfs_free_path(path); 3000 return ret; 3001 } 3002 3003 static int is_waiting_for_move(struct send_ctx *sctx, u64 ino) 3004 { 3005 struct waiting_dir_move *entry = get_waiting_dir_move(sctx, ino); 3006 3007 return entry != NULL; 3008 } 3009 3010 static int add_waiting_dir_move(struct send_ctx *sctx, u64 ino, bool orphanized) 3011 { 3012 struct rb_node **p = &sctx->waiting_dir_moves.rb_node; 3013 struct rb_node *parent = NULL; 3014 struct waiting_dir_move *entry, *dm; 3015 3016 dm = kmalloc(sizeof(*dm), GFP_KERNEL); 3017 if (!dm) 3018 return -ENOMEM; 3019 dm->ino = ino; 3020 dm->rmdir_ino = 0; 3021 dm->rmdir_gen = 0; 3022 dm->orphanized = orphanized; 3023 3024 while (*p) { 3025 parent = *p; 3026 entry = rb_entry(parent, struct waiting_dir_move, node); 3027 if (ino < entry->ino) { 3028 p = &(*p)->rb_left; 3029 } else if (ino > entry->ino) { 3030 p = &(*p)->rb_right; 3031 } else { 3032 kfree(dm); 3033 return -EEXIST; 3034 } 3035 } 3036 3037 rb_link_node(&dm->node, parent, p); 3038 rb_insert_color(&dm->node, &sctx->waiting_dir_moves); 3039 return 0; 3040 } 3041 3042 static struct waiting_dir_move * 3043 get_waiting_dir_move(struct send_ctx *sctx, u64 ino) 3044 { 3045 struct rb_node *n = sctx->waiting_dir_moves.rb_node; 3046 struct waiting_dir_move *entry; 3047 3048 while (n) { 3049 entry = rb_entry(n, struct waiting_dir_move, node); 3050 if (ino < entry->ino) 3051 n = n->rb_left; 3052 else if (ino > entry->ino) 3053 n = n->rb_right; 3054 else 3055 return entry; 3056 } 3057 return NULL; 3058 } 3059 3060 static void free_waiting_dir_move(struct send_ctx *sctx, 3061 struct waiting_dir_move *dm) 3062 { 3063 if (!dm) 3064 return; 3065 rb_erase(&dm->node, &sctx->waiting_dir_moves); 3066 kfree(dm); 3067 } 3068 3069 static int add_pending_dir_move(struct send_ctx *sctx, 3070 u64 ino, 3071 u64 ino_gen, 3072 u64 parent_ino, 3073 struct list_head *new_refs, 3074 struct list_head *deleted_refs, 3075 const bool is_orphan) 3076 { 3077 struct rb_node **p = &sctx->pending_dir_moves.rb_node; 3078 struct rb_node *parent = NULL; 3079 struct pending_dir_move *entry = NULL, *pm; 3080 struct recorded_ref *cur; 3081 int exists = 0; 3082 int ret; 3083 3084 pm = kmalloc(sizeof(*pm), GFP_KERNEL); 3085 if (!pm) 3086 return -ENOMEM; 3087 pm->parent_ino = parent_ino; 3088 pm->ino = ino; 3089 pm->gen = ino_gen; 3090 INIT_LIST_HEAD(&pm->list); 3091 INIT_LIST_HEAD(&pm->update_refs); 3092 RB_CLEAR_NODE(&pm->node); 3093 3094 while (*p) { 3095 parent = *p; 3096 entry = rb_entry(parent, struct pending_dir_move, node); 3097 if (parent_ino < entry->parent_ino) { 3098 p = &(*p)->rb_left; 3099 } else if (parent_ino > entry->parent_ino) { 3100 p = &(*p)->rb_right; 3101 } else { 3102 exists = 1; 3103 break; 3104 } 3105 } 3106 3107 list_for_each_entry(cur, deleted_refs, list) { 3108 ret = dup_ref(cur, &pm->update_refs); 3109 if (ret < 0) 3110 goto out; 3111 } 3112 list_for_each_entry(cur, new_refs, list) { 3113 ret = dup_ref(cur, &pm->update_refs); 3114 if (ret < 0) 3115 goto out; 3116 } 3117 3118 ret = add_waiting_dir_move(sctx, pm->ino, is_orphan); 3119 if (ret) 3120 goto out; 3121 3122 if (exists) { 3123 list_add_tail(&pm->list, &entry->list); 3124 } else { 3125 rb_link_node(&pm->node, parent, p); 3126 rb_insert_color(&pm->node, &sctx->pending_dir_moves); 3127 } 3128 ret = 0; 3129 out: 3130 if (ret) { 3131 __free_recorded_refs(&pm->update_refs); 3132 kfree(pm); 3133 } 3134 return ret; 3135 } 3136 3137 static struct pending_dir_move *get_pending_dir_moves(struct send_ctx *sctx, 3138 u64 parent_ino) 3139 { 3140 struct rb_node *n = sctx->pending_dir_moves.rb_node; 3141 struct pending_dir_move *entry; 3142 3143 while (n) { 3144 entry = rb_entry(n, struct pending_dir_move, node); 3145 if (parent_ino < entry->parent_ino) 3146 n = n->rb_left; 3147 else if (parent_ino > entry->parent_ino) 3148 n = n->rb_right; 3149 else 3150 return entry; 3151 } 3152 return NULL; 3153 } 3154 3155 static int path_loop(struct send_ctx *sctx, struct fs_path *name, 3156 u64 ino, u64 gen, u64 *ancestor_ino) 3157 { 3158 int ret = 0; 3159 u64 parent_inode = 0; 3160 u64 parent_gen = 0; 3161 u64 start_ino = ino; 3162 3163 *ancestor_ino = 0; 3164 while (ino != BTRFS_FIRST_FREE_OBJECTID) { 3165 fs_path_reset(name); 3166 3167 if (is_waiting_for_rm(sctx, ino, gen)) 3168 break; 3169 if (is_waiting_for_move(sctx, ino)) { 3170 if (*ancestor_ino == 0) 3171 *ancestor_ino = ino; 3172 ret = get_first_ref(sctx->parent_root, ino, 3173 &parent_inode, &parent_gen, name); 3174 } else { 3175 ret = __get_cur_name_and_parent(sctx, ino, gen, 3176 &parent_inode, 3177 &parent_gen, name); 3178 if (ret > 0) { 3179 ret = 0; 3180 break; 3181 } 3182 } 3183 if (ret < 0) 3184 break; 3185 if (parent_inode == start_ino) { 3186 ret = 1; 3187 if (*ancestor_ino == 0) 3188 *ancestor_ino = ino; 3189 break; 3190 } 3191 ino = parent_inode; 3192 gen = parent_gen; 3193 } 3194 return ret; 3195 } 3196 3197 static int apply_dir_move(struct send_ctx *sctx, struct pending_dir_move *pm) 3198 { 3199 struct fs_path *from_path = NULL; 3200 struct fs_path *to_path = NULL; 3201 struct fs_path *name = NULL; 3202 u64 orig_progress = sctx->send_progress; 3203 struct recorded_ref *cur; 3204 u64 parent_ino, parent_gen; 3205 struct waiting_dir_move *dm = NULL; 3206 u64 rmdir_ino = 0; 3207 u64 rmdir_gen; 3208 u64 ancestor; 3209 bool is_orphan; 3210 int ret; 3211 3212 name = fs_path_alloc(); 3213 from_path = fs_path_alloc(); 3214 if (!name || !from_path) { 3215 ret = -ENOMEM; 3216 goto out; 3217 } 3218 3219 dm = get_waiting_dir_move(sctx, pm->ino); 3220 ASSERT(dm); 3221 rmdir_ino = dm->rmdir_ino; 3222 rmdir_gen = dm->rmdir_gen; 3223 is_orphan = dm->orphanized; 3224 free_waiting_dir_move(sctx, dm); 3225 3226 if (is_orphan) { 3227 ret = gen_unique_name(sctx, pm->ino, 3228 pm->gen, from_path); 3229 } else { 3230 ret = get_first_ref(sctx->parent_root, pm->ino, 3231 &parent_ino, &parent_gen, name); 3232 if (ret < 0) 3233 goto out; 3234 ret = get_cur_path(sctx, parent_ino, parent_gen, 3235 from_path); 3236 if (ret < 0) 3237 goto out; 3238 ret = fs_path_add_path(from_path, name); 3239 } 3240 if (ret < 0) 3241 goto out; 3242 3243 sctx->send_progress = sctx->cur_ino + 1; 3244 ret = path_loop(sctx, name, pm->ino, pm->gen, &ancestor); 3245 if (ret < 0) 3246 goto out; 3247 if (ret) { 3248 LIST_HEAD(deleted_refs); 3249 ASSERT(ancestor > BTRFS_FIRST_FREE_OBJECTID); 3250 ret = add_pending_dir_move(sctx, pm->ino, pm->gen, ancestor, 3251 &pm->update_refs, &deleted_refs, 3252 is_orphan); 3253 if (ret < 0) 3254 goto out; 3255 if (rmdir_ino) { 3256 dm = get_waiting_dir_move(sctx, pm->ino); 3257 ASSERT(dm); 3258 dm->rmdir_ino = rmdir_ino; 3259 dm->rmdir_gen = rmdir_gen; 3260 } 3261 goto out; 3262 } 3263 fs_path_reset(name); 3264 to_path = name; 3265 name = NULL; 3266 ret = get_cur_path(sctx, pm->ino, pm->gen, to_path); 3267 if (ret < 0) 3268 goto out; 3269 3270 ret = send_rename(sctx, from_path, to_path); 3271 if (ret < 0) 3272 goto out; 3273 3274 if (rmdir_ino) { 3275 struct orphan_dir_info *odi; 3276 u64 gen; 3277 3278 odi = get_orphan_dir_info(sctx, rmdir_ino, rmdir_gen); 3279 if (!odi) { 3280 /* already deleted */ 3281 goto finish; 3282 } 3283 gen = odi->gen; 3284 3285 ret = can_rmdir(sctx, rmdir_ino, gen, sctx->cur_ino); 3286 if (ret < 0) 3287 goto out; 3288 if (!ret) 3289 goto finish; 3290 3291 name = fs_path_alloc(); 3292 if (!name) { 3293 ret = -ENOMEM; 3294 goto out; 3295 } 3296 ret = get_cur_path(sctx, rmdir_ino, gen, name); 3297 if (ret < 0) 3298 goto out; 3299 ret = send_rmdir(sctx, name); 3300 if (ret < 0) 3301 goto out; 3302 } 3303 3304 finish: 3305 ret = send_utimes(sctx, pm->ino, pm->gen); 3306 if (ret < 0) 3307 goto out; 3308 3309 /* 3310 * After rename/move, need to update the utimes of both new parent(s) 3311 * and old parent(s). 3312 */ 3313 list_for_each_entry(cur, &pm->update_refs, list) { 3314 /* 3315 * The parent inode might have been deleted in the send snapshot 3316 */ 3317 ret = get_inode_info(sctx->send_root, cur->dir, NULL, 3318 NULL, NULL, NULL, NULL, NULL); 3319 if (ret == -ENOENT) { 3320 ret = 0; 3321 continue; 3322 } 3323 if (ret < 0) 3324 goto out; 3325 3326 ret = send_utimes(sctx, cur->dir, cur->dir_gen); 3327 if (ret < 0) 3328 goto out; 3329 } 3330 3331 out: 3332 fs_path_free(name); 3333 fs_path_free(from_path); 3334 fs_path_free(to_path); 3335 sctx->send_progress = orig_progress; 3336 3337 return ret; 3338 } 3339 3340 static void free_pending_move(struct send_ctx *sctx, struct pending_dir_move *m) 3341 { 3342 if (!list_empty(&m->list)) 3343 list_del(&m->list); 3344 if (!RB_EMPTY_NODE(&m->node)) 3345 rb_erase(&m->node, &sctx->pending_dir_moves); 3346 __free_recorded_refs(&m->update_refs); 3347 kfree(m); 3348 } 3349 3350 static void tail_append_pending_moves(struct send_ctx *sctx, 3351 struct pending_dir_move *moves, 3352 struct list_head *stack) 3353 { 3354 if (list_empty(&moves->list)) { 3355 list_add_tail(&moves->list, stack); 3356 } else { 3357 LIST_HEAD(list); 3358 list_splice_init(&moves->list, &list); 3359 list_add_tail(&moves->list, stack); 3360 list_splice_tail(&list, stack); 3361 } 3362 if (!RB_EMPTY_NODE(&moves->node)) { 3363 rb_erase(&moves->node, &sctx->pending_dir_moves); 3364 RB_CLEAR_NODE(&moves->node); 3365 } 3366 } 3367 3368 static int apply_children_dir_moves(struct send_ctx *sctx) 3369 { 3370 struct pending_dir_move *pm; 3371 struct list_head stack; 3372 u64 parent_ino = sctx->cur_ino; 3373 int ret = 0; 3374 3375 pm = get_pending_dir_moves(sctx, parent_ino); 3376 if (!pm) 3377 return 0; 3378 3379 INIT_LIST_HEAD(&stack); 3380 tail_append_pending_moves(sctx, pm, &stack); 3381 3382 while (!list_empty(&stack)) { 3383 pm = list_first_entry(&stack, struct pending_dir_move, list); 3384 parent_ino = pm->ino; 3385 ret = apply_dir_move(sctx, pm); 3386 free_pending_move(sctx, pm); 3387 if (ret) 3388 goto out; 3389 pm = get_pending_dir_moves(sctx, parent_ino); 3390 if (pm) 3391 tail_append_pending_moves(sctx, pm, &stack); 3392 } 3393 return 0; 3394 3395 out: 3396 while (!list_empty(&stack)) { 3397 pm = list_first_entry(&stack, struct pending_dir_move, list); 3398 free_pending_move(sctx, pm); 3399 } 3400 return ret; 3401 } 3402 3403 /* 3404 * We might need to delay a directory rename even when no ancestor directory 3405 * (in the send root) with a higher inode number than ours (sctx->cur_ino) was 3406 * renamed. This happens when we rename a directory to the old name (the name 3407 * in the parent root) of some other unrelated directory that got its rename 3408 * delayed due to some ancestor with higher number that got renamed. 3409 * 3410 * Example: 3411 * 3412 * Parent snapshot: 3413 * . (ino 256) 3414 * |---- a/ (ino 257) 3415 * | |---- file (ino 260) 3416 * | 3417 * |---- b/ (ino 258) 3418 * |---- c/ (ino 259) 3419 * 3420 * Send snapshot: 3421 * . (ino 256) 3422 * |---- a/ (ino 258) 3423 * |---- x/ (ino 259) 3424 * |---- y/ (ino 257) 3425 * |----- file (ino 260) 3426 * 3427 * Here we can not rename 258 from 'b' to 'a' without the rename of inode 257 3428 * from 'a' to 'x/y' happening first, which in turn depends on the rename of 3429 * inode 259 from 'c' to 'x'. So the order of rename commands the send stream 3430 * must issue is: 3431 * 3432 * 1 - rename 259 from 'c' to 'x' 3433 * 2 - rename 257 from 'a' to 'x/y' 3434 * 3 - rename 258 from 'b' to 'a' 3435 * 3436 * Returns 1 if the rename of sctx->cur_ino needs to be delayed, 0 if it can 3437 * be done right away and < 0 on error. 3438 */ 3439 static int wait_for_dest_dir_move(struct send_ctx *sctx, 3440 struct recorded_ref *parent_ref, 3441 const bool is_orphan) 3442 { 3443 struct btrfs_fs_info *fs_info = sctx->parent_root->fs_info; 3444 struct btrfs_path *path; 3445 struct btrfs_key key; 3446 struct btrfs_key di_key; 3447 struct btrfs_dir_item *di; 3448 u64 left_gen; 3449 u64 right_gen; 3450 int ret = 0; 3451 struct waiting_dir_move *wdm; 3452 3453 if (RB_EMPTY_ROOT(&sctx->waiting_dir_moves)) 3454 return 0; 3455 3456 path = alloc_path_for_send(); 3457 if (!path) 3458 return -ENOMEM; 3459 3460 key.objectid = parent_ref->dir; 3461 key.type = BTRFS_DIR_ITEM_KEY; 3462 key.offset = btrfs_name_hash(parent_ref->name, parent_ref->name_len); 3463 3464 ret = btrfs_search_slot(NULL, sctx->parent_root, &key, path, 0, 0); 3465 if (ret < 0) { 3466 goto out; 3467 } else if (ret > 0) { 3468 ret = 0; 3469 goto out; 3470 } 3471 3472 di = btrfs_match_dir_item_name(fs_info, path, parent_ref->name, 3473 parent_ref->name_len); 3474 if (!di) { 3475 ret = 0; 3476 goto out; 3477 } 3478 /* 3479 * di_key.objectid has the number of the inode that has a dentry in the 3480 * parent directory with the same name that sctx->cur_ino is being 3481 * renamed to. We need to check if that inode is in the send root as 3482 * well and if it is currently marked as an inode with a pending rename, 3483 * if it is, we need to delay the rename of sctx->cur_ino as well, so 3484 * that it happens after that other inode is renamed. 3485 */ 3486 btrfs_dir_item_key_to_cpu(path->nodes[0], di, &di_key); 3487 if (di_key.type != BTRFS_INODE_ITEM_KEY) { 3488 ret = 0; 3489 goto out; 3490 } 3491 3492 ret = get_inode_info(sctx->parent_root, di_key.objectid, NULL, 3493 &left_gen, NULL, NULL, NULL, NULL); 3494 if (ret < 0) 3495 goto out; 3496 ret = get_inode_info(sctx->send_root, di_key.objectid, NULL, 3497 &right_gen, NULL, NULL, NULL, NULL); 3498 if (ret < 0) { 3499 if (ret == -ENOENT) 3500 ret = 0; 3501 goto out; 3502 } 3503 3504 /* Different inode, no need to delay the rename of sctx->cur_ino */ 3505 if (right_gen != left_gen) { 3506 ret = 0; 3507 goto out; 3508 } 3509 3510 wdm = get_waiting_dir_move(sctx, di_key.objectid); 3511 if (wdm && !wdm->orphanized) { 3512 ret = add_pending_dir_move(sctx, 3513 sctx->cur_ino, 3514 sctx->cur_inode_gen, 3515 di_key.objectid, 3516 &sctx->new_refs, 3517 &sctx->deleted_refs, 3518 is_orphan); 3519 if (!ret) 3520 ret = 1; 3521 } 3522 out: 3523 btrfs_free_path(path); 3524 return ret; 3525 } 3526 3527 /* 3528 * Check if inode ino2, or any of its ancestors, is inode ino1. 3529 * Return 1 if true, 0 if false and < 0 on error. 3530 */ 3531 static int check_ino_in_path(struct btrfs_root *root, 3532 const u64 ino1, 3533 const u64 ino1_gen, 3534 const u64 ino2, 3535 const u64 ino2_gen, 3536 struct fs_path *fs_path) 3537 { 3538 u64 ino = ino2; 3539 3540 if (ino1 == ino2) 3541 return ino1_gen == ino2_gen; 3542 3543 while (ino > BTRFS_FIRST_FREE_OBJECTID) { 3544 u64 parent; 3545 u64 parent_gen; 3546 int ret; 3547 3548 fs_path_reset(fs_path); 3549 ret = get_first_ref(root, ino, &parent, &parent_gen, fs_path); 3550 if (ret < 0) 3551 return ret; 3552 if (parent == ino1) 3553 return parent_gen == ino1_gen; 3554 ino = parent; 3555 } 3556 return 0; 3557 } 3558 3559 /* 3560 * Check if inode ino1 is an ancestor of inode ino2 in the given root for any 3561 * possible path (in case ino2 is not a directory and has multiple hard links). 3562 * Return 1 if true, 0 if false and < 0 on error. 3563 */ 3564 static int is_ancestor(struct btrfs_root *root, 3565 const u64 ino1, 3566 const u64 ino1_gen, 3567 const u64 ino2, 3568 struct fs_path *fs_path) 3569 { 3570 bool free_fs_path = false; 3571 int ret = 0; 3572 int iter_ret = 0; 3573 struct btrfs_path *path = NULL; 3574 struct btrfs_key key; 3575 3576 if (!fs_path) { 3577 fs_path = fs_path_alloc(); 3578 if (!fs_path) 3579 return -ENOMEM; 3580 free_fs_path = true; 3581 } 3582 3583 path = alloc_path_for_send(); 3584 if (!path) { 3585 ret = -ENOMEM; 3586 goto out; 3587 } 3588 3589 key.objectid = ino2; 3590 key.type = BTRFS_INODE_REF_KEY; 3591 key.offset = 0; 3592 3593 btrfs_for_each_slot(root, &key, &key, path, iter_ret) { 3594 struct extent_buffer *leaf = path->nodes[0]; 3595 int slot = path->slots[0]; 3596 u32 cur_offset = 0; 3597 u32 item_size; 3598 3599 if (key.objectid != ino2) 3600 break; 3601 if (key.type != BTRFS_INODE_REF_KEY && 3602 key.type != BTRFS_INODE_EXTREF_KEY) 3603 break; 3604 3605 item_size = btrfs_item_size(leaf, slot); 3606 while (cur_offset < item_size) { 3607 u64 parent; 3608 u64 parent_gen; 3609 3610 if (key.type == BTRFS_INODE_EXTREF_KEY) { 3611 unsigned long ptr; 3612 struct btrfs_inode_extref *extref; 3613 3614 ptr = btrfs_item_ptr_offset(leaf, slot); 3615 extref = (struct btrfs_inode_extref *) 3616 (ptr + cur_offset); 3617 parent = btrfs_inode_extref_parent(leaf, 3618 extref); 3619 cur_offset += sizeof(*extref); 3620 cur_offset += btrfs_inode_extref_name_len(leaf, 3621 extref); 3622 } else { 3623 parent = key.offset; 3624 cur_offset = item_size; 3625 } 3626 3627 ret = get_inode_info(root, parent, NULL, &parent_gen, 3628 NULL, NULL, NULL, NULL); 3629 if (ret < 0) 3630 goto out; 3631 ret = check_ino_in_path(root, ino1, ino1_gen, 3632 parent, parent_gen, fs_path); 3633 if (ret) 3634 goto out; 3635 } 3636 } 3637 ret = 0; 3638 if (iter_ret < 0) 3639 ret = iter_ret; 3640 3641 out: 3642 btrfs_free_path(path); 3643 if (free_fs_path) 3644 fs_path_free(fs_path); 3645 return ret; 3646 } 3647 3648 static int wait_for_parent_move(struct send_ctx *sctx, 3649 struct recorded_ref *parent_ref, 3650 const bool is_orphan) 3651 { 3652 int ret = 0; 3653 u64 ino = parent_ref->dir; 3654 u64 ino_gen = parent_ref->dir_gen; 3655 u64 parent_ino_before, parent_ino_after; 3656 struct fs_path *path_before = NULL; 3657 struct fs_path *path_after = NULL; 3658 int len1, len2; 3659 3660 path_after = fs_path_alloc(); 3661 path_before = fs_path_alloc(); 3662 if (!path_after || !path_before) { 3663 ret = -ENOMEM; 3664 goto out; 3665 } 3666 3667 /* 3668 * Our current directory inode may not yet be renamed/moved because some 3669 * ancestor (immediate or not) has to be renamed/moved first. So find if 3670 * such ancestor exists and make sure our own rename/move happens after 3671 * that ancestor is processed to avoid path build infinite loops (done 3672 * at get_cur_path()). 3673 */ 3674 while (ino > BTRFS_FIRST_FREE_OBJECTID) { 3675 u64 parent_ino_after_gen; 3676 3677 if (is_waiting_for_move(sctx, ino)) { 3678 /* 3679 * If the current inode is an ancestor of ino in the 3680 * parent root, we need to delay the rename of the 3681 * current inode, otherwise don't delayed the rename 3682 * because we can end up with a circular dependency 3683 * of renames, resulting in some directories never 3684 * getting the respective rename operations issued in 3685 * the send stream or getting into infinite path build 3686 * loops. 3687 */ 3688 ret = is_ancestor(sctx->parent_root, 3689 sctx->cur_ino, sctx->cur_inode_gen, 3690 ino, path_before); 3691 if (ret) 3692 break; 3693 } 3694 3695 fs_path_reset(path_before); 3696 fs_path_reset(path_after); 3697 3698 ret = get_first_ref(sctx->send_root, ino, &parent_ino_after, 3699 &parent_ino_after_gen, path_after); 3700 if (ret < 0) 3701 goto out; 3702 ret = get_first_ref(sctx->parent_root, ino, &parent_ino_before, 3703 NULL, path_before); 3704 if (ret < 0 && ret != -ENOENT) { 3705 goto out; 3706 } else if (ret == -ENOENT) { 3707 ret = 0; 3708 break; 3709 } 3710 3711 len1 = fs_path_len(path_before); 3712 len2 = fs_path_len(path_after); 3713 if (ino > sctx->cur_ino && 3714 (parent_ino_before != parent_ino_after || len1 != len2 || 3715 memcmp(path_before->start, path_after->start, len1))) { 3716 u64 parent_ino_gen; 3717 3718 ret = get_inode_info(sctx->parent_root, ino, NULL, 3719 &parent_ino_gen, NULL, NULL, NULL, 3720 NULL); 3721 if (ret < 0) 3722 goto out; 3723 if (ino_gen == parent_ino_gen) { 3724 ret = 1; 3725 break; 3726 } 3727 } 3728 ino = parent_ino_after; 3729 ino_gen = parent_ino_after_gen; 3730 } 3731 3732 out: 3733 fs_path_free(path_before); 3734 fs_path_free(path_after); 3735 3736 if (ret == 1) { 3737 ret = add_pending_dir_move(sctx, 3738 sctx->cur_ino, 3739 sctx->cur_inode_gen, 3740 ino, 3741 &sctx->new_refs, 3742 &sctx->deleted_refs, 3743 is_orphan); 3744 if (!ret) 3745 ret = 1; 3746 } 3747 3748 return ret; 3749 } 3750 3751 static int update_ref_path(struct send_ctx *sctx, struct recorded_ref *ref) 3752 { 3753 int ret; 3754 struct fs_path *new_path; 3755 3756 /* 3757 * Our reference's name member points to its full_path member string, so 3758 * we use here a new path. 3759 */ 3760 new_path = fs_path_alloc(); 3761 if (!new_path) 3762 return -ENOMEM; 3763 3764 ret = get_cur_path(sctx, ref->dir, ref->dir_gen, new_path); 3765 if (ret < 0) { 3766 fs_path_free(new_path); 3767 return ret; 3768 } 3769 ret = fs_path_add(new_path, ref->name, ref->name_len); 3770 if (ret < 0) { 3771 fs_path_free(new_path); 3772 return ret; 3773 } 3774 3775 fs_path_free(ref->full_path); 3776 set_ref_path(ref, new_path); 3777 3778 return 0; 3779 } 3780 3781 /* 3782 * When processing the new references for an inode we may orphanize an existing 3783 * directory inode because its old name conflicts with one of the new references 3784 * of the current inode. Later, when processing another new reference of our 3785 * inode, we might need to orphanize another inode, but the path we have in the 3786 * reference reflects the pre-orphanization name of the directory we previously 3787 * orphanized. For example: 3788 * 3789 * parent snapshot looks like: 3790 * 3791 * . (ino 256) 3792 * |----- f1 (ino 257) 3793 * |----- f2 (ino 258) 3794 * |----- d1/ (ino 259) 3795 * |----- d2/ (ino 260) 3796 * 3797 * send snapshot looks like: 3798 * 3799 * . (ino 256) 3800 * |----- d1 (ino 258) 3801 * |----- f2/ (ino 259) 3802 * |----- f2_link/ (ino 260) 3803 * | |----- f1 (ino 257) 3804 * | 3805 * |----- d2 (ino 258) 3806 * 3807 * When processing inode 257 we compute the name for inode 259 as "d1", and we 3808 * cache it in the name cache. Later when we start processing inode 258, when 3809 * collecting all its new references we set a full path of "d1/d2" for its new 3810 * reference with name "d2". When we start processing the new references we 3811 * start by processing the new reference with name "d1", and this results in 3812 * orphanizing inode 259, since its old reference causes a conflict. Then we 3813 * move on the next new reference, with name "d2", and we find out we must 3814 * orphanize inode 260, as its old reference conflicts with ours - but for the 3815 * orphanization we use a source path corresponding to the path we stored in the 3816 * new reference, which is "d1/d2" and not "o259-6-0/d2" - this makes the 3817 * receiver fail since the path component "d1/" no longer exists, it was renamed 3818 * to "o259-6-0/" when processing the previous new reference. So in this case we 3819 * must recompute the path in the new reference and use it for the new 3820 * orphanization operation. 3821 */ 3822 static int refresh_ref_path(struct send_ctx *sctx, struct recorded_ref *ref) 3823 { 3824 char *name; 3825 int ret; 3826 3827 name = kmemdup(ref->name, ref->name_len, GFP_KERNEL); 3828 if (!name) 3829 return -ENOMEM; 3830 3831 fs_path_reset(ref->full_path); 3832 ret = get_cur_path(sctx, ref->dir, ref->dir_gen, ref->full_path); 3833 if (ret < 0) 3834 goto out; 3835 3836 ret = fs_path_add(ref->full_path, name, ref->name_len); 3837 if (ret < 0) 3838 goto out; 3839 3840 /* Update the reference's base name pointer. */ 3841 set_ref_path(ref, ref->full_path); 3842 out: 3843 kfree(name); 3844 return ret; 3845 } 3846 3847 /* 3848 * This does all the move/link/unlink/rmdir magic. 3849 */ 3850 static int process_recorded_refs(struct send_ctx *sctx, int *pending_move) 3851 { 3852 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info; 3853 int ret = 0; 3854 struct recorded_ref *cur; 3855 struct recorded_ref *cur2; 3856 struct list_head check_dirs; 3857 struct fs_path *valid_path = NULL; 3858 u64 ow_inode = 0; 3859 u64 ow_gen; 3860 u64 ow_mode; 3861 int did_overwrite = 0; 3862 int is_orphan = 0; 3863 u64 last_dir_ino_rm = 0; 3864 bool can_rename = true; 3865 bool orphanized_dir = false; 3866 bool orphanized_ancestor = false; 3867 3868 btrfs_debug(fs_info, "process_recorded_refs %llu", sctx->cur_ino); 3869 3870 /* 3871 * This should never happen as the root dir always has the same ref 3872 * which is always '..' 3873 */ 3874 BUG_ON(sctx->cur_ino <= BTRFS_FIRST_FREE_OBJECTID); 3875 INIT_LIST_HEAD(&check_dirs); 3876 3877 valid_path = fs_path_alloc(); 3878 if (!valid_path) { 3879 ret = -ENOMEM; 3880 goto out; 3881 } 3882 3883 /* 3884 * First, check if the first ref of the current inode was overwritten 3885 * before. If yes, we know that the current inode was already orphanized 3886 * and thus use the orphan name. If not, we can use get_cur_path to 3887 * get the path of the first ref as it would like while receiving at 3888 * this point in time. 3889 * New inodes are always orphan at the beginning, so force to use the 3890 * orphan name in this case. 3891 * The first ref is stored in valid_path and will be updated if it 3892 * gets moved around. 3893 */ 3894 if (!sctx->cur_inode_new) { 3895 ret = did_overwrite_first_ref(sctx, sctx->cur_ino, 3896 sctx->cur_inode_gen); 3897 if (ret < 0) 3898 goto out; 3899 if (ret) 3900 did_overwrite = 1; 3901 } 3902 if (sctx->cur_inode_new || did_overwrite) { 3903 ret = gen_unique_name(sctx, sctx->cur_ino, 3904 sctx->cur_inode_gen, valid_path); 3905 if (ret < 0) 3906 goto out; 3907 is_orphan = 1; 3908 } else { 3909 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, 3910 valid_path); 3911 if (ret < 0) 3912 goto out; 3913 } 3914 3915 /* 3916 * Before doing any rename and link operations, do a first pass on the 3917 * new references to orphanize any unprocessed inodes that may have a 3918 * reference that conflicts with one of the new references of the current 3919 * inode. This needs to happen first because a new reference may conflict 3920 * with the old reference of a parent directory, so we must make sure 3921 * that the path used for link and rename commands don't use an 3922 * orphanized name when an ancestor was not yet orphanized. 3923 * 3924 * Example: 3925 * 3926 * Parent snapshot: 3927 * 3928 * . (ino 256) 3929 * |----- testdir/ (ino 259) 3930 * | |----- a (ino 257) 3931 * | 3932 * |----- b (ino 258) 3933 * 3934 * Send snapshot: 3935 * 3936 * . (ino 256) 3937 * |----- testdir_2/ (ino 259) 3938 * | |----- a (ino 260) 3939 * | 3940 * |----- testdir (ino 257) 3941 * |----- b (ino 257) 3942 * |----- b2 (ino 258) 3943 * 3944 * Processing the new reference for inode 257 with name "b" may happen 3945 * before processing the new reference with name "testdir". If so, we 3946 * must make sure that by the time we send a link command to create the 3947 * hard link "b", inode 259 was already orphanized, since the generated 3948 * path in "valid_path" already contains the orphanized name for 259. 3949 * We are processing inode 257, so only later when processing 259 we do 3950 * the rename operation to change its temporary (orphanized) name to 3951 * "testdir_2". 3952 */ 3953 list_for_each_entry(cur, &sctx->new_refs, list) { 3954 ret = get_cur_inode_state(sctx, cur->dir, cur->dir_gen); 3955 if (ret < 0) 3956 goto out; 3957 if (ret == inode_state_will_create) 3958 continue; 3959 3960 /* 3961 * Check if this new ref would overwrite the first ref of another 3962 * unprocessed inode. If yes, orphanize the overwritten inode. 3963 * If we find an overwritten ref that is not the first ref, 3964 * simply unlink it. 3965 */ 3966 ret = will_overwrite_ref(sctx, cur->dir, cur->dir_gen, 3967 cur->name, cur->name_len, 3968 &ow_inode, &ow_gen, &ow_mode); 3969 if (ret < 0) 3970 goto out; 3971 if (ret) { 3972 ret = is_first_ref(sctx->parent_root, 3973 ow_inode, cur->dir, cur->name, 3974 cur->name_len); 3975 if (ret < 0) 3976 goto out; 3977 if (ret) { 3978 struct name_cache_entry *nce; 3979 struct waiting_dir_move *wdm; 3980 3981 if (orphanized_dir) { 3982 ret = refresh_ref_path(sctx, cur); 3983 if (ret < 0) 3984 goto out; 3985 } 3986 3987 ret = orphanize_inode(sctx, ow_inode, ow_gen, 3988 cur->full_path); 3989 if (ret < 0) 3990 goto out; 3991 if (S_ISDIR(ow_mode)) 3992 orphanized_dir = true; 3993 3994 /* 3995 * If ow_inode has its rename operation delayed 3996 * make sure that its orphanized name is used in 3997 * the source path when performing its rename 3998 * operation. 3999 */ 4000 if (is_waiting_for_move(sctx, ow_inode)) { 4001 wdm = get_waiting_dir_move(sctx, 4002 ow_inode); 4003 ASSERT(wdm); 4004 wdm->orphanized = true; 4005 } 4006 4007 /* 4008 * Make sure we clear our orphanized inode's 4009 * name from the name cache. This is because the 4010 * inode ow_inode might be an ancestor of some 4011 * other inode that will be orphanized as well 4012 * later and has an inode number greater than 4013 * sctx->send_progress. We need to prevent 4014 * future name lookups from using the old name 4015 * and get instead the orphan name. 4016 */ 4017 nce = name_cache_search(sctx, ow_inode, ow_gen); 4018 if (nce) { 4019 name_cache_delete(sctx, nce); 4020 kfree(nce); 4021 } 4022 4023 /* 4024 * ow_inode might currently be an ancestor of 4025 * cur_ino, therefore compute valid_path (the 4026 * current path of cur_ino) again because it 4027 * might contain the pre-orphanization name of 4028 * ow_inode, which is no longer valid. 4029 */ 4030 ret = is_ancestor(sctx->parent_root, 4031 ow_inode, ow_gen, 4032 sctx->cur_ino, NULL); 4033 if (ret > 0) { 4034 orphanized_ancestor = true; 4035 fs_path_reset(valid_path); 4036 ret = get_cur_path(sctx, sctx->cur_ino, 4037 sctx->cur_inode_gen, 4038 valid_path); 4039 } 4040 if (ret < 0) 4041 goto out; 4042 } else { 4043 /* 4044 * If we previously orphanized a directory that 4045 * collided with a new reference that we already 4046 * processed, recompute the current path because 4047 * that directory may be part of the path. 4048 */ 4049 if (orphanized_dir) { 4050 ret = refresh_ref_path(sctx, cur); 4051 if (ret < 0) 4052 goto out; 4053 } 4054 ret = send_unlink(sctx, cur->full_path); 4055 if (ret < 0) 4056 goto out; 4057 } 4058 } 4059 4060 } 4061 4062 list_for_each_entry(cur, &sctx->new_refs, list) { 4063 /* 4064 * We may have refs where the parent directory does not exist 4065 * yet. This happens if the parent directories inum is higher 4066 * than the current inum. To handle this case, we create the 4067 * parent directory out of order. But we need to check if this 4068 * did already happen before due to other refs in the same dir. 4069 */ 4070 ret = get_cur_inode_state(sctx, cur->dir, cur->dir_gen); 4071 if (ret < 0) 4072 goto out; 4073 if (ret == inode_state_will_create) { 4074 ret = 0; 4075 /* 4076 * First check if any of the current inodes refs did 4077 * already create the dir. 4078 */ 4079 list_for_each_entry(cur2, &sctx->new_refs, list) { 4080 if (cur == cur2) 4081 break; 4082 if (cur2->dir == cur->dir) { 4083 ret = 1; 4084 break; 4085 } 4086 } 4087 4088 /* 4089 * If that did not happen, check if a previous inode 4090 * did already create the dir. 4091 */ 4092 if (!ret) 4093 ret = did_create_dir(sctx, cur->dir); 4094 if (ret < 0) 4095 goto out; 4096 if (!ret) { 4097 ret = send_create_inode(sctx, cur->dir); 4098 if (ret < 0) 4099 goto out; 4100 } 4101 } 4102 4103 if (S_ISDIR(sctx->cur_inode_mode) && sctx->parent_root) { 4104 ret = wait_for_dest_dir_move(sctx, cur, is_orphan); 4105 if (ret < 0) 4106 goto out; 4107 if (ret == 1) { 4108 can_rename = false; 4109 *pending_move = 1; 4110 } 4111 } 4112 4113 if (S_ISDIR(sctx->cur_inode_mode) && sctx->parent_root && 4114 can_rename) { 4115 ret = wait_for_parent_move(sctx, cur, is_orphan); 4116 if (ret < 0) 4117 goto out; 4118 if (ret == 1) { 4119 can_rename = false; 4120 *pending_move = 1; 4121 } 4122 } 4123 4124 /* 4125 * link/move the ref to the new place. If we have an orphan 4126 * inode, move it and update valid_path. If not, link or move 4127 * it depending on the inode mode. 4128 */ 4129 if (is_orphan && can_rename) { 4130 ret = send_rename(sctx, valid_path, cur->full_path); 4131 if (ret < 0) 4132 goto out; 4133 is_orphan = 0; 4134 ret = fs_path_copy(valid_path, cur->full_path); 4135 if (ret < 0) 4136 goto out; 4137 } else if (can_rename) { 4138 if (S_ISDIR(sctx->cur_inode_mode)) { 4139 /* 4140 * Dirs can't be linked, so move it. For moved 4141 * dirs, we always have one new and one deleted 4142 * ref. The deleted ref is ignored later. 4143 */ 4144 ret = send_rename(sctx, valid_path, 4145 cur->full_path); 4146 if (!ret) 4147 ret = fs_path_copy(valid_path, 4148 cur->full_path); 4149 if (ret < 0) 4150 goto out; 4151 } else { 4152 /* 4153 * We might have previously orphanized an inode 4154 * which is an ancestor of our current inode, 4155 * so our reference's full path, which was 4156 * computed before any such orphanizations, must 4157 * be updated. 4158 */ 4159 if (orphanized_dir) { 4160 ret = update_ref_path(sctx, cur); 4161 if (ret < 0) 4162 goto out; 4163 } 4164 ret = send_link(sctx, cur->full_path, 4165 valid_path); 4166 if (ret < 0) 4167 goto out; 4168 } 4169 } 4170 ret = dup_ref(cur, &check_dirs); 4171 if (ret < 0) 4172 goto out; 4173 } 4174 4175 if (S_ISDIR(sctx->cur_inode_mode) && sctx->cur_inode_deleted) { 4176 /* 4177 * Check if we can already rmdir the directory. If not, 4178 * orphanize it. For every dir item inside that gets deleted 4179 * later, we do this check again and rmdir it then if possible. 4180 * See the use of check_dirs for more details. 4181 */ 4182 ret = can_rmdir(sctx, sctx->cur_ino, sctx->cur_inode_gen, 4183 sctx->cur_ino); 4184 if (ret < 0) 4185 goto out; 4186 if (ret) { 4187 ret = send_rmdir(sctx, valid_path); 4188 if (ret < 0) 4189 goto out; 4190 } else if (!is_orphan) { 4191 ret = orphanize_inode(sctx, sctx->cur_ino, 4192 sctx->cur_inode_gen, valid_path); 4193 if (ret < 0) 4194 goto out; 4195 is_orphan = 1; 4196 } 4197 4198 list_for_each_entry(cur, &sctx->deleted_refs, list) { 4199 ret = dup_ref(cur, &check_dirs); 4200 if (ret < 0) 4201 goto out; 4202 } 4203 } else if (S_ISDIR(sctx->cur_inode_mode) && 4204 !list_empty(&sctx->deleted_refs)) { 4205 /* 4206 * We have a moved dir. Add the old parent to check_dirs 4207 */ 4208 cur = list_entry(sctx->deleted_refs.next, struct recorded_ref, 4209 list); 4210 ret = dup_ref(cur, &check_dirs); 4211 if (ret < 0) 4212 goto out; 4213 } else if (!S_ISDIR(sctx->cur_inode_mode)) { 4214 /* 4215 * We have a non dir inode. Go through all deleted refs and 4216 * unlink them if they were not already overwritten by other 4217 * inodes. 4218 */ 4219 list_for_each_entry(cur, &sctx->deleted_refs, list) { 4220 ret = did_overwrite_ref(sctx, cur->dir, cur->dir_gen, 4221 sctx->cur_ino, sctx->cur_inode_gen, 4222 cur->name, cur->name_len); 4223 if (ret < 0) 4224 goto out; 4225 if (!ret) { 4226 /* 4227 * If we orphanized any ancestor before, we need 4228 * to recompute the full path for deleted names, 4229 * since any such path was computed before we 4230 * processed any references and orphanized any 4231 * ancestor inode. 4232 */ 4233 if (orphanized_ancestor) { 4234 ret = update_ref_path(sctx, cur); 4235 if (ret < 0) 4236 goto out; 4237 } 4238 ret = send_unlink(sctx, cur->full_path); 4239 if (ret < 0) 4240 goto out; 4241 } 4242 ret = dup_ref(cur, &check_dirs); 4243 if (ret < 0) 4244 goto out; 4245 } 4246 /* 4247 * If the inode is still orphan, unlink the orphan. This may 4248 * happen when a previous inode did overwrite the first ref 4249 * of this inode and no new refs were added for the current 4250 * inode. Unlinking does not mean that the inode is deleted in 4251 * all cases. There may still be links to this inode in other 4252 * places. 4253 */ 4254 if (is_orphan) { 4255 ret = send_unlink(sctx, valid_path); 4256 if (ret < 0) 4257 goto out; 4258 } 4259 } 4260 4261 /* 4262 * We did collect all parent dirs where cur_inode was once located. We 4263 * now go through all these dirs and check if they are pending for 4264 * deletion and if it's finally possible to perform the rmdir now. 4265 * We also update the inode stats of the parent dirs here. 4266 */ 4267 list_for_each_entry(cur, &check_dirs, list) { 4268 /* 4269 * In case we had refs into dirs that were not processed yet, 4270 * we don't need to do the utime and rmdir logic for these dirs. 4271 * The dir will be processed later. 4272 */ 4273 if (cur->dir > sctx->cur_ino) 4274 continue; 4275 4276 ret = get_cur_inode_state(sctx, cur->dir, cur->dir_gen); 4277 if (ret < 0) 4278 goto out; 4279 4280 if (ret == inode_state_did_create || 4281 ret == inode_state_no_change) { 4282 /* TODO delayed utimes */ 4283 ret = send_utimes(sctx, cur->dir, cur->dir_gen); 4284 if (ret < 0) 4285 goto out; 4286 } else if (ret == inode_state_did_delete && 4287 cur->dir != last_dir_ino_rm) { 4288 ret = can_rmdir(sctx, cur->dir, cur->dir_gen, 4289 sctx->cur_ino); 4290 if (ret < 0) 4291 goto out; 4292 if (ret) { 4293 ret = get_cur_path(sctx, cur->dir, 4294 cur->dir_gen, valid_path); 4295 if (ret < 0) 4296 goto out; 4297 ret = send_rmdir(sctx, valid_path); 4298 if (ret < 0) 4299 goto out; 4300 last_dir_ino_rm = cur->dir; 4301 } 4302 } 4303 } 4304 4305 ret = 0; 4306 4307 out: 4308 __free_recorded_refs(&check_dirs); 4309 free_recorded_refs(sctx); 4310 fs_path_free(valid_path); 4311 return ret; 4312 } 4313 4314 static int record_ref(struct btrfs_root *root, u64 dir, struct fs_path *name, 4315 void *ctx, struct list_head *refs) 4316 { 4317 int ret = 0; 4318 struct send_ctx *sctx = ctx; 4319 struct fs_path *p; 4320 u64 gen; 4321 4322 p = fs_path_alloc(); 4323 if (!p) 4324 return -ENOMEM; 4325 4326 ret = get_inode_info(root, dir, NULL, &gen, NULL, NULL, 4327 NULL, NULL); 4328 if (ret < 0) 4329 goto out; 4330 4331 ret = get_cur_path(sctx, dir, gen, p); 4332 if (ret < 0) 4333 goto out; 4334 ret = fs_path_add_path(p, name); 4335 if (ret < 0) 4336 goto out; 4337 4338 ret = __record_ref(refs, dir, gen, p); 4339 4340 out: 4341 if (ret) 4342 fs_path_free(p); 4343 return ret; 4344 } 4345 4346 static int __record_new_ref(int num, u64 dir, int index, 4347 struct fs_path *name, 4348 void *ctx) 4349 { 4350 struct send_ctx *sctx = ctx; 4351 return record_ref(sctx->send_root, dir, name, ctx, &sctx->new_refs); 4352 } 4353 4354 4355 static int __record_deleted_ref(int num, u64 dir, int index, 4356 struct fs_path *name, 4357 void *ctx) 4358 { 4359 struct send_ctx *sctx = ctx; 4360 return record_ref(sctx->parent_root, dir, name, ctx, 4361 &sctx->deleted_refs); 4362 } 4363 4364 static int record_new_ref(struct send_ctx *sctx) 4365 { 4366 int ret; 4367 4368 ret = iterate_inode_ref(sctx->send_root, sctx->left_path, 4369 sctx->cmp_key, 0, __record_new_ref, sctx); 4370 if (ret < 0) 4371 goto out; 4372 ret = 0; 4373 4374 out: 4375 return ret; 4376 } 4377 4378 static int record_deleted_ref(struct send_ctx *sctx) 4379 { 4380 int ret; 4381 4382 ret = iterate_inode_ref(sctx->parent_root, sctx->right_path, 4383 sctx->cmp_key, 0, __record_deleted_ref, sctx); 4384 if (ret < 0) 4385 goto out; 4386 ret = 0; 4387 4388 out: 4389 return ret; 4390 } 4391 4392 struct find_ref_ctx { 4393 u64 dir; 4394 u64 dir_gen; 4395 struct btrfs_root *root; 4396 struct fs_path *name; 4397 int found_idx; 4398 }; 4399 4400 static int __find_iref(int num, u64 dir, int index, 4401 struct fs_path *name, 4402 void *ctx_) 4403 { 4404 struct find_ref_ctx *ctx = ctx_; 4405 u64 dir_gen; 4406 int ret; 4407 4408 if (dir == ctx->dir && fs_path_len(name) == fs_path_len(ctx->name) && 4409 strncmp(name->start, ctx->name->start, fs_path_len(name)) == 0) { 4410 /* 4411 * To avoid doing extra lookups we'll only do this if everything 4412 * else matches. 4413 */ 4414 ret = get_inode_info(ctx->root, dir, NULL, &dir_gen, NULL, 4415 NULL, NULL, NULL); 4416 if (ret) 4417 return ret; 4418 if (dir_gen != ctx->dir_gen) 4419 return 0; 4420 ctx->found_idx = num; 4421 return 1; 4422 } 4423 return 0; 4424 } 4425 4426 static int find_iref(struct btrfs_root *root, 4427 struct btrfs_path *path, 4428 struct btrfs_key *key, 4429 u64 dir, u64 dir_gen, struct fs_path *name) 4430 { 4431 int ret; 4432 struct find_ref_ctx ctx; 4433 4434 ctx.dir = dir; 4435 ctx.name = name; 4436 ctx.dir_gen = dir_gen; 4437 ctx.found_idx = -1; 4438 ctx.root = root; 4439 4440 ret = iterate_inode_ref(root, path, key, 0, __find_iref, &ctx); 4441 if (ret < 0) 4442 return ret; 4443 4444 if (ctx.found_idx == -1) 4445 return -ENOENT; 4446 4447 return ctx.found_idx; 4448 } 4449 4450 static int __record_changed_new_ref(int num, u64 dir, int index, 4451 struct fs_path *name, 4452 void *ctx) 4453 { 4454 u64 dir_gen; 4455 int ret; 4456 struct send_ctx *sctx = ctx; 4457 4458 ret = get_inode_info(sctx->send_root, dir, NULL, &dir_gen, NULL, 4459 NULL, NULL, NULL); 4460 if (ret) 4461 return ret; 4462 4463 ret = find_iref(sctx->parent_root, sctx->right_path, 4464 sctx->cmp_key, dir, dir_gen, name); 4465 if (ret == -ENOENT) 4466 ret = __record_new_ref(num, dir, index, name, sctx); 4467 else if (ret > 0) 4468 ret = 0; 4469 4470 return ret; 4471 } 4472 4473 static int __record_changed_deleted_ref(int num, u64 dir, int index, 4474 struct fs_path *name, 4475 void *ctx) 4476 { 4477 u64 dir_gen; 4478 int ret; 4479 struct send_ctx *sctx = ctx; 4480 4481 ret = get_inode_info(sctx->parent_root, dir, NULL, &dir_gen, NULL, 4482 NULL, NULL, NULL); 4483 if (ret) 4484 return ret; 4485 4486 ret = find_iref(sctx->send_root, sctx->left_path, sctx->cmp_key, 4487 dir, dir_gen, name); 4488 if (ret == -ENOENT) 4489 ret = __record_deleted_ref(num, dir, index, name, sctx); 4490 else if (ret > 0) 4491 ret = 0; 4492 4493 return ret; 4494 } 4495 4496 static int record_changed_ref(struct send_ctx *sctx) 4497 { 4498 int ret = 0; 4499 4500 ret = iterate_inode_ref(sctx->send_root, sctx->left_path, 4501 sctx->cmp_key, 0, __record_changed_new_ref, sctx); 4502 if (ret < 0) 4503 goto out; 4504 ret = iterate_inode_ref(sctx->parent_root, sctx->right_path, 4505 sctx->cmp_key, 0, __record_changed_deleted_ref, sctx); 4506 if (ret < 0) 4507 goto out; 4508 ret = 0; 4509 4510 out: 4511 return ret; 4512 } 4513 4514 /* 4515 * Record and process all refs at once. Needed when an inode changes the 4516 * generation number, which means that it was deleted and recreated. 4517 */ 4518 static int process_all_refs(struct send_ctx *sctx, 4519 enum btrfs_compare_tree_result cmd) 4520 { 4521 int ret = 0; 4522 int iter_ret = 0; 4523 struct btrfs_root *root; 4524 struct btrfs_path *path; 4525 struct btrfs_key key; 4526 struct btrfs_key found_key; 4527 iterate_inode_ref_t cb; 4528 int pending_move = 0; 4529 4530 path = alloc_path_for_send(); 4531 if (!path) 4532 return -ENOMEM; 4533 4534 if (cmd == BTRFS_COMPARE_TREE_NEW) { 4535 root = sctx->send_root; 4536 cb = __record_new_ref; 4537 } else if (cmd == BTRFS_COMPARE_TREE_DELETED) { 4538 root = sctx->parent_root; 4539 cb = __record_deleted_ref; 4540 } else { 4541 btrfs_err(sctx->send_root->fs_info, 4542 "Wrong command %d in process_all_refs", cmd); 4543 ret = -EINVAL; 4544 goto out; 4545 } 4546 4547 key.objectid = sctx->cmp_key->objectid; 4548 key.type = BTRFS_INODE_REF_KEY; 4549 key.offset = 0; 4550 btrfs_for_each_slot(root, &key, &found_key, path, iter_ret) { 4551 if (found_key.objectid != key.objectid || 4552 (found_key.type != BTRFS_INODE_REF_KEY && 4553 found_key.type != BTRFS_INODE_EXTREF_KEY)) 4554 break; 4555 4556 ret = iterate_inode_ref(root, path, &found_key, 0, cb, sctx); 4557 if (ret < 0) 4558 goto out; 4559 } 4560 /* Catch error found during iteration */ 4561 if (iter_ret < 0) { 4562 ret = iter_ret; 4563 goto out; 4564 } 4565 btrfs_release_path(path); 4566 4567 /* 4568 * We don't actually care about pending_move as we are simply 4569 * re-creating this inode and will be rename'ing it into place once we 4570 * rename the parent directory. 4571 */ 4572 ret = process_recorded_refs(sctx, &pending_move); 4573 out: 4574 btrfs_free_path(path); 4575 return ret; 4576 } 4577 4578 static int send_set_xattr(struct send_ctx *sctx, 4579 struct fs_path *path, 4580 const char *name, int name_len, 4581 const char *data, int data_len) 4582 { 4583 int ret = 0; 4584 4585 ret = begin_cmd(sctx, BTRFS_SEND_C_SET_XATTR); 4586 if (ret < 0) 4587 goto out; 4588 4589 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path); 4590 TLV_PUT_STRING(sctx, BTRFS_SEND_A_XATTR_NAME, name, name_len); 4591 TLV_PUT(sctx, BTRFS_SEND_A_XATTR_DATA, data, data_len); 4592 4593 ret = send_cmd(sctx); 4594 4595 tlv_put_failure: 4596 out: 4597 return ret; 4598 } 4599 4600 static int send_remove_xattr(struct send_ctx *sctx, 4601 struct fs_path *path, 4602 const char *name, int name_len) 4603 { 4604 int ret = 0; 4605 4606 ret = begin_cmd(sctx, BTRFS_SEND_C_REMOVE_XATTR); 4607 if (ret < 0) 4608 goto out; 4609 4610 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, path); 4611 TLV_PUT_STRING(sctx, BTRFS_SEND_A_XATTR_NAME, name, name_len); 4612 4613 ret = send_cmd(sctx); 4614 4615 tlv_put_failure: 4616 out: 4617 return ret; 4618 } 4619 4620 static int __process_new_xattr(int num, struct btrfs_key *di_key, 4621 const char *name, int name_len, const char *data, 4622 int data_len, void *ctx) 4623 { 4624 int ret; 4625 struct send_ctx *sctx = ctx; 4626 struct fs_path *p; 4627 struct posix_acl_xattr_header dummy_acl; 4628 4629 /* Capabilities are emitted by finish_inode_if_needed */ 4630 if (!strncmp(name, XATTR_NAME_CAPS, name_len)) 4631 return 0; 4632 4633 p = fs_path_alloc(); 4634 if (!p) 4635 return -ENOMEM; 4636 4637 /* 4638 * This hack is needed because empty acls are stored as zero byte 4639 * data in xattrs. Problem with that is, that receiving these zero byte 4640 * acls will fail later. To fix this, we send a dummy acl list that 4641 * only contains the version number and no entries. 4642 */ 4643 if (!strncmp(name, XATTR_NAME_POSIX_ACL_ACCESS, name_len) || 4644 !strncmp(name, XATTR_NAME_POSIX_ACL_DEFAULT, name_len)) { 4645 if (data_len == 0) { 4646 dummy_acl.a_version = 4647 cpu_to_le32(POSIX_ACL_XATTR_VERSION); 4648 data = (char *)&dummy_acl; 4649 data_len = sizeof(dummy_acl); 4650 } 4651 } 4652 4653 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p); 4654 if (ret < 0) 4655 goto out; 4656 4657 ret = send_set_xattr(sctx, p, name, name_len, data, data_len); 4658 4659 out: 4660 fs_path_free(p); 4661 return ret; 4662 } 4663 4664 static int __process_deleted_xattr(int num, struct btrfs_key *di_key, 4665 const char *name, int name_len, 4666 const char *data, int data_len, void *ctx) 4667 { 4668 int ret; 4669 struct send_ctx *sctx = ctx; 4670 struct fs_path *p; 4671 4672 p = fs_path_alloc(); 4673 if (!p) 4674 return -ENOMEM; 4675 4676 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p); 4677 if (ret < 0) 4678 goto out; 4679 4680 ret = send_remove_xattr(sctx, p, name, name_len); 4681 4682 out: 4683 fs_path_free(p); 4684 return ret; 4685 } 4686 4687 static int process_new_xattr(struct send_ctx *sctx) 4688 { 4689 int ret = 0; 4690 4691 ret = iterate_dir_item(sctx->send_root, sctx->left_path, 4692 __process_new_xattr, sctx); 4693 4694 return ret; 4695 } 4696 4697 static int process_deleted_xattr(struct send_ctx *sctx) 4698 { 4699 return iterate_dir_item(sctx->parent_root, sctx->right_path, 4700 __process_deleted_xattr, sctx); 4701 } 4702 4703 struct find_xattr_ctx { 4704 const char *name; 4705 int name_len; 4706 int found_idx; 4707 char *found_data; 4708 int found_data_len; 4709 }; 4710 4711 static int __find_xattr(int num, struct btrfs_key *di_key, const char *name, 4712 int name_len, const char *data, int data_len, void *vctx) 4713 { 4714 struct find_xattr_ctx *ctx = vctx; 4715 4716 if (name_len == ctx->name_len && 4717 strncmp(name, ctx->name, name_len) == 0) { 4718 ctx->found_idx = num; 4719 ctx->found_data_len = data_len; 4720 ctx->found_data = kmemdup(data, data_len, GFP_KERNEL); 4721 if (!ctx->found_data) 4722 return -ENOMEM; 4723 return 1; 4724 } 4725 return 0; 4726 } 4727 4728 static int find_xattr(struct btrfs_root *root, 4729 struct btrfs_path *path, 4730 struct btrfs_key *key, 4731 const char *name, int name_len, 4732 char **data, int *data_len) 4733 { 4734 int ret; 4735 struct find_xattr_ctx ctx; 4736 4737 ctx.name = name; 4738 ctx.name_len = name_len; 4739 ctx.found_idx = -1; 4740 ctx.found_data = NULL; 4741 ctx.found_data_len = 0; 4742 4743 ret = iterate_dir_item(root, path, __find_xattr, &ctx); 4744 if (ret < 0) 4745 return ret; 4746 4747 if (ctx.found_idx == -1) 4748 return -ENOENT; 4749 if (data) { 4750 *data = ctx.found_data; 4751 *data_len = ctx.found_data_len; 4752 } else { 4753 kfree(ctx.found_data); 4754 } 4755 return ctx.found_idx; 4756 } 4757 4758 4759 static int __process_changed_new_xattr(int num, struct btrfs_key *di_key, 4760 const char *name, int name_len, 4761 const char *data, int data_len, 4762 void *ctx) 4763 { 4764 int ret; 4765 struct send_ctx *sctx = ctx; 4766 char *found_data = NULL; 4767 int found_data_len = 0; 4768 4769 ret = find_xattr(sctx->parent_root, sctx->right_path, 4770 sctx->cmp_key, name, name_len, &found_data, 4771 &found_data_len); 4772 if (ret == -ENOENT) { 4773 ret = __process_new_xattr(num, di_key, name, name_len, data, 4774 data_len, ctx); 4775 } else if (ret >= 0) { 4776 if (data_len != found_data_len || 4777 memcmp(data, found_data, data_len)) { 4778 ret = __process_new_xattr(num, di_key, name, name_len, 4779 data, data_len, ctx); 4780 } else { 4781 ret = 0; 4782 } 4783 } 4784 4785 kfree(found_data); 4786 return ret; 4787 } 4788 4789 static int __process_changed_deleted_xattr(int num, struct btrfs_key *di_key, 4790 const char *name, int name_len, 4791 const char *data, int data_len, 4792 void *ctx) 4793 { 4794 int ret; 4795 struct send_ctx *sctx = ctx; 4796 4797 ret = find_xattr(sctx->send_root, sctx->left_path, sctx->cmp_key, 4798 name, name_len, NULL, NULL); 4799 if (ret == -ENOENT) 4800 ret = __process_deleted_xattr(num, di_key, name, name_len, data, 4801 data_len, ctx); 4802 else if (ret >= 0) 4803 ret = 0; 4804 4805 return ret; 4806 } 4807 4808 static int process_changed_xattr(struct send_ctx *sctx) 4809 { 4810 int ret = 0; 4811 4812 ret = iterate_dir_item(sctx->send_root, sctx->left_path, 4813 __process_changed_new_xattr, sctx); 4814 if (ret < 0) 4815 goto out; 4816 ret = iterate_dir_item(sctx->parent_root, sctx->right_path, 4817 __process_changed_deleted_xattr, sctx); 4818 4819 out: 4820 return ret; 4821 } 4822 4823 static int process_all_new_xattrs(struct send_ctx *sctx) 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 4832 path = alloc_path_for_send(); 4833 if (!path) 4834 return -ENOMEM; 4835 4836 root = sctx->send_root; 4837 4838 key.objectid = sctx->cmp_key->objectid; 4839 key.type = BTRFS_XATTR_ITEM_KEY; 4840 key.offset = 0; 4841 btrfs_for_each_slot(root, &key, &found_key, path, iter_ret) { 4842 if (found_key.objectid != key.objectid || 4843 found_key.type != key.type) { 4844 ret = 0; 4845 break; 4846 } 4847 4848 ret = iterate_dir_item(root, path, __process_new_xattr, sctx); 4849 if (ret < 0) 4850 break; 4851 } 4852 /* Catch error found during iteration */ 4853 if (iter_ret < 0) 4854 ret = iter_ret; 4855 4856 btrfs_free_path(path); 4857 return ret; 4858 } 4859 4860 static inline u64 max_send_read_size(const struct send_ctx *sctx) 4861 { 4862 return sctx->send_max_size - SZ_16K; 4863 } 4864 4865 static int put_data_header(struct send_ctx *sctx, u32 len) 4866 { 4867 struct btrfs_tlv_header *hdr; 4868 4869 if (sctx->send_max_size - sctx->send_size < sizeof(*hdr) + len) 4870 return -EOVERFLOW; 4871 hdr = (struct btrfs_tlv_header *)(sctx->send_buf + sctx->send_size); 4872 put_unaligned_le16(BTRFS_SEND_A_DATA, &hdr->tlv_type); 4873 put_unaligned_le16(len, &hdr->tlv_len); 4874 sctx->send_size += sizeof(*hdr); 4875 return 0; 4876 } 4877 4878 static int put_file_data(struct send_ctx *sctx, u64 offset, u32 len) 4879 { 4880 struct btrfs_root *root = sctx->send_root; 4881 struct btrfs_fs_info *fs_info = root->fs_info; 4882 struct page *page; 4883 pgoff_t index = offset >> PAGE_SHIFT; 4884 pgoff_t last_index; 4885 unsigned pg_offset = offset_in_page(offset); 4886 int ret; 4887 4888 ret = put_data_header(sctx, len); 4889 if (ret) 4890 return ret; 4891 4892 last_index = (offset + len - 1) >> PAGE_SHIFT; 4893 4894 while (index <= last_index) { 4895 unsigned cur_len = min_t(unsigned, len, 4896 PAGE_SIZE - pg_offset); 4897 4898 page = find_lock_page(sctx->cur_inode->i_mapping, index); 4899 if (!page) { 4900 page_cache_sync_readahead(sctx->cur_inode->i_mapping, 4901 &sctx->ra, NULL, index, 4902 last_index + 1 - index); 4903 4904 page = find_or_create_page(sctx->cur_inode->i_mapping, 4905 index, GFP_KERNEL); 4906 if (!page) { 4907 ret = -ENOMEM; 4908 break; 4909 } 4910 } 4911 4912 if (PageReadahead(page)) 4913 page_cache_async_readahead(sctx->cur_inode->i_mapping, 4914 &sctx->ra, NULL, page_folio(page), 4915 index, last_index + 1 - index); 4916 4917 if (!PageUptodate(page)) { 4918 btrfs_read_folio(NULL, page_folio(page)); 4919 lock_page(page); 4920 if (!PageUptodate(page)) { 4921 unlock_page(page); 4922 btrfs_err(fs_info, 4923 "send: IO error at offset %llu for inode %llu root %llu", 4924 page_offset(page), sctx->cur_ino, 4925 sctx->send_root->root_key.objectid); 4926 put_page(page); 4927 ret = -EIO; 4928 break; 4929 } 4930 } 4931 4932 memcpy_from_page(sctx->send_buf + sctx->send_size, page, 4933 pg_offset, cur_len); 4934 unlock_page(page); 4935 put_page(page); 4936 index++; 4937 pg_offset = 0; 4938 len -= cur_len; 4939 sctx->send_size += cur_len; 4940 } 4941 4942 return ret; 4943 } 4944 4945 /* 4946 * Read some bytes from the current inode/file and send a write command to 4947 * user space. 4948 */ 4949 static int send_write(struct send_ctx *sctx, u64 offset, u32 len) 4950 { 4951 struct btrfs_fs_info *fs_info = sctx->send_root->fs_info; 4952 int ret = 0; 4953 struct fs_path *p; 4954 4955 p = fs_path_alloc(); 4956 if (!p) 4957 return -ENOMEM; 4958 4959 btrfs_debug(fs_info, "send_write offset=%llu, len=%d", offset, len); 4960 4961 ret = begin_cmd(sctx, BTRFS_SEND_C_WRITE); 4962 if (ret < 0) 4963 goto out; 4964 4965 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p); 4966 if (ret < 0) 4967 goto out; 4968 4969 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p); 4970 TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset); 4971 ret = put_file_data(sctx, offset, len); 4972 if (ret < 0) 4973 goto out; 4974 4975 ret = send_cmd(sctx); 4976 4977 tlv_put_failure: 4978 out: 4979 fs_path_free(p); 4980 return ret; 4981 } 4982 4983 /* 4984 * Send a clone command to user space. 4985 */ 4986 static int send_clone(struct send_ctx *sctx, 4987 u64 offset, u32 len, 4988 struct clone_root *clone_root) 4989 { 4990 int ret = 0; 4991 struct fs_path *p; 4992 u64 gen; 4993 4994 btrfs_debug(sctx->send_root->fs_info, 4995 "send_clone offset=%llu, len=%d, clone_root=%llu, clone_inode=%llu, clone_offset=%llu", 4996 offset, len, clone_root->root->root_key.objectid, 4997 clone_root->ino, clone_root->offset); 4998 4999 p = fs_path_alloc(); 5000 if (!p) 5001 return -ENOMEM; 5002 5003 ret = begin_cmd(sctx, BTRFS_SEND_C_CLONE); 5004 if (ret < 0) 5005 goto out; 5006 5007 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p); 5008 if (ret < 0) 5009 goto out; 5010 5011 TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset); 5012 TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_LEN, len); 5013 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p); 5014 5015 if (clone_root->root == sctx->send_root) { 5016 ret = get_inode_info(sctx->send_root, clone_root->ino, NULL, 5017 &gen, NULL, NULL, NULL, NULL); 5018 if (ret < 0) 5019 goto out; 5020 ret = get_cur_path(sctx, clone_root->ino, gen, p); 5021 } else { 5022 ret = get_inode_path(clone_root->root, clone_root->ino, p); 5023 } 5024 if (ret < 0) 5025 goto out; 5026 5027 /* 5028 * If the parent we're using has a received_uuid set then use that as 5029 * our clone source as that is what we will look for when doing a 5030 * receive. 5031 * 5032 * This covers the case that we create a snapshot off of a received 5033 * subvolume and then use that as the parent and try to receive on a 5034 * different host. 5035 */ 5036 if (!btrfs_is_empty_uuid(clone_root->root->root_item.received_uuid)) 5037 TLV_PUT_UUID(sctx, BTRFS_SEND_A_CLONE_UUID, 5038 clone_root->root->root_item.received_uuid); 5039 else 5040 TLV_PUT_UUID(sctx, BTRFS_SEND_A_CLONE_UUID, 5041 clone_root->root->root_item.uuid); 5042 TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_CTRANSID, 5043 btrfs_root_ctransid(&clone_root->root->root_item)); 5044 TLV_PUT_PATH(sctx, BTRFS_SEND_A_CLONE_PATH, p); 5045 TLV_PUT_U64(sctx, BTRFS_SEND_A_CLONE_OFFSET, 5046 clone_root->offset); 5047 5048 ret = send_cmd(sctx); 5049 5050 tlv_put_failure: 5051 out: 5052 fs_path_free(p); 5053 return ret; 5054 } 5055 5056 /* 5057 * Send an update extent command to user space. 5058 */ 5059 static int send_update_extent(struct send_ctx *sctx, 5060 u64 offset, u32 len) 5061 { 5062 int ret = 0; 5063 struct fs_path *p; 5064 5065 p = fs_path_alloc(); 5066 if (!p) 5067 return -ENOMEM; 5068 5069 ret = begin_cmd(sctx, BTRFS_SEND_C_UPDATE_EXTENT); 5070 if (ret < 0) 5071 goto out; 5072 5073 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p); 5074 if (ret < 0) 5075 goto out; 5076 5077 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p); 5078 TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset); 5079 TLV_PUT_U64(sctx, BTRFS_SEND_A_SIZE, len); 5080 5081 ret = send_cmd(sctx); 5082 5083 tlv_put_failure: 5084 out: 5085 fs_path_free(p); 5086 return ret; 5087 } 5088 5089 static int send_hole(struct send_ctx *sctx, u64 end) 5090 { 5091 struct fs_path *p = NULL; 5092 u64 read_size = max_send_read_size(sctx); 5093 u64 offset = sctx->cur_inode_last_extent; 5094 int ret = 0; 5095 5096 /* 5097 * A hole that starts at EOF or beyond it. Since we do not yet support 5098 * fallocate (for extent preallocation and hole punching), sending a 5099 * write of zeroes starting at EOF or beyond would later require issuing 5100 * a truncate operation which would undo the write and achieve nothing. 5101 */ 5102 if (offset >= sctx->cur_inode_size) 5103 return 0; 5104 5105 /* 5106 * Don't go beyond the inode's i_size due to prealloc extents that start 5107 * after the i_size. 5108 */ 5109 end = min_t(u64, end, sctx->cur_inode_size); 5110 5111 if (sctx->flags & BTRFS_SEND_FLAG_NO_FILE_DATA) 5112 return send_update_extent(sctx, offset, end - offset); 5113 5114 p = fs_path_alloc(); 5115 if (!p) 5116 return -ENOMEM; 5117 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, p); 5118 if (ret < 0) 5119 goto tlv_put_failure; 5120 while (offset < end) { 5121 u64 len = min(end - offset, read_size); 5122 5123 ret = begin_cmd(sctx, BTRFS_SEND_C_WRITE); 5124 if (ret < 0) 5125 break; 5126 TLV_PUT_PATH(sctx, BTRFS_SEND_A_PATH, p); 5127 TLV_PUT_U64(sctx, BTRFS_SEND_A_FILE_OFFSET, offset); 5128 ret = put_data_header(sctx, len); 5129 if (ret < 0) 5130 break; 5131 memset(sctx->send_buf + sctx->send_size, 0, len); 5132 sctx->send_size += len; 5133 ret = send_cmd(sctx); 5134 if (ret < 0) 5135 break; 5136 offset += len; 5137 } 5138 sctx->cur_inode_next_write_offset = offset; 5139 tlv_put_failure: 5140 fs_path_free(p); 5141 return ret; 5142 } 5143 5144 static int send_extent_data(struct send_ctx *sctx, 5145 const u64 offset, 5146 const u64 len) 5147 { 5148 const u64 end = offset + len; 5149 u64 read_size = max_send_read_size(sctx); 5150 u64 sent = 0; 5151 5152 if (sctx->flags & BTRFS_SEND_FLAG_NO_FILE_DATA) 5153 return send_update_extent(sctx, offset, len); 5154 5155 if (sctx->cur_inode == NULL) { 5156 struct btrfs_root *root = sctx->send_root; 5157 5158 sctx->cur_inode = btrfs_iget(root->fs_info->sb, sctx->cur_ino, root); 5159 if (IS_ERR(sctx->cur_inode)) { 5160 int err = PTR_ERR(sctx->cur_inode); 5161 5162 sctx->cur_inode = NULL; 5163 return err; 5164 } 5165 memset(&sctx->ra, 0, sizeof(struct file_ra_state)); 5166 file_ra_state_init(&sctx->ra, sctx->cur_inode->i_mapping); 5167 5168 /* 5169 * It's very likely there are no pages from this inode in the page 5170 * cache, so after reading extents and sending their data, we clean 5171 * the page cache to avoid trashing the page cache (adding pressure 5172 * to the page cache and forcing eviction of other data more useful 5173 * for applications). 5174 * 5175 * We decide if we should clean the page cache simply by checking 5176 * if the inode's mapping nrpages is 0 when we first open it, and 5177 * not by using something like filemap_range_has_page() before 5178 * reading an extent because when we ask the readahead code to 5179 * read a given file range, it may (and almost always does) read 5180 * pages from beyond that range (see the documentation for 5181 * page_cache_sync_readahead()), so it would not be reliable, 5182 * because after reading the first extent future calls to 5183 * filemap_range_has_page() would return true because the readahead 5184 * on the previous extent resulted in reading pages of the current 5185 * extent as well. 5186 */ 5187 sctx->clean_page_cache = (sctx->cur_inode->i_mapping->nrpages == 0); 5188 sctx->page_cache_clear_start = round_down(offset, PAGE_SIZE); 5189 } 5190 5191 while (sent < len) { 5192 u64 size = min(len - sent, read_size); 5193 int ret; 5194 5195 ret = send_write(sctx, offset + sent, size); 5196 if (ret < 0) 5197 return ret; 5198 sent += size; 5199 } 5200 5201 if (sctx->clean_page_cache && IS_ALIGNED(end, PAGE_SIZE)) { 5202 /* 5203 * Always operate only on ranges that are a multiple of the page 5204 * size. This is not only to prevent zeroing parts of a page in 5205 * the case of subpage sector size, but also to guarantee we evict 5206 * pages, as passing a range that is smaller than page size does 5207 * not evict the respective page (only zeroes part of its content). 5208 * 5209 * Always start from the end offset of the last range cleared. 5210 * This is because the readahead code may (and very often does) 5211 * reads pages beyond the range we request for readahead. So if 5212 * we have an extent layout like this: 5213 * 5214 * [ extent A ] [ extent B ] [ extent C ] 5215 * 5216 * When we ask page_cache_sync_readahead() to read extent A, it 5217 * may also trigger reads for pages of extent B. If we are doing 5218 * an incremental send and extent B has not changed between the 5219 * parent and send snapshots, some or all of its pages may end 5220 * up being read and placed in the page cache. So when truncating 5221 * the page cache we always start from the end offset of the 5222 * previously processed extent up to the end of the current 5223 * extent. 5224 */ 5225 truncate_inode_pages_range(&sctx->cur_inode->i_data, 5226 sctx->page_cache_clear_start, 5227 end - 1); 5228 sctx->page_cache_clear_start = end; 5229 } 5230 5231 return 0; 5232 } 5233 5234 /* 5235 * Search for a capability xattr related to sctx->cur_ino. If the capability is 5236 * found, call send_set_xattr function to emit it. 5237 * 5238 * Return 0 if there isn't a capability, or when the capability was emitted 5239 * successfully, or < 0 if an error occurred. 5240 */ 5241 static int send_capabilities(struct send_ctx *sctx) 5242 { 5243 struct fs_path *fspath = NULL; 5244 struct btrfs_path *path; 5245 struct btrfs_dir_item *di; 5246 struct extent_buffer *leaf; 5247 unsigned long data_ptr; 5248 char *buf = NULL; 5249 int buf_len; 5250 int ret = 0; 5251 5252 path = alloc_path_for_send(); 5253 if (!path) 5254 return -ENOMEM; 5255 5256 di = btrfs_lookup_xattr(NULL, sctx->send_root, path, sctx->cur_ino, 5257 XATTR_NAME_CAPS, strlen(XATTR_NAME_CAPS), 0); 5258 if (!di) { 5259 /* There is no xattr for this inode */ 5260 goto out; 5261 } else if (IS_ERR(di)) { 5262 ret = PTR_ERR(di); 5263 goto out; 5264 } 5265 5266 leaf = path->nodes[0]; 5267 buf_len = btrfs_dir_data_len(leaf, di); 5268 5269 fspath = fs_path_alloc(); 5270 buf = kmalloc(buf_len, GFP_KERNEL); 5271 if (!fspath || !buf) { 5272 ret = -ENOMEM; 5273 goto out; 5274 } 5275 5276 ret = get_cur_path(sctx, sctx->cur_ino, sctx->cur_inode_gen, fspath); 5277 if (ret < 0) 5278 goto out; 5279 5280 data_ptr = (unsigned long)(di + 1) + btrfs_dir_name_len(leaf, di); 5281 read_extent_buffer(leaf, buf, data_ptr, buf_len); 5282 5283 ret = send_set_xattr(sctx, fspath, XATTR_NAME_CAPS, 5284 strlen(XATTR_NAME_CAPS), buf, buf_len); 5285 out: 5286 kfree(buf); 5287 fs_path_free(fspath); 5288 btrfs_free_path(path); 5289 return ret; 5290 } 5291 5292 static int clone_range(struct send_ctx *sctx, 5293 struct clone_root *clone_root, 5294 const u64 disk_byte, 5295 u64 data_offset, 5296 u64 offset, 5297 u64 len) 5298 { 5299 struct btrfs_path *path; 5300 struct btrfs_key key; 5301 int ret; 5302 u64 clone_src_i_size = 0; 5303 5304 /* 5305 * Prevent cloning from a zero offset with a length matching the sector 5306 * size because in some scenarios this will make the receiver fail. 5307 * 5308 * For example, if in the source filesystem the extent at offset 0 5309 * has a length of sectorsize and it was written using direct IO, then 5310 * it can never be an inline extent (even if compression is enabled). 5311 * Then this extent can be cloned in the original filesystem to a non 5312 * zero file offset, but it may not be possible to clone in the 5313 * destination filesystem because it can be inlined due to compression 5314 * on the destination filesystem (as the receiver's write operations are 5315 * always done using buffered IO). The same happens when the original 5316 * filesystem does not have compression enabled but the destination 5317 * filesystem has. 5318 */ 5319 if (clone_root->offset == 0 && 5320 len == sctx->send_root->fs_info->sectorsize) 5321 return send_extent_data(sctx, offset, len); 5322 5323 path = alloc_path_for_send(); 5324 if (!path) 5325 return -ENOMEM; 5326 5327 /* 5328 * There are inodes that have extents that lie behind its i_size. Don't 5329 * accept clones from these extents. 5330 */ 5331 ret = __get_inode_info(clone_root->root, path, clone_root->ino, 5332 &clone_src_i_size, NULL, NULL, NULL, NULL, NULL); 5333 btrfs_release_path(path); 5334 if (ret < 0) 5335 goto out; 5336 5337 /* 5338 * We can't send a clone operation for the entire range if we find 5339 * extent items in the respective range in the source file that 5340 * refer to different extents or if we find holes. 5341 * So check for that and do a mix of clone and regular write/copy 5342 * operations if needed. 5343 * 5344 * Example: 5345 * 5346 * mkfs.btrfs -f /dev/sda 5347 * mount /dev/sda /mnt 5348 * xfs_io -f -c "pwrite -S 0xaa 0K 100K" /mnt/foo 5349 * cp --reflink=always /mnt/foo /mnt/bar 5350 * xfs_io -c "pwrite -S 0xbb 50K 50K" /mnt/foo 5351 * btrfs subvolume snapshot -r /mnt /mnt/snap 5352 * 5353 * If when we send the snapshot and we are processing file bar (which 5354 * has a higher inode number than foo) we blindly send a clone operation 5355 * for the [0, 100K[ range from foo to bar, the receiver ends up getting 5356 * a file bar that matches the content of file foo - iow, doesn't match 5357 * the content from bar in the original filesystem. 5358 */ 5359 key.objectid = clone_root->ino; 5360 key.type = BTRFS_EXTENT_DATA_KEY; 5361 key.offset = clone_root->offset; 5362 ret = btrfs_search_slot(NULL, clone_root->root, &key, path, 0, 0); 5363 if (ret < 0) 5364 goto out; 5365 if (ret > 0 && path->slots[0] > 0) { 5366 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0] - 1); 5367 if (key.objectid == clone_root->ino && 5368 key.type == BTRFS_EXTENT_DATA_KEY) 5369 path->slots[0]--; 5370 } 5371 5372 while (true) { 5373 struct extent_buffer *leaf = path->nodes[0]; 5374 int slot = path->slots[0]; 5375 struct btrfs_file_extent_item *ei; 5376 u8 type; 5377 u64 ext_len; 5378 u64 clone_len; 5379 u64 clone_data_offset; 5380 5381 if (slot >= btrfs_header_nritems(leaf)) { 5382 ret = btrfs_next_leaf(clone_root->root, path); 5383 if (ret < 0) 5384 goto out; 5385 else if (ret > 0) 5386 break; 5387 continue; 5388 } 5389 5390 btrfs_item_key_to_cpu(leaf, &key, slot); 5391 5392 /* 5393 * We might have an implicit trailing hole (NO_HOLES feature 5394 * enabled). We deal with it after leaving this loop. 5395 */ 5396 if (key.objectid != clone_root->ino || 5397 key.type != BTRFS_EXTENT_DATA_KEY) 5398 break; 5399 5400 ei = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item); 5401 type = btrfs_file_extent_type(leaf, ei); 5402 if (type == BTRFS_FILE_EXTENT_INLINE) { 5403 ext_len = btrfs_file_extent_ram_bytes(leaf, ei); 5404 ext_len = PAGE_ALIGN(ext_len); 5405 } else { 5406 ext_len = btrfs_file_extent_num_bytes(leaf, ei); 5407 } 5408 5409 if (key.offset + ext_len <= clone_root->offset) 5410 goto next; 5411 5412 if (key.offset > clone_root->offset) { 5413 /* Implicit hole, NO_HOLES feature enabled. */ 5414 u64 hole_len = key.offset - clone_root->offset; 5415 5416 if (hole_len > len) 5417 hole_len = len; 5418 ret = send_extent_data(sctx, offset, hole_len); 5419 if (ret < 0) 5420 goto out; 5421 5422 len -= hole_len; 5423 if (len == 0) 5424 break; 5425 offset += hole_len; 5426 clone_root->offset += hole_len; 5427 data_offset += hole_len; 5428 } 5429 5430 if (key.offset >= clone_root->offset + len) 5431 break; 5432 5433 if (key.offset >= clone_src_i_size) 5434 break; 5435 5436 if (key.offset + ext_len > clone_src_i_size) 5437 ext_len = clone_src_i_size - key.offset; 5438 5439 clone_data_offset = btrfs_file_extent_offset(leaf, ei); 5440 if (btrfs_file_extent_disk_bytenr(leaf, ei) == disk_byte) { 5441 clone_root->offset = key.offset; 5442 if (clone_data_offset < data_offset && 5443 clone_data_offset + ext_len > data_offset) { 5444 u64 extent_offset; 5445 5446 extent_offset = data_offset - clone_data_offset; 5447 ext_len -= extent_offset; 5448 clone_data_offset += extent_offset; 5449 clone_root->offset += extent_offset; 5450 } 5451 } 5452 5453 clone_len = min_t(u64, ext_len, len); 5454 5455 if (btrfs_file_extent_disk_bytenr(leaf, ei) == disk_byte && 5456 clone_data_offset == data_offset) { 5457 const u64 src_end = clone_root->offset + clone_len; 5458 const u64 sectorsize = SZ_64K; 5459 5460 /* 5461 * We can't clone the last block, when its size is not 5462 * sector size aligned, into the middle of a file. If we 5463 * do so, the receiver will get a failure (-EINVAL) when 5464 * trying to clone or will silently corrupt the data in 5465 * the destination file if it's on a kernel without the 5466 * fix introduced by commit ac765f83f1397646 5467 * ("Btrfs: fix data corruption due to cloning of eof 5468 * block). 5469 * 5470 * So issue a clone of the aligned down range plus a 5471 * regular write for the eof block, if we hit that case. 5472 * 5473 * Also, we use the maximum possible sector size, 64K, 5474 * because we don't know what's the sector size of the 5475 * filesystem that receives the stream, so we have to 5476 * assume the largest possible sector size. 5477 */ 5478 if (src_end == clone_src_i_size && 5479 !IS_ALIGNED(src_end, sectorsize) && 5480 offset + clone_len < sctx->cur_inode_size) { 5481 u64 slen; 5482 5483 slen = ALIGN_DOWN(src_end - clone_root->offset, 5484 sectorsize); 5485 if (slen > 0) { 5486 ret = send_clone(sctx, offset, slen, 5487 clone_root); 5488 if (ret < 0) 5489 goto out; 5490 } 5491 ret = send_extent_data(sctx, offset + slen, 5492 clone_len - slen); 5493 } else { 5494 ret = send_clone(sctx, offset, clone_len, 5495 clone_root); 5496 } 5497 } else { 5498 ret = send_extent_data(sctx, offset, clone_len); 5499 } 5500 5501 if (ret < 0) 5502 goto out; 5503 5504 len -= clone_len; 5505 if (len == 0) 5506 break; 5507 offset += clone_len; 5508 clone_root->offset += clone_len; 5509 5510 /* 5511 * If we are cloning from the file we are currently processing, 5512 * and using the send root as the clone root, we must stop once 5513 * the current clone offset reaches the current eof of the file 5514 * at the receiver, otherwise we would issue an invalid clone 5515 * operation (source range going beyond eof) and cause the 5516 * receiver to fail. So if we reach the current eof, bail out 5517 * and fallback to a regular write. 5518 */ 5519 if (clone_root->root == sctx->send_root && 5520 clone_root->ino == sctx->cur_ino && 5521 clone_root->offset >= sctx->cur_inode_next_write_offset) 5522 break; 5523 5524 data_offset += clone_len; 5525 next: 5526 path->slots[0]++; 5527 } 5528 5529 if (len > 0) 5530 ret = send_extent_data(sctx, offset, len); 5531 else 5532 ret = 0; 5533 out: 5534 btrfs_free_path(path); 5535 return ret; 5536 } 5537 5538 static int send_write_or_clone(struct send_ctx *sctx, 5539 struct btrfs_path *path, 5540 struct btrfs_key *key, 5541 struct clone_root *clone_root) 5542 { 5543 int ret = 0; 5544 u64 offset = key->offset; 5545 u64 end; 5546 u64 bs = sctx->send_root->fs_info->sb->s_blocksize; 5547 5548 end = min_t(u64, btrfs_file_extent_end(path), sctx->cur_inode_size); 5549 if (offset >= end) 5550 return 0; 5551 5552 if (clone_root && IS_ALIGNED(end, bs)) { 5553 struct btrfs_file_extent_item *ei; 5554 u64 disk_byte; 5555 u64 data_offset; 5556 5557 ei = btrfs_item_ptr(path->nodes[0], path->slots[0], 5558 struct btrfs_file_extent_item); 5559 disk_byte = btrfs_file_extent_disk_bytenr(path->nodes[0], ei); 5560 data_offset = btrfs_file_extent_offset(path->nodes[0], ei); 5561 ret = clone_range(sctx, clone_root, disk_byte, data_offset, 5562 offset, end - offset); 5563 } else { 5564 ret = send_extent_data(sctx, offset, end - offset); 5565 } 5566 sctx->cur_inode_next_write_offset = end; 5567 return ret; 5568 } 5569 5570 static int is_extent_unchanged(struct send_ctx *sctx, 5571 struct btrfs_path *left_path, 5572 struct btrfs_key *ekey) 5573 { 5574 int ret = 0; 5575 struct btrfs_key key; 5576 struct btrfs_path *path = NULL; 5577 struct extent_buffer *eb; 5578 int slot; 5579 struct btrfs_key found_key; 5580 struct btrfs_file_extent_item *ei; 5581 u64 left_disknr; 5582 u64 right_disknr; 5583 u64 left_offset; 5584 u64 right_offset; 5585 u64 left_offset_fixed; 5586 u64 left_len; 5587 u64 right_len; 5588 u64 left_gen; 5589 u64 right_gen; 5590 u8 left_type; 5591 u8 right_type; 5592 5593 path = alloc_path_for_send(); 5594 if (!path) 5595 return -ENOMEM; 5596 5597 eb = left_path->nodes[0]; 5598 slot = left_path->slots[0]; 5599 ei = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item); 5600 left_type = btrfs_file_extent_type(eb, ei); 5601 5602 if (left_type != BTRFS_FILE_EXTENT_REG) { 5603 ret = 0; 5604 goto out; 5605 } 5606 left_disknr = btrfs_file_extent_disk_bytenr(eb, ei); 5607 left_len = btrfs_file_extent_num_bytes(eb, ei); 5608 left_offset = btrfs_file_extent_offset(eb, ei); 5609 left_gen = btrfs_file_extent_generation(eb, ei); 5610 5611 /* 5612 * Following comments will refer to these graphics. L is the left 5613 * extents which we are checking at the moment. 1-8 are the right 5614 * extents that we iterate. 5615 * 5616 * |-----L-----| 5617 * |-1-|-2a-|-3-|-4-|-5-|-6-| 5618 * 5619 * |-----L-----| 5620 * |--1--|-2b-|...(same as above) 5621 * 5622 * Alternative situation. Happens on files where extents got split. 5623 * |-----L-----| 5624 * |-----------7-----------|-6-| 5625 * 5626 * Alternative situation. Happens on files which got larger. 5627 * |-----L-----| 5628 * |-8-| 5629 * Nothing follows after 8. 5630 */ 5631 5632 key.objectid = ekey->objectid; 5633 key.type = BTRFS_EXTENT_DATA_KEY; 5634 key.offset = ekey->offset; 5635 ret = btrfs_search_slot_for_read(sctx->parent_root, &key, path, 0, 0); 5636 if (ret < 0) 5637 goto out; 5638 if (ret) { 5639 ret = 0; 5640 goto out; 5641 } 5642 5643 /* 5644 * Handle special case where the right side has no extents at all. 5645 */ 5646 eb = path->nodes[0]; 5647 slot = path->slots[0]; 5648 btrfs_item_key_to_cpu(eb, &found_key, slot); 5649 if (found_key.objectid != key.objectid || 5650 found_key.type != key.type) { 5651 /* If we're a hole then just pretend nothing changed */ 5652 ret = (left_disknr) ? 0 : 1; 5653 goto out; 5654 } 5655 5656 /* 5657 * We're now on 2a, 2b or 7. 5658 */ 5659 key = found_key; 5660 while (key.offset < ekey->offset + left_len) { 5661 ei = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item); 5662 right_type = btrfs_file_extent_type(eb, ei); 5663 if (right_type != BTRFS_FILE_EXTENT_REG && 5664 right_type != BTRFS_FILE_EXTENT_INLINE) { 5665 ret = 0; 5666 goto out; 5667 } 5668 5669 if (right_type == BTRFS_FILE_EXTENT_INLINE) { 5670 right_len = btrfs_file_extent_ram_bytes(eb, ei); 5671 right_len = PAGE_ALIGN(right_len); 5672 } else { 5673 right_len = btrfs_file_extent_num_bytes(eb, ei); 5674 } 5675 5676 /* 5677 * Are we at extent 8? If yes, we know the extent is changed. 5678 * This may only happen on the first iteration. 5679 */ 5680 if (found_key.offset + right_len <= ekey->offset) { 5681 /* If we're a hole just pretend nothing changed */ 5682 ret = (left_disknr) ? 0 : 1; 5683 goto out; 5684 } 5685 5686 /* 5687 * We just wanted to see if when we have an inline extent, what 5688 * follows it is a regular extent (wanted to check the above 5689 * condition for inline extents too). This should normally not 5690 * happen but it's possible for example when we have an inline 5691 * compressed extent representing data with a size matching 5692 * the page size (currently the same as sector size). 5693 */ 5694 if (right_type == BTRFS_FILE_EXTENT_INLINE) { 5695 ret = 0; 5696 goto out; 5697 } 5698 5699 right_disknr = btrfs_file_extent_disk_bytenr(eb, ei); 5700 right_offset = btrfs_file_extent_offset(eb, ei); 5701 right_gen = btrfs_file_extent_generation(eb, ei); 5702 5703 left_offset_fixed = left_offset; 5704 if (key.offset < ekey->offset) { 5705 /* Fix the right offset for 2a and 7. */ 5706 right_offset += ekey->offset - key.offset; 5707 } else { 5708 /* Fix the left offset for all behind 2a and 2b */ 5709 left_offset_fixed += key.offset - ekey->offset; 5710 } 5711 5712 /* 5713 * Check if we have the same extent. 5714 */ 5715 if (left_disknr != right_disknr || 5716 left_offset_fixed != right_offset || 5717 left_gen != right_gen) { 5718 ret = 0; 5719 goto out; 5720 } 5721 5722 /* 5723 * Go to the next extent. 5724 */ 5725 ret = btrfs_next_item(sctx->parent_root, path); 5726 if (ret < 0) 5727 goto out; 5728 if (!ret) { 5729 eb = path->nodes[0]; 5730 slot = path->slots[0]; 5731 btrfs_item_key_to_cpu(eb, &found_key, slot); 5732 } 5733 if (ret || found_key.objectid != key.objectid || 5734 found_key.type != key.type) { 5735 key.offset += right_len; 5736 break; 5737 } 5738 if (found_key.offset != key.offset + right_len) { 5739 ret = 0; 5740 goto out; 5741 } 5742 key = found_key; 5743 } 5744 5745 /* 5746 * We're now behind the left extent (treat as unchanged) or at the end 5747 * of the right side (treat as changed). 5748 */ 5749 if (key.offset >= ekey->offset + left_len) 5750 ret = 1; 5751 else 5752 ret = 0; 5753 5754 5755 out: 5756 btrfs_free_path(path); 5757 return ret; 5758 } 5759 5760 static int get_last_extent(struct send_ctx *sctx, u64 offset) 5761 { 5762 struct btrfs_path *path; 5763 struct btrfs_root *root = sctx->send_root; 5764 struct btrfs_key key; 5765 int ret; 5766 5767 path = alloc_path_for_send(); 5768 if (!path) 5769 return -ENOMEM; 5770 5771 sctx->cur_inode_last_extent = 0; 5772 5773 key.objectid = sctx->cur_ino; 5774 key.type = BTRFS_EXTENT_DATA_KEY; 5775 key.offset = offset; 5776 ret = btrfs_search_slot_for_read(root, &key, path, 0, 1); 5777 if (ret < 0) 5778 goto out; 5779 ret = 0; 5780 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); 5781 if (key.objectid != sctx->cur_ino || key.type != BTRFS_EXTENT_DATA_KEY) 5782 goto out; 5783 5784 sctx->cur_inode_last_extent = btrfs_file_extent_end(path); 5785 out: 5786 btrfs_free_path(path); 5787 return ret; 5788 } 5789 5790 static int range_is_hole_in_parent(struct send_ctx *sctx, 5791 const u64 start, 5792 const u64 end) 5793 { 5794 struct btrfs_path *path; 5795 struct btrfs_key key; 5796 struct btrfs_root *root = sctx->parent_root; 5797 u64 search_start = start; 5798 int ret; 5799 5800 path = alloc_path_for_send(); 5801 if (!path) 5802 return -ENOMEM; 5803 5804 key.objectid = sctx->cur_ino; 5805 key.type = BTRFS_EXTENT_DATA_KEY; 5806 key.offset = search_start; 5807 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 5808 if (ret < 0) 5809 goto out; 5810 if (ret > 0 && path->slots[0] > 0) 5811 path->slots[0]--; 5812 5813 while (search_start < end) { 5814 struct extent_buffer *leaf = path->nodes[0]; 5815 int slot = path->slots[0]; 5816 struct btrfs_file_extent_item *fi; 5817 u64 extent_end; 5818 5819 if (slot >= btrfs_header_nritems(leaf)) { 5820 ret = btrfs_next_leaf(root, path); 5821 if (ret < 0) 5822 goto out; 5823 else if (ret > 0) 5824 break; 5825 continue; 5826 } 5827 5828 btrfs_item_key_to_cpu(leaf, &key, slot); 5829 if (key.objectid < sctx->cur_ino || 5830 key.type < BTRFS_EXTENT_DATA_KEY) 5831 goto next; 5832 if (key.objectid > sctx->cur_ino || 5833 key.type > BTRFS_EXTENT_DATA_KEY || 5834 key.offset >= end) 5835 break; 5836 5837 fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item); 5838 extent_end = btrfs_file_extent_end(path); 5839 if (extent_end <= start) 5840 goto next; 5841 if (btrfs_file_extent_disk_bytenr(leaf, fi) == 0) { 5842 search_start = extent_end; 5843 goto next; 5844 } 5845 ret = 0; 5846 goto out; 5847 next: 5848 path->slots[0]++; 5849 } 5850 ret = 1; 5851 out: 5852 btrfs_free_path(path); 5853 return ret; 5854 } 5855 5856 static int maybe_send_hole(struct send_ctx *sctx, struct btrfs_path *path, 5857 struct btrfs_key *key) 5858 { 5859 int ret = 0; 5860 5861 if (sctx->cur_ino != key->objectid || !need_send_hole(sctx)) 5862 return 0; 5863 5864 if (sctx->cur_inode_last_extent == (u64)-1) { 5865 ret = get_last_extent(sctx, key->offset - 1); 5866 if (ret) 5867 return ret; 5868 } 5869 5870 if (path->slots[0] == 0 && 5871 sctx->cur_inode_last_extent < key->offset) { 5872 /* 5873 * We might have skipped entire leafs that contained only 5874 * file extent items for our current inode. These leafs have 5875 * a generation number smaller (older) than the one in the 5876 * current leaf and the leaf our last extent came from, and 5877 * are located between these 2 leafs. 5878 */ 5879 ret = get_last_extent(sctx, key->offset - 1); 5880 if (ret) 5881 return ret; 5882 } 5883 5884 if (sctx->cur_inode_last_extent < key->offset) { 5885 ret = range_is_hole_in_parent(sctx, 5886 sctx->cur_inode_last_extent, 5887 key->offset); 5888 if (ret < 0) 5889 return ret; 5890 else if (ret == 0) 5891 ret = send_hole(sctx, key->offset); 5892 else 5893 ret = 0; 5894 } 5895 sctx->cur_inode_last_extent = btrfs_file_extent_end(path); 5896 return ret; 5897 } 5898 5899 static int process_extent(struct send_ctx *sctx, 5900 struct btrfs_path *path, 5901 struct btrfs_key *key) 5902 { 5903 struct clone_root *found_clone = NULL; 5904 int ret = 0; 5905 5906 if (S_ISLNK(sctx->cur_inode_mode)) 5907 return 0; 5908 5909 if (sctx->parent_root && !sctx->cur_inode_new) { 5910 ret = is_extent_unchanged(sctx, path, key); 5911 if (ret < 0) 5912 goto out; 5913 if (ret) { 5914 ret = 0; 5915 goto out_hole; 5916 } 5917 } else { 5918 struct btrfs_file_extent_item *ei; 5919 u8 type; 5920 5921 ei = btrfs_item_ptr(path->nodes[0], path->slots[0], 5922 struct btrfs_file_extent_item); 5923 type = btrfs_file_extent_type(path->nodes[0], ei); 5924 if (type == BTRFS_FILE_EXTENT_PREALLOC || 5925 type == BTRFS_FILE_EXTENT_REG) { 5926 /* 5927 * The send spec does not have a prealloc command yet, 5928 * so just leave a hole for prealloc'ed extents until 5929 * we have enough commands queued up to justify rev'ing 5930 * the send spec. 5931 */ 5932 if (type == BTRFS_FILE_EXTENT_PREALLOC) { 5933 ret = 0; 5934 goto out; 5935 } 5936 5937 /* Have a hole, just skip it. */ 5938 if (btrfs_file_extent_disk_bytenr(path->nodes[0], ei) == 0) { 5939 ret = 0; 5940 goto out; 5941 } 5942 } 5943 } 5944 5945 ret = find_extent_clone(sctx, path, key->objectid, key->offset, 5946 sctx->cur_inode_size, &found_clone); 5947 if (ret != -ENOENT && ret < 0) 5948 goto out; 5949 5950 ret = send_write_or_clone(sctx, path, key, found_clone); 5951 if (ret) 5952 goto out; 5953 out_hole: 5954 ret = maybe_send_hole(sctx, path, key); 5955 out: 5956 return ret; 5957 } 5958 5959 static int process_all_extents(struct send_ctx *sctx) 5960 { 5961 int ret = 0; 5962 int iter_ret = 0; 5963 struct btrfs_root *root; 5964 struct btrfs_path *path; 5965 struct btrfs_key key; 5966 struct btrfs_key found_key; 5967 5968 root = sctx->send_root; 5969 path = alloc_path_for_send(); 5970 if (!path) 5971 return -ENOMEM; 5972 5973 key.objectid = sctx->cmp_key->objectid; 5974 key.type = BTRFS_EXTENT_DATA_KEY; 5975 key.offset = 0; 5976 btrfs_for_each_slot(root, &key, &found_key, path, iter_ret) { 5977 if (found_key.objectid != key.objectid || 5978 found_key.type != key.type) { 5979 ret = 0; 5980 break; 5981 } 5982 5983 ret = process_extent(sctx, path, &found_key); 5984 if (ret < 0) 5985 break; 5986 } 5987 /* Catch error found during iteration */ 5988 if (iter_ret < 0) 5989 ret = iter_ret; 5990 5991 btrfs_free_path(path); 5992 return ret; 5993 } 5994 5995 static int process_recorded_refs_if_needed(struct send_ctx *sctx, int at_end, 5996 int *pending_move, 5997 int *refs_processed) 5998 { 5999 int ret = 0; 6000 6001 if (sctx->cur_ino == 0) 6002 goto out; 6003 if (!at_end && sctx->cur_ino == sctx->cmp_key->objectid && 6004 sctx->cmp_key->type <= BTRFS_INODE_EXTREF_KEY) 6005 goto out; 6006 if (list_empty(&sctx->new_refs) && list_empty(&sctx->deleted_refs)) 6007 goto out; 6008 6009 ret = process_recorded_refs(sctx, pending_move); 6010 if (ret < 0) 6011 goto out; 6012 6013 *refs_processed = 1; 6014 out: 6015 return ret; 6016 } 6017 6018 static int finish_inode_if_needed(struct send_ctx *sctx, int at_end) 6019 { 6020 int ret = 0; 6021 u64 left_mode; 6022 u64 left_uid; 6023 u64 left_gid; 6024 u64 right_mode; 6025 u64 right_uid; 6026 u64 right_gid; 6027 int need_chmod = 0; 6028 int need_chown = 0; 6029 int need_truncate = 1; 6030 int pending_move = 0; 6031 int refs_processed = 0; 6032 6033 if (sctx->ignore_cur_inode) 6034 return 0; 6035 6036 ret = process_recorded_refs_if_needed(sctx, at_end, &pending_move, 6037 &refs_processed); 6038 if (ret < 0) 6039 goto out; 6040 6041 /* 6042 * We have processed the refs and thus need to advance send_progress. 6043 * Now, calls to get_cur_xxx will take the updated refs of the current 6044 * inode into account. 6045 * 6046 * On the other hand, if our current inode is a directory and couldn't 6047 * be moved/renamed because its parent was renamed/moved too and it has 6048 * a higher inode number, we can only move/rename our current inode 6049 * after we moved/renamed its parent. Therefore in this case operate on 6050 * the old path (pre move/rename) of our current inode, and the 6051 * move/rename will be performed later. 6052 */ 6053 if (refs_processed && !pending_move) 6054 sctx->send_progress = sctx->cur_ino + 1; 6055 6056 if (sctx->cur_ino == 0 || sctx->cur_inode_deleted) 6057 goto out; 6058 if (!at_end && sctx->cmp_key->objectid == sctx->cur_ino) 6059 goto out; 6060 6061 ret = get_inode_info(sctx->send_root, sctx->cur_ino, NULL, NULL, 6062 &left_mode, &left_uid, &left_gid, NULL); 6063 if (ret < 0) 6064 goto out; 6065 6066 if (!sctx->parent_root || sctx->cur_inode_new) { 6067 need_chown = 1; 6068 if (!S_ISLNK(sctx->cur_inode_mode)) 6069 need_chmod = 1; 6070 if (sctx->cur_inode_next_write_offset == sctx->cur_inode_size) 6071 need_truncate = 0; 6072 } else { 6073 u64 old_size; 6074 6075 ret = get_inode_info(sctx->parent_root, sctx->cur_ino, 6076 &old_size, NULL, &right_mode, &right_uid, 6077 &right_gid, NULL); 6078 if (ret < 0) 6079 goto out; 6080 6081 if (left_uid != right_uid || left_gid != right_gid) 6082 need_chown = 1; 6083 if (!S_ISLNK(sctx->cur_inode_mode) && left_mode != right_mode) 6084 need_chmod = 1; 6085 if ((old_size == sctx->cur_inode_size) || 6086 (sctx->cur_inode_size > old_size && 6087 sctx->cur_inode_next_write_offset == sctx->cur_inode_size)) 6088 need_truncate = 0; 6089 } 6090 6091 if (S_ISREG(sctx->cur_inode_mode)) { 6092 if (need_send_hole(sctx)) { 6093 if (sctx->cur_inode_last_extent == (u64)-1 || 6094 sctx->cur_inode_last_extent < 6095 sctx->cur_inode_size) { 6096 ret = get_last_extent(sctx, (u64)-1); 6097 if (ret) 6098 goto out; 6099 } 6100 if (sctx->cur_inode_last_extent < 6101 sctx->cur_inode_size) { 6102 ret = send_hole(sctx, sctx->cur_inode_size); 6103 if (ret) 6104 goto out; 6105 } 6106 } 6107 if (need_truncate) { 6108 ret = send_truncate(sctx, sctx->cur_ino, 6109 sctx->cur_inode_gen, 6110 sctx->cur_inode_size); 6111 if (ret < 0) 6112 goto out; 6113 } 6114 } 6115 6116 if (need_chown) { 6117 ret = send_chown(sctx, sctx->cur_ino, sctx->cur_inode_gen, 6118 left_uid, left_gid); 6119 if (ret < 0) 6120 goto out; 6121 } 6122 if (need_chmod) { 6123 ret = send_chmod(sctx, sctx->cur_ino, sctx->cur_inode_gen, 6124 left_mode); 6125 if (ret < 0) 6126 goto out; 6127 } 6128 6129 ret = send_capabilities(sctx); 6130 if (ret < 0) 6131 goto out; 6132 6133 /* 6134 * If other directory inodes depended on our current directory 6135 * inode's move/rename, now do their move/rename operations. 6136 */ 6137 if (!is_waiting_for_move(sctx, sctx->cur_ino)) { 6138 ret = apply_children_dir_moves(sctx); 6139 if (ret) 6140 goto out; 6141 /* 6142 * Need to send that every time, no matter if it actually 6143 * changed between the two trees as we have done changes to 6144 * the inode before. If our inode is a directory and it's 6145 * waiting to be moved/renamed, we will send its utimes when 6146 * it's moved/renamed, therefore we don't need to do it here. 6147 */ 6148 sctx->send_progress = sctx->cur_ino + 1; 6149 ret = send_utimes(sctx, sctx->cur_ino, sctx->cur_inode_gen); 6150 if (ret < 0) 6151 goto out; 6152 } 6153 6154 out: 6155 return ret; 6156 } 6157 6158 struct parent_paths_ctx { 6159 struct list_head *refs; 6160 struct send_ctx *sctx; 6161 }; 6162 6163 static int record_parent_ref(int num, u64 dir, int index, struct fs_path *name, 6164 void *ctx) 6165 { 6166 struct parent_paths_ctx *ppctx = ctx; 6167 6168 return record_ref(ppctx->sctx->parent_root, dir, name, ppctx->sctx, 6169 ppctx->refs); 6170 } 6171 6172 /* 6173 * Issue unlink operations for all paths of the current inode found in the 6174 * parent snapshot. 6175 */ 6176 static int btrfs_unlink_all_paths(struct send_ctx *sctx) 6177 { 6178 LIST_HEAD(deleted_refs); 6179 struct btrfs_path *path; 6180 struct btrfs_root *root = sctx->parent_root; 6181 struct btrfs_key key; 6182 struct btrfs_key found_key; 6183 struct parent_paths_ctx ctx; 6184 int iter_ret = 0; 6185 int ret; 6186 6187 path = alloc_path_for_send(); 6188 if (!path) 6189 return -ENOMEM; 6190 6191 key.objectid = sctx->cur_ino; 6192 key.type = BTRFS_INODE_REF_KEY; 6193 key.offset = 0; 6194 6195 ctx.refs = &deleted_refs; 6196 ctx.sctx = sctx; 6197 6198 btrfs_for_each_slot(root, &key, &found_key, path, iter_ret) { 6199 if (found_key.objectid != key.objectid) 6200 break; 6201 if (found_key.type != key.type && 6202 found_key.type != BTRFS_INODE_EXTREF_KEY) 6203 break; 6204 6205 ret = iterate_inode_ref(root, path, &found_key, 1, 6206 record_parent_ref, &ctx); 6207 if (ret < 0) 6208 goto out; 6209 } 6210 /* Catch error found during iteration */ 6211 if (iter_ret < 0) { 6212 ret = iter_ret; 6213 goto out; 6214 } 6215 6216 while (!list_empty(&deleted_refs)) { 6217 struct recorded_ref *ref; 6218 6219 ref = list_first_entry(&deleted_refs, struct recorded_ref, list); 6220 ret = send_unlink(sctx, ref->full_path); 6221 if (ret < 0) 6222 goto out; 6223 fs_path_free(ref->full_path); 6224 list_del(&ref->list); 6225 kfree(ref); 6226 } 6227 ret = 0; 6228 out: 6229 btrfs_free_path(path); 6230 if (ret) 6231 __free_recorded_refs(&deleted_refs); 6232 return ret; 6233 } 6234 6235 static void close_current_inode(struct send_ctx *sctx) 6236 { 6237 u64 i_size; 6238 6239 if (sctx->cur_inode == NULL) 6240 return; 6241 6242 i_size = i_size_read(sctx->cur_inode); 6243 6244 /* 6245 * If we are doing an incremental send, we may have extents between the 6246 * last processed extent and the i_size that have not been processed 6247 * because they haven't changed but we may have read some of their pages 6248 * through readahead, see the comments at send_extent_data(). 6249 */ 6250 if (sctx->clean_page_cache && sctx->page_cache_clear_start < i_size) 6251 truncate_inode_pages_range(&sctx->cur_inode->i_data, 6252 sctx->page_cache_clear_start, 6253 round_up(i_size, PAGE_SIZE) - 1); 6254 6255 iput(sctx->cur_inode); 6256 sctx->cur_inode = NULL; 6257 } 6258 6259 static int changed_inode(struct send_ctx *sctx, 6260 enum btrfs_compare_tree_result result) 6261 { 6262 int ret = 0; 6263 struct btrfs_key *key = sctx->cmp_key; 6264 struct btrfs_inode_item *left_ii = NULL; 6265 struct btrfs_inode_item *right_ii = NULL; 6266 u64 left_gen = 0; 6267 u64 right_gen = 0; 6268 6269 close_current_inode(sctx); 6270 6271 sctx->cur_ino = key->objectid; 6272 sctx->cur_inode_new_gen = 0; 6273 sctx->cur_inode_last_extent = (u64)-1; 6274 sctx->cur_inode_next_write_offset = 0; 6275 sctx->ignore_cur_inode = false; 6276 6277 /* 6278 * Set send_progress to current inode. This will tell all get_cur_xxx 6279 * functions that the current inode's refs are not updated yet. Later, 6280 * when process_recorded_refs is finished, it is set to cur_ino + 1. 6281 */ 6282 sctx->send_progress = sctx->cur_ino; 6283 6284 if (result == BTRFS_COMPARE_TREE_NEW || 6285 result == BTRFS_COMPARE_TREE_CHANGED) { 6286 left_ii = btrfs_item_ptr(sctx->left_path->nodes[0], 6287 sctx->left_path->slots[0], 6288 struct btrfs_inode_item); 6289 left_gen = btrfs_inode_generation(sctx->left_path->nodes[0], 6290 left_ii); 6291 } else { 6292 right_ii = btrfs_item_ptr(sctx->right_path->nodes[0], 6293 sctx->right_path->slots[0], 6294 struct btrfs_inode_item); 6295 right_gen = btrfs_inode_generation(sctx->right_path->nodes[0], 6296 right_ii); 6297 } 6298 if (result == BTRFS_COMPARE_TREE_CHANGED) { 6299 right_ii = btrfs_item_ptr(sctx->right_path->nodes[0], 6300 sctx->right_path->slots[0], 6301 struct btrfs_inode_item); 6302 6303 right_gen = btrfs_inode_generation(sctx->right_path->nodes[0], 6304 right_ii); 6305 6306 /* 6307 * The cur_ino = root dir case is special here. We can't treat 6308 * the inode as deleted+reused because it would generate a 6309 * stream that tries to delete/mkdir the root dir. 6310 */ 6311 if (left_gen != right_gen && 6312 sctx->cur_ino != BTRFS_FIRST_FREE_OBJECTID) 6313 sctx->cur_inode_new_gen = 1; 6314 } 6315 6316 /* 6317 * Normally we do not find inodes with a link count of zero (orphans) 6318 * because the most common case is to create a snapshot and use it 6319 * for a send operation. However other less common use cases involve 6320 * using a subvolume and send it after turning it to RO mode just 6321 * after deleting all hard links of a file while holding an open 6322 * file descriptor against it or turning a RO snapshot into RW mode, 6323 * keep an open file descriptor against a file, delete it and then 6324 * turn the snapshot back to RO mode before using it for a send 6325 * operation. So if we find such cases, ignore the inode and all its 6326 * items completely if it's a new inode, or if it's a changed inode 6327 * make sure all its previous paths (from the parent snapshot) are all 6328 * unlinked and all other the inode items are ignored. 6329 */ 6330 if (result == BTRFS_COMPARE_TREE_NEW || 6331 result == BTRFS_COMPARE_TREE_CHANGED) { 6332 u32 nlinks; 6333 6334 nlinks = btrfs_inode_nlink(sctx->left_path->nodes[0], left_ii); 6335 if (nlinks == 0) { 6336 sctx->ignore_cur_inode = true; 6337 if (result == BTRFS_COMPARE_TREE_CHANGED) 6338 ret = btrfs_unlink_all_paths(sctx); 6339 goto out; 6340 } 6341 } 6342 6343 if (result == BTRFS_COMPARE_TREE_NEW) { 6344 sctx->cur_inode_gen = left_gen; 6345 sctx->cur_inode_new = 1; 6346 sctx->cur_inode_deleted = 0; 6347 sctx->cur_inode_size = btrfs_inode_size( 6348 sctx->left_path->nodes[0], left_ii); 6349 sctx->cur_inode_mode = btrfs_inode_mode( 6350 sctx->left_path->nodes[0], left_ii); 6351 sctx->cur_inode_rdev = btrfs_inode_rdev( 6352 sctx->left_path->nodes[0], left_ii); 6353 if (sctx->cur_ino != BTRFS_FIRST_FREE_OBJECTID) 6354 ret = send_create_inode_if_needed(sctx); 6355 } else if (result == BTRFS_COMPARE_TREE_DELETED) { 6356 sctx->cur_inode_gen = right_gen; 6357 sctx->cur_inode_new = 0; 6358 sctx->cur_inode_deleted = 1; 6359 sctx->cur_inode_size = btrfs_inode_size( 6360 sctx->right_path->nodes[0], right_ii); 6361 sctx->cur_inode_mode = btrfs_inode_mode( 6362 sctx->right_path->nodes[0], right_ii); 6363 } else if (result == BTRFS_COMPARE_TREE_CHANGED) { 6364 /* 6365 * We need to do some special handling in case the inode was 6366 * reported as changed with a changed generation number. This 6367 * means that the original inode was deleted and new inode 6368 * reused the same inum. So we have to treat the old inode as 6369 * deleted and the new one as new. 6370 */ 6371 if (sctx->cur_inode_new_gen) { 6372 /* 6373 * First, process the inode as if it was deleted. 6374 */ 6375 sctx->cur_inode_gen = right_gen; 6376 sctx->cur_inode_new = 0; 6377 sctx->cur_inode_deleted = 1; 6378 sctx->cur_inode_size = btrfs_inode_size( 6379 sctx->right_path->nodes[0], right_ii); 6380 sctx->cur_inode_mode = btrfs_inode_mode( 6381 sctx->right_path->nodes[0], right_ii); 6382 ret = process_all_refs(sctx, 6383 BTRFS_COMPARE_TREE_DELETED); 6384 if (ret < 0) 6385 goto out; 6386 6387 /* 6388 * Now process the inode as if it was new. 6389 */ 6390 sctx->cur_inode_gen = left_gen; 6391 sctx->cur_inode_new = 1; 6392 sctx->cur_inode_deleted = 0; 6393 sctx->cur_inode_size = btrfs_inode_size( 6394 sctx->left_path->nodes[0], left_ii); 6395 sctx->cur_inode_mode = btrfs_inode_mode( 6396 sctx->left_path->nodes[0], left_ii); 6397 sctx->cur_inode_rdev = btrfs_inode_rdev( 6398 sctx->left_path->nodes[0], left_ii); 6399 ret = send_create_inode_if_needed(sctx); 6400 if (ret < 0) 6401 goto out; 6402 6403 ret = process_all_refs(sctx, BTRFS_COMPARE_TREE_NEW); 6404 if (ret < 0) 6405 goto out; 6406 /* 6407 * Advance send_progress now as we did not get into 6408 * process_recorded_refs_if_needed in the new_gen case. 6409 */ 6410 sctx->send_progress = sctx->cur_ino + 1; 6411 6412 /* 6413 * Now process all extents and xattrs of the inode as if 6414 * they were all new. 6415 */ 6416 ret = process_all_extents(sctx); 6417 if (ret < 0) 6418 goto out; 6419 ret = process_all_new_xattrs(sctx); 6420 if (ret < 0) 6421 goto out; 6422 } else { 6423 sctx->cur_inode_gen = left_gen; 6424 sctx->cur_inode_new = 0; 6425 sctx->cur_inode_new_gen = 0; 6426 sctx->cur_inode_deleted = 0; 6427 sctx->cur_inode_size = btrfs_inode_size( 6428 sctx->left_path->nodes[0], left_ii); 6429 sctx->cur_inode_mode = btrfs_inode_mode( 6430 sctx->left_path->nodes[0], left_ii); 6431 } 6432 } 6433 6434 out: 6435 return ret; 6436 } 6437 6438 /* 6439 * We have to process new refs before deleted refs, but compare_trees gives us 6440 * the new and deleted refs mixed. To fix this, we record the new/deleted refs 6441 * first and later process them in process_recorded_refs. 6442 * For the cur_inode_new_gen case, we skip recording completely because 6443 * changed_inode did already initiate processing of refs. The reason for this is 6444 * that in this case, compare_tree actually compares the refs of 2 different 6445 * inodes. To fix this, process_all_refs is used in changed_inode to handle all 6446 * refs of the right tree as deleted and all refs of the left tree as new. 6447 */ 6448 static int changed_ref(struct send_ctx *sctx, 6449 enum btrfs_compare_tree_result result) 6450 { 6451 int ret = 0; 6452 6453 if (sctx->cur_ino != sctx->cmp_key->objectid) { 6454 inconsistent_snapshot_error(sctx, result, "reference"); 6455 return -EIO; 6456 } 6457 6458 if (!sctx->cur_inode_new_gen && 6459 sctx->cur_ino != BTRFS_FIRST_FREE_OBJECTID) { 6460 if (result == BTRFS_COMPARE_TREE_NEW) 6461 ret = record_new_ref(sctx); 6462 else if (result == BTRFS_COMPARE_TREE_DELETED) 6463 ret = record_deleted_ref(sctx); 6464 else if (result == BTRFS_COMPARE_TREE_CHANGED) 6465 ret = record_changed_ref(sctx); 6466 } 6467 6468 return ret; 6469 } 6470 6471 /* 6472 * Process new/deleted/changed xattrs. We skip processing in the 6473 * cur_inode_new_gen case because changed_inode did already initiate processing 6474 * of xattrs. The reason is the same as in changed_ref 6475 */ 6476 static int changed_xattr(struct send_ctx *sctx, 6477 enum btrfs_compare_tree_result result) 6478 { 6479 int ret = 0; 6480 6481 if (sctx->cur_ino != sctx->cmp_key->objectid) { 6482 inconsistent_snapshot_error(sctx, result, "xattr"); 6483 return -EIO; 6484 } 6485 6486 if (!sctx->cur_inode_new_gen && !sctx->cur_inode_deleted) { 6487 if (result == BTRFS_COMPARE_TREE_NEW) 6488 ret = process_new_xattr(sctx); 6489 else if (result == BTRFS_COMPARE_TREE_DELETED) 6490 ret = process_deleted_xattr(sctx); 6491 else if (result == BTRFS_COMPARE_TREE_CHANGED) 6492 ret = process_changed_xattr(sctx); 6493 } 6494 6495 return ret; 6496 } 6497 6498 /* 6499 * Process new/deleted/changed extents. We skip processing in the 6500 * cur_inode_new_gen case because changed_inode did already initiate processing 6501 * of extents. The reason is the same as in changed_ref 6502 */ 6503 static int changed_extent(struct send_ctx *sctx, 6504 enum btrfs_compare_tree_result result) 6505 { 6506 int ret = 0; 6507 6508 /* 6509 * We have found an extent item that changed without the inode item 6510 * having changed. This can happen either after relocation (where the 6511 * disk_bytenr of an extent item is replaced at 6512 * relocation.c:replace_file_extents()) or after deduplication into a 6513 * file in both the parent and send snapshots (where an extent item can 6514 * get modified or replaced with a new one). Note that deduplication 6515 * updates the inode item, but it only changes the iversion (sequence 6516 * field in the inode item) of the inode, so if a file is deduplicated 6517 * the same amount of times in both the parent and send snapshots, its 6518 * iversion becomes the same in both snapshots, whence the inode item is 6519 * the same on both snapshots. 6520 */ 6521 if (sctx->cur_ino != sctx->cmp_key->objectid) 6522 return 0; 6523 6524 if (!sctx->cur_inode_new_gen && !sctx->cur_inode_deleted) { 6525 if (result != BTRFS_COMPARE_TREE_DELETED) 6526 ret = process_extent(sctx, sctx->left_path, 6527 sctx->cmp_key); 6528 } 6529 6530 return ret; 6531 } 6532 6533 static int dir_changed(struct send_ctx *sctx, u64 dir) 6534 { 6535 u64 orig_gen, new_gen; 6536 int ret; 6537 6538 ret = get_inode_info(sctx->send_root, dir, NULL, &new_gen, NULL, NULL, 6539 NULL, NULL); 6540 if (ret) 6541 return ret; 6542 6543 ret = get_inode_info(sctx->parent_root, dir, NULL, &orig_gen, NULL, 6544 NULL, NULL, NULL); 6545 if (ret) 6546 return ret; 6547 6548 return (orig_gen != new_gen) ? 1 : 0; 6549 } 6550 6551 static int compare_refs(struct send_ctx *sctx, struct btrfs_path *path, 6552 struct btrfs_key *key) 6553 { 6554 struct btrfs_inode_extref *extref; 6555 struct extent_buffer *leaf; 6556 u64 dirid = 0, last_dirid = 0; 6557 unsigned long ptr; 6558 u32 item_size; 6559 u32 cur_offset = 0; 6560 int ref_name_len; 6561 int ret = 0; 6562 6563 /* Easy case, just check this one dirid */ 6564 if (key->type == BTRFS_INODE_REF_KEY) { 6565 dirid = key->offset; 6566 6567 ret = dir_changed(sctx, dirid); 6568 goto out; 6569 } 6570 6571 leaf = path->nodes[0]; 6572 item_size = btrfs_item_size(leaf, path->slots[0]); 6573 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); 6574 while (cur_offset < item_size) { 6575 extref = (struct btrfs_inode_extref *)(ptr + 6576 cur_offset); 6577 dirid = btrfs_inode_extref_parent(leaf, extref); 6578 ref_name_len = btrfs_inode_extref_name_len(leaf, extref); 6579 cur_offset += ref_name_len + sizeof(*extref); 6580 if (dirid == last_dirid) 6581 continue; 6582 ret = dir_changed(sctx, dirid); 6583 if (ret) 6584 break; 6585 last_dirid = dirid; 6586 } 6587 out: 6588 return ret; 6589 } 6590 6591 /* 6592 * Updates compare related fields in sctx and simply forwards to the actual 6593 * changed_xxx functions. 6594 */ 6595 static int changed_cb(struct btrfs_path *left_path, 6596 struct btrfs_path *right_path, 6597 struct btrfs_key *key, 6598 enum btrfs_compare_tree_result result, 6599 struct send_ctx *sctx) 6600 { 6601 int ret = 0; 6602 6603 /* 6604 * We can not hold the commit root semaphore here. This is because in 6605 * the case of sending and receiving to the same filesystem, using a 6606 * pipe, could result in a deadlock: 6607 * 6608 * 1) The task running send blocks on the pipe because it's full; 6609 * 6610 * 2) The task running receive, which is the only consumer of the pipe, 6611 * is waiting for a transaction commit (for example due to a space 6612 * reservation when doing a write or triggering a transaction commit 6613 * when creating a subvolume); 6614 * 6615 * 3) The transaction is waiting to write lock the commit root semaphore, 6616 * but can not acquire it since it's being held at 1). 6617 * 6618 * Down this call chain we write to the pipe through kernel_write(). 6619 * The same type of problem can also happen when sending to a file that 6620 * is stored in the same filesystem - when reserving space for a write 6621 * into the file, we can trigger a transaction commit. 6622 * 6623 * Our caller has supplied us with clones of leaves from the send and 6624 * parent roots, so we're safe here from a concurrent relocation and 6625 * further reallocation of metadata extents while we are here. Below we 6626 * also assert that the leaves are clones. 6627 */ 6628 lockdep_assert_not_held(&sctx->send_root->fs_info->commit_root_sem); 6629 6630 /* 6631 * We always have a send root, so left_path is never NULL. We will not 6632 * have a leaf when we have reached the end of the send root but have 6633 * not yet reached the end of the parent root. 6634 */ 6635 if (left_path->nodes[0]) 6636 ASSERT(test_bit(EXTENT_BUFFER_UNMAPPED, 6637 &left_path->nodes[0]->bflags)); 6638 /* 6639 * When doing a full send we don't have a parent root, so right_path is 6640 * NULL. When doing an incremental send, we may have reached the end of 6641 * the parent root already, so we don't have a leaf at right_path. 6642 */ 6643 if (right_path && right_path->nodes[0]) 6644 ASSERT(test_bit(EXTENT_BUFFER_UNMAPPED, 6645 &right_path->nodes[0]->bflags)); 6646 6647 if (result == BTRFS_COMPARE_TREE_SAME) { 6648 if (key->type == BTRFS_INODE_REF_KEY || 6649 key->type == BTRFS_INODE_EXTREF_KEY) { 6650 ret = compare_refs(sctx, left_path, key); 6651 if (!ret) 6652 return 0; 6653 if (ret < 0) 6654 return ret; 6655 } else if (key->type == BTRFS_EXTENT_DATA_KEY) { 6656 return maybe_send_hole(sctx, left_path, key); 6657 } else { 6658 return 0; 6659 } 6660 result = BTRFS_COMPARE_TREE_CHANGED; 6661 ret = 0; 6662 } 6663 6664 sctx->left_path = left_path; 6665 sctx->right_path = right_path; 6666 sctx->cmp_key = key; 6667 6668 ret = finish_inode_if_needed(sctx, 0); 6669 if (ret < 0) 6670 goto out; 6671 6672 /* Ignore non-FS objects */ 6673 if (key->objectid == BTRFS_FREE_INO_OBJECTID || 6674 key->objectid == BTRFS_FREE_SPACE_OBJECTID) 6675 goto out; 6676 6677 if (key->type == BTRFS_INODE_ITEM_KEY) { 6678 ret = changed_inode(sctx, result); 6679 } else if (!sctx->ignore_cur_inode) { 6680 if (key->type == BTRFS_INODE_REF_KEY || 6681 key->type == BTRFS_INODE_EXTREF_KEY) 6682 ret = changed_ref(sctx, result); 6683 else if (key->type == BTRFS_XATTR_ITEM_KEY) 6684 ret = changed_xattr(sctx, result); 6685 else if (key->type == BTRFS_EXTENT_DATA_KEY) 6686 ret = changed_extent(sctx, result); 6687 } 6688 6689 out: 6690 return ret; 6691 } 6692 6693 static int search_key_again(const struct send_ctx *sctx, 6694 struct btrfs_root *root, 6695 struct btrfs_path *path, 6696 const struct btrfs_key *key) 6697 { 6698 int ret; 6699 6700 if (!path->need_commit_sem) 6701 lockdep_assert_held_read(&root->fs_info->commit_root_sem); 6702 6703 /* 6704 * Roots used for send operations are readonly and no one can add, 6705 * update or remove keys from them, so we should be able to find our 6706 * key again. The only exception is deduplication, which can operate on 6707 * readonly roots and add, update or remove keys to/from them - but at 6708 * the moment we don't allow it to run in parallel with send. 6709 */ 6710 ret = btrfs_search_slot(NULL, root, key, path, 0, 0); 6711 ASSERT(ret <= 0); 6712 if (ret > 0) { 6713 btrfs_print_tree(path->nodes[path->lowest_level], false); 6714 btrfs_err(root->fs_info, 6715 "send: key (%llu %u %llu) not found in %s root %llu, lowest_level %d, slot %d", 6716 key->objectid, key->type, key->offset, 6717 (root == sctx->parent_root ? "parent" : "send"), 6718 root->root_key.objectid, path->lowest_level, 6719 path->slots[path->lowest_level]); 6720 return -EUCLEAN; 6721 } 6722 6723 return ret; 6724 } 6725 6726 static int full_send_tree(struct send_ctx *sctx) 6727 { 6728 int ret; 6729 struct btrfs_root *send_root = sctx->send_root; 6730 struct btrfs_key key; 6731 struct btrfs_fs_info *fs_info = send_root->fs_info; 6732 struct btrfs_path *path; 6733 6734 path = alloc_path_for_send(); 6735 if (!path) 6736 return -ENOMEM; 6737 path->reada = READA_FORWARD_ALWAYS; 6738 6739 key.objectid = BTRFS_FIRST_FREE_OBJECTID; 6740 key.type = BTRFS_INODE_ITEM_KEY; 6741 key.offset = 0; 6742 6743 down_read(&fs_info->commit_root_sem); 6744 sctx->last_reloc_trans = fs_info->last_reloc_trans; 6745 up_read(&fs_info->commit_root_sem); 6746 6747 ret = btrfs_search_slot_for_read(send_root, &key, path, 1, 0); 6748 if (ret < 0) 6749 goto out; 6750 if (ret) 6751 goto out_finish; 6752 6753 while (1) { 6754 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); 6755 6756 ret = changed_cb(path, NULL, &key, 6757 BTRFS_COMPARE_TREE_NEW, sctx); 6758 if (ret < 0) 6759 goto out; 6760 6761 down_read(&fs_info->commit_root_sem); 6762 if (fs_info->last_reloc_trans > sctx->last_reloc_trans) { 6763 sctx->last_reloc_trans = fs_info->last_reloc_trans; 6764 up_read(&fs_info->commit_root_sem); 6765 /* 6766 * A transaction used for relocating a block group was 6767 * committed or is about to finish its commit. Release 6768 * our path (leaf) and restart the search, so that we 6769 * avoid operating on any file extent items that are 6770 * stale, with a disk_bytenr that reflects a pre 6771 * relocation value. This way we avoid as much as 6772 * possible to fallback to regular writes when checking 6773 * if we can clone file ranges. 6774 */ 6775 btrfs_release_path(path); 6776 ret = search_key_again(sctx, send_root, path, &key); 6777 if (ret < 0) 6778 goto out; 6779 } else { 6780 up_read(&fs_info->commit_root_sem); 6781 } 6782 6783 ret = btrfs_next_item(send_root, path); 6784 if (ret < 0) 6785 goto out; 6786 if (ret) { 6787 ret = 0; 6788 break; 6789 } 6790 } 6791 6792 out_finish: 6793 ret = finish_inode_if_needed(sctx, 1); 6794 6795 out: 6796 btrfs_free_path(path); 6797 return ret; 6798 } 6799 6800 static int replace_node_with_clone(struct btrfs_path *path, int level) 6801 { 6802 struct extent_buffer *clone; 6803 6804 clone = btrfs_clone_extent_buffer(path->nodes[level]); 6805 if (!clone) 6806 return -ENOMEM; 6807 6808 free_extent_buffer(path->nodes[level]); 6809 path->nodes[level] = clone; 6810 6811 return 0; 6812 } 6813 6814 static int tree_move_down(struct btrfs_path *path, int *level, u64 reada_min_gen) 6815 { 6816 struct extent_buffer *eb; 6817 struct extent_buffer *parent = path->nodes[*level]; 6818 int slot = path->slots[*level]; 6819 const int nritems = btrfs_header_nritems(parent); 6820 u64 reada_max; 6821 u64 reada_done = 0; 6822 6823 lockdep_assert_held_read(&parent->fs_info->commit_root_sem); 6824 6825 BUG_ON(*level == 0); 6826 eb = btrfs_read_node_slot(parent, slot); 6827 if (IS_ERR(eb)) 6828 return PTR_ERR(eb); 6829 6830 /* 6831 * Trigger readahead for the next leaves we will process, so that it is 6832 * very likely that when we need them they are already in memory and we 6833 * will not block on disk IO. For nodes we only do readahead for one, 6834 * since the time window between processing nodes is typically larger. 6835 */ 6836 reada_max = (*level == 1 ? SZ_128K : eb->fs_info->nodesize); 6837 6838 for (slot++; slot < nritems && reada_done < reada_max; slot++) { 6839 if (btrfs_node_ptr_generation(parent, slot) > reada_min_gen) { 6840 btrfs_readahead_node_child(parent, slot); 6841 reada_done += eb->fs_info->nodesize; 6842 } 6843 } 6844 6845 path->nodes[*level - 1] = eb; 6846 path->slots[*level - 1] = 0; 6847 (*level)--; 6848 6849 if (*level == 0) 6850 return replace_node_with_clone(path, 0); 6851 6852 return 0; 6853 } 6854 6855 static int tree_move_next_or_upnext(struct btrfs_path *path, 6856 int *level, int root_level) 6857 { 6858 int ret = 0; 6859 int nritems; 6860 nritems = btrfs_header_nritems(path->nodes[*level]); 6861 6862 path->slots[*level]++; 6863 6864 while (path->slots[*level] >= nritems) { 6865 if (*level == root_level) { 6866 path->slots[*level] = nritems - 1; 6867 return -1; 6868 } 6869 6870 /* move upnext */ 6871 path->slots[*level] = 0; 6872 free_extent_buffer(path->nodes[*level]); 6873 path->nodes[*level] = NULL; 6874 (*level)++; 6875 path->slots[*level]++; 6876 6877 nritems = btrfs_header_nritems(path->nodes[*level]); 6878 ret = 1; 6879 } 6880 return ret; 6881 } 6882 6883 /* 6884 * Returns 1 if it had to move up and next. 0 is returned if it moved only next 6885 * or down. 6886 */ 6887 static int tree_advance(struct btrfs_path *path, 6888 int *level, int root_level, 6889 int allow_down, 6890 struct btrfs_key *key, 6891 u64 reada_min_gen) 6892 { 6893 int ret; 6894 6895 if (*level == 0 || !allow_down) { 6896 ret = tree_move_next_or_upnext(path, level, root_level); 6897 } else { 6898 ret = tree_move_down(path, level, reada_min_gen); 6899 } 6900 6901 /* 6902 * Even if we have reached the end of a tree, ret is -1, update the key 6903 * anyway, so that in case we need to restart due to a block group 6904 * relocation, we can assert that the last key of the root node still 6905 * exists in the tree. 6906 */ 6907 if (*level == 0) 6908 btrfs_item_key_to_cpu(path->nodes[*level], key, 6909 path->slots[*level]); 6910 else 6911 btrfs_node_key_to_cpu(path->nodes[*level], key, 6912 path->slots[*level]); 6913 6914 return ret; 6915 } 6916 6917 static int tree_compare_item(struct btrfs_path *left_path, 6918 struct btrfs_path *right_path, 6919 char *tmp_buf) 6920 { 6921 int cmp; 6922 int len1, len2; 6923 unsigned long off1, off2; 6924 6925 len1 = btrfs_item_size(left_path->nodes[0], left_path->slots[0]); 6926 len2 = btrfs_item_size(right_path->nodes[0], right_path->slots[0]); 6927 if (len1 != len2) 6928 return 1; 6929 6930 off1 = btrfs_item_ptr_offset(left_path->nodes[0], left_path->slots[0]); 6931 off2 = btrfs_item_ptr_offset(right_path->nodes[0], 6932 right_path->slots[0]); 6933 6934 read_extent_buffer(left_path->nodes[0], tmp_buf, off1, len1); 6935 6936 cmp = memcmp_extent_buffer(right_path->nodes[0], tmp_buf, off2, len1); 6937 if (cmp) 6938 return 1; 6939 return 0; 6940 } 6941 6942 /* 6943 * A transaction used for relocating a block group was committed or is about to 6944 * finish its commit. Release our paths and restart the search, so that we are 6945 * not using stale extent buffers: 6946 * 6947 * 1) For levels > 0, we are only holding references of extent buffers, without 6948 * any locks on them, which does not prevent them from having been relocated 6949 * and reallocated after the last time we released the commit root semaphore. 6950 * The exception are the root nodes, for which we always have a clone, see 6951 * the comment at btrfs_compare_trees(); 6952 * 6953 * 2) For leaves, level 0, we are holding copies (clones) of extent buffers, so 6954 * we are safe from the concurrent relocation and reallocation. However they 6955 * can have file extent items with a pre relocation disk_bytenr value, so we 6956 * restart the start from the current commit roots and clone the new leaves so 6957 * that we get the post relocation disk_bytenr values. Not doing so, could 6958 * make us clone the wrong data in case there are new extents using the old 6959 * disk_bytenr that happen to be shared. 6960 */ 6961 static int restart_after_relocation(struct btrfs_path *left_path, 6962 struct btrfs_path *right_path, 6963 const struct btrfs_key *left_key, 6964 const struct btrfs_key *right_key, 6965 int left_level, 6966 int right_level, 6967 const struct send_ctx *sctx) 6968 { 6969 int root_level; 6970 int ret; 6971 6972 lockdep_assert_held_read(&sctx->send_root->fs_info->commit_root_sem); 6973 6974 btrfs_release_path(left_path); 6975 btrfs_release_path(right_path); 6976 6977 /* 6978 * Since keys can not be added or removed to/from our roots because they 6979 * are readonly and we do not allow deduplication to run in parallel 6980 * (which can add, remove or change keys), the layout of the trees should 6981 * not change. 6982 */ 6983 left_path->lowest_level = left_level; 6984 ret = search_key_again(sctx, sctx->send_root, left_path, left_key); 6985 if (ret < 0) 6986 return ret; 6987 6988 right_path->lowest_level = right_level; 6989 ret = search_key_again(sctx, sctx->parent_root, right_path, right_key); 6990 if (ret < 0) 6991 return ret; 6992 6993 /* 6994 * If the lowest level nodes are leaves, clone them so that they can be 6995 * safely used by changed_cb() while not under the protection of the 6996 * commit root semaphore, even if relocation and reallocation happens in 6997 * parallel. 6998 */ 6999 if (left_level == 0) { 7000 ret = replace_node_with_clone(left_path, 0); 7001 if (ret < 0) 7002 return ret; 7003 } 7004 7005 if (right_level == 0) { 7006 ret = replace_node_with_clone(right_path, 0); 7007 if (ret < 0) 7008 return ret; 7009 } 7010 7011 /* 7012 * Now clone the root nodes (unless they happen to be the leaves we have 7013 * already cloned). This is to protect against concurrent snapshotting of 7014 * the send and parent roots (see the comment at btrfs_compare_trees()). 7015 */ 7016 root_level = btrfs_header_level(sctx->send_root->commit_root); 7017 if (root_level > 0) { 7018 ret = replace_node_with_clone(left_path, root_level); 7019 if (ret < 0) 7020 return ret; 7021 } 7022 7023 root_level = btrfs_header_level(sctx->parent_root->commit_root); 7024 if (root_level > 0) { 7025 ret = replace_node_with_clone(right_path, root_level); 7026 if (ret < 0) 7027 return ret; 7028 } 7029 7030 return 0; 7031 } 7032 7033 /* 7034 * This function compares two trees and calls the provided callback for 7035 * every changed/new/deleted item it finds. 7036 * If shared tree blocks are encountered, whole subtrees are skipped, making 7037 * the compare pretty fast on snapshotted subvolumes. 7038 * 7039 * This currently works on commit roots only. As commit roots are read only, 7040 * we don't do any locking. The commit roots are protected with transactions. 7041 * Transactions are ended and rejoined when a commit is tried in between. 7042 * 7043 * This function checks for modifications done to the trees while comparing. 7044 * If it detects a change, it aborts immediately. 7045 */ 7046 static int btrfs_compare_trees(struct btrfs_root *left_root, 7047 struct btrfs_root *right_root, struct send_ctx *sctx) 7048 { 7049 struct btrfs_fs_info *fs_info = left_root->fs_info; 7050 int ret; 7051 int cmp; 7052 struct btrfs_path *left_path = NULL; 7053 struct btrfs_path *right_path = NULL; 7054 struct btrfs_key left_key; 7055 struct btrfs_key right_key; 7056 char *tmp_buf = NULL; 7057 int left_root_level; 7058 int right_root_level; 7059 int left_level; 7060 int right_level; 7061 int left_end_reached = 0; 7062 int right_end_reached = 0; 7063 int advance_left = 0; 7064 int advance_right = 0; 7065 u64 left_blockptr; 7066 u64 right_blockptr; 7067 u64 left_gen; 7068 u64 right_gen; 7069 u64 reada_min_gen; 7070 7071 left_path = btrfs_alloc_path(); 7072 if (!left_path) { 7073 ret = -ENOMEM; 7074 goto out; 7075 } 7076 right_path = btrfs_alloc_path(); 7077 if (!right_path) { 7078 ret = -ENOMEM; 7079 goto out; 7080 } 7081 7082 tmp_buf = kvmalloc(fs_info->nodesize, GFP_KERNEL); 7083 if (!tmp_buf) { 7084 ret = -ENOMEM; 7085 goto out; 7086 } 7087 7088 left_path->search_commit_root = 1; 7089 left_path->skip_locking = 1; 7090 right_path->search_commit_root = 1; 7091 right_path->skip_locking = 1; 7092 7093 /* 7094 * Strategy: Go to the first items of both trees. Then do 7095 * 7096 * If both trees are at level 0 7097 * Compare keys of current items 7098 * If left < right treat left item as new, advance left tree 7099 * and repeat 7100 * If left > right treat right item as deleted, advance right tree 7101 * and repeat 7102 * If left == right do deep compare of items, treat as changed if 7103 * needed, advance both trees and repeat 7104 * If both trees are at the same level but not at level 0 7105 * Compare keys of current nodes/leafs 7106 * If left < right advance left tree and repeat 7107 * If left > right advance right tree and repeat 7108 * If left == right compare blockptrs of the next nodes/leafs 7109 * If they match advance both trees but stay at the same level 7110 * and repeat 7111 * If they don't match advance both trees while allowing to go 7112 * deeper and repeat 7113 * If tree levels are different 7114 * Advance the tree that needs it and repeat 7115 * 7116 * Advancing a tree means: 7117 * If we are at level 0, try to go to the next slot. If that's not 7118 * possible, go one level up and repeat. Stop when we found a level 7119 * where we could go to the next slot. We may at this point be on a 7120 * node or a leaf. 7121 * 7122 * If we are not at level 0 and not on shared tree blocks, go one 7123 * level deeper. 7124 * 7125 * If we are not at level 0 and on shared tree blocks, go one slot to 7126 * the right if possible or go up and right. 7127 */ 7128 7129 down_read(&fs_info->commit_root_sem); 7130 left_level = btrfs_header_level(left_root->commit_root); 7131 left_root_level = left_level; 7132 /* 7133 * We clone the root node of the send and parent roots to prevent races 7134 * with snapshot creation of these roots. Snapshot creation COWs the 7135 * root node of a tree, so after the transaction is committed the old 7136 * extent can be reallocated while this send operation is still ongoing. 7137 * So we clone them, under the commit root semaphore, to be race free. 7138 */ 7139 left_path->nodes[left_level] = 7140 btrfs_clone_extent_buffer(left_root->commit_root); 7141 if (!left_path->nodes[left_level]) { 7142 ret = -ENOMEM; 7143 goto out_unlock; 7144 } 7145 7146 right_level = btrfs_header_level(right_root->commit_root); 7147 right_root_level = right_level; 7148 right_path->nodes[right_level] = 7149 btrfs_clone_extent_buffer(right_root->commit_root); 7150 if (!right_path->nodes[right_level]) { 7151 ret = -ENOMEM; 7152 goto out_unlock; 7153 } 7154 /* 7155 * Our right root is the parent root, while the left root is the "send" 7156 * root. We know that all new nodes/leaves in the left root must have 7157 * a generation greater than the right root's generation, so we trigger 7158 * readahead for those nodes and leaves of the left root, as we know we 7159 * will need to read them at some point. 7160 */ 7161 reada_min_gen = btrfs_header_generation(right_root->commit_root); 7162 7163 if (left_level == 0) 7164 btrfs_item_key_to_cpu(left_path->nodes[left_level], 7165 &left_key, left_path->slots[left_level]); 7166 else 7167 btrfs_node_key_to_cpu(left_path->nodes[left_level], 7168 &left_key, left_path->slots[left_level]); 7169 if (right_level == 0) 7170 btrfs_item_key_to_cpu(right_path->nodes[right_level], 7171 &right_key, right_path->slots[right_level]); 7172 else 7173 btrfs_node_key_to_cpu(right_path->nodes[right_level], 7174 &right_key, right_path->slots[right_level]); 7175 7176 sctx->last_reloc_trans = fs_info->last_reloc_trans; 7177 7178 while (1) { 7179 if (need_resched() || 7180 rwsem_is_contended(&fs_info->commit_root_sem)) { 7181 up_read(&fs_info->commit_root_sem); 7182 cond_resched(); 7183 down_read(&fs_info->commit_root_sem); 7184 } 7185 7186 if (fs_info->last_reloc_trans > sctx->last_reloc_trans) { 7187 ret = restart_after_relocation(left_path, right_path, 7188 &left_key, &right_key, 7189 left_level, right_level, 7190 sctx); 7191 if (ret < 0) 7192 goto out_unlock; 7193 sctx->last_reloc_trans = fs_info->last_reloc_trans; 7194 } 7195 7196 if (advance_left && !left_end_reached) { 7197 ret = tree_advance(left_path, &left_level, 7198 left_root_level, 7199 advance_left != ADVANCE_ONLY_NEXT, 7200 &left_key, reada_min_gen); 7201 if (ret == -1) 7202 left_end_reached = ADVANCE; 7203 else if (ret < 0) 7204 goto out_unlock; 7205 advance_left = 0; 7206 } 7207 if (advance_right && !right_end_reached) { 7208 ret = tree_advance(right_path, &right_level, 7209 right_root_level, 7210 advance_right != ADVANCE_ONLY_NEXT, 7211 &right_key, reada_min_gen); 7212 if (ret == -1) 7213 right_end_reached = ADVANCE; 7214 else if (ret < 0) 7215 goto out_unlock; 7216 advance_right = 0; 7217 } 7218 7219 if (left_end_reached && right_end_reached) { 7220 ret = 0; 7221 goto out_unlock; 7222 } else if (left_end_reached) { 7223 if (right_level == 0) { 7224 up_read(&fs_info->commit_root_sem); 7225 ret = changed_cb(left_path, right_path, 7226 &right_key, 7227 BTRFS_COMPARE_TREE_DELETED, 7228 sctx); 7229 if (ret < 0) 7230 goto out; 7231 down_read(&fs_info->commit_root_sem); 7232 } 7233 advance_right = ADVANCE; 7234 continue; 7235 } else if (right_end_reached) { 7236 if (left_level == 0) { 7237 up_read(&fs_info->commit_root_sem); 7238 ret = changed_cb(left_path, right_path, 7239 &left_key, 7240 BTRFS_COMPARE_TREE_NEW, 7241 sctx); 7242 if (ret < 0) 7243 goto out; 7244 down_read(&fs_info->commit_root_sem); 7245 } 7246 advance_left = ADVANCE; 7247 continue; 7248 } 7249 7250 if (left_level == 0 && right_level == 0) { 7251 up_read(&fs_info->commit_root_sem); 7252 cmp = btrfs_comp_cpu_keys(&left_key, &right_key); 7253 if (cmp < 0) { 7254 ret = changed_cb(left_path, right_path, 7255 &left_key, 7256 BTRFS_COMPARE_TREE_NEW, 7257 sctx); 7258 advance_left = ADVANCE; 7259 } else if (cmp > 0) { 7260 ret = changed_cb(left_path, right_path, 7261 &right_key, 7262 BTRFS_COMPARE_TREE_DELETED, 7263 sctx); 7264 advance_right = ADVANCE; 7265 } else { 7266 enum btrfs_compare_tree_result result; 7267 7268 WARN_ON(!extent_buffer_uptodate(left_path->nodes[0])); 7269 ret = tree_compare_item(left_path, right_path, 7270 tmp_buf); 7271 if (ret) 7272 result = BTRFS_COMPARE_TREE_CHANGED; 7273 else 7274 result = BTRFS_COMPARE_TREE_SAME; 7275 ret = changed_cb(left_path, right_path, 7276 &left_key, result, sctx); 7277 advance_left = ADVANCE; 7278 advance_right = ADVANCE; 7279 } 7280 7281 if (ret < 0) 7282 goto out; 7283 down_read(&fs_info->commit_root_sem); 7284 } else if (left_level == right_level) { 7285 cmp = btrfs_comp_cpu_keys(&left_key, &right_key); 7286 if (cmp < 0) { 7287 advance_left = ADVANCE; 7288 } else if (cmp > 0) { 7289 advance_right = ADVANCE; 7290 } else { 7291 left_blockptr = btrfs_node_blockptr( 7292 left_path->nodes[left_level], 7293 left_path->slots[left_level]); 7294 right_blockptr = btrfs_node_blockptr( 7295 right_path->nodes[right_level], 7296 right_path->slots[right_level]); 7297 left_gen = btrfs_node_ptr_generation( 7298 left_path->nodes[left_level], 7299 left_path->slots[left_level]); 7300 right_gen = btrfs_node_ptr_generation( 7301 right_path->nodes[right_level], 7302 right_path->slots[right_level]); 7303 if (left_blockptr == right_blockptr && 7304 left_gen == right_gen) { 7305 /* 7306 * As we're on a shared block, don't 7307 * allow to go deeper. 7308 */ 7309 advance_left = ADVANCE_ONLY_NEXT; 7310 advance_right = ADVANCE_ONLY_NEXT; 7311 } else { 7312 advance_left = ADVANCE; 7313 advance_right = ADVANCE; 7314 } 7315 } 7316 } else if (left_level < right_level) { 7317 advance_right = ADVANCE; 7318 } else { 7319 advance_left = ADVANCE; 7320 } 7321 } 7322 7323 out_unlock: 7324 up_read(&fs_info->commit_root_sem); 7325 out: 7326 btrfs_free_path(left_path); 7327 btrfs_free_path(right_path); 7328 kvfree(tmp_buf); 7329 return ret; 7330 } 7331 7332 static int send_subvol(struct send_ctx *sctx) 7333 { 7334 int ret; 7335 7336 if (!(sctx->flags & BTRFS_SEND_FLAG_OMIT_STREAM_HEADER)) { 7337 ret = send_header(sctx); 7338 if (ret < 0) 7339 goto out; 7340 } 7341 7342 ret = send_subvol_begin(sctx); 7343 if (ret < 0) 7344 goto out; 7345 7346 if (sctx->parent_root) { 7347 ret = btrfs_compare_trees(sctx->send_root, sctx->parent_root, sctx); 7348 if (ret < 0) 7349 goto out; 7350 ret = finish_inode_if_needed(sctx, 1); 7351 if (ret < 0) 7352 goto out; 7353 } else { 7354 ret = full_send_tree(sctx); 7355 if (ret < 0) 7356 goto out; 7357 } 7358 7359 out: 7360 free_recorded_refs(sctx); 7361 return ret; 7362 } 7363 7364 /* 7365 * If orphan cleanup did remove any orphans from a root, it means the tree 7366 * was modified and therefore the commit root is not the same as the current 7367 * root anymore. This is a problem, because send uses the commit root and 7368 * therefore can see inode items that don't exist in the current root anymore, 7369 * and for example make calls to btrfs_iget, which will do tree lookups based 7370 * on the current root and not on the commit root. Those lookups will fail, 7371 * returning a -ESTALE error, and making send fail with that error. So make 7372 * sure a send does not see any orphans we have just removed, and that it will 7373 * see the same inodes regardless of whether a transaction commit happened 7374 * before it started (meaning that the commit root will be the same as the 7375 * current root) or not. 7376 */ 7377 static int ensure_commit_roots_uptodate(struct send_ctx *sctx) 7378 { 7379 int i; 7380 struct btrfs_trans_handle *trans = NULL; 7381 7382 again: 7383 if (sctx->parent_root && 7384 sctx->parent_root->node != sctx->parent_root->commit_root) 7385 goto commit_trans; 7386 7387 for (i = 0; i < sctx->clone_roots_cnt; i++) 7388 if (sctx->clone_roots[i].root->node != 7389 sctx->clone_roots[i].root->commit_root) 7390 goto commit_trans; 7391 7392 if (trans) 7393 return btrfs_end_transaction(trans); 7394 7395 return 0; 7396 7397 commit_trans: 7398 /* Use any root, all fs roots will get their commit roots updated. */ 7399 if (!trans) { 7400 trans = btrfs_join_transaction(sctx->send_root); 7401 if (IS_ERR(trans)) 7402 return PTR_ERR(trans); 7403 goto again; 7404 } 7405 7406 return btrfs_commit_transaction(trans); 7407 } 7408 7409 /* 7410 * Make sure any existing dellaloc is flushed for any root used by a send 7411 * operation so that we do not miss any data and we do not race with writeback 7412 * finishing and changing a tree while send is using the tree. This could 7413 * happen if a subvolume is in RW mode, has delalloc, is turned to RO mode and 7414 * a send operation then uses the subvolume. 7415 * After flushing delalloc ensure_commit_roots_uptodate() must be called. 7416 */ 7417 static int flush_delalloc_roots(struct send_ctx *sctx) 7418 { 7419 struct btrfs_root *root = sctx->parent_root; 7420 int ret; 7421 int i; 7422 7423 if (root) { 7424 ret = btrfs_start_delalloc_snapshot(root, false); 7425 if (ret) 7426 return ret; 7427 btrfs_wait_ordered_extents(root, U64_MAX, 0, U64_MAX); 7428 } 7429 7430 for (i = 0; i < sctx->clone_roots_cnt; i++) { 7431 root = sctx->clone_roots[i].root; 7432 ret = btrfs_start_delalloc_snapshot(root, false); 7433 if (ret) 7434 return ret; 7435 btrfs_wait_ordered_extents(root, U64_MAX, 0, U64_MAX); 7436 } 7437 7438 return 0; 7439 } 7440 7441 static void btrfs_root_dec_send_in_progress(struct btrfs_root* root) 7442 { 7443 spin_lock(&root->root_item_lock); 7444 root->send_in_progress--; 7445 /* 7446 * Not much left to do, we don't know why it's unbalanced and 7447 * can't blindly reset it to 0. 7448 */ 7449 if (root->send_in_progress < 0) 7450 btrfs_err(root->fs_info, 7451 "send_in_progress unbalanced %d root %llu", 7452 root->send_in_progress, root->root_key.objectid); 7453 spin_unlock(&root->root_item_lock); 7454 } 7455 7456 static void dedupe_in_progress_warn(const struct btrfs_root *root) 7457 { 7458 btrfs_warn_rl(root->fs_info, 7459 "cannot use root %llu for send while deduplications on it are in progress (%d in progress)", 7460 root->root_key.objectid, root->dedupe_in_progress); 7461 } 7462 7463 long btrfs_ioctl_send(struct inode *inode, struct btrfs_ioctl_send_args *arg) 7464 { 7465 int ret = 0; 7466 struct btrfs_root *send_root = BTRFS_I(inode)->root; 7467 struct btrfs_fs_info *fs_info = send_root->fs_info; 7468 struct btrfs_root *clone_root; 7469 struct send_ctx *sctx = NULL; 7470 u32 i; 7471 u64 *clone_sources_tmp = NULL; 7472 int clone_sources_to_rollback = 0; 7473 size_t alloc_size; 7474 int sort_clone_roots = 0; 7475 7476 if (!capable(CAP_SYS_ADMIN)) 7477 return -EPERM; 7478 7479 /* 7480 * The subvolume must remain read-only during send, protect against 7481 * making it RW. This also protects against deletion. 7482 */ 7483 spin_lock(&send_root->root_item_lock); 7484 if (btrfs_root_readonly(send_root) && send_root->dedupe_in_progress) { 7485 dedupe_in_progress_warn(send_root); 7486 spin_unlock(&send_root->root_item_lock); 7487 return -EAGAIN; 7488 } 7489 send_root->send_in_progress++; 7490 spin_unlock(&send_root->root_item_lock); 7491 7492 /* 7493 * Userspace tools do the checks and warn the user if it's 7494 * not RO. 7495 */ 7496 if (!btrfs_root_readonly(send_root)) { 7497 ret = -EPERM; 7498 goto out; 7499 } 7500 7501 /* 7502 * Check that we don't overflow at later allocations, we request 7503 * clone_sources_count + 1 items, and compare to unsigned long inside 7504 * access_ok. 7505 */ 7506 if (arg->clone_sources_count > 7507 ULONG_MAX / sizeof(struct clone_root) - 1) { 7508 ret = -EINVAL; 7509 goto out; 7510 } 7511 7512 if (arg->flags & ~BTRFS_SEND_FLAG_MASK) { 7513 ret = -EINVAL; 7514 goto out; 7515 } 7516 7517 sctx = kzalloc(sizeof(struct send_ctx), GFP_KERNEL); 7518 if (!sctx) { 7519 ret = -ENOMEM; 7520 goto out; 7521 } 7522 7523 INIT_LIST_HEAD(&sctx->new_refs); 7524 INIT_LIST_HEAD(&sctx->deleted_refs); 7525 INIT_RADIX_TREE(&sctx->name_cache, GFP_KERNEL); 7526 INIT_LIST_HEAD(&sctx->name_cache_list); 7527 7528 sctx->flags = arg->flags; 7529 7530 if (arg->flags & BTRFS_SEND_FLAG_VERSION) { 7531 if (arg->version > BTRFS_SEND_STREAM_VERSION) { 7532 ret = -EPROTO; 7533 goto out; 7534 } 7535 /* Zero means "use the highest version" */ 7536 sctx->proto = arg->version ?: BTRFS_SEND_STREAM_VERSION; 7537 } else { 7538 sctx->proto = 1; 7539 } 7540 7541 sctx->send_filp = fget(arg->send_fd); 7542 if (!sctx->send_filp) { 7543 ret = -EBADF; 7544 goto out; 7545 } 7546 7547 sctx->send_root = send_root; 7548 /* 7549 * Unlikely but possible, if the subvolume is marked for deletion but 7550 * is slow to remove the directory entry, send can still be started 7551 */ 7552 if (btrfs_root_dead(sctx->send_root)) { 7553 ret = -EPERM; 7554 goto out; 7555 } 7556 7557 sctx->clone_roots_cnt = arg->clone_sources_count; 7558 7559 sctx->send_max_size = BTRFS_SEND_BUF_SIZE; 7560 sctx->send_buf = kvmalloc(sctx->send_max_size, GFP_KERNEL); 7561 if (!sctx->send_buf) { 7562 ret = -ENOMEM; 7563 goto out; 7564 } 7565 7566 sctx->pending_dir_moves = RB_ROOT; 7567 sctx->waiting_dir_moves = RB_ROOT; 7568 sctx->orphan_dirs = RB_ROOT; 7569 7570 sctx->clone_roots = kvcalloc(sizeof(*sctx->clone_roots), 7571 arg->clone_sources_count + 1, 7572 GFP_KERNEL); 7573 if (!sctx->clone_roots) { 7574 ret = -ENOMEM; 7575 goto out; 7576 } 7577 7578 alloc_size = array_size(sizeof(*arg->clone_sources), 7579 arg->clone_sources_count); 7580 7581 if (arg->clone_sources_count) { 7582 clone_sources_tmp = kvmalloc(alloc_size, GFP_KERNEL); 7583 if (!clone_sources_tmp) { 7584 ret = -ENOMEM; 7585 goto out; 7586 } 7587 7588 ret = copy_from_user(clone_sources_tmp, arg->clone_sources, 7589 alloc_size); 7590 if (ret) { 7591 ret = -EFAULT; 7592 goto out; 7593 } 7594 7595 for (i = 0; i < arg->clone_sources_count; i++) { 7596 clone_root = btrfs_get_fs_root(fs_info, 7597 clone_sources_tmp[i], true); 7598 if (IS_ERR(clone_root)) { 7599 ret = PTR_ERR(clone_root); 7600 goto out; 7601 } 7602 spin_lock(&clone_root->root_item_lock); 7603 if (!btrfs_root_readonly(clone_root) || 7604 btrfs_root_dead(clone_root)) { 7605 spin_unlock(&clone_root->root_item_lock); 7606 btrfs_put_root(clone_root); 7607 ret = -EPERM; 7608 goto out; 7609 } 7610 if (clone_root->dedupe_in_progress) { 7611 dedupe_in_progress_warn(clone_root); 7612 spin_unlock(&clone_root->root_item_lock); 7613 btrfs_put_root(clone_root); 7614 ret = -EAGAIN; 7615 goto out; 7616 } 7617 clone_root->send_in_progress++; 7618 spin_unlock(&clone_root->root_item_lock); 7619 7620 sctx->clone_roots[i].root = clone_root; 7621 clone_sources_to_rollback = i + 1; 7622 } 7623 kvfree(clone_sources_tmp); 7624 clone_sources_tmp = NULL; 7625 } 7626 7627 if (arg->parent_root) { 7628 sctx->parent_root = btrfs_get_fs_root(fs_info, arg->parent_root, 7629 true); 7630 if (IS_ERR(sctx->parent_root)) { 7631 ret = PTR_ERR(sctx->parent_root); 7632 goto out; 7633 } 7634 7635 spin_lock(&sctx->parent_root->root_item_lock); 7636 sctx->parent_root->send_in_progress++; 7637 if (!btrfs_root_readonly(sctx->parent_root) || 7638 btrfs_root_dead(sctx->parent_root)) { 7639 spin_unlock(&sctx->parent_root->root_item_lock); 7640 ret = -EPERM; 7641 goto out; 7642 } 7643 if (sctx->parent_root->dedupe_in_progress) { 7644 dedupe_in_progress_warn(sctx->parent_root); 7645 spin_unlock(&sctx->parent_root->root_item_lock); 7646 ret = -EAGAIN; 7647 goto out; 7648 } 7649 spin_unlock(&sctx->parent_root->root_item_lock); 7650 } 7651 7652 /* 7653 * Clones from send_root are allowed, but only if the clone source 7654 * is behind the current send position. This is checked while searching 7655 * for possible clone sources. 7656 */ 7657 sctx->clone_roots[sctx->clone_roots_cnt++].root = 7658 btrfs_grab_root(sctx->send_root); 7659 7660 /* We do a bsearch later */ 7661 sort(sctx->clone_roots, sctx->clone_roots_cnt, 7662 sizeof(*sctx->clone_roots), __clone_root_cmp_sort, 7663 NULL); 7664 sort_clone_roots = 1; 7665 7666 ret = flush_delalloc_roots(sctx); 7667 if (ret) 7668 goto out; 7669 7670 ret = ensure_commit_roots_uptodate(sctx); 7671 if (ret) 7672 goto out; 7673 7674 ret = send_subvol(sctx); 7675 if (ret < 0) 7676 goto out; 7677 7678 if (!(sctx->flags & BTRFS_SEND_FLAG_OMIT_END_CMD)) { 7679 ret = begin_cmd(sctx, BTRFS_SEND_C_END); 7680 if (ret < 0) 7681 goto out; 7682 ret = send_cmd(sctx); 7683 if (ret < 0) 7684 goto out; 7685 } 7686 7687 out: 7688 WARN_ON(sctx && !ret && !RB_EMPTY_ROOT(&sctx->pending_dir_moves)); 7689 while (sctx && !RB_EMPTY_ROOT(&sctx->pending_dir_moves)) { 7690 struct rb_node *n; 7691 struct pending_dir_move *pm; 7692 7693 n = rb_first(&sctx->pending_dir_moves); 7694 pm = rb_entry(n, struct pending_dir_move, node); 7695 while (!list_empty(&pm->list)) { 7696 struct pending_dir_move *pm2; 7697 7698 pm2 = list_first_entry(&pm->list, 7699 struct pending_dir_move, list); 7700 free_pending_move(sctx, pm2); 7701 } 7702 free_pending_move(sctx, pm); 7703 } 7704 7705 WARN_ON(sctx && !ret && !RB_EMPTY_ROOT(&sctx->waiting_dir_moves)); 7706 while (sctx && !RB_EMPTY_ROOT(&sctx->waiting_dir_moves)) { 7707 struct rb_node *n; 7708 struct waiting_dir_move *dm; 7709 7710 n = rb_first(&sctx->waiting_dir_moves); 7711 dm = rb_entry(n, struct waiting_dir_move, node); 7712 rb_erase(&dm->node, &sctx->waiting_dir_moves); 7713 kfree(dm); 7714 } 7715 7716 WARN_ON(sctx && !ret && !RB_EMPTY_ROOT(&sctx->orphan_dirs)); 7717 while (sctx && !RB_EMPTY_ROOT(&sctx->orphan_dirs)) { 7718 struct rb_node *n; 7719 struct orphan_dir_info *odi; 7720 7721 n = rb_first(&sctx->orphan_dirs); 7722 odi = rb_entry(n, struct orphan_dir_info, node); 7723 free_orphan_dir_info(sctx, odi); 7724 } 7725 7726 if (sort_clone_roots) { 7727 for (i = 0; i < sctx->clone_roots_cnt; i++) { 7728 btrfs_root_dec_send_in_progress( 7729 sctx->clone_roots[i].root); 7730 btrfs_put_root(sctx->clone_roots[i].root); 7731 } 7732 } else { 7733 for (i = 0; sctx && i < clone_sources_to_rollback; i++) { 7734 btrfs_root_dec_send_in_progress( 7735 sctx->clone_roots[i].root); 7736 btrfs_put_root(sctx->clone_roots[i].root); 7737 } 7738 7739 btrfs_root_dec_send_in_progress(send_root); 7740 } 7741 if (sctx && !IS_ERR_OR_NULL(sctx->parent_root)) { 7742 btrfs_root_dec_send_in_progress(sctx->parent_root); 7743 btrfs_put_root(sctx->parent_root); 7744 } 7745 7746 kvfree(clone_sources_tmp); 7747 7748 if (sctx) { 7749 if (sctx->send_filp) 7750 fput(sctx->send_filp); 7751 7752 kvfree(sctx->clone_roots); 7753 kvfree(sctx->send_buf); 7754 7755 name_cache_free(sctx); 7756 7757 close_current_inode(sctx); 7758 7759 kfree(sctx); 7760 } 7761 7762 return ret; 7763 } 7764