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