fs/btrfs/send.c

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