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