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