fs/btrfs/send.c

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